интерактивный урок

struct + pair в C++

Когда одного числа мало — нужно группировать данные. Координата — это два числа. Участник — имя + баллы + штраф. В C++ для этого есть pair и struct.

История: координаты на карте

Ты пишешь навигатор. Каждая точка — это два числа: широта и долгота. Хранить их в отдельных переменных x1, y1, x2, y2 — путаница. Нужен один объект для двух значений.

pair<int, int> — ровно для этого. Два значения, доступ через .first и .second.

💡 pair = «контейнер ровно из двух значений».

Создаём первый pair

pair_basic.cpp шаг 1 из 3

Создали pair из двух int. first = 3, second = 7.

make_pair — альтернативный способ:

pair_make.cpp шаг 1 из 2

make_pair создаёт pair. Типы выводятся автоматически.

Сортировка pair: магия лексикографии

Главная суперсила pair — автоматическая сортировка. Сначала по first, при равенстве по second.

pair_sort.cpp шаг 1 из 4

Вектор пар: (значение, индекс).

💡 Контестный приём: чтобы отсортировать массив, но запомнить исходные индексы, используй vector<pair<int,int>> — {a[i], i}.

pair_index.cpp шаг 1 из 3

Создаём вектор пар (значение, оригинальный индекс).

Сложность сортировки: O(n log n) по времени, O(n) по памяти.

Трюки с pair в контестах

Трюк 1: сортировка по убыванию first

pair_trick1.cpp шаг 1 из 2

Храним {-value, index}. sort по возрастанию -value = по убыванию value.

Трюк 2: pair как координата

pair_point.cpp шаг 1 из 3

typedef для удобства. Теперь Point — это pair<int,int>.

struct: когда pair не хватает

Если данных больше двух полей — pair становится неудобным. first и second ничего не говорят о смысле данных. Тогда → struct.

	pair	struct
Полей	Ровно 2	Сколько угодно
Имена полей	first / second	Говорящие имена
Сортировка	Автоматическая	Нужен компаратор
Когда	2 коротких поля	3+ полей или сложная логика

Создаём первый struct

struct_basic.cpp шаг 1 из 4

Описали свой тип Student с тремя полями.

Задача: рейтинг участников

Условие. Есть n участников с полями name, solved, penalty. Отсортируй:

Больше solved → выше
При равном solved — меньше penalty → выше
При полном равенстве — по имени

struct_sort.cpp шаг 1 из 5

Компаратор cmp сравнивает двух участников.

Сложность: O(n log n) — стандартная сортировка.

🏆 Контестный лайфхак: если правила сортировки сложные (3+ критерия), всегда используй struct + компаратор. С pair будет каша.

Задача: результаты забега

Условие. n бегунов, у каждого имя и время (секунды). Выведи тройку призёров.

struct_runners.cpp шаг 1 из 5

struct Runner: имя + время.

💡 Лямбда [](const Runner& a, const Runner& b) { ... } — компактная альтернатива отдельной функции cmp.

Когда pair, когда struct?

Ситуация	Лучше	Почему
Координата (x, y)	pair	Быстро, компактно, auto-sort
(значение, индекс) для сортировки	pair	Классический контестный паттерн
Участник (имя, баллы, штраф)	struct	3 поля + понятные имена
Ребро графа (u, v, w)	struct	3 поля + кастомная сортировка
Быстрый temporary	pair	Не хочется писать struct ради 2 полей

Правило: 2 коротких поля → pair. 3+ полей или сложная логика → struct.

Проверь себя

Как pair сортируется по умолчанию?

Почему для 4-5 полей лучше struct?

Что выведет sort для {(3,1), (1,2), (3,0)}?

Как в struct задать сортировку по убыванию поля score?

Итог

pair и struct — фундамент моделирования данных:

pair — для коротких двоек: координаты, (значение, индекс)
struct — для реальных сущностей: участник, ребро, событие
pair сортируется автоматически (лексикографически)
struct требует компаратор, но даёт полный контроль

Паттерны:

{ai, i} — сортировка с запоминанием индексов
struct + cmp — кастомная сортировка с 3+ критериями
лямбда — компактный компаратор прямо в sort

Комбинируй pair, struct, sort, map и set — и большинство контестных задач на моделирование тебе по зубам!