В чем разница между контейнерами map и unordered_map в C++?

std::map — это ассоциативный контейнер, хранящий элементы как пары ключ-значение, отсортированные по ключам. Основан на сбалансированном бинарном дереве поиска (обычно красно-черном дереве).

std::unordered_map — также ассоциативный контейнер, хранящий пары ключ-значение, но без определенного порядка. Основан на хеш-таблице.

Основные отличия:

• Порядок элементов:
  • std::map: Элементы отсортированы по ключам.
  • std::unordered_map: Элементы не отсортированы, порядок зависит от хеш-функции и состояния хеш-таблицы.
• Производительность:
  • std::map:
    • Поиск, вставка и удаление: в среднем O(log N), где N — количество элементов.
    • Время доступа не зависит от содержимого.
  • std::unordered_map:
    • Поиск, вставка и удаление: в среднем O(1).
    • В худшем случае (при коллизиях) O(N). Время доступа зависит от качества хеш-функции и коэффициента заполнения.
• Использование памяти:
  • std::map: Требует немного больше памяти для хранения узлов дерева.
  • std::unordered_map: Может требовать больше памяти при низком коэффициенте заполнения (для уменьшения коллизий). Зависит от реализации.
• Требования к ключу:
  • std::map: Ключи должны поддерживать операцию сравнения (operator<).
  • std::unordered_map: Ключи должны поддерживать:
    • Равенство (operator==).
    • Хеширование (специализация std::hash или предоставление хеш-функции).
• Итераторы:
  • std::map: Двунаправленные итераторы, обходят элементы в отсортированном порядке.
  • std::unordered_map: Итераторы вперед, обходят элементы в произвольном порядке (зависящем от структуры хеш-таблицы).

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

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

// std::map
std::map<int, std::string> sorted_map;
sorted_map[3] = "three";
sorted_map[1] = "one";
sorted_map[2] = "two";

// Итерация по map выведет элементы в отсортированном порядке ключей (1, 2, 3)
for (const auto& pair : sorted_map) {
    // std::cout << pair.first << ": " << pair.second << std::endl;
}

// std::unordered_map
std::unordered_map<int, std::string> unsorted_map;
unsorted_map[3] = "three";
unsorted_map[1] = "one";
unsorted_map[2] = "two";

// Итерация по unordered_map выведет элементы в произвольном порядке
for (const auto& pair : unsorted_map) {
    // std::cout << pair.first << ": " << pair.second << std::endl;
}

Выбор между std::map и std::unordered_map зависит от требуемого функционала: если важен отсортированный порядок элементов или ключи нельзя хешировать/сравнивать на равенство эффективно, используется std::map. Если важна максимальная производительность для поиска/вставки/удаления, и порядок элементов не имеет значения, предпочтительнее std::unordered_map (при условии хорошей хеш-функции).