508 _____________Часть III. Современное программирование на C++

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

Множество и мультимножество (set и multiset) принадлежат к категории ассоциативных контейнеров STL. Ассоциативные контейнеры поддерживают упорядочивание элементов на основе определенного ключа. Для множеств и мультимножеств этот ключ определяется хранимым объектом. Такое упорядочивание объектов делает очень эффективным поиск, удаление и добавление элементов. Разница между множеством и мультимножеством состоит в том, что множество не допускает повторяющихся ключей, а мультимножество допускает.

Для объектов множества должны быть определены операции эквивалентности == и сравнения <.

Для использования множества или мультимножества в исходный текст модуля необходимо включить заголовок set.h.

Операции, функции-члены и определения типов для множеств и мультимножеств одинаковы. Конструкторы этих контейнеров имеют три формы:

// Конструктор по умолчанию. Множество пусто. set<int> intSet;

// ОР-^кт-функция передается для определения порядка в множестве. multiset<STUDENT> floatMSet(GRADE_COMPARE) ;

// Множество studentSet формируется путем копирования

// элементов из вектора.

set<STUDENT> studentSet(studentVectorl.begin(), studentVectorl.end()) ;

// Создается мультимножество целых и копируется содержимое списка. // Для упорядочивания используется объект-функция STL greater, // порядок изменяется на обратный. multiset<int> intMS(intList.begin(), intList.end 0, greater<int>);

Функции-члены begin (), rbeginO, rendO, empty (), niax_size (), sized И swap () такие же, как для векторов. Итераторы, возвращаемые такими функциями, как begin о — это итераторы произвольного доступа. Для множеств и для мультимножеств итераторы являются двунаправленными. Для множеств и мультимножеств определен весьма полезный тип iterator, подобный типу iterator векторных контейнеров. Все эти подробности обсуждались выше в разделе "Вектор" .

Функция-член erase () работает так же, как для векторов, но ее версия для множеств и мультимножеств несколько расширена. Расширенная форма принимает объект и ищет для него контейнер; если такой находится, он удаляется, insert () не производит никакого действия, если пытается вставить объект, ключ которого повторяется в множестве. Для мультимножества двойные ключи не мешают добавлять элементы.

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