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))
}

Answer 3

Take a look at the following piece of code:

#include <iostream>
#include <unordered_map>
#include <string>
#include <random>

static std::mt19937_64 rng;

int main()
{
    std::unordered_multimap<std::string, std::string> fruits = {
        { "apple", "red" },
        { "apple", "green" },
        { "apple", "blue"},
        { "apple", "white"},
        { "apple" , "black"},
        { "orange", "orange" },
        { "strawberry", "red" }
    };
    std::random_device rd; // obtain a random number from hardware
    std::mt19937 eng(rd()); // seed the generator
    for (auto i(0); i < fruits.bucket_count(); ++i) {
        auto d = std::distance(fruits.begin(i), fruits.end(i));
        if (d > 0) {
          std::uniform_int_distribution<> distr(0, d - 1); // define the range
          auto r = distr(eng);
          std::cout << "random index = " << r << std::endl;
          auto elem = fruits.begin(i);
          std::advance(elem, r);
          std::cout << elem->first << " : " << elem->second << std::endl;
        }
    }

    return 0;
}

Update

A more portable and generic version:

#include <iostream>
#include <unordered_map>
#include <string>
#include <random>

static std::mt19937_64 rng;

// Returns random iterator from an input range.
template<typename LIST_ITERATOR>
LIST_ITERATOR
getRandomIteratorFromRange(LIST_ITERATOR const &begin, 
                           LIST_ITERATOR const &end, 
                           std::mt19937 &random_engine)
{
  auto d = std::distance(begin, end);
  if(d > 0) {
    LIST_ITERATOR out(begin);
    std::advance(out, std::uniform_int_distribution<>(0, d - 1).operator()(random_engine));
    return out;
  }
  return end;
}

int main()
{
  std::unordered_multimap<std::string, std::string> fruits = {
  {"apple", "red"}, { "apple", "green" }, { "apple", "blue" }, { "apple", "white" },
  {"apple", "black"}, {"apple", "pink"},{"orange","orange"},{"strawberry", "red"}};

  std::random_device rd; // obtain a random number from hardware
  std::mt19937 eng(rd()); // seed the generator
  for(auto i(0); i < fruits.bucket_count(); ++i) {
    auto it = getRandomIteratorFromRange(fruits.begin(i), fruits.end(i), eng);
    if(it != fruits.end(i)) std::cout << it->first << " : " << it->second << std::endl;
  }

  return 0;
}