Выберите случайный элемент в unordered_map

Ответ 1

Решение до С++ 11:

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()));

С++ 11 и более поздние решения:

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

Функция, которая выбирает действительное случайное число, зависит от вашего выбора, но убедитесь, что она возвращает число в диапазоне [0 ; edges.size() - 1], когда edges не пусто.

Функция std::next просто оборачивает функцию std::advance таким образом, который разрешает прямое назначение.

Ответ 2

Существует ли эффективный способ выбора случайного края из краев неупорядоченного_мапа?

Если по эффективности вы имеете в виду O (1), то нет, это невозможно.

Так как итераторы, возвращаемые unordered_map::begin / end, являются ForwardIterator s, подходы, которые просто используют std::advance, - это O (n) в количестве элементов.

Если ваше конкретное использование позволяет это, вы можете торговать некоторой случайностью для эффективности:

Вы можете выбрать случайное ведро (к которому можно получить доступ в O (1)), а затем случайный элемент внутри этого ведра.

int bucket, bucket_size;
do
{ 
    bucket = rnd(edges.bucket_count());
}
while ( (bucket_size = edges.bucket_size(bucket)) == 0 );

auto element = std::next(edges.begin(bucket), rnd(bucket_size));

Где rnd(n) возвращает случайное число в диапазоне [0, n).

На практике, если у вас есть приличный хеш, большинство ведер будет содержать ровно один элемент, иначе эта функция будет немного привилегировать элементы, которые одни в своих ковшиках.

Ответ 3

Вот как вы можете получить случайный элемент с карты:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
int random_index = rand() % edges.size();
std::advance(item, random_index);

Или посмотрите этот ответ, который предоставляет следующее решение:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
std::advance( item, random_0_to_n(edges.size()) );

Ответ 4

Строгое решение O (1) без ведер:

• Сохраняйте вектор ключей, когда вам нужно получить случайный элемент с вашей карты, выберите случайный ключ из вектора и верните соответствующее значение из карты - требуется постоянное время
• Если вы вставляете пару ключ-значение в свою карту, проверьте, присутствует ли такой ключ, и если это не так, добавьте этот ключ в свой вектор-ключ - требуется постоянное время
• Если вы хотите удалить элемент с карты после его выбора, поменяйте ключ, выбранный вами с помощью элемента back() вашего вектора ключа, и вызовите pop_back(), после чего удалите элемент с карты и верните value - принимает постоянное время

Однако существует ограничение: если вы хотите удалить элементы с карты, кроме случайного выбора, вам нужно исправить свой ключевой вектор, это займет O (n) с наивным подходом. Но все же есть способ получить O (1) производительность: сохранить карту, которая сообщает вам, где ключ находится в ключевом векторе, и обновлять его с помощью swap:)

Ответ 5

Решение

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

очень медленно....

Гораздо более быстрое решение будет:

• при назначении ребер одновременно использует свои ключи для std::vector<std::string> vec
• случайное значение int index в диапазоне от 0 до vec.size() - 1
• затем получите edges[vec[index]]