Как получить столкновение неупорядоченной карты?

Question

У меня есть два элемента (6 и 747), которые разделяют их ключ («яйца»). Я хочу найти все элементы, которые разделяют ключ (скажем, «яйца», но я бы в реальной жизни сделал это для каждого ключа). Как это сделать?

Должен быть способ получить контейнер или что-то обратно из структуры данных. , ,

Answer 1

Вы по-прежнему считаете ключ значение с ключом hash. Но ответить на вопрос, как спросил: вы можете использовать функцию bucket() член unordered_map «s с ковшом итераторов:

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

demo

В простых и в основном правильные точки, маркированные контейнеры подражают их упорядоченные аналоги с точки зрения интерфейса. Это означает, что если map не позволит вам иметь дубликаты ключей, то ни один из них не будет unordered_map.

unordered do использовать функцию хэширования, чтобы ускорить поиск, но если два ключа имеют одинаковый хеш, они не обязательно будут иметь одинаковое значение. Чтобы поведение было похоже на упорядоченные контейнеры, 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.

Answer 2

Неупорядоченная карта не имеет элементов, разделяющих ключ.

Unordered мульти карта.

Используйте umm.equal_range(key), чтобы получить итераторы pair, описывающие элементы на карте, соответствующие данному ключу.

Однако обратите внимание, что «столкновение» при разговоре о хешированных контейнерах обычно относится к элементам с одним и тем же хэшированным ключом, а не к одному и тому же ключу.

Кроме того, рассмотрите возможность использования unordered_map<key, std::vector<value>> вместо мультимапа.