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

3
votes

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?

3
c++randomstlmultimapbucket
equal_range will only return elements that match the key. There could be other elements in the same bucket as key, so do you want a random element that matches key, or a random element from a random bucket? - user657267
I am looking for a way to retrieve a random element from within the bucket. The key of the bucket from which I want to draw is known. - fuji
It still sounds like you are confused about what a bucket is, just because the hash values of two keys are equal does not mean that the keys themselves are equal. Buckets can hold different keys. - user657267
Thanks for pointing this out - I changed the title of the question accordingly. - fuji

3 Answers

2
votes

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.

1
votes

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

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