C++ std::map: ключи, значения, поиск и вставка

Поиск по ключу

vector хорош, когда вы обращаетесь по позиции — элемент 0, элемент 1 и так далее. Но часто у вас нет позиции; у вас есть имя, и вам нужно то, что с ним связано: пользователь и его счёт, слово и сколько раз оно встречается, код страны и её столица. Перебирать vector в поисках совпадения — это O(n), и быстро становится медленно.

std::map решает эту задачу. Он хранит пары ключ-значение, держит их отсортированными по ключу и позволяет находить значение по ключу за время O(log n). Подключите <map>, чтобы его использовать:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> читается как «map из ключей string в значения int». Ключи уникальны: присвоите одному и тому же ключу дважды — победит второе значение. Внутри map — это сбалансированное двоичное дерево поиска, поэтому всё остаётся отсортированным, а поиск логарифмический, а не константный.

Вставка элементов

Есть несколько способов добавить записи, и разница между ними важна. Самый распространённый — operator[], который создаёт ключ, если его нет, и возвращает ссылку, которой можно присвоить значение:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // создать + присвоить
    inventory["apples"] += 3;     // чтение-изменение-запись, теперь 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Если вам нужна вставка, которая откажется перезаписывать существующий ключ, используйте insert или emplace. Оба возвращают pair, у которого .second — это bool, сообщающий, действительно ли вставка произошла:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada уже существует
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, без изменений
}

Используйте [], когда нужно «побеждает последняя запись», и insert/emplace, когда существующий ключ нужно оставить нетронутым.

Ловушка operator[]: он вставляет при чтении

Это самая частая ошибка с map. operator[] — это не чистое чтение: если ключа нет, он молча вставляет его со значением по умолчанию (0 для int, "" для string и т. д.) и возвращает ссылку на него. Так что простая проверка ключа через [] изменяет map:

map<string, int> m;
if (m["maybe"] == 0) {   // ОШИБКА: это только что создало "maybe" -> 0
    // ...
}
cout << m.size();        // 1, а не 0 - вы случайно вставили ключ

То же самое подведёт вас и с const map, где operator[] даже не скомпилируется, потому что ему может потребоваться вставка. Чтобы читать без вставки, используйте find, count/contains или at:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: возвращает итератор, == end(), если ключа нет
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) или count (любая версия)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: бросает std::out_of_range, если ключа нет - никогда не вставляет
    cout << "a = " << m.at("a") << "\n";
}

Эмпирическое правило: если вы собираетесь читать, никогда не тянитесь к []. Используйте at, когда ключ обязан существовать, и find/contains, когда его может не быть.

Обход в отсортированном порядке

Поскольку map основан на дереве, обход проходит по ключам в порядке возрастания — всегда и бесплатно. Каждый элемент — это pair<const Key, Value>, поэтому используйте структурированное связывание, чтобы аккуратно распаковать ключ и значение:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // отсутствующие ключи начинаются с 0, затем ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Обратите внимание, что ключ в связывании — const: значение в цикле можно менять через auto&, но ключ изменить на месте нельзя никогда (это нарушило бы порядок сортировки). Вывод получается в алфавитном порядке (blue, sea, sky) без какого-либо шага сортировки — именно поэтому выбирают map, а не хеш-таблицу, когда важен упорядоченный обход.

Идиома wordCount[w]++ — это также канонический пример использования вставки-при-доступе: здесь вы хотите, чтобы отсутствующий ключ начинался с 0, так что [] — правильный инструмент.

Удаление элементов и размер

Удаляйте по ключу с помощью erase, который возвращает, сколько элементов было удалено (0 или 1 для map). Можно также удалять через итератор, полученный от find. Проверяйте состояние контейнера с помощью size() и empty():

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (его не было)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Одна ловушка при удалении внутри цикла: m.erase(it) делает it недействительным, поэтому после этого нельзя выполнить ++it. Безопасный приём начиная с C++11 — it = m.erase(it), который возвращает итератор на следующий элемент. Для разового условного удаления по всему map чище использовать std::erase_if(m, predicate) (C++20).

Далее: unordered_map

std::map даёт вам отсортированные ключи и предсказуемые операции за O(log n), но за этот порядок вы платите при каждом поиске. Когда порядок ключей не важен и нужен просто максимально быстрый поиск, unordered_map меняет отсортированное дерево на хеш-таблицу — доступ в среднем за O(1). Дальше мы увидим, как он работает, когда его среднее константное время выигрывает у логарифма map и какие подводные камни хеширования (пользовательские типы ключей, коллизии в худшем случае) с ним связаны.