Таблица 6.20 [продолжение) Операция Описание

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

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

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

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

О set<Elem> - множество с сортировкой но критерию lesso (оператор <);

О set<Elem,op> - множество с сортировкой но критерию ор;

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

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

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

std::set<1nt,std::greater<int> > coll;

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

О В параметре конструктора. В этом варианте можно определить тип для нескольких критериев сортировки с разными значениями или состояниями этих критериев. Такой подход удобен при формировании критериев сортировки на стадии выполнения, а также при использовании различающихся критериев сортировки, которые относятся к одному тину данных. Пример приведен па с. 198,

Если критерий сортировки не указан, по умолчанию используется объект функции lesso, сортирующий элементы оператором <2.

Учтите, что критерий сортировки также используется при проверке элементов на равенство. При использовании критерия сортировки по умолчанию проверка двух элементов на равенство реализуется так:

if (! (eleml<elem2 И eleni2<eleml))

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

В системах, не поддерживающих значения по умолчанию для параметров шаблонов, критерий С1>]1тиуюикн обычно является обязательным параметром;

set<int.less<1nt> > coll:

У такой реализации есть три достоинства:

О она не требует передачи дополнительного аргумента (достаточно передать всего один аргумент - критерий сортировки);

О при определении типа элемента не обязательно определять оператор ==;

О в программе можно использовать расходящиеся определения равенства (то есть оператор == и проверка по критерию сортировки могут давать разные результаты), хотя это усложняет и запутывает программу.

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

Полное имя типа для контейнера получается излишне сложным и громоздким, поэтому для него рекомендуется определить псевдоним (то же самое полезно сделать и для определений итераторов);

typedef std::set<int,std::greater<1nt> > IntSet;

IntSet coll;

IntSet;:Iterator pos:

Конструктор, которому передается начало и конец интервала, может применяться для инициализации контейнера элементами контейнеров, относящихся к другим типам (от массива до стандартного входного потока данных). За подробностями обращайтесь на с. 153.

Немодифицирующие операции над множествами и мультимножествами

Множества и мультимножества поддерживают обычный набор операций для получения размера контейнера и сравнения элементов (табл. 6.21).

Таблица 6.21. Немодифицирующие операции над множествами и мультимножествами Операция Описание

c.sizeO Возвращает фактическое количество элементов

c.emptyO Проверяет, пуст ли контейнер (эквивалент sizeO==0, но иногда

выполняется быстрее)

c.max si2e0 Возвращает максимально возможное количество элементов

с1 == с2 Проверяет равенство с1 и с2

с1! = с2 Проверяет неравенство с1 и с2 (эквивалент !(с1==с2))

с1 < с2 Проверяет, что с1 меньше с2

с1 > с2 Проверяет, что с1 больше с2 (эквивалент с2<с1)

с1 <= с2 Проверяет, что с1 не больше с2 (эквивалент !(с2<с1))

с1 >= с2 Проверяет, что с1 не меньше с2 (эквивалент 1(с1<с2))

Операции сравнения определены только для однотипных контейнеров. Это означает совпадение как типов элементов, так и критерия сортировки; в противном случае происходит ошибка компиляции. Пример:

std::set<float> cl; Критерий сортировки: std::less<> std::set<float.std;:greater<float> > c2;

If (cl == c2) { ОШИБКА: разные типы }

Отношение «меньше/больше» между контейнерами проверяется по лексикографическому критерию (см. с. 356). Для сравнения контейнеров разных типов (с разными критериями сортировки) необходимо использовать алгоритмы, описанные на с. 352.

Специальные операции поиска

Множества и мультимножества оптимизированы для поиска элементов, поэтому в этих контейнерах определены специальные функции поиска (табл. 6.22), Эти функции представляют собой оптимизированные версии одноименных универсальных алгоритмов. Всегда используйте оптимизированные версии функций для множеств и мультимножеств, обеспечивающие логарифмическую сложность вместо линейной сложности универсальных алгоррггмов. Например, поиск в коллекции из 1000 элементов требует в среднем 10 сравнений вместо 500 (см. с. 37).

Таблица 6.22. Специальные операции поиска в множествах и мультимножествах Операция Описание

count(elem) Возвращает количество злементов со значением elem

find(eiem) Возвращает позицию первого элемента со значением elem (или end())

iower bound(eiem) Возвращает первую позицию, в которой может бьпь вставлен элемент elem (первый элемент >= elem)

upper bound(eiem) Возвращает последнюю позицию, в которой может быть вставлен элемент elem (первый элемент > elem)

equal range(elem) Возвращает первую и последнюю позиции, в которых может быть вставлен элемент elem (интервал, в котором элементы == elem)

Функция find() ищет первый элемент, значение которого передается в аргументе, и возвращает его позицию в виде итератора. Если поиск оказывается безуспешным, функция find() возвращает end().

Функции lower bound() и upper bound() возвращают соответственно первую и последнюю позиции, в которых может быть вставлен элемент с заданным значением. Иначе говоря, lower bound() возвращает позицию первого элемента, значение которого больше либо равно аргументу, а функция upper bound() возвращает позицию последнего элемента, значение которого больше аргумента. Функция equaLrangeO возвращает значения lower bound() и upper bound() в виде объекта типа pair (тип pair описан на с. 50). Таким образом, фзшкция возвращает интервал