retrieve random key element for std::map in c++

Question

how to get random key for std::map in c++ ? using iterator? I don't want extra data structure to be maintained

Solution 1

std::map iterators are Bidirectional, which means selecting a random key will be O(n). Without using another data structure, basically your only choice is to use std::advance with a random increment from begin(). For example:

std::map<K, V> m;
auto it = m.begin();
std::advance(it, rand() % m.size());
K random_key = it->first;

(Or swapping out rand() with (for example) std::mt19939 if you have access to <random>).

Solution 2

It depends what's random for your purpose. std::map is a sorted container, but doesn't support random access by element number. Given that and knowledge of the set of keys, you can randomly select a point at which to dig into the map using lower_bound or upper_bound to find an element near there. This has a tendency to keep picking elements based on the gap between them and other elements in the map, which means while the initial result may be considered effectively random if the elements/gaps are themselves effectively random, repeated selection of random elements will not be evenly distributed.

For example, say your keys were upper case letters, and the keys 'C', 'O', 'Q' and 'S' were in the map. If you generate a random letter from A-Z, you'd be much more likely to end up on C, O or S than Q, as only PQR are near Q and using upper or lower bound you'd end up selecting two of those, so 2/26 chance despite there being only 4 elements. Still, if there was some randomness to the selection of C, O, Q and S to begin with, you could argue that that the gaps and choice are random.

You could improve on that a little by stabbing into the container like this, then doing a small random number of iterator increments/decrements, but it still wouldn't be truly random.

A truly random result requires advancing a one-by-one traversal through the list, or the secondary indexing container you want to avoid.