Random element in STL set/map in log n

Question

Since C++ STL set/map are implemented as red-black trees, it should be possible to not only do insert, delete, and find in O(log n) time, but also getMin, getMax, getRandom. As I understand the former two have their equivalent in begin() and end() (is that correct?). How about the last one? How can I do that?

The only idea I had so far was to use advance with a random argument, which however takes linear time...

EDIT: 'random' should refer to a uniform distribution

Answer 1

begin() is equivalent to a getMin operation, but end() returns an iterator one past the maximum, so it'd be rbegin().

As for getRandom: assuming you mean getting any item randomly with uniform probability, that might be possible in O(lg n) time in an AVL tree, but I don't see how to do it efficiently in a red-black tree. How will you know how many subtrees there are left and right of a given node without counting them in n/2 = O(n) time? And since std::set and std::map don't give direct access to their underlying tree, how are you going to traverse it?

I see three possible solutions:

• use an AVL tree instead;
• maintain a vector with the elements in the map or set parallel to it;
• use a Boost::MultiIndex container with a sorted and a random-access view.

Edit: Boost.Intrusive might also do the trick.