Как устроен Map?

Как устроен Map в C++

std::map — это упорядоченный контейнер, который хранит пары ключ-значение в отсортированном порядке по ключам. Это один из фундаментальных контейнеров стандартной библиотеки C++, и понимание его внутреннего устройства критично для написания эффективного кода.

Внутренняя структура: Red-Black Tree

std::map реализует свои данные с помощью красно-чёрного дерева (Red-Black Tree) — это самобалансирующееся двоичное дерево поиска:

#include <map>
#include <iostream>

int main() {
    // Внутренняя структура map:
    //        [5]
    //       /   \
    //      [3]   [7]
    //     / \   / \
    //   [1][4][6][8]
    
    std::map<int, std::string> map;
    map[5] = "five";
    map[3] = "three";
    map[7] = "seven";
    
    // Элементы хранятся в отсортированном порядке
    for (auto& [key, value] : map) {
        std::cout << key << ": " << value << std::endl;  // 3, 5, 7
    }
}

Свойства Red-Black Tree

Цветовые правила:

1. Каждый узел окрашен в красный или чёрный цвет
2. Корень всегда чёрный
3. Листья (NIL) окрашены в чёрный
4. Если узел красный, его дети чёрные
5. Все пути от узла к листьям содержат одинаковое число чёрных узлов

Эти правила гарантируют, что дерево приблизительно сбалансировано, обеспечивая O(log n) для всех операций.

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

std::map<int, std::string> map;

map[10] = "ten";          // O(log n) - вставка
map.at(10);               // O(log n) - поиск
map.erase(10);            // O(log n) - удаление
map.find(10);             // O(log n) - поиск с итератором
map.lower_bound(10);      // O(log n) - первый >= key
map.upper_bound(10);      // O(log n) - первый > key

Все операции работают за O(log n), что делает map подходящим для приложений, требующих частых операций поиска/вставки.

Структура узла

template <typename Key, typename Value>
struct TreeNode {
    std::pair<const Key, Value> data;
    TreeNode* left;      // левый потомок (ключи меньше)
    TreeNode* right;     // правый потомок (ключи больше)
    TreeNode* parent;    // родитель для восстановления баланса
    Color color;         // RED или BLACK
};

Итерирование и порядок

std::map хранит элементы в отсортированном порядке (in-order обход дерева):

#include <map>

int main() {
    std::map<int, std::string> map = {
        {5, "five"},
        {2, "two"},
        {8, "eight"},
        {1, "one"},
        {9, "nine"}
    };
    
    // Итерация в порядке возрастания ключей
    for (auto& [key, value] : map) {
        std::cout << key << " ";  // 1 2 5 8 9
    }
    
    // Обратная итерация
    for (auto it = map.rbegin(); it != map.rend(); ++it) {
        std::cout << it->first << " ";  // 9 8 5 2 1
    }
}

Сравнение с unordered_map

Практические примеры

Поиск диапазона значений:

std::map<int, std::string> ages;
ages[20] = "Alice";
ages[25] = "Bob";
ages[30] = "Charlie";
ages[35] = "David";

// Найти всех людей с возрастом от 25 до 30 включительно
auto lower = ages.lower_bound(25);  // first >= 25
auto upper = ages.upper_bound(30);  // first > 30

for (auto it = lower; it != upper; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

Пользовательский компаратор:

#include <map>
#include <string>

struct CompareByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

int main() {
    // Сортировка по длине строки, не по алфавиту
    std::map<std::string, int, CompareByLength> map;
    map["a"] = 1;
    map["bb"] = 2;
    map["ccc"] = 3;
    
    for (auto& [key, value] : map) {
        std::cout << key << " ";  // a bb ccc
    }
}

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

• Нужна отсортированность данных
• Важна предсказуемость производительности (всегда O(log n))
• Нужны операции с диапазонами (lower_bound, upper_bound)
• Рабочий набор умещается в памяти (каждый узел требует дополнительной памяти)

std::map остаётся одним из самых полезных контейнеров в C++ благодаря хорошему балансу между производительностью и функциональностью.