В чем разница между std::map и std::unordered_map?

Основные различия между std::map и std::unordered_map в C++:

Структура данных и порядок:

• std::map — реализован как красно-черное дерево, элементы хранятся отсортированными по ключу
• std::unordered_map — реализован как хеш-таблица, порядок элементов не гарантирован

Сложность операций:

• std::map: поиск, вставка, удаление — O(log n)
• std::unordered_map: в среднем O(1), в худшем случае O(n) (при коллизиях)

Требования к ключам:

• Для std::map ключ должен поддерживать оператор сравнения (operator<) или нужно предоставить компаратор
• Для std::unordered_map нужны хеш-функция (std::hash специализация) и оператор равенства (operator==)

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

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

// std::map - сохраняет порядок
std::map<int, std::string> ordered_map = {
    {3, "three"},
    {1, "one"},
    {2, "two"}
};
// При итерации: 1->"one", 2->"two", 3->"three"

// std::unordered_map - порядок не определен
std::unordered_map<int, std::string> unordered_map = {
    {3, "three"},
    {1, "one"},
    {2, "two"}
};
// Порядок может быть любым

// Специализация хеша для пользовательского типа
struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

namespace std {
    template<>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

Когда что использовать:

• std::map: когда нужен гарантированный порядок элементов или частые операции с диапазонами
• std::unordered_map: когда важна максимальная скорость доступа и порядок не важен