Множества - Язык программирования C++ для спортивного программирования
Неделя 11Множества, Словари, Мультимножества и Обработка данных по ключу
Множества
Множество хранит каждое значение один раз и по порядку: insert, size и обход по порядку, count и find, erase, ближайшие значения через lower_bound и upper_bound и множество позиций для каждой буквы.
Теория
Урок 1 из 7
19 мин чтения
Вопросов: 6
Вектор помнит всё: каждое значение, в том порядке, в каком оно пришло, вместе с
повторами. Часто задаче нужно меньше — зато быстро. Какие значения уже
встречались? Есть ли среди них вот это? Искать в векторе из 200 000 значений
ответ на каждый из 200 000 вопросов — это 40 миллиардов шагов. Множество
(set) отвечает на каждый вопрос примерно за 18.
Множество хранит каждое значение один раз и по порядку
Множество соблюдает два правила и следит за ними само:
Без повторов. Вставка значения, которое уже есть, ничего не меняет.
Всегда по порядку. Значения хранятся по возрастанию, в каком бы порядке
они ни приходили. Вызывать sort не нужно никогда.
s.size() — сколько значений в множестве, поэтому после вставки всех значений
это количество различных значений. s.empty() говорит, пусто ли множество.
Пройдите по шести вставкам и посмотрите, куда попадает каждое значение:
Множество хранит каждое значение один раз и по порядку
Цикл for по множеству проходит значения от меньшего к большему — это тот же
цикл, что и для вектора. Больше этой задаче ничего не нужно:
В первой строке n, во второй — n целых чисел. Выведите, сколько среди них
различных значений, а затем сами эти значения по возрастанию.
Для ввода 7 и 50 20 50 40 20 10 50 программа печатает
Четыре различных значения, уже отсортированные, и никаких повторов, которые
надо пропускать. set<string> работает так же и держит слова в словарном
порядке — том, который даёт < для строк, символ за символом.
Есть ли оно там? count и find
Есть два способа спросить, лежит ли x в множестве, ничего в нём не меняя:
s.count(x) равно 1, если x есть, и 0, если нет: двух копий в
множестве не бывает, так что других ответов быть не может.
s.find(x) даёт позициюx в множестве — итератор. Чтобы прочитать
значение в этой позиции, пишут *it. Если x нет, find возвращает
s.end() — позицию сразу за последним значением, которая означает «не
найдено».
Чаще всего хватает count, как в этой задаче:
В первой строке n, во второй — n имён из списка гостей. Затем идут q и
q имён людей у входа. Для каждого из них выведите YES, если имя есть в
списке, и NO, если нет.
Сложите список в множество один раз — и тогда каждый человек у входа — это
один вызов count:
Если в списке zara ali tim bek, а у входа стоят bek dana ali, программа
печатает YES, NO, YES.
Удаление значения: erase
s.erase(x) удаляет x из множества. Если x там нет, ничего не происходит —
и ошибки тоже нет.
У множества нет индексов: s[0] не компилируется. Наименьшее значение —
*s.begin(), значение в первой позиции, а наибольшее — *s.rbegin(), первая
позиция, если считать с конца. И то и другое можно писать только для непустого
множества.
Ближайшие значения: lower_bound и upper_bound
Раз множество отсортировано, оно так же быстро отвечает на вопрос «какое
значение ближе всего к x?»:
s.lower_bound(x) — первое значение ≥ x;
s.upper_bound(x) — первое значение > x.
Обе возвращают позицию, а если такого значения нет — s.end(). Для
s = {10, 20, 30, 40, 50}:
x
*s.lower_bound(x)
*s.upper_bound(x)
25
30
30
30
30
40
5
10
10
50
50
end() — значений > 50 нет
Вот задача, где нужно ближайшее значение с обеих сторон:
Вдоль дороги стоят n автобусных остановок, каждая на целом расстоянии от
начала дороги. Для каждой из q точек x выведите следующую остановку —
первую в точке x или после неё — и предыдущую — последнюю в точке x или
до неё. Если такой остановки нет, выведите -.
Следующая остановка — это lower_bound(x). Предыдущая — наибольшее значение
≤ x, и готовой функции для него нет. Возьмите upper_bound(x) — первую
остановку после x — и отступите на одну позицию назад: it--. Ошибиться
можно только в одном: если upper_bound уже указывает на самую первую
позицию, то перед ней ничего нет.
Для остановок 40 10 30 50 20 и вопросов 25 50 5 программа печатает
Пишите s.lower_bound(x), а не lower_bound(s.begin(), s.end(), x). Второй
вариант тоже компилируется, но проходит по множеству по одному значению — так
же медленно, как поиск в векторе.
Теперь всё вместе. Гости приходят в клуб, вход в который охраняет множество:
Охранник множествапопробуй!
По множеству на каждую букву
Множество не обязано хранить сами значения — оно может хранить, где они
стоят. Возьмём такую задачу:
В первой строке — строка из строчных латинских букв, во второй — q. В
каждой из следующих q строк — отрезок l r, позиции считаются с 1. Для
каждого отрезка выведите различные буквы между позициями l и r в
алфавитном порядке.
Проходить по каждой позиции длинного отрезка снова и снова — медленно. Вместо
этого заведите по множеству позиций для каждой буквы. Тогда один
lower_bound на букву отвечает на вопрос «встречается ли эта буква между l и
r?»: её первая позиция, начиная с l, должна существовать и быть не больше
r.
Для mississippi и отрезков 1 4 и 5 11 программа печатает ims и ips.
vector<set<int>> pos(26) — это 26 пустых множеств, по одному на букву, а
s[i] - 'a' выбирает нужное, как на неделе 5.
В некоторых задачах строка ещё и меняется. Если буква на позиции p
становится буквой c, переложите p из множества старой буквы в множество
новой:
Сколько это стоит
Множество хранит значения в сбалансированном дереве, поэтому insert, erase,
count, find, lower_bound и upper_bound занимают примерно log₂ n
шагов каждая — 18 для 200 000 значений. Обход всего множества — n шагов.
vector<int>
set<int>
Повторы
хранятся
отбрасываются
Порядок
как вставляли
всегда по возрастанию
a[i]
один шаг
недоступно
Есть ли x?
просмотреть всё: n шагов
count / find: около log₂ n
Ближайшее к x значение
сначала сортировка, потом поиск
lower_bound / upper_bound: около log₂ n
Добавить или удалить значение
в конце — один шаг, в середине — до n
около log₂ n, в любом месте
Проверьте себя
А вы знали?
Английское слово set когда-то было словом с наибольшим числом значений. В
издании Оксфордского словаря английского языка 1989 года его статья содержала
около 430 значений и занимала примерно 60 000 слов. Программистский смысл —
набор без повторов — пришёл из математики, где Георг Кантор в 1870-х годах
положил множества в основу своей работы.
set<int> s; // пустое множество чисел ints.insert(40);s.insert(10);s.insert(40); // 40 уже есть: ничего не происходитs.insert(25); // теперь s — это {10, 25, 40}cout << s.size(); // 3
проверь себя1 балл
Для пустого множества set<int> s выполняют s.insert(5); s.insert(3); s.insert(5); s.insert(1); s.insert(3);. Чему равно s.size()?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Если s.insert(7) выполнить для set<int> s дважды, s.count(7) будет равно 2.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
s — множество {10, 20, 30, 40}. Чему равны *s.lower_bound(20) и *s.upper_bound(20)?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
s — множество {10, 20, 30, 40}. Что напечатает этот код?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает программа?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Как получить наименьшее значение непустого set<int> s?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
4
10 20 40 50
30 20
50 50
10 -
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; set<int> s; for(int i = 0; i < n; i++){ int x; cin >> x; s.insert(x); // значение, которое уже есть, второй раз не добавляется} cout << s.size()<< "\n"; // сколько различных значений for(int x : s){ // от меньшего к большему cout << x << " ";} cout << "\n"; return 0;}
auto it = s.find(25); // auto: пусть компилятор сам выведет типif(it != s.end()){ cout << *it << " is here";}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; set<string> invited; for(int i = 0; i < n; i++){ string name; cin >> name; invited.insert(name);} int q; cin >> q; for(int i = 0; i < q; i++){ string name; cin >> name; if(invited.count(name)){ // 1, если имя есть в множестве, иначе 0 cout << "YES"<< "\n";} else{ cout << "NO"<< "\n";}} return 0;}
set<int> s ={10, 25, 40};s.erase(25); // {10, 40}s.erase(99); // такого нет: по-прежнему {10, 40}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; set<int> stops; // где вдоль дороги стоят остановки for(int i = 0; i < n; i++){ int x; cin >> x; stops.insert(x);} int q; cin >> q; for(int i = 0; i < q; i++){ int x; cin >> x; auto it = stops.lower_bound(x); // первая остановка не раньше x if(it == stops.end()){ cout << "-"; // все остановки раньше x} else{ cout << *it;} cout << " "; it = stops.upper_bound(x); // первая остановка после x if(it == stops.begin()){ cout << "-"; // это самая первая остановка: не позже x остановок нет} else{ it--; // шаг назад: последняя остановка не позже x cout << *it;} cout << "\n";} return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; vector<set<int>> pos(26); // pos[0]: где стоят буквы a, pos[1]: буквы b, ... for(int i = 0; i <(int)s.size(); i++){ pos[s[i] - 'a'].insert(i + 1); // позиции считаются с 1} int q; cin >> q; for(int i = 0; i < q; i++){ int l, r; cin >> l >> r; for(int c = 0; c < 26; c++){ auto it = pos[c].lower_bound(l); // первая позиция этой буквы начиная с l if(it != pos[c].end() && *it <= r){ cout <<(char)('a' + c); // она внутри [l, r]}} cout << "\n";} return 0;}
pos[s[p - 1] - 'a'].erase(p); // старая буква уходит с позиции ps[p - 1] = c;pos[c - 'a'].insert(p); // приходит новая буква
auto it = s.upper_bound(35);it--;cout << *it;
set<int> s ={30, 10, 20, 10};for(int x : s){ cout << x << " ";}