Просто для уверенности.,. 1f (colli.v3lue compC) == col12.value comp()) {

cout colli and C0II2 have same sorting criterion endl;

else {

cout colli and C0II2 have different sorting criterion endl;

void fill (IntSetS set) {

Вставка элементов в произвольном порядке set.insert(4) set.1nsert(7) set.insert(5) set.insertd) set.insert(6) set.insert(2) set.insert(5)

В этой программе RuntimeCmpo представляет собой простой шаблон, позволяющий задать критерий сортировки для произвольного типа во время выполнения программы. Конструктор по умолчанию сортирует элементы по возрастанию, для чего используется стандартное зпачепие normal. Также при вызове конструктора может быть передан аргумент RuntimeCmpo::reverse, чтобы сортировка осуществлялась по убыванию.

Результат выполнения программы выглядит так:

colli: 12 4 5 6 7 С0112: 7 6 5 4 2 1 colli: 7 6 5 4 3 2 1

coin and C0II2 have same sorting criterion

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

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

Элементами отображений и мультиотображений яв.тяются пары ключ/значе-нне . Сортировка элементов производится автоматически на ос1ювании критерия сортировки, применяемого к ключу. Отображения и мультиотображения

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

Отображение

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

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

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

#1nclude <[пар>

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

namespace std {

template <class Key, class T.

class Compare = less<Key>.

class Allocator = allocatQr<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, определенная в стандартной библиотеке С++.

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

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

4 у

9 X

7Т 7\

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

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

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

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

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