associative / random access container

Question

I'm looking for a data structure to hold an unordered collection of unique elements, which would support the following operations

1. insertions/deletions of elements anywhere in the collection
2. querying if an element is present
3. access to a random element

Naively, 1 and 2 suggest using an associative container, e.g. unordered_set, but then 3 is linear in number of elements. Using a random access container, e.g. vector, makes 3 easy, 1 can be done in O(1), but then 2 is again O(N).

The question is if there's a known way around this linear complexity?

EDIT: By a random element in 3 I mean: given an arbitrary ordering of N elements, retrieve an element number j where j is between 0 and N-1. For an std::vector it's just subscripting, for an std::list or an std::set it's incrementing the list/set iterator j times starting from begin() etc.

Answer 1

The two standard containers which are the best for your task, are - like you said, vector with 1. and 2. in O(n) and 3. in O(1) and set with 1. and 2. in O(log n) and 3. in O(n). Depending on the size of your data structure, the algorithmic complexity is not that important. A vector has the additional advantage of data locality so the CPU Cache can be exploited better.

If the actual order of the elements doesn't matter, insertion in the vector can be done in amortized O(1) (push_back) and deletion can be done in amortized O(1) if you swap the element you want to delete with the last element and delete that.

If you really have a big data structure, you could use Boost.Multi-Index to build a data structure where 1. is O(n), 2. is O(log n) and 3. is O(1). But, like I said, if your data structure is not really big a vector should just work.

If the order in the random access index does not matter, insertion can be done in amortized O(log n) (push_back). For deletion you can't use the swap trick because this would invalidate the other indices.

Answer 2

I have been looking for such a data structure for a long time.

Recently, I found quite promising library which has all the functionality that you are looking for.

See the cntree::set with random access in O(log n).

here is the link. http://dl.dropbox.com/u/8437476/works/countertree/index.html

Although it seems to be under development, I see it is quite usable.