Как устроен контейнер map в C++?

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

Основные характеристики:

• Элементы хранятся в отсортированном порядке по ключу.
• Ключи уникальны. Каждый ключ может встречаться только один раз.
• Время доступа, вставки и удаления в среднем логарифмическое: $O(\log n)$, где $n$ - количество элементов.
• Реализован, как правило, на основе самобалансирующегося бинарного дерева поиска, чаще всего красно-чёрного дерева.

Внутреннее устройство (красно-чёрное дерево):

Каждый узел дерева хранит:

1. Пару ключ-значение (std::pair<const Key, T>). Ключ константный, чтобы избежать его изменения и сохранения свойства упорядоченности.
2. Указатели на левого и правого потомков.
3. Указатель на родителя.
4. Цвет узла (красный или чёрный).

Свойства красно-чёрного дерева, поддерживаемые при операциях вставки и удаления с помощью вращений и перекрашиваний, обеспечивают логарифмическую высоту дерева и, как следствие, логарифмическую сложность операций.

Операции:

• operator[]: Доступ по ключу. Если ключ не найден, вставляет новый элемент с ключом и значением по умолчанию для типа значения.
• at(): Доступ по ключу. Если ключ не найден, бросает исключение std::out_of_range.
• insert(): Вставляет новый элемент-пару. Игнорирует вставку, если ключ уже существует.
• erase(): Удаляет элемент по