C++

Вместо того, чтобы подключать каждый #include по-отдельности, можно один раз подключить bits/stdc++.h

Ускорение ввода/вывода

В задачах, где много вывода, можно получить TL только из-за того, что ввод (или вывод) занимает очень много времени. Его можно значительно ускорить, написав буквально несколько строк. Не будем вдаваться в подробности, почему это ускоряет, но ничего не мешает писать это в начале main() в каждой программе. Единственное ограничение - вы не сможете использовать cin/cout одновременно с scanf/printf.

Еще можно ускорить вывод, если избежать лишних вызовов flush(). Дело в том, что когда вы выводите что-либо, сначала вывод складывается в буффер, и, только когда в нем набирается достаточно данных, они выводятся на экран (или же в файл). Так сделано, потому что операция вывода на самом деле довольно долгая, а вот положить данные в буффер не стоит почти ничего. Но иногда хочется сразу получить вывод, а не ждать, пока буффер заполнится. Для этого придумали функци cout.flush(). Если вызывать ее неоправданно часто (а в НЕ интерактивных задачах всегда можно подождать, пока буффер заполнится), программа начнет работать ощутимо медленнее. Неожиданность заключается в том, что когда вы выводите std::endl, неявно вызывается flush(), поэтому если выводить очень много строк с endl, скорее всего вы получите TL. Из-за этого стоит заменять endl на '\n', всегда, когда это возможно.

Структуры

Вместо того, чтобы писать pair<int, pair<string, string>>, лучше создать структуру

Структуры можно передавать в функции и возвращать из функций

Итераторы

В C++ стандартная библиотека работает с итераторами. Итератор это "указатель" на элемент какой-либо структуры данных. Ведут они себя почти как настоящие указатели, чтобы посмотреть значение, нужно его разыменовать, чтобы обратиться к полю или методу нужно использовать оператор ->

Итераторы делятся на несколько типов:

Forward Iterator
Умеет только разыменовываться и делать инкремент (++)

Bidirectional Iterator
Дополнительно умеет делать декремент (--)

Random-Access Iterator
Умеет прыгать в любую позицию. То есть допустимо прибавлять, вычитать значения и сравнивать итераторы

Кстати, если у вас есть Bidirectional Iterator, и хочется посмотреть предыдущий/следующий элемент, но не хочется модифицировать итератор, можно воспользоваться методами prev(it)/next(it) соответственно.

std::vector

Вектор - это массив, в который можно добавлять/удалять элементы. Внутри себя он хранит расширяющийся (но не сужающийся!) буффер. Когда буффер заполняется, вектор создает новый, в два раза больший, и копирует туда все элементы. Текущий размер буффера можно получить через метод capacity

Из-за этого может возникнуть опасная ситуация. Если мы сохраним указатель (или итератор) на элемент вектора, потом подобавляем туда каких-то элементов, а потом попробуем обновить элемент по этому указателю, то мы обратимся в память, уже не принадлежащую вектору.

Несмотря на "нетривиальную" логику, n добавлений в вектор все равно работают за $O(n)$. Пусть мы добавили $n$ элементов, тогда случилось $\log n$ перестроений и суммарное количество операций копирования равно $1 + 2 + 4 + 8 + \ldots = 2n - 1 = O(n)$. От константы 2 можно избавиться, если знать заранее количество элементов, добавляемое в вектор

Стек, очередь, дек

В C++ есть еще несколько контейнеров, похожих на вектор. Мы их рассмотрим максимально кратко, более подробно сможете прочитать сами на cppreference. Все эти структуры делают добавления, удаления и обращения к элементу за O(1).

std::stack

Умеет делать push, pop и получать верхний элемент через top. Не позволяет смотреть (и конечно модифицировать) произвольные элементы. Почти всегда лучше использовать vector

std::queue

Умеет добавить элемент в конец (push) и удалить элемент с начала (pop). Как и стек, не позволяет смотреть произвольные элементы, кроме первого (front) и последнего (back)

std::deque

По-сути это double-ended queue. Наверное, самый полезный из всех трех. Умеет и добавлять, и удалять и с начала, и с конца. Делает это через push_back, push_front, pop_back, pop_front. По сравнению со стеком и очередью, умеет обращаться к произвольному элементу через []. Еще обладает полезным (но скорее не в олимпиадах) свойством: его итераторы никогда не инвалидируются. Кажется, что это идеальная структура, но на практике вектор оказывается быстрее, поэтому, когда возможностей вектора достаточно, стоит использовать именно его.

Список

Как известно, чтобы добавить элемент в произвольное место вектора, нужно сначала сдвинуть все элементы после него, а только потом вставить в освободившееся место. Это работает за $O(n)$.

Этого недочета нет в std::list. Это двусвязный список (есть еще std::forward_list, он односвязный, но мы его рассматривать не будем), в который можно вставлять элементы в произвольную позицию при условии, что есть итератор на нужную позицию. В обмен на это мы лишаемся возможности обращаться к произвольному элементу по индексу.

Итераторы в списке не инвалидируются.

std::set, std::map

Перейдем к категории "все за логарифм". Контейнеры std::set и std::map поддерживают элементы отсортированными по значению. std::set - это упорядоченное множество элементов, а std::map - множество пар ключ/значение, отсортированное по ключу. Реализованы они на основе деревьев (а точнее rb-дерева), отсюда и время работы всех операций за $O(\log n)$. Итераторы не инвалидируются, что тоже может быть удобно.

Ключом (а в случае сета - значением) может быть любой тип, для которого определен оператор меньше, а также все ключи должны быть различны.

Вообще все фунции в std, которые как-то работают с порядком элементов, требуют наличие оператора меньше, и только его. В set/map альтернативно можно передать класс (или структуру), для которого определен оператор вызова. Такой класс будет называться компаратором.

