std::unordered_map vs QMap/QHash: производительность и когда что выбрать

Введение

В Qt-проектах разработчик часто стоит перед выбором: использовать стандартный std::unordered_map из STL или Qt-контейнеры QMap/QHash. На первый взгляд они решают одну и ту же задачу — отображение «ключ → значение», но у них разная внутренняя организация, разные гарантии и разная производительность в типичных сценариях.

Концепция

QMap — упорядоченное ассоциативное хранилище, реализованное как сбалансированное дерево (в Qt 6 — на основе дерева, аналог std::map). Сложность операций — O(log n), порядок обхода — по возрастанию ключей.
QHash — хеш-таблица, аналог std::unordered_map. Средняя сложность вставки/поиска — O(1), порядок неопределён.
std::unordered_map — хеш-таблица из STL, концептуально аналогична QHash, но с другой внутренней реализацией (как правило, цепочки/buckets) и другим API.
std::map — аналог QMap, дерево (обычно красно-чёрное).

Главное отличие не в алгоритмической сложности (она одинакова с точки зрения Big O), а в деталях реализации: накладные расходы на элемент, стратегия хеширования, поведение при копировании (Qt-контейнеры используют copy-on-write), интеграция с остальным кодом (сигналы/слоты, QVariant, сериализация).

Пример кода

#include <unordered_map>
#include <map>
#include <chrono>
#include <iostream>
#include <string>
#include <random>

#ifdef QT_CORE_LIB
#include <QHash>
#include <QMap>
#include <QString>
#endif

template <typename Func>
long long measureMs(Func&& f) {
    auto start = std::chrono::high_resolution_clock::now();
    f();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

int main() {
    constexpr int N = 1'000'000;
    std::vector<int> keys(N);
    std::mt19937 rng(42);
    for (auto& k : keys) k = rng();

    // std::unordered_map: вставка и поиск
    std::unordered_map<int, int> umap;
    umap.reserve(N); // важно: заранее резервировать buckets!
    auto insertTime = measureMs([&]() {
        for (int k : keys) umap[k] = k * 2;
    });
    std::cout << "std::unordered_map insert: " << insertTime << " msn";

    auto lookupTime = measureMs([&]() {
        long long sum = 0;
        for (int k : keys) sum += umap[k];
        std::cout << "(checksum " << sum << ")n";
    });
    std::cout << "std::unordered_map lookup: " << lookupTime << " msn";

    // std::map для сравнения порядка O(log n)
    std::map<int, int> ordered;
    auto mapInsertTime = measureMs([&]() {
        for (int k : keys) ordered[k] = k * 2;
    });
    std::cout << "std::map insert: " << mapInsertTime << " msn";

#ifdef QT_CORE_LIB
    QHash<int, int> qhash;
    auto qhashTime = measureMs([&]() {
        for (int k : keys) qhash[k] = k * 2;
    });
    std::cout << "QHash insert: " << qhashTime << " msn";
#endif

    return 0;
}

Пояснения к коду

Бенчмарк сравнивает время вставки миллиона элементов в std::unordered_map, std::map и (опционально, если код компилируется в Qt-проекте) QHash. Важная деталь — вызов reserve(N) для unordered_map: без предварительного резервирования контейнер будет многократно перестраивать таблицу bucket’ов по мере роста, что заметно снижает производительность вставки. Аналогичный приём (reserve) доступен и у QHash.

На практике разница между std::unordered_map и QHash в чистой скорости операций обычно не драматична (обе — хеш-таблицы с похожей асимптотикой), но QHash до недавних версий Qt использовал другую стратегию разрешения коллизий и был оптимизирован под небольшие объекты и интенсивное использование внутри Qt-фреймворка (например, в QObject::property).

Подводные камни и советы

1. Copy-on-write у Qt-контейнеров: QHash/QMap поддерживают неявное совместное использование данных (implicit sharing) — копирование контейнера почти бесплатно, пока не происходит модификация (тогда срабатывает детач). Это может давать иллюзию дешёвых копий там, где std::unordered_map скопировал бы все данные целиком. 2. Совместимость с Qt API: если объект участвует в сигналах/слотах, передаётся через QVariant, сериализуется через QDataStream — естественнее использовать QHash/QMap. Если код — чистая бизнес-логика без зависимостей от Qt, либо вы пишете переносимую библиотеку — предпочтительнее STL-контейнеры. 3. Итерация и порядок: если нужен предсказуемый порядок по ключу — QMap/std::map; если порядок не важен и нужна максимальная скорость — QHash/std::unordered_map. 4. Хеш-функции: для std::unordered_map с собственными типами ключей нужно специализировать std::hash<T>; для QHash — определить qHash(const T&). Забытая или плохая хеш-функция — частая причина деградации производительности до O(n). 5. Всегда измеряйте на реальных данных и реальном компиляторе/билде (Release, а не Debug) — разница в производительности между реализациями сильно зависит от стандартной библиотеки (libstdc++, MSVC STL, libc++) и версии Qt.

================================================================================