Перейти к содержанию

4.3. Структуры отображений (map)

Отображение (map) — это «обобщённый массив», который хранит пары вида ключ → значение.

flowchart LR
    A1["apple"] --> B1[5]
    A2["banana"] --> B2[3]
    A3["orange"] --> B3[8]
Hold "Ctrl" to enable pan & zoom

В обычном массиве ключи — это подряд идущие целые числа 0, 1, …, n-1. В map же:

  • ключи могут быть любого типа (например, string, int, pair<int,int> и т. д.),
  • ключи не обязаны быть последовательными,
  • по ключу можно быстро получить связанное с ним значение.

В стандартной библиотеке C++ есть две основные реализации:

  • map — основан на сбалансированном дереве. Доступ/вставка/удаление работают за O(log n).
  • unordered_map — использует хеширование. Доступ/вставка/удаление работают в среднем за O(1).

Выбор между ними обычно зависит от задачи: map хранит ключи упорядоченными, а unordered_map часто быстрее, но порядок не гарантирует.

1) Пример: словарь «слово → частота/оценка»

Создадим отображение, где ключ — строка, а значение — целое число.

#include <bits/stdc++.h>
using namespace std;

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

    m["apple"] = 4;
    m["orange"] = 3;
    m["piano"] = 9;

    cout << m["orange"] << "\n"; // 3
}

flowchart TB
    A[map&lt;string,int&gt; counts]

    A --> B["counts[apple] = 5"]
    A --> C["counts[banana] = 3"]
    A --> D["counts[orange] = 8"]

    B --> E[Ключ: apple]
    B --> F[Значение: 5]

    C --> G[Ключ: banana]
    C --> H[Значение: 3]

    D --> I[Ключ: orange]
    D --> J[Значение: 8]
Hold "Ctrl" to enable pan & zoom

Важная особенность operator[]

Если вы обращаетесь к m[key], а такого ключа нет, C++ автоматически добавит его в map со значением по умолчанию:

  • для int это 0,
  • для string это пустая строка "",
  • для vector<int> это пустой вектор и т. д.

Пример:

map<string,int> m;
cout << m["unknown"] << "\n"; // 0
// теперь ключ "unknown" реально существует в m

Это удобно для подсчёта частот:

string s;
map<string,int> cnt;
while (cin >> s) {
    cnt[s]++; // если ключа не было, станет 1
}

Но иногда это опасно, потому что вы можете «случайно» засорить структуру лишними ключами.

2) Проверка существования ключа

Чтобы проверить, есть ли ключ, используйте count (вернёт 0 или 1 для map):

if (m.count("unknown")) {
    // ключ существует
}

Альтернатива (часто удобнее, если нужно получить итератор):

auto it = m.find("unknown");
if (it != m.end()) {
    // it->first  — ключ
    // it->second — значение
}

3) Перебор всех пар ключ–значение

map хранит элементы отсортированными по ключу, поэтому перебор идёт в порядке ключей:

for (auto kv : m) {
    cout << kv.first << " " << kv.second << "\n";
}

Если хочется без копирования пары (актуально для больших значений), используйте ссылку:

for (const auto &kv : m) {
    cout << kv.first << " " << kv.second << "\n";
}

4) Когда что выбирать

Выбирайте map, если:

  • нужен упорядоченный перебор ключей,
  • нужны операции вроде lower_bound/upper_bound по ключам,
  • важна гарантированная асимптотика O(log n).

Выбирайте unordered_map, если:

  • порядок ключей не важен,
  • хотите максимальную среднюю скорость (O(1)),
  • ключи хорошо хешируются (стандартные типы — да).