Select random element in an unordered_map

Joe Cool picture Joe Cool · Nov 19, 2014 · Viewed 9.9k times · Source

I define an unordered_map like this:

std::unordered_map<std::string, Edge> edges;

Is there a efficient way to choose a random Edge from the unordered_map edges ?

Answer

Chnossos picture Chnossos · Nov 19, 2014

Pre-C++11 solution:

std::tr1::unordered_map<std::string, Edge> edges;
std::tr1::unordered_map<std::string, Edge>::iterator random_it = edges.begin();
std::advance(random_it, rand_between(0, edges.size()));

C++11 onward solution:

std::unordered_map<std::string, Edge> edges;
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size()));

The function that selects a valid random number is up to your choice, but be sure it returns a number in range [0 ; edges.size() - 1] when edges is not empty.

The std::next function simply wraps the std::advance function in a way that permits direct assignation.