Set

Материал из Algocode wiki
Версия от 12:45, 28 ноября 2019; Gutrov Egor (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

set - это коллекция, которая содержит множество уникальных упорядоченных элементов. Чтобы добавить элемент в set, есть функция insert. В случае, если элемент уже был в множестве, ничего не происходит. Чтобы удалить элемент из set, есть функция erase (в нее можно передать либо итератор на элемент, либо просто элемент). Если erase была вызвана с элементом, а элемента не было в set, то ничего не произойдет. Чтобы посмотреть, есть ли элемент в set, есть функция count. Она вернёт $0$, если элемента нет в множестве, и $1$, если он есть. Также есть метод find, который возвращает итератор на элемент или end, если элемента нет. Все операции с элементами set (добавление, удаление, поиск) работают за $O(\log n)$, где $n$ - количество элементов в нём, так как он реализован с помощью сбалансированного двоичного дерева поиска.

Итераторы set относятся к категории BidirectionalIterator и имеют тип set<T>::iterator. Начало set можно получить с помощью функции begin, конец — с помощью функции end. Как и в случае с вектором, end указывает на конец полуинтервала. Инкремент и декремент итераторов set также работают за логарифмическое время. Стоит отметить, что, так как элементы в set упорядочены, с помощью begin и end можно искать наименьший/наибольший элемент в set. Чтобы найти наименьший элемент, больший или равный заданному, есть функция lower_bound. Чтобы найти наименьший элемент, строго больший заданному, есть функция upper_bound. Каждая из этих функций возвращает итератор на искомый элемент или end(), если такого элемента не существует. set может содержать только элементы тех типов, для которых определён оператор <, поскольку ему важен порядок элементов. Рассмотрим пример простейших операций с set.

set<int> s;

s.insert(3); // s = {3}
s.insert(2); // s = {2, 3}
cout << s.size() << "\n"; // выведет 2

s.insert(3); // 3 не будет добавлено ещё раз, так как уже присутствует в множестве
cout << s.size() << "\n"; // выведет 2

s.insert(5); // s = {2, 3, 5}
cout << s.count(3) << "\n"; // выведет 1
cout << s.count(4) << "\n"; // выведет 0

s.erase(3); // s = {2, 5}
s.insert(6); // s = {2, 5, 6}

set<int>::iterator it1 = s.find(5);
it1++;
cout << *it1 << "\n"; // выведет 6

auto it2 = s.lower_bound(1);
cout << *it2 << "\n"; // выведет 2, так как это первый элемент >= 1

auto it3 = s.upper_bound(2);
cout << *it3 << "\n"; // выведет 5, так как это первый элемент > 2.

auto it4 = s.upper_bound(10);
if (it4 == s.end()) {
    cout << "No element > 10\n"; // аккуратно, если разыменуете it4, получите undefined behaviour!
}

// вывод всех элементов сета с использованием итераторов; элементы следуют в порядке возрастания
for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << " ";
}
cout << "\n"; // но для таких целей лучше использовать range-based for loop!



Автор конспекта: Егор Гутров

По всем вопросам пишите в telegram @Egor_Gutrov