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

c++, dictionary, std

Solution

`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>`).

Problem

Original source