На этом шаге мы рассмотрим основные возможности отображений и мультиотображений.
Отображения и мультиотображения, как и другие ассоциативные контейнеры, обычно реализуются в виде сбалансированных бинарных деревьев (рисунок 1).
Рис.1. Внутренняя структура отображений и мультиотображений
В стандарте такая реализация не оговорена, но она следует из требований к сложности операций над отображениями и мультиотображениями. В сущности, множества, мультимножества, отображения и мультиотображения используют один и тот же внутренний тип данных. Множества и мультимножества можно рассматривать как частные случаи соответственно отображений и мультиотображений, у которых значения тождественны ключам элементов. Следовательно, отображения и мультиотображения обладают всеми свойствами и поддерживают все операции множеств и мультимножеств. Впрочем, второстепенные различия все же существуют. Во-первых, элементы представляют собой пары "ключ/значение". Во-вторых, отображения могут использоваться в качестве ассоциативных массивов.
В отображениях и мультиотображениях элементы автоматически сортируются по ключу, поэтому эти контейнеры обеспечивают хорошее быстродействие при поиске элементов по известному ключу - операции, которая обычно выполняется относительно медленно. Автоматическая сортировка устанавливает важное ограничение для отображений и мультиотображений: ключ элемента нельзя изменить напрямую, потому что это нарушит упорядоченность элементов. Чтобы изменить ключ элемента, необходимо удалить элемент со старым ключом, а затем вставить новый элемент с новым ключом и старым значением. Как следствие, с точки зрения итератора ключ элемента является константным, однако прямая модификация значения элемента разрешена (если значение не принадлежит к константному типу).
Со следующего шага мы начнем рассматривать операции над отображениями и мультиотображениями.
