Контейнер map в C++: учебные примеры словаря для школьников

std::map — контейнер стандартной библиотеки C++ для пар «ключ — значение». Например, в учебном проекте школьника по имени участника можно находить число баллов за тест. Ключи уникальны с точки зрения заданного сравнения, а обход идёт в порядке этого сравнения; по умолчанию для строк это лексикографический порядок. В уроке разберём примеры C++17: вставку, поиск и подсчёт слов. Сбалансированное дерево — типичный способ реализации, но конкретный вид дерева стандартом не предписан.

Создание и наполнение

В этом примере marks хранит баллы за учебный тест с максимумом 10, а не школьные отметки по пятибалльной шкале. Синтаксис структурного связывания в цикле требует C++17.

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<std::string, int> marks;
    marks["Anna"] = 9;
    marks["Boris"] = 7;
    for (const auto& [name, mark] : marks) {
        std::cout << name << '=' << mark << ' ';
    }
}

Квадратные скобки работают интуитивно: marks["Anna"] = 9; либо создаёт пару с ключом "Anna", либо перезаписывает значение, если ключ уже есть.

Два способа вставки и их ловушка

Следующие фрагменты продолжают первую программу внутри main после заполнения marks.

Пример 1. Перезапись против бездействия. Повторное присваивание через operator[] заменяет значение, а вставка insert существующего ключа ничего не делает — вставляется только отсутствующий ключ:

marks["Anna"] = 9;
marks["Anna"] = 10;               // перезапись: значение 10
marks.insert({"Anna", 5});        // не сработает: ключ уже есть
marks.insert({"Vera", 8});        // добавилась новая пара
std::cout << marks.size();        // выведет 3

Пример 2. operator[] создаёт элемент даже при чтении. Строка int v = marks["Olga"]; для отсутствующего ключа не бросает ошибку, а создаёт пару со значением по умолчанию (для int — 0) и возвращает его. После предыдущего фрагмента v равен 0, а размер контейнера вырастает с 3 до 4. Если нельзя допускать новую запись, проверяйте ключ через count или find. В следующем примере Olga уже добавлена предыдущим чтением, поэтому count вернёт 1. Для отсутствующего Petr find вернёт end():

if (marks.count("Olga") > 0) {   // есть ли ключ
    std::cout << marks["Olga"];
}
auto it = marks.find("Petr");     // it == marks.end(), если ключа нет
if (it != marks.end()) {
    std::cout << it->second;      // значение без лишней вставки
}

Порядок обхода и сложность

Итераторы map идут по возрастанию ключей — у нашего словаря это лексикографический порядок строк: до чтения отсутствующего Olga обход выдаёт Anna=10 Boris=7 Vera=8 независимо от порядка вставки. После чтения появится ещё Olga=0. Замена компаратора (например, std::greater<std::string> в шаблоне) переворачивает порядок. Для std::greater явно подключите <functional>. Поиск и удаление по ключу, а также обычная вставка одной пары имеют сложность O(log n) по числу элементов. Это не обещание точного количества шагов или времени: стоимость сравнения строк тоже зависит от их длины. Удаление по известному итератору имеет амортизированную сложность O(1), а очистка всего контейнера — O(n). Если дубликаты ключей нужны, существует близкий контейнер std::multimap; если требуется найти первый ключ не меньше заданного, помогает lower_bound; upper_bound ищет первый ключ строго больше заданного при обычном сравнении. Оба могут вернуть end(). У unordered_map таких методов нет.

map против unordered_map

Если порядок не нужен, а важна скорость точечного поиска, выбирают unordered_map; если нужны диапазоны и обход по порядку — map. Та же дилемма «дерево против хеш-таблицы» знакома и по Java: её разбор есть в материале об иерархии коллекций Java.

Типовая задача: подсчёт слов

Пример 3. Частотный словарь. Map удобен там, где значение накапливается по ключу. Внутри main сначала задайте std::vector<std::string> words = {"the", "cat", "the"}; и подключите в начале файла <vector>, <string>, <map> и <iostream>:

std::map<std::string, int> freq;
for (const std::string& w : words) {
    freq[w]++;   // нет ключа — создаст 0 и увеличит до 1
}
std::cout << freq["the"];   // сколько раз встретилось слово

Идиома freq[w]++ сочетает обе роли operator[]: создание элемента со значением по умолчанию и возврат ссылки на значение, которое тут же увеличивается. Для последовательности слов "the cat the" словарь построит пары cat=1, the=2, и обход выдаст их в алфавитном порядке ключей. Удаление выполняют через m.erase(k) (по ключу) или m.erase(it) (по итератору); очистка — m.clear(), проверка пустоты — m.empty().

Упражнения

Задание 1

Что выведет обход изначально пустого map после операций: m["x"] = 1; m["a"] = 2; m["x"] = 3; m.insert({"b", 4});?

Ответ 1: a=2 b=4 x=3. Обход идёт по возрастанию ключей; повторное присваивание m["x"] перезаписало значение, а insert("x") не выполнился бы, но здесь вставлен новый ключ "b".

Задание 2

Чему равен размер map после кода std::map<std::string,int> m; int v = m["key"];?

Ответ 2: 1. Чтение через operator[] для отсутствующего ключа создаёт элемент со значением по умолчанию (v равен 0), это значение для int при такой вставке.

Задание 3

Как проверить, есть ли ключ в map, не создавая новый элемент?

Ответ 3: использовать count(k) (возвращает 0 или 1 для map) либо find(k) и сравнить результат с end(). Обращение m[k] для проверки не подходит — оно вставляет пару.

Задание 4

Пусть m изначально пуст. Что произойдёт при m.insert({"a", 1}); m.insert({"a", 2}); и чему будет равно m["a"]?

Ответ 4: вторая вставка проигнорируется, так как ключ "a" уже существует; m["a"] равно 1. Изменить значение можно, например, через operator[], m.at("a") = 2 или insert_or_assign (C++17). at не добавляет отсутствующий ключ, а выбрасывает std::out_of_range. Через найденный итератор меняют it->second; сам ключ it->first менять нельзя.

Задание 5

Нужно 1000000 раз проверять наличие записи по строковому ключу и при этом периодически обходить записи в алфавитном порядке. Какой контейнер выбрать?

Ответ 5: std::map: обеспечит и O(log n) поиск, и обход по возрастанию ключей. unordered_map дал бы более быстрый средний поиск, но не гарантировал бы порядок обхода, который здесь требуется.

Задание 6

Может ли std::map хранить два разных значения с одним ключом, если вставлять их через insert?

Ответ 6: нет. Уникальность ключей — гарантия контейнера: вторая вставка с существующим ключом игнорируется. Для нескольких значений на ключ предназначен std::multimap, либо в качестве значения используют контейнер, например map<string, vector<int>>.

Как понимать уникальность ключей

Два ключа считаются эквивалентными, если компаратор не ставит ни один из них перед другим: !comp(a,b) && !comp(b,a). Это не обязано совпадать с operator==. Пользовательский компаратор должен задавать строгий слабый порядок. Вставка не портит существующие итераторы, а erase делает недействительными только итераторы и ссылки на удалённые элементы.

Источники и материалы

• C++ working draft: map.overview
• C++ working draft: map.access
• C++ working draft: associative.reqmts
• C++ working draft: unord.req