0:13 Начнём с самой простой программы на C++ — она выводит Hello World. Среда разработки после запуска печатает служебную строку вроде «process finished with exit code 0»: это код возврата программы. Код $0$ означает «ошибок нет»; его возвращает оператор return 0; в конце main. Если написать return 1;, код возврата будет ненулевым, и тестирующая система сообщит «ошибка выполнения» (Runtime Error), даже если весь вывод правильный. Поэтому в main всегда пишут return 0;.
7:21 Можно ли не писать return 0? В функции main — можно: если оператора return нет, считается, что вернулся ноль. Это единственное исключение: в любой другой функции, которая должна что-то вернуть, return обязателен.
'\n' или endl: буфер и flush 1:271:27 Перенести строку можно двумя способами: добавить в вывод символ '\n' или написать endl. Оба раза строка переносится, но разница между ними существенная.
'\n' — это один невидимый символ «перенос строки». Он только переносит строку.endl переносит строку и ещё принудительно говорит программе: «выведи на экран всё, что накоплено до этого». Это называется flush (сброс буфера).2:30 Дело в том, что C++ печатает не мгновенно: вывод сначала попадает в буфер — область памяти, которая нужна для ускорения ввода-вывода, — и только потом уходит из программы на экран или в файл. Буфер сбрасывается, если явно попросить (endl, flush) и когда программа завершается.
3:12 Есть и третий способ: вывести '\n', а затем отдельно flush: cout << "text" << '\n' << flush;. Можно сбросить буфер и без переноса строки — cout << "text" << flush;, но так пишут редко. Практически используют один из двух вариантов: '\n' или endl.
'\n' | endl | |
|---|---|---|
| Переносит строку | да | да |
| Сбрасывает буфер | нет | да, сразу |
| Скорость при большом выводе | быстро | заметно медленнее |
| Где применять | обычные (неинтерактивные) задачи | интерактивные задачи |
3:49 Интерактивные задачи. Это отдельный вид задач: ввод не зафиксирован заранее, а зависит от ваших действий. Классический пример — «угадай число»: специальная программа-интерактор загадала число, а вы задаёте вопросы и получаете ответы, которые подстраиваются под ваши запросы. Частая ошибка — вывести запрос с '\n': он может остаться в буфере и не дойти до интерактора, тот будет ждать, программа зависнет и получит вердикт «превышено ограничение по времени». В интерактивных задачах пишите endl.
4:53 Минус endl — он работает сильно медленнее, особенно если строк много. Поэтому правило такое: задача неинтерактивная — используйте '\n'; интерактивная — endl. При большом выводе (миллион строк) endl легко даёт превышение времени, тогда как с '\n' всё работает хорошо.
7:54 Мы уже знаем один способ ускорить вывод — писать '\n' вместо endl. Есть ещё «две магические строчки», которые ускоряют и ввод, и вывод. Их вставляют в начало main:
int main() {
ios::sync_with_stdio(false); // отвязываем потоки C++ от потоков языка C
cin.tie(nullptr); // не сбрасывать cout перед каждым чтением из cin
// ... остальная программа
}8:30 На занятии не обсуждали, как они устроены; можно считать, что они просто ускоряют ввод-вывод. Если по условию на вход приходится, например, $200\,000$ чисел и столько же надо вывести, это уже большой ввод-вывод, и эти две строчки стоит добавить. При небольшом вводе (одно число, пять чисел) они ничего не меняют, но и не вредят. Если же ввод большой, программа с ними работает быстрее.
9:32 Почему по умолчанию не сделано быстро? Люди пишут на C++ в разных сценариях и ждут от ввода-вывода разного. В обычном программировании мы хотим, чтобы всё выведенное до чтения числа гарантированно появилось на экране, пока программа ждёт ввод. Поэтому по умолчанию сделано так, как удобно для обычного программирования. В олимпиадном программировании нас не интересует, как связаны поток ввода и поток вывода, поэтому мы включаем быстрый режим сами.
sync_with_stdio(false) нельзя смешивать cin/cout с scanf/printf в одной программе — порядок данных может нарушиться. (2) В интерактивных задачах с cin.tie(nullptr) вывод перед чтением уже не сбрасывается автоматически, поэтому сброс нужно делать явно: endl или cout.flush(). Эти оговорки в записи не звучали.12:06 Иногда в задаче нужно читать числа не из консоли, а из файла (и писать результат тоже в файл). Для этого подключают библиотеку fstream. Создадим рядом с программой два файла — input.txt (запишем в него шесть чисел) и output.txt — и прочитаем числа, умножив каждое на два.
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream fin("input.txt"); // input file stream: читаем из файла
ofstream fout("output.txt"); // output file stream: пишем в файл
vector<int> a(6);
for (int i = 0; i < 6; i++) fin >> a[i]; // читаем так же, как из cin
for (int i = 0; i < 6; i++) fout << a[i] * 2 << ' ';
return 0;
}14:25 После запуска на экране ничего не появилось — но в файле output.txt лежат все числа, умноженные на два. Чтение из файла работает так же, как из cin, только вместо cin стоит имя потока (fin), а вывод — вместо cout имя потока (fout).
14:39 Имена fin и fout — просто имена переменных, их можно назвать как угодно (хоть abc), главное — одинаково использовать при объявлении и при чтении.
15:13 Про std. Всё это относится к пространству имён std. Если убрать строку using namespace std;, всё подсветится красным, и придётся везде писать std:: — std::ifstream, std::vector. На олимпиадах многие (и преподаватель) пишут using namespace std;, чтобы не мучиться.
16:01 Другие способы. Читать из файла можно и иначе (например, функциями из C), но ifstream/ofstream — самый простой и самый быстрый по сравнению с остальными, особых минусов у них нет. Если нужен другой метод, достаточно загуглить «как считать число из файла в C++».
"input.txt" без пути означает «файл с таким именем в рабочей папке программы» (в среде разработки это папка запуска проекта). Если файл не найден, чтение просто ничего не прочитает, и поток окажется в состоянии ошибки. Ещё один распространённый способ перенаправить стандартный ввод-вывод на файлы — функция freopen; в записи она не разбиралась.16:45 Бывают задачи, где количество чисел не дано заранее. В Python такое решают за одну строку: input().split(). В C++ вектор делают без фиксированного размера и читают в цикле:
vector<int> a;
int x;
while (fin >> x) { // пока удалось считать очередное число
a.push_back(x);
}17:46 Выражение fin >> x само по себе имеет значение: оно «истинно», если чтение прошло успешно, и «ложно», если числа кончились. Тело цикла выполняется, пока удаётся что-то считать. Мы дописали в файл ещё два числа, запустили — вывелись все восемь, то есть программа справилась с заранее неизвестным количеством.
18:55 То же самое работает и для обычного ввода (while (cin >> x)). В консоли это выглядит так, будто программа ждёт новых чисел бесконечно: конец ввода нужно отправить специальной комбинацией клавиш (у преподавателя в среде сработало сочетание Command+D). Для файлов понятно, где конец ввода, а в тестирующей системе, где вход тоже поступает из файла, цикл заканчивается сам. Трудности — именно особенность демонстрации в консоли.
Ctrl+D, в консоли Windows — Ctrl+Z, затем Enter. В среде разработки поведение может отличаться (как и на занятии).20:54 Как считать строку с пробелами и вывести целиком? Попробуем «очевидный» код:
string s;
cin >> s;
cout << "S = " << s;21:31 Введём Hello World. Что выведет программа? Мнения разделились, но правильный ответ — S = Hello. Причина: cin >> считывает слово до первого пробельного символа. Пробел остановил чтение, и вторая половина не считалась.
22:29 Чтобы считать строку целиком до переноса, используют getline:
string s;
getline(cin, s); // читает всю строку до '\n', вместе с пробелами
cout << "S = " << s; // S = Hello World23:03 Такие задачи встречаются редко, но встречаются. Из вопросов в чате: getline можно поставить и в условие while (преподаватель такого никогда не встречал, но проверил — работает). Аналога split из Python в C++ нет: если нужно разбить строку на части, придётся написать это самостоятельно.
getline после cin >>. Если сначала прочитать число через cin >> n, а затем вызвать getline, он сразу вернёт пустую строку: символ перевода строки после числа остался во вводе. Нужно один раз «съесть» остаток строки, например cin.ignore(); или лишний getline. Разбить строку на слова можно через stringstream: stringstream ss(s); string w; while (ss >> w) { ... }.24:45 Последняя тема про вывод — точность. Пусть double x = 3.1415926535; и мы пишем просто cout << x;. Программа выведет 3.14159: значащих цифр мало (по умолчанию шесть; на записи говорили «пять знаков после точки»). Если условие требует более точного вывода, получится неверный ответ.
25:35 Чтобы выводилось больше знаков, перед выводом пишут:
cout.precision(16); // сколько знаков выводить
cout << fixed; // фиксированная запись: precision — число цифр после точки
cout << x << '\n'; // 3.141592653500000126:04 Заметьте хвостик «…001» в конце. Он появляется из-за того, как хранятся числа с плавающей точкой (тип double): они хранятся не с абсолютной точностью, а с некоторой погрешностью, поэтому мы видим не точно то число, которое записали, а число с маленьким «хвостиком». Так устроено во всех языках программирования. Поэтому в задачах, где нужен дробный ответ, его просят не с абсолютной точностью, а с небольшой погрешностью (порядка $10^{-6}$; точное требование всегда указано в условии).
27:02 То же можно записать короче, в одну строчку: cout << fixed << setprecision(16);. Результат тот же — это просто разный способ оформления.
precision и fixed только на следующий вывод? Нет: они меняют сам поток cout, поэтому действуют на все последующие операции вывода. 27:14 Округляет ли double или обрубает? Его лучше понимать как «делает что-то непонятное»: величина погрешности зависит от размера хранимого числа (у чисел порядка миллиона она одна, у чисел около нуля другая). 29:52 Как отменить? Преподаватель не помнил способа и заметил, что обычно отменять не нужно.setprecision и отмена. Манипулятор setprecision живёт в библиотеке <iomanip>; cout.precision(16) дополнительных библиотек не требует. Отменить режим fixed можно через cout << defaultfloat;, но число знаков (precision) при этом сохраняется — его нужно вернуть отдельно, например cout.precision(6).27:59 Эту проблему с точностью вы, скорее всего, уже встречали в контесте на бинарный поиск.
30:47 Допустим, у нас есть set чисел, и мы вставили в него несколько значений:
set<int> x;
x.insert(3); x.insert(1); x.insert(2);31:17 Хотим вывести минимальное число. Мы знаем, что в set элементы лежат отсортированными по возрастанию (цикл по set печатает 1 2 3). Но как получить именно первый элемент, не проходя всё множество? Чтобы обращаться к элементам контейнера, проходиться по ним и искать их, придумали итераторы.
auto it = x.begin(); // итератор на первый элемент
cout << *it; // 1 — разыменование: значение, на которое он указывает32:01 Слово auto означает, что компилятор сам определит тип переменной — мы не указываем его явно. it — просто имя переменной. Функция x.begin() возвращает итератор на первый элемент множества, а x.end() — итератор, о котором ниже.
32:51 Итератор — это не само значение, а специальный объект. Поэтому cout << it не сработает. Чтобы получить значение, написанное «в ячейке», нужна звёздочка: *it. Это называется разыменование итератора.
begin, end и полуинтервалы 33:2533:25 Как вывести максимум множества? Хочется взять «последний» итератор: *x.end(). Запускаем — выводится 0, а не 3. Причина: x.end() указывает не на последний элемент, а на следующую позицию за последним. В C++ итераторы удобно представлять себе работающими на полуинтервалах $[\text{begin},\,\text{end})$: begin() указывает на «1», begin()+1 — на «2», begin()+2 — на «3», а begin()+3 — на «позицию после последнего»; туда же указывает end().
34:38 На предыдущий элемент указывает end() - 1, на предыдущий от него — end() - 2 и так далее. В set, однако, нельзя написать it + 2 или end() - 1 (почему — чуть ниже), зато можно сделать шаг назад операцией --:
auto it = x.end();
--it; // теперь it указывает на последний элемент
cout << *it; // 335:25 Итак, итераторы — специальные объекты, позволяющие итерироваться по элементам множества и обращаться к их значениям.
set можно получить и так: *x.rbegin() или *prev(x.end()). Если множество пусто, begin() == end(), и разыменовывать нечего — перед *it проверяйте it != x.end().35:49 Итератор можно увеличивать: ++it сдвигает его на следующий элемент. Если it указывал на begin() (то есть на «1»), после ++it он указывает на «2». Один такой шаг в set работает за $O(\log n)$, где $n$ — размер множества; обращение к первому элементу и к последнему — за $O(1)$.
36:48 Теперь можно написать цикл по всем элементам:
for (auto it = x.begin(); it != x.end(); ++it)
cout << *it << ' '; // 1 2 337:12 Такой проход занимает $O(n)$, а не $O(n\log n)$, хотя каждый шаг по отдельности оценивается как $\log$: если пройти по всем элементам, суммарно получается $O(n)$.
set хранятся в сбалансированном двоичном дереве поиска. Один шаг ++it в худшем случае поднимается или спускается по дереву на глубину $O(\log n)$, но при полном обходе каждое ребро дерева проходится не более двух раз. Поэтому сумма по всем шагам равна $O(n)$, и в среднем шаг — это $O(1)$.37:51 Раньше, на бинарном поиске, мы видели функции lower_bound и upper_bound. У set есть их аналоги — методы x.lower_bound(2) и x.upper_bound(2). Они возвращают не индекс и не значение, а итератор:
auto it = x.lower_bound(2); // итератор на первый элемент, не меньший 2
x.erase(it); // удаляет элемент, на который указывает итераторset и map нужно вызывать метод x.lower_bound(v). Общая функция lower_bound(x.begin(), x.end(), v) на них работает за линейное время, потому что итераторы set нельзя сдвинуть сразу на много позиций (см. следующий пункт).39:14 Итераторы есть не только у set, но и у любых контейнеров: map, vector, unordered_set и других. У вектора тоже есть v.begin() и v.end(); если вектор пуст, они равны.
40:03 Но есть важное различие. У итераторов вектора можно выполнять арифметику: прибавлять и вычитать числа, вычитать один итератор из другого. Всё это работает за $O(1)$:
auto it = v.begin();
it = it + 3; // сдвиг сразу на 3 вперёд
int len = v.end() - v.begin(); // разность итераторов — число: размер вектора40:42 В set и map так нельзя: там итератор можно сдвигать лишь на один шаг операциями ++ и --. С итераторами вектора вы уже сталкивались на бинарном поиске:
int idx = lower_bound(v.begin(), v.end(), 0) - v.begin(); // индекс первого элемента ≥ 041:07 Функция возвращает итератор, и чтобы понять индекс в векторе, мы вычитали из него v.begin(). Это просто разность двух итераторов — расстояние между элементами вектора.
41:42 Чтобы сдвинуть итератор set на несколько позиций, нужно либо писать цикл, либо вызвать функцию advance(it, k) — но она всё равно делает ++ ровно $k$ раз. Если написать так для переменной $k$, это будет работать долго (преподаватель называл оценку $k\log n$): при большом $k$ и многих сдвигах — это медленно. В векторе же можно просто написать v.begin() + 100, и это $O(1)$, потому что у вектора есть индексы.
advance в set. Формально $k$ шагов ++ стоят $O(k\log n)$ в худшем случае; при подряд идущих шагах реальная стоимость ближе к $O(k)$. В любом случае стоимость растёт с $k$, а не постоянна, как у вектора.lower_bound, sort и другие: они работают не с самим вектором, а с итераторами. 44:12 Что делает advance? Сдвигает переданный итератор на указанное число шагов (ровно столько раз делает ++). 44:24 Что такое set? Контейнер, хранящий элементы в отсортированном порядке по возрастанию, причём каждый элемент в одном экземпляре: если вставить число несколько раз, оно будет лежать только один раз.sort и полуинтервал 45:0045:09 Заведём вектор и положим в него числа от 1 до 5 в некотором порядке: 5 2 1 4 3. Чтобы отсортировать, вспоминаем:
sort(a.begin(), a.end()); // 1 2 3 4 546:12 Видно, что sort принимает именно итераторы. Вместо a.end() можно писать a.begin() + a.size() — это буквально тот же итератор.
46:35 Хотим отсортировать только первые три элемента, остальные оставив на местах:
sort(a.begin(), a.begin() + 3); // 1 2 5 4 3 — отсортированы только первые три
sort(a.begin(), a.begin() + 4); // сортируется ровно полуинтервал [begin, begin+4)47:10 То есть sort сортирует тот полуинтервал, который ему передали; остальные элементы он не трогает.
47:21 Итераторы из разных контейнеров. Передавать в sort begin() одного вектора и конец другого нельзя: в лучшем случае программа упадёт, в худшем — сделает что попало. Любые действия с итераторами (сравнение, вычитание, сложение, передача в функцию) допустимы только если они из одного контейнера. На записи такой вызов завершился ошибкой выполнения (код выхода 138).
49:09 Как отсортировать массив в порядке убывания? Для этого есть обратные итераторы rbegin() и rend(): они указывают на элементы в обратном порядке. Если отсортировать «в обратном порядке», получим массив по убыванию:
sort(a.rbegin(), a.rend()); // 5 4 3 2 149:52 Как соотносятся rbegin, rend и begin, end. rbegin() указывает на тот же элемент, что end() - 1 (последний), а rend() — на позицию перед первым элементом. Сложение с обратными итераторами работает так же, как с обычными: например, у массива из пяти элементов a.rbegin() + 5 == a.rend(), но «двигаются» они справа налево.
50:16 Напрямую сравнивать прямые итераторы с обратными не нужно. Если вы работаете с rbegin/rend, воспринимайте их как обычные итераторы, просто идущие в обратном порядке.
51:09 Представим задачу: отсортировать числа так, чтобы сначала шли все чётные по возрастанию, а потом все нечётные по возрастанию. Для этого пишут свой компаратор — функцию, которая отвечает на вопрос: «правда ли, что число $a$ должно стоять раньше, чем число $b$?» Её передают в sort третьим аргументом — именем, без скобок (cmp, а не cmp()).
bool cmp(int a, int b) {
if (a % 2 != b % 2) // разной чётности:
return a % 2 == 0; // раньше стоит чётное
return a < b; // одной чётности: по возрастанию
}
sort(a.begin(), a.end(), cmp); // из 5 2 1 4 3 получится 2 4 1 3 553:09 Если в векторе не числа, а, например, пары, можно написать компаратор для них. Это даже более мощная вещь, чем параметр key в Python: можно сравнивать объекты любым способом.
53:45 Строгость сравнения. В компараторе нужно проверять именно строгое «меньше» (a < b), а не «меньше или равно». Если при равенстве возвращать true, то для пары равных элементов окажутся истинными одновременно cmp(a, b) и cmp(b, a). Такого быть не должно — иначе всё сломается (программа может вести себя непредсказуемо или упасть).
sort + unique 54:2554:31 Пусть в векторе есть несколько одинаковых элементов, например две двойки: 5 2 1 4 3 2. Иногда нужно оставить только различные значения. Для этого есть функция unique: она удаляет подряд идущие равные элементы. Значит, сначала нужно отсортировать вектор, чтобы все одинаковые элементы встали рядом:
sort(a.begin(), a.end()); // 1 2 2 3 4 5
a.resize(unique(a.begin(), a.end()) - a.begin()); // 1 2 3 4 555:22 Разберём второй строкой: unique(a.begin(), a.end()) принимает два итератора, проходит по всему массиву, убирает подряд идущие повторы и возвращает итератор на новый конец массива. Вычитая из него a.begin(), получаем новый размер, и resize уменьшает вектор до такого размера.
57:03 Вопросы из чата. Что делает resize? Уменьшает вектор до переданного размера. Зачем сначала sort? После сортировки все равные элементы идут подряд — это свойство сортировки; unique убирает только соседей. Без сортировки в массиве 5 2 1 4 3 2 ничего не удалится: двойки не стоят рядом. 56:26 Можно ли обойтись без unique? Конечно, можно написать свою функцию, но две строки sort и unique писать намного быстрее, чем делать это руками.
1:00:03 Асимптотика: sort — $O(n\log n)$, unique — $O(n)$.
unique «переносит двойку в конец». Это упрощённая картинка: на самом деле элементы, которые оказались после возвращённого итератора, имеют неопределённые значения (в нашей проверке для 1 2 2 3 3 4 после unique массив стал 1 2 3 4 3 4, а возвращённая позиция — 4). Поэтому хвост нужно обязательно отрезать — resize или a.erase(unique(a.begin(), a.end()), a.end()).lower_bound и upper_bound 1:00:321:00:32 Вспомним задачу «найти количество чисел, равных $x$». Если массив отсортирован, достаточно двух итераторов: первый — lower_bound от $x$ (первый элемент, не меньший $x$), второй — upper_bound (первый элемент, больший $x$). Все числа, равные $x$, лежат между ними, поэтому их количество — это разность итераторов.
sort(a.begin(), a.end()); // 1 2 2 3 4 5
auto l = lower_bound(a.begin(), a.end(), 2); // указывает на первую двойку
auto r = upper_bound(a.begin(), a.end(), 2); // указывает на тройку
cout << r - l << '\n'; // 21:01:56 Самое важное, что нужно понять про итераторы вектора: с ними можно работать как с числами — складывать, прибавлять к ним числа, брать разность (она — число). Разность итераторов вычисляется за $O(1)$, а сам поиск — за $O(\log n)$.
1:02:43 Почему вычитание a.begin() даёт правильный размер? Потому что unique возвращает такой итератор, что при вычитании из него begin() получается размер нового массива. Это просто то, что возвращает функция.
1:03:14 Отдельную внешнюю функцию-компаратор писать не всегда удобно, поэтому можно воспользоваться лямбда-функцией. Синтаксис такой: квадратные скобки, в круглых — параметры, в фигурных — тело.
sort(a.begin(), a.end(), [](int a, int b) {
if (a % 2 != b % 2) return a % 2 == 0;
return a < b;
});1:05:09 Если внутри лямбды нужна внешняя переменная, в квадратные скобки пишут амперсанд — [&]; тогда внутри функции видны все внешние переменные. Пример: сортировка чисел по остатку от деления на $x$:
int x = 2;
sort(a.begin(), a.end(), [&](int a, int b) {
return a % x < b % x; // сравниваем только по остатку
});1:05:45 Числа отсортировались по модулю два: сначала сравнимые с нулём, затем с единицей. Обратите внимание: числа 2, 4, 2 идут в произвольном порядке, и этот порядок никак не гарантирован, потому что с точки зрения компаратора они одинаковые — могут стоять как угодно.
stable_sort — он сохраняет относительный порядок равных элементов (с теми же параметрами, что и sort).1:06:35 Пусть теперь у нас не вектор чисел, а вектор векторов — vector<vector<int>> — и мы пишем компаратор для него. Если параметры объявить как vector<int> a, vector<int> b, то при каждом вызове компаратора вектор будет копироваться. Чтобы этого не было, векторы передают по константной ссылке: const тип& имя.
sort(v.begin(), v.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0]; // сравниваем первые элементы
});1:07:35 С числами тоже можно написать const int&, но в этом нет смысла: int копируется быстро, а вот вектор может быть большим, и его копирование будет очень долгим. Слово const значит, что менять объект внутри нельзя: например, a[0] = 1; не скомпилируется.
1:08:55 Хотим завести свой тип — например, дату. Дата — это день, месяц и год. Тип объявляют ключевым словом struct, внутри перечисляют поля:
struct Date {
int day, mon, year;
};
vector<Date> dates;
dates.push_back({1, 1, 2000}); // в фигурных скобках — поля в порядке объявления
dates.push_back({2, 1, 2010});1:10:33 Теперь хотим отсортировать этот вектор: sort(dates.begin(), dates.end());. Такая запись не скомпилируется (подсветится красным): C++ по умолчанию не знает, как сравнивать наши типы. Чтобы всё заработало, внутри структуры нужно описать оператор сравнения:
struct Date {
int day, mon, year;
bool operator<(const Date& other) const {
if (year != other.year) return year < other.year;
if (mon != other.mon) return mon < other.mon;
if (day != other.day) return day < other.day;
return false; // даты равны, значит «не меньше»
}
};1:11:09 Расшифруем запись. Функция называется operator< — это специальное имя. Она возвращает bool: правда ли, что эта дата меньше другой. Другая дата передаётся как const Date& other: амперсанд означает, что дата не копируется, а передаётся тот экземпляр, который уже лежит в векторе; а const после скобок значит, что функция не изменяет саму дату. В теле: сначала сравниваем годы; если равны — месяцы; если и месяцы равны — дни; если всё совпало, то эта дата не меньше другой — возвращаем false.
1:13:12 Теперь ошибка пропала. Выведем даты циклом for (const Date& d : dates) — первая дата идёт раньше второй; если поменять местами порядок push_back, даты всё равно выведутся в нужном (отсортированном) порядке.
1:13:48 Вопрос из чата: можно ли записывать так — Date d = {1, 1, 2000};? Можно. Способов много: с равно, без равно, с именами полей (.day = …, .mon = …, .year = …); чтобы разобрать все способы инициализации структур, нужно глубже погружаться в C++, и этим сегодня не занимались.
return tie(year, mon, day) < tie(other.year, other.mon, other.day); — tie собирает значения в кортеж, а кортежи сравниваются лексикографически, как и нужно датам.int и переполнение 1:15:091:15:09 Вспомним, какие бывают типы. Тип int хранит целые числа в диапазоне примерно от $-2\cdot10^{9}$ до $2\cdot10^{9}$ (точнее, от $-2^{31}$ до $2^{31}-1$); это можно найти в шпаргалке. Что делать, если нужно перемножить два int? Заведём int c = a * b; и введём 1 2 — выведется $2$. Теперь введём $10^6$ и $10^6$: результат $10^{12}$, но выведется отрицательное число.
1:16:31 Так быть не должно, но мы столкнулись с переполнением. Оно возникает, когда результат операции не помещается в тип. Число $10^6\cdot10^6=10^{12}$ лежит за пределами диапазона int, поэтому получается «мусор».
long long и большие числа 1:17:011:17:08 Числа больше, чем помещаются в int, нужны часто, поэтому есть тип int64_t — целые числа примерно от $-9\cdot10^{18}$ до $9\cdot10^{18}$ (на записи преподаватель поправил себя: не $2\cdot10^{18}$, а $9\cdot10^{18}$). Заменим тип на int64_t — теперь вывелось правильное число $10^{12}$.
1:17:57 Многие вместо int64_t пишут long long — это то же самое. Если нужно хранить ещё большие числа, нужно придумывать что-то отдельное, но по опыту преподавателя такое почти никогда не встречается: числа почти всегда помещаются в 64-битный тип.
long и long long. На записи звучит «long», но имеется в виду именно long long. Одиночный long зависит от системы: на Windows он 32-битный, на Linux 64-битный (в нашей проверке на Linux sizeof(long) = 8), поэтому для надёжности пишут long long или int64_t.1:18:46 Есть ещё __int128: его нельзя вводить и выводить напрямую (cin и cout с ним не работают), но для промежуточных вычислений он годится, если поддерживается вашей системой. Встроенной поддержки сколь угодно больших чисел в C++ нет.
1:19:14 Что будет, если несколько раз умножить и вызвать переполнение — результат будет одинаковым? Переполнение знаковых чисел в C++ — это неопределённое поведение (undefined behavior, UB). С ним вы уже встречались: например, когда выходите за границы массива, ошибка не обязательно возникает — может вывестись какой-то мусор. С переполнением то же самое.
1:19:40 На одном и том же компьютере результат, скорее всего, будет одинаковым, но никто этого не гарантирует. Поэтому нельзя писать код, рассчитывая на то, что переполнение произойдёт определённым образом. И нельзя использовать UB как генератор случайных чисел — это будет мусор, причём одинаковый.
1:20:39 Покажем выход за границу: цикл по индексам вектора, которых нет. На маленьких значениях что-то выводится, но если выводить $10^4$, $10^6$, $10^7$ чисел — программа рано или поздно упадёт с ошибкой сегментации. Результат сильно зависит от системы и от того, как выделяется память.
1:22:06 Если нужен рандомайзер, для этого есть специальные средства — не используйте UB как генератор случайных чисел.
<random>, например mt19937 rng(seed);. Для беззнаковых типов (unsigned) переполнение, напротив, определено: счёт идёт по модулю $2^{32}$ (или $2^{64}$).set, multiset, map, unordered_* 1:22:28set: основные операции 1:22:371:22:45 С set чисел мы уже работали. Теперь можно сделать и set<Date>: это возможно, потому что у нас определён оператор сравнения. Если его удалить, x.insert(...) подсветится красным — нет операции сравнения. Если вернуть, всё заработает. Вывод: если вы определили operator< для своей структуры, её можно класть в set.
1:23:45 Повторим, что можно делать с множеством чисел:
x.insert(v) — вставка за $O(\log n)$.x.erase(v) — удаление значения, тоже за $O(\log n)$. Если такого элемента нет, ничего не произойдёт — ничего страшного.x.begin(), x.end(), итераторы — о них говорили выше.x.find(v) — итератор на элемент $v$. Если элемента нет, возвращается x.end(), а разыменование такого итератора — ошибка выполнения (на записи find от шестёрки дал ошибку).x.lower_bound(v), x.upper_bound(v) — итераторы-границы. Чтобы вывести элемент, следующий за троечкой, можно воспользоваться upper_bound(3) — он возвращает первый элемент, больший трёх.x.contains(v) — возвращает bool; x.count(v) — число (в set оно либо $0$, либо $1$); x.size() — размер; все эти операции — $O(\log n)$ (кроме size — $O(1)$).1:25:37 Все элементы множества выводятся циклом for (int v : x) cout << v << ' ';.
contains появился в C++20; в более ранних стандартах пишут x.count(v) или x.find(v) != x.end().1:26:08 Допустим, нужно удалить из множества все нечётные числа. Хочется написать так: пройти циклом по x и для нечётного i вызвать x.erase(i). Делать так строго нельзя: если идти по множеству циклом с двоеточием (for (int i : x)), множество в это время нельзя изменять — вы, скорее всего, получите ошибку выполнения.
1:27:00 Вместо этого пишут явный итератор и сами решают, когда его двигать:
for (auto it = x.begin(); it != x.end(); ) { // в заголовке цикла итератор не увеличиваем
if (*it % 2 == 0) {
++it; // чётное оставляем — идём дальше
} else {
it = x.erase(it); // нечётное удаляем; erase возвращает следующий элемент
}
}1:27:52 erase от итератора возвращает итератор на элемент после удалённого, и мы присваиваем его it. Так можно корректно удалять элементы во время обхода.
1:28:34 Вопрос из чата: чем ++it отличается от it++? С точки зрения увеличения итератора ничем, так же как для чисел; они различаются только возвращаемым значением: ++it возвращает уже увеличенное значение, а it++ — прежнее. Если запись стоит отдельной командой, разницы нет.
set 1:29:211:29:21 Представим, что вставили числа от 1 до 6 и хотим, чтобы сначала шли чётные, потом нечётные. Тогда пишем компаратор как лямбду, называем её f и указываем её тип вторым параметром шаблона:
auto f = [](int a, int b) {
if (a % 2 != b % 2) return a % 2 == 0;
return a < b;
};
set<int, decltype(f)> x(f); // множество упорядочено по f
for (int i = 1; i <= 6; i++) x.insert(i);
for (int v : x) cout << v << ' '; // 2 4 6 1 3 51:30:45 Вот так можно передать в set свой компаратор не только для собственной структуры, но и для обычных типов вроде int. decltype — способ получить тип лямбды, чтобы передать его в set; в олимпиадном программировании он почти нигде не используется, кроме таких случаев, когда нужно что-то передать в set.
x(f) в C++17. В записи показан только тип, но в стандарте C++17 лямбду нужно ещё и передать конструктору: set<int, decltype(f)> x(f);. Без (f) компилятор C++17 выдаёт ошибку (мы проверили: «use of deleted function»); начиная с C++20 лямбда без захвата создаётся сама, и достаточно set<int, decltype(f)> x;.multiset 1:33:081:33:08 В set каждое значение хранится либо 0, либо 1 раз: повторный insert просто ничего не добавляет. Но иногда нужно хранить несколько экземпляров. Для этого есть multiset: если вставить каждое число два раза, в нём сохранится по два экземпляра.
1:33:56 Как удалять элементы из multiset. x.erase(3) удаляет все вхождения тройки. Чтобы удалить ровно одно вхождение, пишут x.extract(3): удалится только одна троечка, вторая останется. Если такого числа нет (x.extract(7)), ничего не изменится.
1:34:42 Со всем остальным multiset работает так же, как set, и с такой же асимптотикой (lower_bound, upper_bound и другие операции). Но count в multiset работает за $O(\log n + k)$, где $k$ — количество элементов с этим значением: он находит первое число и затем идёт вперёд, пока значения совпадают. Поэтому count в multiset лучше не использовать. Если нужно подсчитывать количества, лучше воспользоваться map.
multiset<int> m = {1,1,2,2,3,3} мы проверили: m.erase(m.find(3)) оставляет одну тройку, m.erase(2) убирает обе двойки, m.extract(1) убирает одну единицу и возвращает непустой «узел», а extract(7) (нет такого числа) возвращает пустой узел и ничего не меняет. Эквивалент для старых стандартов — m.erase(m.find(v)) (но только если find нашёл элемент).map 1:35:511:35:51 map — это просто словарь. Нужно подключить <map> (или <bits/stdc++.h>). В угловых скобках пишут тип ключа и тип значения:
map<string, int> mp;
mp["amongus"] = 1;
mp["hello"] = 2;
mp["xabc"] = 0;
for (auto [key, value] : mp) // key — ключ, value — значение
cout << key << " -> " << value << '\n';1:36:55 Вывод получится amongus -> 1, hello -> 2, xabc -> 0: всё отсортировано по ключу (строка xabc оказалась последней, amongus первой, hello второй).
1:37:34 Что можно делать:
mp.contains("hello") — есть ли такой ключ (вернётся 1, если есть; в старых стандартах пишут mp.count(key)).mp.erase("xabc") — удаляет ключ и возвращает, сколько элементов удалено (при повторном вызове — 0), а в выводе удалённого элемента уже нет.mp.lower_bound(a) — первый элемент, у которого ключ не меньше $a$. Все операции — erase, lower_bound, upper_bound — работают по ключу, а не по значению. Итераторы (begin, end и т.д.) работают так же, как у set.1:39:32 В обычной map все операции — вставка, обращение к элементу, проверка наличия, lower_bound — работают за $O(\log n)$; обход — за $O(n)$.
mp[key] создаёт элемент. Если ключа в словаре не было, обращение mp[key] добавляет его со значением по умолчанию (для int — 0) и увеличивает размер. Чтобы только проверить наличие ключа, используйте contains, count или find (в нашей проверке mp["new"] дало 0 и размер вырос с 2 до 3).unordered_map и unordered_set 1:39:171:39:17 Есть ещё два типа, про которые неоднократно спрашивали: unordered_map и unordered_set. Мы только что сказали, что в map элементы лежат в отсортированном порядке, но это свойство нужно не всегда: иногда достаточно быстро обращаться по ключу. Для этого и есть unordered_map — он умеет делать то же, что обычная map, но не умеет делать lower_bound. Зато в нём вставка, обращение, удаление и проверка наличия работают за $O(1)$ (в среднем).
1:40:33 Но элементы в нём не отсортированы: порядок произвольный и может зависеть от версии компилятора, операционной системы и так далее. Внутри используется хеш-таблица. Это аналог dict в Python — там словарь тоже не отсортирован по ключу.
1:41:19 По аналогии есть unordered_set. Нужны #include <unordered_set> и #include <unordered_map>. Вставили числа 1, 10, 3, 1000 — вывелись они в каком-то произвольном порядке. Преимущество перед set — операции за $O(1)$ вместо $O(\log n)$. Но если нужны lower_bound/upper_bound или чтобы числа лежали отсортированными, нужен обычный set. Если же нужна более быстрая вставка и удаление — unordered_set.
unordered_*. Если сомневаетесь — берите map/set.| Контейнер | Что хранит | Порядок | insert / erase / поиск | lower_bound |
|---|---|---|---|---|
set | уникальные значения | по возрастанию | $O(\log n)$ | есть, $O(\log n)$ |
multiset | значения с повторами | по возрастанию | $O(\log n)$; count — $O(\log n + k)$ | есть, $O(\log n)$ |
map | пары «ключ — значение» | по ключу | $O(\log n)$ | есть, по ключу |
unordered_set / unordered_map | уникальные значения / пары | произвольный | $O(1)$ в среднем | нет |
Эта таблица — собранный по записи итог: она показывает выбор контейнера по задаче («нужна сортировка или lower_bound» — set/map; «нужны только быстрые вставка, удаление и поиск» — unordered_*; «нужны повторы» — multiset, а для подсчёта количеств — map).
1:43:51 Вспомним: если завести вектор из трёх чисел и вывести v[4], программа выведет что угодно (у преподавателя — ноль): мы вышли за границы массива, и это никак не отловилось. Чтобы ловить такие ошибки, в самом начале программы до всех #include можно написать:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
cout << v[4] << endl; // теперь это завершится понятной ошибкой
}1:45:04 Этот #define работает, если у вас компилятор GCC (g++) или MinGW — а он может стоять, например, если вы поставили Code::Blocks со встроенным компилятором. Тогда при запуске появится сообщение об ошибке: на занятии показали «attempt to subscript container … out-of-bounds index … container only holds 3 elements». Сообщение большое, но смысл не в нём, а в том, что при отладке такие проблемы легче находить.
1:46:13 Преподаватель сначала написал имя с двумя подчёркиваниями — и у него ничего не заработало; правильно писать с одним подчёркиванием в начале, как выше.
1:47:09 Обратная сторона: эта проверка очень сильно замедляет программу, потому что при каждом обращении выполняется проверка границ. Поэтому, когда вы отправляете код в тестирующую систему, этот #define нужно убирать — иначе вы, скорее всего, получите превышение времени (TL).
while (fin >> x) на строковом потоке читает все числа; sort + unique + resize даёт 1 2 3 4 5; r - l для двойки в 1 2 2 3 4 5 равно 2; компаратор «чётные, потом нечётные» даёт 2 4 1 3 5, а set с тем же компаратором — 2 4 6 1 3 5; sort(a.rbegin(), a.rend()) даёт 5 4 3 2 1; удаление нечётных во время обхода оставляет 2 4 6; sizeof(long long) = 8, 10^6 · 10^6 в long long равно 10^12; cout << fixed << setprecision(16) выводит 3.1415926535000001; с #define _GLIBCXX_DEBUG выход за границы вектора даёт сообщение об ошибке.1:47:49 Лекция на этом закончена: после перерыва у вас будет решение контеста, а вопросы по занятию можно задавать в чате или в Telegram.
'\n' быстрее и годится для обычных задач, endl нужен в интерактивных; sync_with_stdio(false) и cin.tie(nullptr) ускоряют большой ввод-вывод; файлы читают через ifstream/ofstream; while (cin >> x) читает неизвестное число значений, getline — строку с пробелами; для точного вывода — precision и fixed.end() указывает за последний элемент; у вектора можно складывать и вычитать, у set и map — только ++ и --.sort работает с полуинтервалом итераторов; свой порядок задаёт компаратор со строгим «меньше»; для удаления повторов — sort + unique + resize.int переполняется на $\approx 2\cdot10^9$, поэтому для больших чисел — long long; переполнение и выход за границы — неопределённое поведение.set/multiset/map — сортированные, операции за $O(\log n)$; unordered_* — без порядка и без lower_bound, но за $O(1)$ в среднем.