Isn't inserting O(1) or at worst O(log n) if you have a pointer to the element you want to insert it after (or before)?
Finding element n is O(n), of course.
/ Mirar
Previous text:
2003-01-30 14:23: Subject: Re: hybrid of array & list
The new multiset implementation seems suitable for that when used without an ordering function. In that mode it takes O(log n) to insert and remove elements at each end but longer in the middle. With an ordering function it still takes O(log n) (assuming that function is O(1)) but with a higher constant. Stepping is O(1) on the average.
All the C level stuff already exists and appears to be stable, so what's needed is to make it available from Pike. If you aren't up to that, it could be an idea to use the C level functions in a specialized object; it'll still save you a lot of the gory details, such as handling resizing and gc interaction.
/ Martin Stjernholm, Roxen IS