На этом шаге мы приведем общие сведения о множествах и мультимножествах.
Множества и мультимножества автоматически сортируют свои элементы по некоторому критерию. Они отличаются только тем, что мультимножества могут содержать дубликаты, а множества - нет (рисунок 1).
Рис.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, определенная в стандартной библиотеке C++.
Критерий сортировки должен определять "строгую квазиупорядоченность" (strict weak ordering). Строгая квазиупорядоченность определяется тремя свойствами.
- Асимметричность.
- Для оператора <: если выражение х<у истинно, то выражение у<х ложно.
- Для предиката ор(): если выражение ор(х,у) истинно, то выражение ор(у,х) ложно.
- Транзитивность.
- Для оператора <: если выражения х<у и y<z истинны, то выражение x<z истинно.
- Для предиката ор(): если выражения ор(х,у) и op(y,z) истинны, то выражение op(x,z) истинно.
- Иррефлексивность.
- Для оператора <: выражение х<х всегда ложно.
- Для предиката ор(): выражение ор(х,х) всегда ложно.
На основании этих свойств критерий сортировки используется также для проверки на равенство, а именно: два элемента равны, если ни один из них не меньше другого (или если ложны оба выражения ор(х,у) и ор(у,х)).
На следующем шаге мы рассмотрим возможности множеств и мультимножеств.
