C++

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

#include <bits/stdc++.h> // подключаем вместо всех инклюдов
using namespace std; // чтобы писать без префикса `std::`

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

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

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

// ускоряем ввод/вывод
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

/*
for (int i = 0; i < n; ++i) {
    cout << a[i] << endl; <--- так плохо
    cout << a[i] << '\n'; <--- так хорошо
}
*/

Структуры

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

struct User {
    int id;
    string name;
    string surname;
    
    void show() {
        cout << id << ' ' << name << ' ' << surname << endl;
    }
};

User user{123, "Andrei", "Odintsov"};
user.show();
user.name = "Sergey"; // можем менять поля
user.show();
user = {321, "Sasha", "Grishutin"}; // можем менять всю структуру
user.show();

123 Andrei Odintsov
123 Sergey Odintsov
321 Sasha Grishutin

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

User with_changed_id(User user, int new_id) {
    user.id = new_id;
    return user;
}

user = with_changed_id(user, 10);
user.show();

10 Sasha Grishutin

Итераторы

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

vector<int> a = {1, 2, 3, 4, 5};

auto begin = a.begin(); // получаем итератор на начало массива
// На самом деле итератор будет иметь тип `std::vector<int>::iterator`, но чтобы не писать
// тип полностью, мы пишем auto, позволяя компилятору самому определить его за нас

auto end = a.end(); // получаем итератор на конец массива (позиция после последнего)
// В C++ стандарт отдал предпочнение полуинтервалам, поэтому правая граница всегда берется НЕ включительно
// Это достаточно удобно, например, чтобы получить количество элементов между двумя границами, достаточно
// написать begin - end. К тому же это удобно в циклах, можно писать for (auto i = begin; i < end; ++i)

print(end - begin);
print(a.size());

// посмотрим на элемент, на который указывает итератор
print(*begin);

// итераторы можно увеличивать и уменьшать
begin++;
print(*begin);
end--;
print(*end);
print(end - begin);

// к итераторам можно прибавлять (и вычитать) значения
print(*(begin + 2));

// итераторы можно сравнивать
print(begin < end);
print(begin + 3 < end);

// можно пройтись по всем элементам между итераторами
for (auto it = begin; it != end; it += 1) {
    print(*it);
}

end - begin = 5
a.size() = 5
*begin = 1
*begin = 2
*end = 5
end - begin = 3
*(begin + 2) = 4
begin < end = 1
begin + 3 < end = 0
*it = 2
*it = 3
*it = 4

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

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

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

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

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

vector<User> users = {
    {123, "Andrei", "Odintsov"},
    {321, "Sasha", "Grishutin"}
};

for (auto it = users.begin(); it != users.end(); it += 1) {
    // НЕ `it.show()`
    it->show();
    if (it != users.begin()) {
        prev(it)->show();
    }
}

123 Andrei Odintsov
321 Sasha Grishutin
123 Andrei Odintsov

std::vector

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

std::vector<int> a;
print(a.size());
print(a.capacity());
for (int i = 0; i < 10; ++i) {
    a.push_back(i);
    print(a.size());
    print(a.capacity());
}

while (!a.empty()) {
    a.pop_back();
    print(a.size());
    print(a.capacity()); // capacity не меняется!
}

a = {1, 2, 3};
print("after assign");
print(a.size());
print(a.capacity()); // и тут не меняется!

a.shrink_to_fit(); // сжимаем максимально
print("after shrink");
print(a.size());
print(a.capacity());

a.size() = 0
a.capacity() = 0
a.size() = 1
a.capacity() = 1
a.size() = 2
a.capacity() = 2
a.size() = 3
a.capacity() = 4
a.size() = 4
a.capacity() = 4
a.size() = 5
a.capacity() = 8
a.size() = 6
a.capacity() = 8
a.size() = 7
a.capacity() = 8
a.size() = 8
a.capacity() = 8
a.size() = 9
a.capacity() = 16
a.size() = 10
a.capacity() = 16
a.size() = 9
a.capacity() = 16
a.size() = 8
a.capacity() = 16
a.size() = 7
a.capacity() = 16
a.size() = 6
a.capacity() = 16
a.size() = 5
a.capacity() = 16
a.size() = 4
a.capacity() = 16
a.size() = 3
a.capacity() = 16
a.size() = 2
a.capacity() = 16
a.size() = 1
a.capacity() = 16
a.size() = 0
a.capacity() = 16
"after assign" = after assign
a.size() = 3
a.capacity() = 16
"after shrink" = after shrink
a.size() = 3
a.capacity() = 3

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

vector<int> a = {1, 2, 3, 4};
auto it = a.begin() + 1; // указывает на 2
print(a);
print(*it);
a.push_back(5);
print(a);
print(*it); // указывает на какой-то мусор
a[1] = 100;
print(a);
print(*it); // не видит изменений

a = [1, 2, 3, 4]
*it = 2
a = [1, 2, 3, 4, 5]
*it = 21928
a = [1, 100, 3, 4, 5]
*it = 21928

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

