Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
20.
Множества и мультимножества
Множества и мультимножества автоматически сортируют свои элементы по некоторому критерию. Они отличаются только тем, что мультимножества могут содержать дубликаты, а множества — нет (рис. 1.).
Чтобы использовать множество или мультимножество в программе, необходимо включить в нее заголовочный файл <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;
}
Элементы множества или мультимножества относятся к произвольному типу Т, поддерживающему присваивание, копирование и сравнение по критерию сортировки. Необязательный второй параметр шаблона определяет критерий сортировки. По умолчанию используется критерий less. Объект функции less сортирует элементы, сравнивая их оператором < . Необязательный третий параметр шаблона определяет модель памяти. По умолчанию используется модель allocator, определенная в стандартной библиотеке С++.
Множества и мультимножества, как и все стандартизированные классы ассоциативных контейнеров, обычно реализуются в виде сбалансированного бинарного дерева. В стандарте такая реализация не указана, но она обусловлена требованиям к сложности операций над множествами и мультимножествами.
Главное достоинство автоматической сортировки заключается в том, что бинарное дерево обеспечивает хорошие показатели при поиске элементов с конкретным значением. Функции поиска в них имеют логарифмическую сложность. Например, чтобы найти элемент в множестве или мультимножестве, содержащем 1000 элементов, процедуре поиска по дереву (функции класса) потребуется выполнить в среднем около 1/50 от количества сравнений при линейном поиске (алгоритм).
Тем не менее автоматическая сортировка также накладывает важное ограничение на множества и мультимножества: значение элементов нельзя изменять напрямую, потому что это может нарушить правильный порядок их расположения. Следовательно, чтобы изменить значение элемента, необходимо удалить элемент со старым значением и вставить элемент с новым значением. Этот принцип нашел свое отражение в интерфейсе:
- множества и мультимножества не поддерживают прямое обращение к элементам;
- при косвенном обращении через итераторы действует ограничение: с точки зрения итератора значение элемента является константным.
Операции над множествами и мультимножествами Операции создания, копирования и уничтожения
Таблица 1. Конструкторы и деструктор множеств и мультимножеств
|
Операция |
Описание |
|
set c |
Создает пустое множество или мультимножество, не содержащее ни одного элемента |
|
set c(op) |
Создает пустое множество или мультимножество, использующее критерий сортировки ор |
|
set c1(c2) |
Создает копию другого множества или мультимножества того же типа (с копированием всех элементов) |
|
set c(beg,end) |
Создает множество или мультимножество, инициализированное элементами интервала [beg,end) |
|
set c(beg,end,op) |
Создает множество или мультимножество с критерием сортировки ор, инициализированное элементами интервала [beg,end) |
|
c.~set() |
Уничтожает все элементы и освобождает память |
В таблице символами «set» обозначена одна из следующих конструкций:
- set<Elem> — множество с сортировкой по критерию less<> (оператор <);
- set<Elem,op> — множество с сортировкой по критерию ор;
- multiset<Elem> — мультимножество с сортировкой по критерию less<> (оператор <);
- multiset<Elem,op> — мультимножество с сортировкой по критерию ор.