Множество — это структура данных, эквивалентная множествам в математике. Множество состоит из различных элементов заданного типа и поддерживает операции добавления элемента в множество, удаления элемента из множества, проверка принадлежности элемента множеству. Одно и то же значение хранится в множестве только один раз.
Для представления множеств в библиотеке STL имеется контейнер set, который реализован при помощи сбалансированного двоичного дерева поиска (красно-черного дерева), поэтому множества в STL хранятся в виде упорядоченной структуры, что позволяет перебирать элементы множества в порядке возрастания их значений. Для использования контейнера set нужно подключить заголовочный файл <set>.
Подробней о возможностях контейнера set можно прочитать, например, на сайте cppreference.com.
В простейшем случае множество, например, данных типа int объявляется так:
set <int> S;
Для добавления элемента в множество используется метод insert:
S.insert(x);
Для проверки принадлежности элемента множеству используется метод count. Этот метод возвращает количество вхождения передаваемого параметра в данный контейнер, но поскольку в множестве все элементы уникальные, то count для типа set всегда возвращает 0 или 1. То есть для проверки принадлежности значения x множеству S можно использовать следующий код:
if (S.count(x)) { ...
Для удаления элемента используется метод erase. Ему можно передать значение элемента, итератор, указывающий на элемент или два итератора (в этом случае удаляется целый интервал элементов, содержащийся между заданными итераторами). Вот два способа удалить элемент x:
S.erase(x);
S.erase(S.find(x));
Метод size() возвращает количество элементов в множестве, метод empty(), возвращает логическое значение, равное true, если в множестве нет элементов, метод clear() удаляет все элементы из множества.
С итераторами контейнера set можно выполнять операции инкремента (что означает переход к следующему элементу) и декремента (переход к предыдущему элементу). Итераторы можно сравнивать на равенство и неравенство. Операции сравнения итераторов при помощи "<", "<=", ">", ">=" невозможны, также невозможно использовать операции прибавления к итератору числа.
Разыменование итератора (применение унарного оператора *) возвращает значение элемента множества, на который указывает итератор.
У множества есть метод begin(), который возвращает итератор на первый элемент множества, и метод end(), который возвращает фиктивный итератор на элемет, следующий за последним элементом в множестве. Таким образом, вывести все элементы множества можно так:
set <int> S;
set <int>::iterator it;
for (it = S.begin(); it != S.end(); ++it)
cout << *it << " "
Благодаря тому, что множества хранятся в упорядоченном виде, все элементы будут выведены в порядке возрастания значений.
В стандарте C++11 разрешается перебор всех элементом множества при помощи range-based цикла:
for (auto elem: S)
cout << elem << " ";
Элементы также будут выведены в порядке возрастания.
Для вывода элементов в порядке убывания можно использовать reverse_iterator аналогично векторам:
for (auto it = S.rbegin(); it != S.rend(); ++it)
cout << *it << " ";
Функции удаления элементов могут принимать итератор в качестве параметра. В этом случае удаляется элемент, на который указывает итератор. Например, чтобы удалить наименьший элемент:
S.erase(S.begin());
Но для удаления последнего (наибольшего) элемента в set нельзя использовать reverse_iterator, нужно взять обычный итератор, указывающий на end(), уменьшить и удалить:
auto it = S.begin();
--it;
S.erase(it);
Для поиска конкретного элемента в set используется метод find. Этот метод возвращает итератор на элемент, а если элемент не найден, то он возвращает итератор end() (т.е. на фиктивный элемент, следующий за последним элементом множества. Используя этот метод проверить принадлежность элемента множеству можно так:
if (S.find(x) != S.end()) { ...
Также есть методы lower_bound и upper_bound, которые находят первых элемент, больше или равный x и первый элемент, строго больший x (аналогично двоичному поиску элемента в массиве).
Эти методы также возвращают итераторы, а если таких элементов (больше или равных или строго больших) нет в множестве, они возвращают end().
Например, удалить из set минимальный элемент, строго больший x можно так:
auto it = S.upper_bound(x);
if (it != S.end())
S.erase(it);