Random element in STL set/map in log n

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 equivalen开发者_开发问答t 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

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.

Yes, begin and rbegin (not end!) are the minimum and maximum key value, respectively.

If your key is simple, e.g. an integer, you could just create a random integer in the range [min, max) (using ) and get the map's lower_bound for that.

As you suspect begin() and either end() - 1 or rbegin() will get you the min and max values. I can't see any way to uniformly get a random element in such a tree though. However you have a couple options:

• You can do it in linear time using advance.
• You can keep a separate vector of map iterators that you keep up to date on all insertions/deletions.
• You could revisit the container choice. For example, would a sorted vector, heap, or some other representation be better?

If you have an even distribution of values in the set or map, you could choose a random value between the min and max and use lower_bound to find the closest value to it.

If insertions and deletions are infrequent, you can use a vector instead and sort it as necessary. Populating a vector and sorting it takes approximately the same amount of time as populating a set or map; it might even be faster, you'd need to test it to be sure. Selecting a random element would be trivial at that point.

I think you can actually do that with STL, but it's a bit more complicated.

You need to maintain a map. Each with a key from 1..N (N is the number of elements).

So each time you need to take a random element, generate a random number from 1..N, then find the element in the map with the chosen key. This is the element that you pick.

Afterwards, you need to maintain the consistency of the map by finding the biggest element, and update its key with the random number that you just picked.

Since each step is a log(n) operation, the total time is log(n).

with existing STL, there's probably no way. But There's a way to get random key in O(1) with addition std::map and std::vector structure by using reverse indexing.

1. Maintaining a map m & a vector v.
2. when inserting a new key k, let i = v.length(), then insert into m, and push k into v so that v[i] = k;
3. when deleting key k, let i = m[k], lookup the last element k2 in v, set m[k2]=i & v[i] = k2, pop_back v, and remove k from m;
4. to get a random key, let r = rand()%v.length(), then random key k = v[r];

so the basic idea is to have a continuous array of all existing keys.