#опытным
std::unoredered_map обязана работать на базе хэш-таблицы, чтобы удовлетворить требованиям по асимптотической сложности ее операций.
А хэш-таблицы обязаны использовать какой-либо механизм разрешения коллизий, которые случаются, когда хэш для двух ключей получается одинаковым. Они могут быть разные: линейное пробирование, двойное хэширование, round robin hashing и тд. Стандарт обычно описывает только требования к контейнерам, не погружаясь в детали реализации. Но в случае std::unordered_map он четко зафиксировал использование метода бакетов, когда каждая ячейка таблицы хранит связный список элементов, у которых одинаковый ключ.
При обычном итерировани по неупорядоченной мапе мы используем всем знакомый range-based for и обычные итераторы(под капотом этого форика):
std::unoredered_map<std::string, int> map = ...;
for (const auto& [key, value]: map) {
...
}
Но это не единственный способ итерироваться по мапе!
У нее есть пара перегрузок методов begin() и end(), который принимают индекс бакета. И они позволяют итерироваться четко внутри него:
local_iterator begin( size_type n );
local_iterator end( size_type n );
Количество бакетов мы получаем через метод bucket_size и готово, мы получили альтернативную итерацию по контейнеру!
std::unordered_map<std::string, int> word_count = {
{"AI", 5}, {"evil", 7}, {"banana", 3},
{"date", 2}, {"elderberry", 4}
};
// Iterate over backets
for (size_t i = 0; i < word_count.bucket_count(); ++i) {
std::cout << "Bucket " << i << " ("
<< word_count.bucket_size(i) << " elements): ";
// Iterate inside certain backet
for (auto it = word_count.begin(i); it != word_count.end(i); ++it) {
std::cout << "[" << it->first << ":" << it->second << "] ";
}
std::cout << std::endl;
}Вывод:
Bucket 0 (0 elements):
Bucket 1 (0 elements):
Bucket 2 (2 elements): [date:2] [evil:7]
Bucket 3 (0 elements):
Bucket 4 (0 elements):
Bucket 5 (2 elements): [elderberry:4] [banana:3]
Bucket 6 (0 elements):
Bucket 7 (0 elements):
Bucket 8 (0 elements):
Bucket 9 (0 elements):
Bucket 10 (0 elements):
Bucket 11 (1 elements): [AI:5]
Bucket 12 (0 elements):
Пользы в этом немного, но может помочь, например, в отладке своей кастомном хэш-функции, чтобы добиться равномерного распределения.
Inspect your solutions. Stay cool.
#cpp11