Отдельно стоит упомянуть std::multiset и std::multimap. Они позволяют хранить равные ключи. К сожалению, эти структуры не только не имеют смысла (ведь muliset<T> можно легко заменить на map<T, int>, храня количество элементов; а multimap по понятным причинам представляет собой какой-то бред), но еще и работают медленнее (например count(x) в мультисете работает за количество элементов равных x), поэтому скорее всего, вы никогда не заходите их использовать. Если интересно, можете прочитать про них на cppreference.

Еще в плюсах есть unordered_ аналоги сета и мапа. Они не гарантируют порядок элементов, но иногда работаю сильно быстрее. По-сути unordered_set и unordered_map - это хеш-таблицы. Для их использования не нужно уметь сравнивать элементы, но нужно уметь получать хеш. Для этого должна быть определена функция std::hash от вашего типа (для большинства стандартных типов она уже реализована). Более подробно разберем эти структуры на леции по хешам, пока что можете обратиться к cppreference.

std::priority_queue

Если вам не нужно удалять элементы, а также получать доступ к произвольным элементам, а только добавлять элемент, и брать минимум (максимум), то std::priority_queue специально для вас. TODO

Полезные функции

Все алгоритмы из std работают с итераторами, при этом ничего не подозревая, что это за итераторы. Поэтому например встроенный бинпоиск будет работать за $O(\log n)$ для вектора, но за $O(n \log n)$ для сета (потому что он не сможет получить элемент по индексу быстрее, чем за $O(n)$). Скоро разберемся, что с этим делать.

Кстати, обычный указатель это вполне себе валидный итератор (Random Access), поэтому указатели тоже вполне можно передавать в подобные функции.

Все функции, работающие с порядком элементов, требуют наличие оператора < для сравнения типов. Кроме этого можно передать дополнительным агрументом компаратор. Рассмотрим это более подробно чуть позже.

sort/is_sorted

Эти функции принимают итераторы на начало и конец и сортируют (проверяют, что отсортирован) этот полуинтервал

unique

Убирает подряд идущие равные значения, возвращает итератор на новый конец последовательности. После этого можно например удалить ненужные элементы.

Очень частое применение выглядит так: отсортируем массив, сделаем unique, удалим лишнее. Таким образом получим все уникальные значения в отсортированном порядке. Это будет полезно например в алгоритме сжатия координат, о котором мы поговорим на одной из лекций.

Работает за $O(n)$

lower_bound/upper_bound

Получает отсортированный полуинтервал и elem, бинпоиском ищет первое значение, не меньше elem (в случае upper_bound - первое строго большее).

Есть еще функция binary_search, которая ищет фиксированное значение. Разобраться с этой функцией остается как упражение.

В начале этого блока мы обсудили, что для сета бинпоиск не будет работать. Но, казалось бы, структура бинарного дерева позволяет нам делать спуск за $O(\log n)$. И да, на этот случай у сета есть свои методы lower_bound и upper_bound.

find

Ищет в полуинтервале $[begin, end)$ первое вхождение значения за $O(n)$, возвращает $end$ если не находит.

reverse

Переворачивает полуинтервал.

rotate

Получает полуинтервал и итератор mid. Делает циклический сдвиг так, что элемент, на который указывает mid, оказывается первым

nth_element

Получает полуинтервал и итератор mid. Ставит на позицию mid тот элемент, который стоял бы там после сортировки. Работает за $O(n)$.

iota

Заполняет полуинтервал значениями от k до k+end-begin.

next_permutation

Получает следующую перестановку. Возвращает false, если следующей не существует.

Еще есть функция prev_permutation, разобраться с ней предлагается самостоятельно.

Компараторы

Как мы уже обсудили, чтобы многие из вышеперечисленных функций работали, нужен определенный оперетор <. Но можно так же передавать еще одним параметром компаратор. Это может быть объект класса (структуры), как мы делали с сетом. Но еще можно передать лямбду (строго говоря, в сет тоже, но не так удобно).

Кстати, в C++ есть пара стандартных компараторов std::less<T> и std::greater<T>, где T - сравниваемый класс. По-умолчанию используется std::less, если вместо него использовать std::greater, порядок сортировки (и того, что делают остальные функции) сменится на противоположный.

Еще один нюанс связан с использованием std::sort. Он не сохраняет относительный порядок равных элементов. Например в следующем примере мы скажем, что все четные числа меньше нечетных, а остальные равны. std::sort сначала положит все четные в каком-то порядке, а затем нечетные тоже в случайном порядке. Для того, чтобы сохранить относительный порядок элементов, есть функция std::stable_sort (не стоит ее использовать всегда, она медленнее).

vector insert/erase

У вектора есть функции для добавления/удаления элементов. Да, это работает за $O(n)$, но такая операция бывает полезна, а руками писать не хочется. Вообще говоря, у них есть много разных способов использования, но мы рассмотрим только работу с одним элементом (остальное см. на cppreference).

vector::insert принимает итератор и элемент и вставляет его перед позицией итератора vector::erase приниает итератор и удаляет элемент, на который он указывает

Рандом

Не будем вдаваться в подробности, просто рассмотрим реализацию рандома, который дает числа с хорошим распределением, и подходит для использования в некоторых функциях из std.

Кому интересно, могут разобраться, как получать распределения отличные от равномерного. Для этого можно загуглить C++ random distributions.

Рассмотрим одно важное применение рандома

pbds

Иногда функциональности сета может не хватить. Например, когда хочется искать ключ по номеру и номер по ключу. Тут на помощь приходит GNU pbds. Это аналог сета (или мапы), который поддерживает эти операции. Более подробно можно почитать тут: https://codeforces.com/blog/entry/11080?locale=ru

tg: @forestryks