listl: QQ1122334455

list2; 0 12 3 4 5

listl: QO0111222333444555 list2:

Множества и мультимножества

Множества и мультимножества автоматически сортируют свои элементы по некоторому критерию (см. главу 5). Они отличаются только тем, что мультимножества могут содержать дубликаты, а множества - нет (рис. 6.6).

Множество

Мультимножество

Рис. б.б. Множество и мультимножество

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

finclude <set>

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

namespace std {

template <class Т.

class Compare = less<T>,

class Allocator = allocator<T> >

class set:

template <class T,

class Compare = less<T>.

class Allocator = allocator<T> > class multiset:

Элементы множества или мультимножества относятся к произвольному типу Т, поддерживающему присваивание, копирование и сравнение по критерию сорти-

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

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

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

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

Точнее говоря, множества и мyл]>тrмнoжecтEa обычно реализуются в виде «красно-чер-пых деревьев». Красно-черные деревья хорошо приспособлены как для изменения количества элементов, так и для поиска. Они гарантируют, что вставка потребует не более двух изменений внутренних ссылок, а самый длинный путь к элементу будет пе более чем вдвое длиннее самого короткого.

ровки. Необязательный второй параметр шаблона определяет критерий сортировки. По умолчанию используется критерий less. Объект функции less сортирует элементы, сравнивая их оператором < (дополнительная информация об объекте less приводится на с. 305). Необязательный третий параметр шаблона определяет модель памяти (см. главу 15). По умолчанию используется модель allocator, определенная в стандартной библиотеке С++.

Критерий сортировки должен определять «строгую квазиупорядоченность» (strict weak ordering ). Строгая квазиупорядочепность определяется тремя свойствами.

О Асимметричность.

□ Для оператора <: если выражение х<у истинно, то выражение у<х ложно.

□ Для предиката ор(): если выражение ор(Х/у) истинно, то выражение ор(у,х) ложно.

о Транзитивность.

□ Для оператора <: если выражения х<у и y<z истинны, то выражение x<z истинно.

□ Для предиката ор(): если выражения ор(х,у) и op(y,z) истинны, то выражение op(x,z) истинно.

о Иррефлексивность.

□ Для оператора <: выражение х<х всегда ложно.

□ Для предиката ор(); выражение ор(х,х) всегда ложно.

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

Возможности множеств и мультимножеств

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

Главное досторгнство автоматической сортировки заключается п том, что бинарное дерево обеспечивает хорошие показатели при поиске Элементов с кон-

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

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

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

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

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

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

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

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

Операция

Описание

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

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

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

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

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

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

продолжение