Как пользоваться std::unordered_map в C++? Нужна хеш-таблица для подсчёта частот
Решаю задачу на Codeforces: дан массив, надо посчитать, сколько раз встречается каждое число. В Python я бы взял словарь, а в C++ слышал про хеш-таблицу unordered_map, но не понимаю синтаксис.
Как её объявить, как добавить элемент, как проверить наличие ключа и как пройтись по всем парам? И чем она отличается от map?
2 ответа
std::unordered_map — это и есть хеш-таблица, прямой аналог словаря из Python. Лежит в заголовке <unordered_map>.
Полный пример для твоей задачи (подсчёт частот):
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int arr[] = {5, 3, 5, 2, 3, 5};
unordered_map<int, int> cnt;
for (int x : arr) {
cnt[x]++; // если ключа нет — создаётся со значением 0, потом +1
}
// проверка наличия ключа
if (cnt.count(5)) {
cout << "5 встречается " << cnt[5] << " раз\n";
}
// проход по всем парам ключ-значение
for (auto& [key, value] : cnt) {
cout << key << " -> " << value << "\n";
}
return 0;
}
Ключевые операции:
m[key]— доступ/создание элементаm.count(key)— вернёт 1 если ключ есть, 0 если нетm.find(key)— итератор (илиm.end()если не нашлось)m.erase(key)— удалитьm.size()— количество элементов
Отличие от map: unordered_map — хеш-таблица, доступ в среднем за O(1), но порядок ключей произвольный. map — это дерево, доступ за O(log n), зато ключи всегда отсортированы. Для подсчёта частот, где порядок не важен, unordered_map быстрее.
Осторожно на Codeforces: у unordered_map бывают anti-hash тесты, когда злонамеренный набор ключей превращает O(1) в O(n) из-за коллизий, и решение получает TL.
Лайфхак — задать свой хеш или просто использовать map если n небольшое. Или зарезервировать память заранее:
unordered_map<int,int> cnt;
cnt.reserve(1024);
cnt.max_load_factor(0.25);
