1. std::map: ключ в мире порядка
Представьте, что контейнер — это библиотекарь. Вы приходите и говорите: «Найди мне книгу по названию». Библиотекарь спрашивает: «А как сравнивать названия? По алфавиту? Без учёта регистра? По длине строки?» Если правила не определены, он может начать искать книгу… по цвету обложки. И формально он не виноват — вы не договорились о правилах.
В C++ ассоциативные контейнеры работают ровно так же: они могут быть очень быстрыми, но только если вы даёте им ясный контракт ключа — правило, по которому контейнер определяет «это тот же ключ» и «куда положить ключ». В стандарте даже есть формулировки в духе «контейнер отсортирован относительно comp» — то есть порядок задаётся компаратором.
Два семейства контейнеров требуют разные «договоры»:
- std::map (и std::set) требуют правило порядка: обычно через operator< (или компаратор).
- std::unordered_map (и std::unordered_set) требуют равенство + хеш: == и hash() (плюс их согласованность).
map использует компаратор, а не ==
Когда вы впервые видите std::map, возникает ощущение: «А, это словарь, значит сравнение ключей — это ==». Но map устроен иначе: он упорядоченный. Это значит, что он поддерживает структуру данных (логически — дерево), которая постоянно держит ключи «в порядке», чтобы быстро находить элементы.
И тут важная мысль: std::map по умолчанию использует std::less<Key>, а для большинства обычных типов std::less<Key> просто вызывает operator<. Поэтому, когда мы говорим «контракт ключа map», мы почти всегда имеем в виду: для ключа должно быть корректно определено строгое сравнение “меньше”.
Упрощённая картинка в голове может быть такой:
flowchart TD
A[Ключ] --> B{"comp(a,b)?"}
B -->|да| L[а идёт левее b]
B -->|нет| R[а не левее b]
Фраза «контейнер отсортирован относительно comp» — это как раз про это правило.
Что map считает «одинаковыми ключами»
Сейчас будет момент, который ломает шаблон: map может вообще не использовать operator==. Он решает «одинаковые ключи или нет» через компаратор.
Интуитивное правило такое: два ключа считаются эквивалентными, если ни один не “меньше” другого по компаратору. То есть:
- a не меньше b
- и b не меньше a
На человеческом уровне это означает: «компаратор не смог поставить их в порядок, значит для контейнера они одинаковые».
Это приводит к очень практичному эффекту: если ваш компаратор сравнивает только часть полей, map начнёт “склеивать” разные ключи в один. И контейнер будет абсолютно уверен, что он прав: вы сами дали такое правило.
Мини‑пример: телефонная книга на map
Давайте продолжим наш учебный мини-проект. Пусть у нас есть простая «телефонная книга», и мы хотим хранить контакты по имени. Для map ключом будет std::string, у которой уже есть корректный operator<.
#include <iostream>
#include <map>
#include <string>
struct Contact {
std::string phone;
};
int main() {
std::map<std::string, Contact> book;
book.emplace("Ann", Contact{"111-11"});
book.emplace("Bob", Contact{"222-22"});
for (const auto& [name, c] : book) {
std::cout << name << ": " << c.phone << '\n';
// Ann: 111-11
// Bob: 222-22
}
}
Здесь контейнер сам поддерживает порядок ключей, и обход получается «отсортированным по имени». И это не «приятный бонус», а фундаментальная часть контракта map: он хранит элементы упорядоченно относительно компаратора.
Ловушка: компаратор через <=
Очень хочется написать компаратор как «не позже» (<=) или «не больше». Логика кажется железобетонной: если a <= b, то a раньше b. Но компаратор в map должен отвечать на другой вопрос: «строго раньше?».
Если использовать <=, вы ломаете “строгость”. В результате компаратор может сказать, что a “раньше” a (ведь a <= a истинно). Это ломает внутренние ожидания контейнера: он рассчитывает, что ключ не меньше самого себя.
Покажем правильный стиль на простом компараторе «по длине строки», где строгость легко увидеть:
#include <map>
#include <string>
struct ByLength {
bool operator()(const std::string& a, const std::string& b) const {
return a.size() < b.size(); // строго <
}
};
int main() {
std::map<std::string, int, ByLength> m;
m["cat"] = 1;
m["lion"] = 2;
}
Да, это странный порядок (по длине), но он строгий: строка не “меньше” самой себя, и контейнеру от этого спокойнее жить.
Ловушка: «склейка» ключей из-за неполного сравнения
Теперь сделаем пример ближе к реальности. Контакт у нас может иметь фамилию и имя. И мы хотим хранить людей по (фамилия, имя). Если сравнивать только фамилию, то два разных человека с одной фамилией станут «одним ключом» для map.
#include <iostream>
#include <map>
#include <string>
struct PersonKey {
std::string last;
std::string first;
};
struct ByLastOnly {
bool operator()(const PersonKey& a, const PersonKey& b) const {
return a.last < b.last; // first игнорируется
}
};
int main() {
std::map<PersonKey, int, ByLastOnly> ids;
ids.emplace(PersonKey{"Smith", "Ann"}, 1);
ids.emplace(PersonKey{"Smith", "Bob"}, 2);
std::cout << ids.size() << '\n'; // 1 (и это не “баг map”, это ваш контракт)
}
Контейнер сделал ровно то, что вы ему разрешили: по вашему правилу все "Smith" эквивалентны. На бытовом уровне это похоже на ситуацию «в картотеке сортируем людей только по фамилии, а имя не пишем вообще». Да, поиск будет быстрым. Но пользоваться таким индексом будет… смело.
3. std::unordered_map: ключ в мире хеша и равенства
Как unordered_map ищет элементы
Теперь переключаемся на вторую семью контейнеров. std::unordered_map не обещает порядок. Он обещает другое: «я быстро найду по ключу, используя хеширование».
Упрощённая картинка:
flowchart TD
K[Ключ] --> H["hash(key)"]
H --> B[bucket / корзина]
B --> C{проверка key == candidate}
C -->|да| F[нашли значение]
C -->|нет| N[ищем дальше в корзине]
То есть unordered_map сначала вычисляет число (хеш), по нему выбирает «корзину», а потом уже сравнивает ключи на равенство, чтобы отличить коллизии.
Внутри стандарта отдельно подчёркивается, что у unordered_* есть требования к объектам Hash и Pred (предикат равенства). Даже если вам не важны формулировки, сам факт полезен: это именно контракт, а не «как повезёт».
Главный закон: если a == b, то hash(a) обязан равняться hash(b)
Сформулируем самое важное правило ключа для unordered_map так, чтобы его можно было повесить на стену (рядом с «не пиши using namespace std; в заголовке», но это будет позже).
Если два ключа считаются равными (a == b), то их хеши обязаны совпадать: hash(a) == hash(b).
Почему так строго? Потому что контейнер сначала идёт в корзину по hash(a). Если b равен a, но у него другой хеш, то b окажется в другой корзине. И тогда поиск по ключу a может не найти b, хотя “по смыслу” это один и тот же ключ. То есть контейнер становится логически некорректным.
Коллизии (когда a != b, но hash(a) == hash(b)) разрешены и нормальны. Контейнер потом разрулит это через ==. А вот обратное (равные, но разные хеши) — ломает базовую механику.
Мини‑пример: телефонная книга по id на unordered_map
Вернёмся к нашему приложению. Допустим, у контакта есть числовой id. Для int уже есть std::hash<int> и корректный operator==, так что ключ идеально подходит для unordered_map.
#include <iostream>
#include <string>
#include <unordered_map>
struct Contact {
int id{};
std::string name;
std::string phone;
};
int main() {
std::unordered_map<int, Contact> book;
book.emplace(1, Contact{1, "Ann", "111-11"});
book.emplace(2, Contact{2, "Bob", "222-22"});
if (auto it = book.find(2); it != book.end()) {
std::cout << it->second.name << '\n'; // Bob
}
}
Обратите внимание: тут ключ — int, и мы не заставляем контейнер ничего сортировать. Поэтому обход по unordered_map не стоит использовать как «упорядоченный список» (сегодня он такой, завтра другой). Зато поиск по ключу очень прямолинейный: “дай контакт по id”.
Коллизии: одинаковый хеш — не конец света
Слово «коллизия» звучит так, будто сейчас будет взрыв сервера и грустный админ в углу. На самом деле коллизия — это нормально: разные ключи могут иметь одинаковый хеш. Контейнер после попадания в корзину всё равно проверяет ==.
Чтобы почувствовать это руками, можно создать нарочно плохой хешер, который всегда возвращает 0. Это будет ужасно по скорости, но корректно по смыслу: все элементы свалятся в одну корзину, а различать их будет ==.
#include <iostream>
#include <string>
#include <unordered_map>
struct AlwaysZeroHash {
std::size_t operator()(const std::string&) const {
return 0;
}
};
int main() {
std::unordered_map<std::string, int, AlwaysZeroHash> cnt;
cnt["apple"] += 1;
cnt["banana"] += 1;
std::cout << cnt["apple"] << '\n'; // 1
std::cout << cnt["banana"] << '\n'; // 1
}
Так делать в реальном коде не надо (разве что вы пишете учебник по страданиям), но пример хорошо показывает логику: коллизии допустимы, потому что финальное решение принимает ==.
Коварная ошибка: поменяли равенство, забыли поменять хеш
Сейчас будет ситуация, которая на практике ломает проекты чаще, чем опечатка в имени переменной. Допустим, вы решили, что ключи-строки нужно сравнивать без учёта регистра: "Ann" и "ann" — один и тот же пользователь.
В unordered_map это возможно: можно передать свой KeyEqual (предикат равенства). Но контракт требует согласованности: раз "Ann" и "ann" равны по вашему KeyEqual, то и хеш должен быть одинаковым, иначе контейнер станет «не находить» то, что “по смыслу” есть.
Покажем плохую версию: равенство без регистра, а хеш обычный (регистрозависимый). Это пример того, как нарушается контракт.
#include <cctype>
#include <string>
#include <unordered_map>
struct CaseInsensitiveEq {
bool operator()(const std::string& a, const std::string& b) const {
if (a.size() != b.size()) return false;
for (std::size_t i = 0; i < a.size(); ++i) {
if (std::tolower((unsigned char)a[i]) != std::tolower((unsigned char)b[i]))
return false;
}
return true;
}
};
int main() {
// Хеш остался стандартный (регистрозависимый) — контракт нарушен.
std::unordered_map<std::string, int, std::hash<std::string>, CaseInsensitiveEq> m;
m.emplace("Ann", 10);
// В реальности такой код может начать вести себя “странно”:
// find("ann") может не найти "Ann", хотя CaseInsensitiveEq считает их равными.
}
Важный момент: я специально не показываю «как правильно сделать хеш без регистра», потому что это уже территория следующей лекции про пользовательские ключи и std::hash<Key>. Сегодня вам нужно вынести главное: в unordered_map равенство и хеш обязаны смотреть на ключ одинаковыми глазами. Требования к Hash и Pred — часть контракта контейнера.
4. Как выбрать: map или unordered_map
Когда вы выбираете контейнер, полезно думать не «что быстрее в вакууме», а «какой контракт проще и естественнее для моего ключа». Иногда порядок вам реально нужен: например, вы хотите печатать контакты по алфавиту без отдельной сортировки. Иногда порядок не важен, и вы хотите просто быстрый поиск по id.
Вот таблица, которая помогает принять решение без гадания на кофейной гуще:
| Вопрос про ваш сценарий | Обычно проще выбрать | Почему |
|---|---|---|
| Нужен упорядоченный вывод по ключу | |
Контейнер хранит элементы отсортированными относительно comp. |
| Хочу быстрый “ключ → значение”, порядок не важен | |
Поиск идёт через хеширование + проверку равенства |
| Ключ “естественно упорядочивается” (числа, строки, пары) | |
operator< уже корректен, контракт простой |
| Ключ “естественно сравнивается на равенство”, но порядок странный | |
Равенство/хеш часто проще, чем придумывать порядок |
| Я хочу особую логику равенства | std::unordered_map (но аккуратно) | Нужно синхронно определить и KeyEqual, и Hash |
5. Типичные ошибки
Ошибка №1: думать, что map использует == для уникальности.
Новичок часто ожидает, что контейнер «сравнит ключи на равенство», как в обычной логике. Но map живёт в мире порядка: если компаратор не может различить два ключа (ни один не меньше другого), ключи считаются эквивалентными. В итоге разные объекты могут “склеиться” в один элемент, и это выглядит как мистика, пока не вспомнишь контракт.
Ошибка №2: писать компаратор через <= или делать его нестрогим.
Компаратор в map/set — это “строго раньше”, а не “раньше или равно”. Когда вы используете <=, контейнер может получить противоречивую картину мира: ключ оказывается “меньше самого себя”, и внутренние предположения ломаются. Даже если код «как-то работает», это не тот случай, когда стоит радоваться.
Ошибка №3: сравнивать не все поля, которые определяют уникальность ключа.
Если ключ — это несколько полей (например, фамилия+имя), а компаратор учитывает только фамилию, то контейнер начнёт считать всех людей с одной фамилией одним и тем же ключом. Это не «ошибка STL», это неверно сформулированный контракт, который приводит к потере данных.
Ошибка №4: в unordered_map менять правило равенства и забывать про хеш.
Самая коварная ловушка: вы делаете “равенство без регистра” (или сравнение только части полей), но оставляете старый хеш. Контейнер начинает вести себя нелогично: find() не находит элемент, который «точно добавляли». Причина в том, что по контракту равные ключи обязаны иметь одинаковый хеш, иначе элементы попадают в разные корзины. Требования к Hash и Pred как раз про это.
Ошибка №5: ожидать, что unordered_map хранит элементы в стабильном порядке.
Иногда хочется «просто распечатать словарь» и получить один и тот же порядок, как в map. Но unordered_map не обещает порядок обхода: он зависит от хешей, корзин, внутренней организации и даже от того, как именно вы добавляли/удаляли элементы. Если порядок важен — выбирайте map или сортируйте отдельно, но не стройте логику на порядке unordered_map.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