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

Question

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

Тип вопроса: STL Вероятность: 30% Категория: C/C++ Разработчик

Ответ

Основные различия между 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: когда важна максимальная скорость доступа и порядок не важен

Ответ 18+ 🔞

А, слушай, про контейнеры в плюсах? Ну это ж классика, прям как выбор между пивом и водкой — оба напитки, но ощущения, бля, разные, ёпта.

Вот смотри, есть у нас std::map. Это такой, бля, педантичный немец. Всё у него по полочкам, всё отсортировано, упорядочено. Внутри у него красно-чёрное дерево, этакая хитрая жопа из узлов, где всё сбалансировано. Ищет он за O(log n), то есть не мгновенно, но стабильно, как швейцарские часы. Ключ к нему попадёт — должен уметь сравниваться, оператор < иметь или компаратор. Без этого — ни хуя себе, не примет, заартачится.

А теперь его братан-разгильдяй — std::unordered_map**. Этот чувак — чистой воды халявщик и понторез. Внутри у него хеш-таблица, бардак организованный, но быстрый. В идеале хватает элемент за **O(1)**, то есть почти мгновенно, но если коллизии начнутся (все ключи в одну корзину полезут), то будет **O(n)** и всё **накрылось медным тазом**. Порядок элементов? Да **похуй** ему! Выведешь на экран — а они в таком виде, в каком компилятору в голову взбредёт. И ключи ему нужны особенные: должна быть хеш-функция (std::hash) и оператор==`. Без этого — доверия ебать ноль, не скомпилируется.

Вот тебе пример, чтобы совсем понятно было:

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

// map — аккуратист
std::map<int, std::string> ordered_map = {
    {3, "three"},
    {1, "one"},
    {2, "two"}
};
// Идешь по нему — всегда получишь: 1, 2, 3. Порядок, сука!

// unordered_map — что попало
std::unordered_map<int, std::string> unordered_map = {
    {3, "three"},
    {1, "one"},
    {2, "two"}
};
// А тут, бля, может вывести 2, 1, 3. Или 3, 2, 1. **Волнение ебать** каждый раз новое!

А если свой тип запихнуть хочешь — вот тут начинается ёперный театр. Для unordered_map надо, чтобы твой класс умел в хеш и сравнение. Смотри, как это выглядит:

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 {
            // Хеш от X и Y скрещиваем — главное, не налажать
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

Итог, чувак:

Берёшь std::map, когда тебе порядок важен, или ты часто работаешь с диапазонами (типа "дай всё от A до B"). Скорость стабильная, но не космическая.
Хватаешь std::unordered_map, когда тебе терпения ноль ебать, и нужна максимальная скорость вставки и поиска в среднем случае, а порядок — да похуй. Но помни: худший случай может быть пиздец медленным, и надо для своих типов хитрую жопу с хеш-функцией городить.

Выбирай с умом, а то будет вам хиросима и нигерсраки в производительности.