1. Контейнер «ключ → значение»
Если в std::vector всё устроено по принципу «элементы лежат подряд, у каждого есть индекс», то в реальных задачах часто хочется другого: найти не «элемент №7», а «пользователя с id=42», «настройку с именем "theme"», «товар по артикулу», «счётчик для слова "apple"». И хочется найти это быстро, не пробегая каждый раз весь список.
Представьте, что вы ведёте маленькое консольное приложение TaskBook (наш учебный мини‑проект): храните задачи, у каждой есть id и текст. Пока задач 10 — можно искать линейно. Когда их 10 000 — линейный поиск превращается в обязательную утреннюю зарядку для процессора (он, конечно, рад, но пользователь — не всегда).
Идея ассоциативных контейнеров в C++ такая: мы храним данные так, чтобы можно было быстро отвечать на вопрос «есть ли ключ?» и «какое значение у этого ключа?».
Модель: «словарь», где элемент — это пара
Перед тем как сравнивать map и unordered_map, важно договориться о базовой картинке мира. В обоих контейнерах мы храним пары: ключ и значение. Ключ — это то, по чему ищем. Значение — то, что получаем.
Например, «имя → возраст», «id → задача», «слово → количество», «код_ошибки → текст». В памяти это выглядит примерно как множество записей вида:
key1 -> value1
key2 -> value2
...В C++ внутри это обычно хранится как std::pair<const Key, Value>. Вам это не нужно заучивать как заклинание, но полезно помнить: при обходе контейнера мы получаем и ключ, и значение. Поэтому structured bindings здесь особенно приятны — меньше стрелочек first/second, больше человеческого языка.
2. std::map: упорядоченный словарь
std::map<Key, Value> — это ассоциативный контейнер, который хранит элементы в порядке ключей. С точки зрения поведения это очень похоже на телефонную книгу: вы можете быстро найти запись по имени, и если вы «листаете» книгу, имена идут по алфавиту.
Под капотом map обычно реализован как сбалансированное дерево (часто вспоминают красно‑чёрное дерево). Вам сейчас не нужно уметь рисовать его на собеседовании, но полезно понимать последствия: операции поиска/вставки/удаления имеют сложность порядка O(log N), потому что дерево каждый шаг «делит область поиска».
Мини‑картинка: интуитивно
Если очень грубо, дерево похоже на «вопросник»:
- ключ меньше текущего? иди влево
- больше? иди вправо
- совпал? нашли
И так несколько шагов, пока не нашли нужное или не упёрлись в «пусто».
Когда map реально удобен
map выбирают, когда:
- важен отсортированный обход по ключам (например, печатаем отчёт «по возрастанию id»);
- нужны операции вида «найти ближайший ключ» (в духе нижняя граница/верхняя граница);
- вы хотите, чтобы порядок был стабильной частью логики (а не «как повезло сегодня»).
4. std::unordered_map: словарь без порядка
std::unordered_map<Key, Value> решает ту же задачу «ключ → значение», но делает это иначе: вместо дерева он обычно использует хеш‑таблицу. В стандарте это семейство контейнеров так и называется — unordered associative containers.
Главная мысль: мы берём ключ, вычисляем для него число (хеш) и по этому числу понимаем, куда примерно смотреть. Если всё хорошо, поиск/вставка/удаление работают в среднем за O(1) (то есть «почти константа», не зависит линейно от количества элементов). На практике это часто означает «очень быстро».
Мини‑картинка: интуитивно
Можно представлять хеш‑таблицу как массив «корзин» (buckets):
- ключ превращается в число (хеш)
- по нему выбирается корзина
- внутри корзины уточняем (на случай коллизий)
Коллизии — это когда разные ключи попали в одну корзину. Это нормально: контейнер всё равно проверит равенство ключей и найдёт правильный.
Когда unordered_map реально удобен
unordered_map выбирают, когда:
- нужен быстрый доступ по ключу и порядок не важен;
- вы делаете счётчики, индексы, таблицы соответствий;
- вам важна скорость на больших объёмах данных.
5. Сравнение map и unordered_map: таблица
Чтобы мозг не пытался держать всё в оперативной памяти одновременно, сведём различия в таблицу:
| Характеристика | |
|
|---|---|---|
| Внутренняя идея | дерево (упорядоченная структура) | хеш‑таблица (корзины по хешу) |
| Порядок обхода | всегда по ключам (от меньшего к большему) | не определён, не считается «по ключу» |
| Поиск/вставка/удаление | обычно O(log N) | обычно O(1) в среднем |
| Когда выбирать | нужен порядок ключей, «красивый» отсортированный вывод | нужен быстрый доступ и порядок не важен |
6. Практика: операции и поведение
Сейчас будет приятная часть: пользоваться map и unordered_map очень похоже. Это сделано специально, чтобы вы не страдали и не переписывали пол‑проекта при замене контейнера. Но есть нюанс: одинаковый синтаксис иногда ведёт к разным ожиданиям, особенно вокруг operator[].
Ниже — те операции, которые вы будете применять чаще всего: find, contains, insert/emplace, erase, operator[].
Обход: map печатает по порядку ключей
Сделаем маленький пример «имя → возраст». Обратите внимание на обход: имена будут отсортированы (обычно лексикографически, то есть как в словаре).
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> ages;
ages.emplace("Bob", 25);
ages.emplace("Ann", 20);
for (const auto& [name, age] : ages) {
std::cout << name << " -> " << age << '\n';
// Ann -> 20
// Bob -> 25
}
}Обход: unordered_map — быстро, но без гарантии порядка
Тот же пример, но с unordered_map. Важный момент: вывод может получиться в любом порядке. Не пытайтесь «поймать закономерность» — это как пытаться предсказать, где окажется носок после стирки. Иногда кажется, что порядок есть. Потом внезапно оказывается, что его нет.
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> ages;
ages.emplace("Bob", 25);
ages.emplace("Ann", 20);
for (const auto& [name, age] : ages) {
std::cout << name << " -> " << age << '\n';
// Порядок НЕ гарантирован
}
}find: безопасное чтение без побочных эффектов
Когда вы хотите прочитать значение по ключу и при этом не менять контейнер, самый спокойный путь — find.
Паттерн выглядит так:
- auto it = m.find(key);
- если it == m.end() — ключа нет
- иначе it->second — значение
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> score{{"Ann", 10}, {"Bob", 12}};
if (auto it = score.find("Eve"); it != score.end()) {
std::cout << it->second << '\n';
} else {
std::cout << "no such key\n"; // no such key
}
}Почему это важно: find не создаёт новых элементов. Он только ищет.
contains: когда нужно просто «есть/нет»
В C++20 у ассоциативных контейнеров есть contains(key) — это «короткая форма» проверки. Возвращает true/false. Для новичка это часто читается проще, чем find (особенно когда значение вам не нужно).
#include <iostream>
#include <map>
int main() {
std::map<int, int> m{{1, 100}, {2, 200}};
std::cout << m.contains(2) << '\n'; // 1
std::cout << m.contains(3) << '\n'; // 0
}Если вам нужно значение — берите find. Если нужно только «существует ли ключ» — contains обычно идеален.
operator[]: очень удобно… и поэтому опасно
Вот главный «мем» (в хорошем смысле) про map и unordered_map.
m[key] — это операция «получить или создать»:
- если ключ уже есть — вы получаете ссылку на значение;
- если ключа нет — он создаётся, а значение становится «по умолчанию».
Из-за этого operator[] идеален для счётчиков, но плох для «просто проверить наличие».
Пример: счётчик слов — operator[] прекрасен
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> cnt;
cnt["apple"] += 1; // было 0 (создалось), стало 1
cnt["apple"] += 1; // стало 2
std::cout << cnt["apple"] << '\n'; // 2
}Пример: «просто прочитаю, что там» — и внезапно изменил контейнер
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m{{1, 10}};
std::cout << m[2] << '\n'; // 0 (и ключ 2 теперь существует!)
std::cout << m.size() << '\n'; // 2
}Вот это изменение размера — типичная причина «почему у меня в контейнере вдруг появились лишние ключи».
insert/emplace: вставка без перезаписи и результат операции
Когда вы вставляете элемент в map/unordered_map, часто хочется знать: «вставилось или ключ уже был?». И контейнер честно возвращает результат: std::pair<iterator, bool>.
bool говорит, была ли реальная вставка.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m;
auto [it1, ok1] = m.emplace(1, 10);
auto [it2, ok2] = m.emplace(1, 99);
std::cout << ok1 << ' ' << ok2 << '\n'; // 1 0
std::cout << m[1] << '\n'; // 10
}Обратите внимание: второй emplace не перезаписал значение, потому что ключ уже существовал.
erase: удаление по ключу и «сколько реально удалили»
erase(key) возвращает количество удалённых элементов. Для map/unordered_map это обычно 0 или 1, потому что ключи уникальны.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m{{1, 10}, {2, 20}};
std::size_t removed = m.erase(2);
std::cout << removed << '\n'; // 1
}Это удобно: можно не делать отдельный contains, если вам просто важно понять, было ли что удалять.
7. Как «дерево» отличается от «хеша»: схема на пальцах
Иногда помогает визуализация, особенно если вы пока не любите абстракции (что нормально — они сами по себе не очень «тактильные»).
flowchart LR
A[Ключ] --> B{map: сравнения}
B --> C[влево/вправо по дереву]
C --> D[нашли значение]
A --> E{unordered_map: хеш}
E --> F[номер корзины]
F --> G[поиск в корзине]
G --> D
У map главный инструмент — сравнение ключей и логарифмическая навигация по структуре. У unordered_map главный инструмент — хеширование и попадание «примерно в нужное место».
8. TaskBook: быстрый доступ к задаче по id
Теперь привяжем это к нашему учебному приложению. Допустим, у нас есть модель:
#include <string>
struct Task {
int id{};
std::string text;
};Раньше мы могли хранить задачи в std::vector<Task> tasks; и искать задачу по id линейно.
Линейный поиск: работает, но может быть медленным
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> ids{10, 20, 30};
int want = 20;
auto it = std::find(ids.begin(), ids.end(), want);
std::cout << (it != ids.end()) << '\n'; // 1
}Для задач будет примерно то же самое, только с find_if и лямбдой (вы это уже встречали).
Индекс id → Task на unordered_map
Если наша частая операция — «по id быстро найти задачу», логичнее хранить индекс:
#include <iostream>
#include <string>
#include <unordered_map>
struct Task {
int id{};
std::string text;
};
int main() {
std::unordered_map<int, Task> by_id;
by_id.emplace(1, Task{1, "Read C++ book"});
by_id.emplace(2, Task{2, "Fix bugs (or create new ones)"});
std::cout << by_id[2].text << '\n'; // Fix bugs (or create new ones)
}Здесь я специально использовал operator[] для чтения, чтобы вы почувствовали «скользкое место»: это безопасно только если вы уверены, что ключ существует. Иначе вы случайно создадите пустую задачу. Поэтому в реальном коде чтение чаще делают через find.
Безопасное чтение задачи по id: через find
#include <iostream>
#include <string>
#include <unordered_map>
struct Task {
int id{};
std::string text;
};
int main() {
std::unordered_map<int, Task> by_id{{1, {1, "Read"}}, {2, {2, "Write"}}};
int id = 3;
if (auto it = by_id.find(id); it != by_id.end()) {
std::cout << it->second.text << '\n';
} else {
std::cout << "No task with id=" << id << '\n'; // No task with id=3
}
}9. Что выбрать: map или unordered_map?
Сделаем честное «прикладное правило», без мистики.
Если вам нужен упорядоченный вывод и вы хотите, чтобы контейнер сам держал всё «по ключам», берите map. Например, вы печатаете задачи всегда по id — так, чтобы пользователю было приятно.
Если вам нужен быстрый доступ и вы не хотите платить log N за каждое обращение, а порядок не важен — берите unordered_map.
Если вы сомневаетесь, то на практике часто начинают с unordered_map, потому что это «словарь по умолчанию» для быстрого доступа. А когда внезапно появляется требование «выводить по ключу отсортированно» — переключаются на map (или сортируют отдельно, но это уже другая история).
И ещё маленькая формальность: у unordered_map есть требования к ключу (хеш и равенство), а у map — требования к порядку (сравнение). Мы подробно разберём эти «контракты ключей» в следующих лекциях этого дня; в материалах стандарта даже выделяют отдельные требования для unordered‑контейнеров.
10. Типичные ошибки при выборе и использовании map/unordered_map
Ошибка №1: ожидать, что unordered_map «обходит по порядку».
Новичок делает unordered_map, наполняет данными, печатает — видит «почти отсортировано» и начинает полагаться на этот порядок. Потом добавляется ещё один элемент, меняется компилятор, режим сборки или просто фаза луны — и порядок становится другим. Для логики программы порядок обхода unordered_map считать нельзя: если порядок важен, выбирайте map.
Ошибка №2: использовать operator[] для проверки наличия ключа.
Классика: пишут if (m[key] == ...) или просто m[key] «посмотреть, есть ли». В итоге ключ создаётся со значением по умолчанию, контейнер меняется, появляются «пустые» записи. Для проверки используйте contains или find, а operator[] оставляйте для сценариев «создать/обновить».
Ошибка №3: разыменовать результат find без проверки на end().
После auto it = m.find(key); нельзя сразу делать it->second, потому что it может оказаться равным m.end(). В лучшем случае вы получите падение, в худшем — странное поведение. Надёжный ритуал здесь полезен: сначала проверка, потом разыменование.
Ошибка №4: выбирать контейнер «по вкусу», а не по требованиям задачи.
Иногда map берут «потому что звучит солидно», а unordered_map — «потому что быстрее». Правильнее начинать с вопроса: важен ли порядок? нужны ли частые поиски? будет ли много элементов? Если порядок важен — map решает задачу проще. Если порядок не важен, но важна скорость — unordered_map обычно естественнее.
Ошибка №5: хранить данные так, что ключи «дублируют» смысл структуры.
Например, вы делаете unordered_map<int, Task>, где внутри Task ещё лежит поле id, и потом начинаете обновлять одно, забывая обновлять другое. Это не всегда ошибка (иногда id в объекте удобен), но это место, где легко получить рассинхрон. Хорошая привычка: если id — ключ, то следите, чтобы Task.id либо всегда совпадал, либо вообще не использовался как источник истины (иначе вы сами себе устроите квест).
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