Set: различия между версиями
м (added tags) |
м |
||
Строка 9: | Строка 9: | ||
Чтобы найти наименьший элемент, строго больший заданному, есть функция <code>upper_bound</code>. | Чтобы найти наименьший элемент, строго больший заданному, есть функция <code>upper_bound</code>. | ||
Каждая из этих функций возвращает итератор на искомый элемент или <code>end()</code>, если такого элемента не существует. | Каждая из этих функций возвращает итератор на искомый элемент или <code>end()</code>, если такого элемента не существует. | ||
− | <code>set</code> может содержать только элементы тех типов, для которых определён оператор <, поскольку ему важен порядок элементов. | + | <code>set</code> может содержать только элементы тех типов, для которых определён оператор <code><</code>, поскольку ему важен порядок элементов. |
Рассмотрим пример простейших операций с <code>set</code>. | Рассмотрим пример простейших операций с <code>set</code>. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> |
Версия 11:40, 28 сентября 2019
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