int n = 10000;
vector<int> a;
a.reserve(n); // говорим вектору выделить место под n элементов
print(a.size());
print(a.capacity());
for (int i = 0; i < n; ++i) {
    a.push_back(i);
}

a.size() = 0
a.capacity() = 10000

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

В 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, он односвязный, но мы его рассматривать не будем), в который можно вставлять элементы в произвольную позицию при условии, что есть итератор на нужную позицию. В обмен на это мы лишаемся возможности обращаться к произвольному элементу по индексу.

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

list<int> a = {1, 2, 3, 4, 5};
// a[1] = 2; // Так нельзя
// *(a.begin() + 2) // Так тоже нельзя

// Воспользуемся функцией std::advance(iter, n) - сдвигает итератор на n позиций за O(n) последовательно вызывая next()
auto iter = a.begin();
advance(iter, 2);
print(*iter);

// Добавляем элемент за O(1) в середину по итератору
auto inserted_iter = a.insert(iter, 10); // Вставляет элемент перед итератором, возвращает итератор на новый элемент
print(*inserted_iter);

// Нельзя писать it < a.end(), итераторы сета нельзя сравнивать!
for (auto it = a.begin(); it != a.end(); ++it) {
    print(*it);
}

*iter = 3
*inserted_iter = 10
*it = 1
*it = 2
*it = 10
*it = 3
*it = 4
*it = 5

std::set, std::map

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

set<int> a;

// добавляем элементы за O(log n)
a.insert(25);
a.insert(3);
a.insert(7);
a.insert(10);
a.insert(2);
a.insert(3); // дублирующиеся элементы не будут добавлены
a.insert(25);
print(a);

// удаляем элементы за O(log n)
a.erase(7);
print(a);

// получаем итератор на элемент 3
auto it = a.find(3);
print(*it);

// можем посмотреть на следующий элемент
// важно: так как у нас дерево, то посмотреть на следующий элемент может занять до O(log n) операций,
// но, если обойти итератором весь сет, то суммарно получится O(n). Такой концепт называется амортизацией,
// похожее поведение мы могли видеть при добавлении в вектор
print(*next(it));

// удаляем по значению
a.erase(7);
// удаляем по итератору
a.erase(it);
print(a);

// проверим, есть ли элемент
print(a.find(25) != a.end());
print(a.count(27));
// print(a.contains(27)) <--- начиная с C++17

// не стоит пытаться изменять значения внутри сета
// `*it = 10;` <--- так делать не нужно

a = {2, 3, 7, 10, 25}
a = {2, 3, 10, 25}
*it = 3
*next(it) = 10
a = {2, 10, 25}
a.find(25) != a.end() = 1
a.count(27) = 0

map<string, int> a;

// можно вставить пару
a.insert({"hello", 1});
a.insert(make_pair("world", 2));

// можно пользоваться оператором []
a["test"] = 3;
print(a);

// если элемента не существует, он создастся со значением по умолчанию
print(a["wow"]);
print(a);

// итераторы в мапе - это итераторы на пары `std::pair<const KeyType, ValueType>`
auto it = next(a.begin());
print(it->first);
print(it->second);

// значения в мапе можно спокойно менять (но не ключи!)
a["wow"] = 10;
it->second = 123;
print(a);

// удалять можно как по ключу, так и по итератору
a.erase("world");
a.erase(it);
print(a);

a = {{hello 1}, {test 3}, {world 2}}
a["wow"] = 0
a = {{hello 1}, {test 3}, {world 2}, {wow 0}}
it->first = test
it->second = 3
a = {{hello 1}, {test 123}, {world 2}, {wow 10}}
a = {{hello 1}, {wow 10}}

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

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

// определим оператор сравнения для классов пользователей. Будем передавать значения по ссылке, чтобы избежать лишних копирований
bool operator<(const User& a, const User& b) {
    // компаратор должен быть строгим, сравним в первую очередь по имени, а затем в порядке убывания id
    if (a.name == b.name) {
        return a.id > b.id;
    }
    return a.name < b.name;
}

// теперь можно кидать пользователей в сет
// создадим сет из всех элементов вектора users, который мы использовали ранее
set<User> users_set(users.begin(), users.end());

// альтернативно можно было сделать так
struct CompareUsers {
    bool operator()(const User& a, const User& b) {
        // если лень писать, и компаратор просто сравнивает поля в каком-то порядке, можно сделать так
        return make_tuple(a.name, -a.id) < make_tuple(b.name, -b.id);
    }
};

Отдельно стоит упомянуть 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

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

vector<int> a = {7, 3, 2, 6, 2, 8, 4, 3, 3, 6, 1};
print(a);
print(is_sorted(a.begin(), a.end()));
sort(a.begin(), a.end());
print(a);
print(is_sorted(a.begin(), a.end()));

a = [7, 3, 2, 6, 2, 8, 4, 3, 3, 6, 1]
is_sorted(a.begin(), a.end()) = 0
a = [1, 2, 2, 3, 3, 3, 4, 6, 6, 7, 8]
is_sorted(a.begin(), a.end()) = 1

unique

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

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

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

