отличаются только тем, что последние могут содержать дубликаты, а первые нет (рис. 6.8).

Отображение

Мультиотображение

Рис. 6.8. Отображение и мультиотображение

Чтобы использовать отображение или мультиотображение в программе, необходимо вк.1ючить в нее заголовочный файл <тар>:

#1nclude <[пар>

Типы отображения и мультиотображения определяются как шаблоны классов в пространстве имен std:

namespace std {

template <class Key, class T.

class Compare = less<Key>.

class Allocator = allocator<pair<const Key. T> > >

class map:

template <class Key. class T.

class Compare = less<Key>.

class Allocator = allocator<pa1r<const Key. T> > > class multimap;

Первый аргумент шаблона определяет тип ключа, а второй - тип значения элемента. Элементы отображений и мультиотображений могут состоять нз произвольных типов Key и Т, удовлетворяющих двум условиям:

О пара «ключ/значение» должна поддерживать присваивание и копирование;

О ключ должен быть совместим с критерием сортировки.

Необязательный третий аргумент шаблона задает критерий сортировки. Как и в случае с множествами, критерий сортировки должен определять «строгую квазиупорядоченность» (см. с. 184). Элементы сортируются по ключам, значения элементов не влияют на порядок следования. Критерий сортировки также используется для проверки на равенство (два элемента равны, если ни один из них НС меньше другого). Если специальный критерий сортировки не

В исходной версии STL отображение определялось в заголовочном файле <map.h>, а мультимножество - п файле <multiniap.h>.

указан, по умолчанию используется критерий less. Объект функции less сортирует элементы, сравнивая их оператором < (дополнительная информация об объекте less приводится на с. 306).

Необязательный четвертый параметр шаблона определяет модель памяти (см. главу 15). По умолчанию используется модель allocator, определенная в стандартной библиотеке 0++.

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

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

4 у

9 X

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

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

В системах, не поддсрживаюв1Их значения по умолчанию для параметров шаблонов,

третий аргумент обычно является обязательным. В системах, пе поддерживающих значения по умолчанию для параметров шаблонов,

четвертый аргумент обычно отсутствует.

ключом, а затем вставить новый элемент с новым ключом и старым значением (подробности см. на с. 208). Как следствие, с точки зрения итератора к.1юч элемента является константным, однако прямая модификация значения элемента разрешена (если значение не принадлежит к константному тину).

Операции над отображениями и мультиотображениями

Операции создания, копирования и уничтожения

в табл. 6.26 представлены конструкторы и деструктор отображений и мультиотображений.

Таблица 6.26. Конструкторы и деструктор отображений и мультиотображений Опера ция Ол исание

тар с Создает пустое отображение или мультиотображение, не содержащее

ни одного элемента

тар с(ор) Создает пустое отображение или мультиотображение, использующее

критерий сортировки ор

тар с1(с2) Создает копию другого отображения или мультиотображения того же

типа (с копированием всех элементов)

тар c(beg,end) Создает отображение или мультиотображение, инициализированное

элементами интервала [beg,end)

map c(beg,end,op) Создает отображение или мультиотображение с критерием сортировки ор, инициализированное элементами интервала [beg,end)

c.mapC) Уничтожает все элементы и освобождает память

В таблице слово «set» обозначает собой одну из следующих конструкций:

О map<Elem> - отображение с сортировкой ключей по критерию lesso (оператор <);

О map<Elem,op> - отображение с сортировкой ключей по критерию ор;

О multimap<Elem> - мультиотображение с сортировкой ключей по критерию lesso (оператор <);

О nriultimap<Elem,op> - мультиотображение с сортировкой ключей по критерию ор.

Существуют два варианта определения критерия сортировки. О В параметре шаблона, например:

std: :map<float.std: :5tr1ng.5td: :greater<float> > coU:

В этом случае критерий сортировки является частью типа. Таким образом, система типов гарантирует, что объединение возможно только для контейне-

Обратите внимание иа пробел между символами >. Последовательность > воспринимается компилятором как оператор сдвига, что приводит к синтаксической ошибке.