Random element from elements with equivalent keys of std::unordered_multimap

Question

How do I pick a random element from a group of elements with equivalent keys of a std::unordered_multimap?

What would be the idiomatic way to do this? I know I can get the range of elements for a given key with mmap.equal_range(key). Is there a way to use this range as bounds for a uniform distribution?

Answer 1

std::unordered_multimap::count : Returns the number of elements with key key.

std::unordered_multimap::equal_range : Returns a range containing all elements with key key in the container. The range is defined by two iterators, the first pointing to the first element of the wanted range and the second pointing past the last element of the range.

So, easily enough (I guess):

auto n = random(0, my_map.count(key) - 1);
auto val = std::next(my_map.equal_range(key).first, n)->second;

What I'm doing here is simply advancing the iterator using std::next. random is a shorthand for whatever more sophisticated uniform int distribution you might want to use.

Answer 2

You can use the bucket member function to obtain the bucket in which a certain key is stored, and then inspect only that one bucket with local iterators:

T const & get_random(std::unordered_map<K, T> const & m)
{
    auto const b = m.bucket(k);
    // return random element from [m.begin(b), m.end(b))
}