Как получить коллизии неупорядоченной карты?
У меня есть два элемента (6 и 747), которые разделяют их ключ («яйца»). Я хочу найти все элементы, которые имеют общий ключ (скажем, «яйца», но я бы в реальной жизни делал это для каждого ключа). Как это сделать?
Должен быть способ получить контейнер или что-то обратно из структуры данных. , ,
Решение
Вы все еще ошибаетесь значение с ключами гашиш. Но чтобы ответить на вопрос, как спросили: вы можете использовать unordered_map«s bucket() функция-член с ведущими итераторами:
std::unordered_map<int,int,dumbest_hash> m;
m[0] = 42;
m[1] = 43;
size_t bucket = m.bucket(1);
for(auto it = m.begin(bucket), e = m.end(bucket); it != e; ++it) {
cout << "bucket " << bucket << ": " << it->first << " -> " << it->second << '\n';
}
В простых и в основном правильных терминах неупорядоченные контейнеры имитируют свои упорядоченные аналоги в терминах интерфейса. Это означает, что если map не позволит вам иметь дубликаты ключей, то ни один не будет unordered_map,
unordered Используйте функцию хеширования для ускорения поиска, но если два ключа имеют одинаковый хеш, они не обязательно будут иметь одинаковое значение. Чтобы сохранить поведение, подобное заказанным контейнерам, unordered_set а также unordered_map будет считать элементы равными, только когда они на самом деле равны (используя operator== или предоставленный компаратор), а не когда их хэшированные значения сталкиваются.
Чтобы положить вещи в перспективе, давайте предположим, что "eggs" а также "chicken" иметь одинаковое значение хеша и что нет проверки на равенство. Тогда следующий код будет «правильным»:
unordered_map<string, int> m;
m["eggs"] = 42;
m.insert(make_pair("chicken", 0)); // not inserted, key already exists
assert(m["chicken"] == 42);
Но если вы хотите разрешить дублирование ключей на одной карте, просто используйте unordered_multimap,
Другие решения
Неупорядоченная карта не имеет элементов, имеющих общий ключ.
Неупорядоченная мультикарта делает.
использование umm.equal_range(key) чтобы получить pair итераторов, описывающих элементы на карте, которые соответствуют заданному ключу.
Однако обратите внимание, что «коллизия», когда речь идет о хэшированных контейнерах, обычно относится к элементам с одинаковым хешированным ключом, а не с одним и тем же ключом.
Кроме того, рассмотрите возможность использования unordered_map<key, std::vector<value>> вместо мультикарты.