Какие плюсы и минусы у std::unordered_map?

std::unordered_map — это хеш-таблица из стандартной библиотеки C++.

Плюсы:

• Средняя константная сложность O(1): Операции вставки (insert, emplace), удаления (erase) и поиска (find, operator[]) выполняются в среднем за постоянное время.
• Не требует упорядоченности ключей: В отличие от std::map, ключи не обязаны поддерживать оператор <. Требуется только хеш-функция и оператор ==.
• Эффективность для частых вставок/поисков: При хорошей хеш-функции и низком коэффициенте нагрузки (load factor) производительность очень высока.

Минусы:

• Худший случай O(n): При большом количестве коллизий (плохая хеш-функция или атака) сложность деградирует до линейной.
• Нет порядка обхода: Элементы хранятся в порядке, зависящем от хеш-функции и процесса вставки. Невозможно получить отсортированную последовательность ключей напрямую.
• Больший расход памяти: Для уменьшения коллизий хеш-таблица поддерживает количество бакетов (buckets), обычно большее, чем число элементов.
• Инвалидация итераторов: Операции рехеширования (при увеличении размера) инвалидируют все итераторы, хотя ссылки на элементы остаются валидными.

Пример использования:

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> wordCount;

    // Вставка - средняя O(1)
    wordCount["hello"] = 1;
    wordCount.insert({"world", 2});

    // Поиск - средняя O(1)
    auto it = wordCount.find("hello");
    if (it != wordCount.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << 'n';
    }

    // Обход в произвольном порядке
    for (const auto& [key, value] : wordCount) {
        std::cout << key << ": " << value << 'n';
    }

    // Управление производительностью
    wordCount.reserve(100); // Резервируем бакеты для 100 элементов
    wordCount.max_load_factor(0.7); // Устанавливаем максимальный коэффициент нагрузки
    return 0;
}