Случайный элемент из элементов с эквивалентными ключами std :: unordered_multimap
Как выбрать случайный элемент из группы элементов с эквивалентными ключами std::unordered_multimap?
Каков был бы идиоматический способ сделать это? Я знаю, что могу получить диапазон элементов для данного ключа с mmap.equal_range(key), Есть ли способ использовать этот диапазон в качестве границ для равномерного распределения?
Решение
std::unordered_multimap::count: Возвращает количество элементов с ключом ключ.
std::unordered_multimap::equal_range: Возвращает диапазон, содержащий все элементы с ключом ключ в контейнере. Диапазон определяется двумя итераторами: первый указывает на первый элемент искомого диапазона, а второй — за последним элементом диапазона.
Итак, достаточно легко (наверное):
auto n = random(0, my_map.count(key) - 1);
auto val = std::next(my_map.equal_range(key).first, n)->second;
То, что я делаю здесь, это просто продвижение итератора с помощью std::next, random это сокращение от любого более сложного единого дистрибутива int, который вы можете использовать.
Другие решения
Вы можете использовать bucket Функция-член для получения сегмента, в котором хранится определенный ключ, а затем проверяется только этот сегмент с локальными итераторами:
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))
}
Взгляните на следующий фрагмент кода:
#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;
}
Обновить
Более портативная и универсальная версия:
#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;
}