Создание двух пустых списков list<1nt> Ustl. I1st2;

Заполнение обоих списков элементами for (int i=Q: 1<6; {

I1stl.push back(i):

list2.push frontCi);

pr1ntL1sts(listl, I1st2):

Вставка всех элементов listl перед первым элементом со значением 3 в I1st2

- findO возвращает итератор на первый элемент со значением 3 I1st2.spllce(f1ndci1st2.beginC).Iist2.end(). Позиция в приемнике 3).

listl); Источник

pr1ntL1sts(listl. I1st2);

Перемещение первого элемента в конец

l1st2.splice(list2.endC), Позиция в приемнике

I1st2. Источник

I1st2.beginO); Позиция в источнике pr1ntL1stsCl1stl, list2):

Сортировка второго списка, присваивание Ustl

и удаление дубликатов

Iist2.sort0;

Ustl = I1st2:

Iist2.un1que0:

printListsCHstl. Iist2):

Слияние двух отсортированных списков в первом списке listl.rrergeCl1st2): printListsdistl. I1st2);

Программа выводит следующий результат:

listl: 0 12 3 4 5 list2: 5 4 3 2 10

listl:

I1st2: 540123453210 Ustl;

l1st2; 401234532105

listl: QQ1122334455

I1st2; 0 12 3 4 5

l1Stl: QO0111222333444555 list2:

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

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

Множество

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

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

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

#include <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>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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