кретным значением. Функции поггска в них имеют логарифмическую сложность. Например, чтобы найти элемент в множестве или мультимножестве, содержащем 1000 элементов, процедуре поиска по дереву (функции класса) потребуется выполнить в среднем около 1/50 от количества сравнений при линейном поиске (алгоритм). За дополнительной информацией о сложности операций обращайтесь на с. 37.

Рис. 6.7. Внутренняя структура множеств и мупьтимножеств

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

О множества и мультимножества не поддерживают прямое обращение к элементам;

О при косвенном обращении через итераторы действует ограничение: с точки зрения итератора значение элемента является константным.

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

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

Таблица 6.20. Конструкторы и деструктор множеств и мультимножеств

Операция

Описание

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

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

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

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

set cUc2) Создает копию другого множества или мупьтимножества того же типа

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

продолжение

Таблица 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>]1тиуювкн обычно является обязательным параметром;

set<int.less<lnt> > 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))