1

There is no standard container which gives such guarantees out from the box, some additional manipulation are required (for instance, like Jerry Coffin suggested), it is NOT duplicate.

Are there any ready data structure/container with at least O(ln N) on random access and O(ln N) on delete? (stl/boost/etc)

Ordering of elements within container is not important.

Such operations may happen in series, like:

  1. random access by index ( index is random too, rand()%size() )

  2. delete this item

  3. random access by index ( index is random too, rand()%size() )

  4. delete this item

etc...

qble
  • 1,256
  • 2
  • 12
  • 29

1 Answers1

4

Since you say ordering doesn't matter, you can do both in constant time using a vector.

Random access is (obviously) constant time.

Deletion in constant time can be done by swapping the element to delete with the last element, then deleting the last element.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • deletion may be O(N), and insertion can be O(N) – 0x90 Feb 10 '13 at 06:24
  • 3
    @0x90: no, because you swap to the end before deleting. Deletion from the end is O(1). – nneonneo Feb 10 '13 at 06:24
  • Thanks, good idea, accepted! ( I am curious why my Q was downvoted? ) – qble Feb 10 '13 at 06:50
  • 1
    @qble: I suspect the downvotes were on the assumption that you hadn't done any research first. But (like votes to close as a duplicate) they seem to be ignoring the fact that what you're asking for isn't entirely a characteristic of the container. – Jerry Coffin Feb 10 '13 at 06:52
  • @Jerry Coffin, yes, most likely. "isn't entirely a characteristic of the container" - I guess your idea can be wrapped to some kind of container form. – qble Feb 10 '13 at 06:56