Контейнеры STL. Возможности отображений и мультиотображений

   
На этом шаге мы рассмотрим основные возможности отображений и мультиотображений.

   
Отображения и мультиотображения, как и другие ассоциативные контейнеры, обычно реализуются в виде сбалансированных бинарных
деревьев (рисунок 1).


Рис.1. Внутренняя структура отображений и мультиотображений

   
В стандарте такая реализация не оговорена, но она следует из требований к сложности операций над отображениями и
мультиотображениями. В сущности, множества, мультимножества, отображения и мультиотображения используют один и тот же
внутренний тип данных. Множества и мультимножества можно рассматривать как частные случаи соответственно отображений и
мультиотображений, у которых значения тождественны ключам элементов. Следовательно, отображения и мультиотображения обладают
всеми свойствами и поддерживают все операции множеств и мультимножеств. Впрочем, второстепенные различия все же существуют.
Во-первых, элементы представляют собой пары "ключ/значение". Во-вторых, отображения могут использоваться в качестве ассоциативных массивов.

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

   
Со следующего шага мы начнем рассматривать операции над отображениями и мультиотображениями.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий