std::map - это ассоциативный контейнер в C++, который хранит элементы, состоящие из пары "ключ-значение", в отсортированном по ключу порядке. Ключи уникальны, и каждый ключ связан ровно с одним значением.
Внутренне std::map обычно реализован как красно-черное дерево.
- Красно-черное дерево (Red-Black Tree): Это самобалансирующееся бинарное дерево поиска. Свойства балансировки гарантируют логарифмическую сложность для большинства операций, таких как вставка, удаление и поиск.
Свойства красно-черного дерева:
- Каждый узел либо красный, либо черный.
- Корень всегда черный.
- Все листья (NULL-узлы) черные.
- Если узел красный, то оба его потомка черные.
- Для каждого узла любой простой путь от этого узла к любому из листовых потомков содержит одинаковое количество черных узлов.
Эти свойства позволяют поддерживать относительный баланс дерева, предотвращая деградацию производительности до линейной в худшем случае.
Ключевые характеристики std::map:
- Уникальность ключей: Нельзя вставить два элемента с одинаковым ключом. Попытка вставки элемента с существующим ключом либо игнорируется, либо обновляет значение (в зависимости от метода вставки).
- Сортировка по ключу: Элементы хранятся в порядке, определяемом функцией сравнения ключей (по умолчанию
std::less для типа ключа).
- Ассоциативный доступ: Доступ к элементам происходит по ключу, а не по индексу.
- Логарифмическая сложность: Большинство операций (вставка, удаление, поиск) имеют сложность O(log N), где N - количество элементов в контейнере.
Пример использования:
cpp