auto it = unique(a.begin(), a.end());
print(it - a.begin()); // количество оставшихся элементов
print(a);
a.erase(it, a.end()); // удалим лишнее (тоже полуинтервал)
print(a);

it - a.begin() = 7
a = [1, 2, 3, 4, 6, 7, 8, 6, 6, 7, 8]
a = [1, 2, 3, 4, 6, 7, 8]

lower_bound/upper_bound

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

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

auto it = lower_bound(a.begin(), a.end(), 5);
cout << "position of first element >= 5: " << (it - a.begin()) << endl;
print(*it);

it = upper_bound(a.begin(), a.end(), 6);
cout << "position of first element > 6: " << (it - a.begin()) << endl;
print(*it);

it = lower_bound(a.begin(), a.end(), 30);
print(it == a.end()); // нет элемента >= 30, поэтому получили end

position of first element >= 5: 4
*it = 6
position of first element > 6: 5
*it = 7
it == a.end() = 1

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

set<int> s(a.begin(), a.end());
auto it = s.lower_bound(-2);
print(*it);

*it = 1

find

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

vector<int> a = {7, 3, 2, 6, 2, 8, 4, 3, 3, 6, 1};
auto it = find(a.begin(), a.end(), 6);
print(it - a.begin());

it = find(a.begin(), a.end(), 5);
print(it == a.end()); // не нашли

it - a.begin() = 3
it == a.end() = 1

reverse

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

vector<int> a = {5, 4, 3, 2, 1};
print(a);
reverse(a.begin(), a.end());
print(a);

a = [5, 4, 3, 2, 1]
a = [1, 2, 3, 4, 5]

rotate

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

print(a);
rotate(a.begin(), a.begin() + 2, a.end());
print(a);

a = [1, 2, 3, 4, 5]
a = [3, 4, 5, 1, 2]

nth_element

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

vector<int> a = {5, 3, 1, 4, 2};
print(a);
nth_element(a.begin(), a.begin() + 1, a.end());
print(a);

a = [5, 3, 1, 4, 2]
a = [1, 2, 3, 4, 5]

iota

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

vector<int> a;
a.resize(10, 0);

iota(a.begin(), a.end(), 0);
print(a);

iota(a.begin(), a.end(), 5);
print(a);

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a = [5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

next_permutation

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

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

vector<int> a = {0, 2, 3, 1};

do {
    print(a);
} while (next_permutation(a.begin(), a.end()));

a = [0, 2, 3, 1]
a = [0, 3, 1, 2]
a = [0, 3, 2, 1]
a = [1, 0, 2, 3]
a = [1, 0, 3, 2]
a = [1, 2, 0, 3]
a = [1, 2, 3, 0]
a = [1, 3, 0, 2]
a = [1, 3, 2, 0]
a = [2, 0, 1, 3]
a = [2, 0, 3, 1]
a = [2, 1, 0, 3]
a = [2, 1, 3, 0]
a = [2, 3, 0, 1]
a = [2, 3, 1, 0]
a = [3, 0, 1, 2]
a = [3, 0, 2, 1]
a = [3, 1, 0, 2]
a = [3, 1, 2, 0]
a = [3, 2, 0, 1]
a = [3, 2, 1, 0]

Компараторы

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

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

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

vector<int> a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
auto comp = [](int a, int b){
    if (a % 2 == 0 && b % 2 == 1) {
       return true;
    } else {
        return false;
    }
};

sort(a.begin(), a.end(), comp);
print(a);

a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
stable_sort(a.begin(), a.end(), comp);
print(a);

a = [10, 20, 18, 16, 14, 12, 0, 8, 6, 4, 2, 7, 9, 11, 5, 13, 15, 3, 17, 19, 1]
a = [0, 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15]

vector insert/erase

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

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

vector<int> a = {0, 1, 2, 3, 4};

print(a);
a.insert(a.begin() + 2, 10);
print(a);
a.erase(a.begin() + 4);
print(a);

a = [0, 1, 2, 3, 4]
a = [0, 1, 10, 2, 3, 4]
a = [0, 1, 10, 2, 4]

Рандом

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

random_device rd; // это медленный, но "настоящий" рандом
mt19937 mt(rd()); // быстрый рандом (тут используется mersen twist engine) требует сид для инициализации, восползуемся медленным рандомом

print(mt()); // случайное число

mt() = -747715898

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

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

vector<int> a = {0, 1, 2, 3, 4, 5};
shuffle(a.begin(), a.end(), mt); // шаффлим массив
print(a);

// НЕ используйте random_shuffle

a = [2, 4, 5, 0, 1, 3]

pbds

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

#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ordered_set s;
s.insert(1);
s.insert(2);
s.insert(4);
s.insert(8);
s.insert(16);

print(*s.find_by_order(1));
print(*s.find_by_order(2));
print(*s.find_by_order(4));
print(end(s) == s.find_by_order(6));

print(s.order_of_key(-5));
print(s.order_of_key(1));
print(s.order_of_key(3));
print(s.order_of_key(4));
print(s.order_of_key(400));

tg: @forestryks