How to select a random element in std::set in less than O(n) time?

Question

This question with an added constraint.

I'm willing to allow not-uniform selection as long as it's not to lop sided.

Given that "sets are typically implemented as binary search trees" and I expect they will contain some kind of depth or size information for balancing, I would expect you could do some sort of weighted random walk of the tree. However I don't know of any remotely portable way to do that.

Edit: The constraint is NOT for the amortized time.

Answer 1

Introduce array with size equal to set. Make array elements hold addresses of every element in set. Generate random integer R bounded by array/set size, pick address in array's element indexed by R and dereference it to obtain set's element.

Answer 2

I don't see how to do it with just std::set, so you probably need a different data structure. Like Victor Sorokin said, you can combine a set with a vector. Instead of set<T>, use map<T, size_t>, plus vector< map<T, size_t>::iterator >. The value for each key is an index into the vector, and each element of the vector points back to the map element. The vector elements have no particular order. When you add an element, put it at the end of the vector. When you remove an element and it's not the last one in the vector, move the last element to the deleted element's position.