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

map в C++

Если set — это коробка уникальных элементов, то map — словарь: к каждому ключу привязано значение. Телефонная книга, подсчёт голосов, частоты букв — всё это map.

История: голосование в классе

💡 map = «словарь: ключ → значение, ключи всегда отсортированы».

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

Без map: создаёшь массив названий, для каждого нового голоса ищешь линейно — O(n). С map: votes["Inception"]++ — O(log n).

Контейнер	Что хранит	Поиск по ключу	Порядок
vector<pair>	Пары	O(n)	Как добавили
map	Ключ → значение	O(log n)	По ключу

Первый взгляд: создаём словарь

Ключевое свойство: mp[key] создаёт запись, если ключа нет. Значение по умолчанию для int — 0.

map_intro.cpp шаг 1 из 6

Создали map: ключ — string, значение — int.

Все операции map и Big O

Операция	Код	Сложность	Что делает
Доступ / создание	mp[key]	O(log n)	Значение по ключу (создаёт, если нет)
Поиск	mp.find(key)	O(log n)	Итератор или end()
Проверка	mp.count(key)	O(log n)	0 или 1
Удаление	mp.erase(key)	O(log n)	Удаляет пару
Размер	mp.size()	O(1)	Кол-во пар
Обход	for (auto [k, v] : mp)	O(n)	По возрастанию ключа

map_ops.cpp шаг 1 из 4

mp["cat"] = 3 — создали запись.

Магия operator[]

⚠️ Осторожно: mp[key] создаёт ключ со значением 0, если его нет. Для проверки без создания используй mp.count(key) или mp.find(key).

Главная фишка map — mp[key]++ работает даже если ключа ещё нет:

map_bracket.cpp шаг 1 из 5

mp пустой. mp[5] создаёт запись 5 → 0.

Задача 1: подсчёт частот

Условие. Дан массив чисел. Выведи, сколько раз встречается каждое число.

Это самый частый паттерн с map в контестах: frequency counting.

frequency.cpp шаг 1 из 4

freq хранит: число → сколько раз встретилось.

Пример: a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

Вывод:

text

1: 2
2: 1
3: 2
4: 1
5: 2
6: 1
9: 1

Сложность: O(n log n) по времени, O(k) по памяти, где k — количество различных значений.

Задача 2: самый частый элемент (mode)

Условие. Найди число, которое встречается чаще всего.

Идея: сначала считаем частоты, потом ищем максимум.

mode.cpp шаг 1 из 5

Шаг 1: считаем частоты (уже знакомый паттерн).

Сложность: O(n log n) — на подсчёт частот. Поиск максимума — O(k).

Задача 3: частота слов

🏆 Задача C из AQL Contest #9 (Maximum Word Frequency) решается именно так — map<string, int> + поиск максимума.

Условие. Дано n слов. Для каждого слова выведи частоту.

Точно такой же паттерн, но ключ — string:

word_freq.cpp шаг 1 из 3

map<string, int> — ключ это слово, значение это кол-во.

Задача 4: суммирование по ключу

💡 Это ровно то, что нужно в задаче G (Maps-STL) из AQL Contest #9: запрос 1 — mp[name] += score, запрос 2 — mp.erase(name), запрос 3 — cout << mp[name].

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

accumulate.cpp шаг 1 из 3

Для каждой пары (name, score) прибавляем score к total[name].

Советы для контестов

Ситуация	map	unordered_map
Нужен порядок ключей	Да	Нет
Поиск / вставка	O(log n)	O(1) среднее
Надёжность	Всегда O(log n)	O(n) при коллизиях
Лексикографический обход	Автоматически	Нужна сортировка

Частые ошибки:

mp[key] создаёт запись. Не используй для проверки — используй count.
Не забывай, что for (auto [k, v] : mp) — копия. Для модификации: for (auto& [k, v] : mp).

Проверь себя

Что делает freq[x]++, если ключа x ещё не было?

Какова сложность mp.find(key) для std::map?

В каком порядке map обходит пары?

map<string,int> mp; mp["a"]=1; mp["b"]=2; cout << mp.size();

Итог

map + set — это фундамент для задач на статистику, строки и события в контестах!

std::map — базовый инструмент для:

Подсчёта частот — freq[x]++
Суммирования по ключу — total[name] += score
Сортированного обхода — ключи автоматически в порядке
Быстрого поиска по ключу — O(log n)

Паттерны:

Frequency map — считай частоты одной строкой
Accumulate — суммируй по ключу
Mode — найди самый частый через max по cnt