3.2. Ассоциативные контейнеры

Ассоциативные контейнеры сопоставляют ключам некоторые значения.

В стандартной библиотеке есть ассоциативные контейнеры, основанные на сбалансированных деревьях поиска (map, set) и контейнеры, основанные на хеш-таблицах (unordered_map, unordered_set). В этих контейнерах ключи уникальны, то есть, не могут повторяться. Также существуют и multi-версии этих контейнеров, в которых допускаются повторы ключей.

Так как C++ — статически типизированный язык, типы ключей и значений должны быть строго зафиксированы на этапе компиляции.

Контейнер std::map

Начнём с контейнера std::map. Он определен в заголовочном файле map. Аналогично вектору, std::map является шаблонным: в угловых скобках нужно указать типы ключей и значений.

Рассмотрим пример:

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

int main() {
    // инициализируем map набором пар {ключ, значение}
    std::map<std::string, int> years = {
        {"Moscow", 1147},
        {"Rome", -753},
        {"London", 47},
    };

    for (const auto& [city, year] : years) {
        std::cout << city << ": " << year << "\n";
    }
}

Вывод программы:

London: 47
Moscow: 1147
Rome: -753

При итерации с помощью ranged-based for возвращаются пары std::pair из константного ключа и значения. Для итерации по элементам мы использовали structured binding, прикрепив ссылки city и year к элементам возвращаемой пары, а также auto для автоматического вывода типа. Согласитесь, это удобнее, чем такая форма записи:

for (const std::pair<const std::string, int>& item : years) {
    std::cout << item.first << ": " << item.second << "\n";
}

Контейнер map реализован как красно-чёрное дерево — сбалансированное дерево поиска с особыми свойствами. Поэтому его элементы при итерации обходятся в порядке возрастания ключей, а на самих ключах должен быть определён оператор < для сравнения.

Внутренне устройство красно-чёрных деревьев мы оставим за рамками этого учебника: для нас важнее научиться пользоваться таким контейнером и знать, что три основных операции — поиск, вставка и удаление элемента — выполняются за логарифмическое время () от числа элементов в контейнере. Покажем, как воспользоваться этими операциями.

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

int main() {
    std::map<std::string, int> data;
    std::string key;
    int value;

    while (std::cin >> key >> value) {
        data[key] = value;  // вставка
    }

    data.erase("hello");  // удаление

    // поиск
    if (auto iter = data.find("test"); iter != data.end()) {
        std::cout << "Found the key " << iter->first << " with the value " << iter->second << "\n";
    } else {
        std::cout << "Not found\n";
    }
}

Рассмотрим эту программу подробнее.

Для вставки мы использовали обращение по ключу в квадратных скобках: data[key] = value. В отличие от вектора или дека, ключ теперь не обязательно является индексом: в нашем случае это строка. Альтернативные способы вставки — data.insert({key, value}) или data.insert_or_assign(key, value).

Эти функции принимают пару из ключа и значения, поэтому нам пришлось обрамить в фигурные скобки key и value, чтобы экземпляр std::pair сконструировался на лету. Если ключ key уже существует в контейнере, то data[key] = value и функция insert_or_assign его перезапишут, а insert — нет (но вернет информацию о старом значении).

Удаляя элемент по ключу, можно не заботиться о его наличии в контейнере: если ключа нет, то функция erase просто ничего не поменяет.

Для поиска элемента мы вызываем функцию find, которая возвращает итератор. Мы пользуемся версией if с инициализатором, чтобы сразу сохранить этот итератор в переменную iter и потом проверить его значение. Такая переменная будет видна только внутри условного оператора: таким образом мы подчеркнём, что iter нам нужен только здесь. Итератор будет либо указывать на пару из найденного ключа и его значения, либо окажется равен значению data.end(), если ключ не найден. Обратиться к найденной паре можно через унарную звёздочку или стрелочку (iter->first означает (*iter).first). Это похоже на указатели, но важно понимать, что итератор ассоциативного контейнера — это не указатель, а самостоятельный объект.

Вернёмся ещё раз к конструкции data[key]. Она возвращает ссылку на значение, которому можно что-то присвоить. Сначала она проверяет, есть ли уже такой ключ в контейнере. Если ключа нет, он тут же вставляется в контейнер со значением по умолчанию (0 для int). Затем возвращается ссылка на значение в контейнере.

Такое поведение оператора [] требует, чтобы контейнер data был изменяемым. Поэтому выражение data[key] не скомпилируется, если data — константа:

void Check(const std::map<std::string, int>& data) {
    if (data["total"] > 0) {  // ошибка компиляции!
        // ...
    }
}

Если мы уверены, что ключ в контейнере есть, то можно воспользоваться функцией at:

void Check(const std::map<std::string, int>& data) {
    if (data.at("total") > 0) {  // OK, это скомпилируется
        // ...
    }
}

Если же ключа всё же не окажется, то at во время работы программы сгенерирует исключение — «цивилизованную» ошибку, которую можно перехватить и обработать. Исключения мы обсудим в параграфе «Обработка исключений».

Задача о подсчёте частот слов

Рассмотрим классическую задачу: построить частотный словарь из текстового файла. Возьмём для тестирования файл text8 с сайта mattmahoney.net. Это архив со словами статей из английской «Википедии» общим объёмом 100 мегабайт. Его часто используют для оценки эффективности алгоритмов сжатия и для машинного обучения систем обработки текстов.

Напишем программу, которая подсчитывает количество повторов для каждого слова. Слова будем читать со стандартного ввода просто до ближайшего пробельного разделителя.

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

int main() {
    std::map<std::string, int> freqs;
    std::string word;
    while (std::cin >> word) {
        ++freqs[word];
    }
    for (const auto& [word, freq] : freqs) {
        std::cout << word << "\t" << freq << "\n";
    }
}

Посмотрите, как мы элегантно добавляем очередное слово в ассоциативный массив через ++freqs[word]! Если слово уже встречалось, то мы просто увеличиваем его частоту. Если такого слова не было, то во freqs автоматически вставится такой ключ со значением 0, и мы тут же увеличим это значение на 1.

Запустим программу, передав ей на вход файл text8, и посмотрим на первые 10 строк её вывода:

$ clang++ --std=c++20 -o count_freqs count_freqs.cpp
$ ./count_freqs < text8 | head
a	325873
aa	276
aaa	57
aaaa	7
aaaaaacceglllnorst	1
aaaaaaccegllnorrst	1
aaaaaah	1
aaaaaalmrsstt	1
aaaaaannrstyy	1
aaaaabbcdrr	1

Мы уже знаем, что итерация по контейнеру map обходит узлы в порядке возрастания ключей. Поэтому мы увидели первые «слова» по алфавиту. Позже мы попробуем сделать так, чтобы слова были отсортированы по убыванию частоты. А сейчас давайте попробуем замерить время работы нашей программы. Скомпилируем её с максимальным уровнем оптимизаций (ключ -O3) и направим её вывод в /dev/null (он нам не нужен). Замеряем время с помощью консольной утилиты time.

$ clang++ --std=c++20 -O3 -o count_freqs count_freqs.cpp
$ time ./count_freqs < text8 > /dev/null
real    0m5,541s
user    0m5,500s
sys     0m0,040s

Конечно, реальное время работы зависит от процессора и других факторов. Но нельзя ли обработать файл быстрее, чем за пять с половиной секунд? В этом нам поможет контейнер std::unordered_map.

Контейнер std::unordered_map

Воспользуемся другой реализацией ассоциативного массива из стандартной библиотеки C++ — хеш-таблицей unordered_map. Само название этого класса подчёркивает, что данные будут храниться не упорядоченными по ключу. Предполагается, что для каждого ключа определена хеш-функция (по умолчанию std::hash<Key>()), а по ней вычисляется номер корзины (bucket), в которую должен попасть ключ.

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

Если хеш-функция достаточно равномерна и корзин достаточно много, то в среднем время поиска, добавления и удаления элементов для unordered_map будет константным ().

Интерфейс unordered_map специально сделан похожим на интерфейс map. Нам будет достаточно заменить только заголовочный файл и имя контейнера:

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> freqs;
    std::string word;
    while (std::cin >> word) {
        ++freqs[word];
    }
    for (const auto& [word, freq] : freqs) {
        std::cout << word << "\t" << freq << "\n";
    }
}

Порядок обхода теперь выглядит произвольным (но на самом деле он диктуется хеш-функцией):

$ clang++ --std=c++20 -o count_freqs count_freqs.cpp
$ ./count_freqs < text8 | head
storerooms	2
fretensis	1
metzada	1
workmans	1
mikhailgorbachev	1
naevus	3
buildups	1
clandenstine	1
democratised	1
wilgoren	2

Время работы сократилось с 5,5 до 3,1 секунды:

$ clang++ --std=c++20 -O3 -o count_freqs count_freqs.cpp
$ time ./count_freqs < text8 > /dev/null
real    0m3,117s
user    0m3,080s
sys     0m0,036s

У контейнера unordered_map есть функция max_load_factor, которая задаёт максимально допустимое соотношение между числом элементов и количеством корзин. По умолчанию эта величина равна единице, так что unordered_map пытается в среднем вообще избежать коллизий. Но это не означает отсутствия коллизий в отдельных корзинах.

Если при вставке очередного элемента среднее число элементов в корзинах превышает этот порог, число корзин автоматически увеличивается и происходит рехеширование. Чем-то это напоминает реаллокацию у вектора.

Если нам заранее известно финальное количество ключей, то можно вызвать заранее функцию reserve и избежать лишних рехеширований при вставках. Тем самым можно отыграть дополнительное время:

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> freqs;
    freqs.reserve(300'000);  // можно использовать апостроф для выделения разрядов
    std::string word;
    while (std::cin >> word) {
        ++freqs[word];
    }
    for (const auto& [word, freq] : freqs) {
        std::cout << word << "\t" << freq << "\n";
    }
}

$ clang++ --std=c++20 -O3 -o count_freqs count_freqs.cpp
$ time ./count_freqs < text8 > /dev/null
real   0m3,067s
user   0m3,035s
sys    0m0,032s

Из контейнера в контейнер

Вернёмся к сортировке слов по убыванию частоты. Для этого проще всего будет переложить слова с частотами в вектор пар и отсортировать его, используя свою функцию сравнения:

#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<std::string, int> freqs;
    std::string word;
    while (std::cin >> word) {
        ++freqs[word];
    }

    // копируем пары в вектор, используя шаблонный конструктор от двух итераторов:
    std::vector<std::pair<std::string, int>> sortedByFreq(
        freqs.begin(),
        freqs.end()
    );

    // сортируем с помощью своей лямбда-функции:
    std::sort(
        sortedByFreq.begin(),
        sortedByFreq.end(),
        [](const auto& p1, const auto& p2) {
            // сначала сравниваем частоты по убыванию, потом — слова по возрастанию
            return std::tie(p2.second, p1.first) < std::tie(p1.second, p2.first);
        }
    );

    for (const auto& [word, freq] : sortedByFreq) {
        std::cout << word << "\t" << freq << "\n";
    }
}

Здесь мы элегантно копируем данные из unordered_map в вектор, указывая при инициализации переменной sortedByFreq пару итераторов другого контейнера. Цикл, копирующий элементы из этого диапазона, скрыт в конструкторе вектора.

Посмотрим на первые 10 результатов с помощью консольной утилиты head. Теперь мы в самом деле получили наиболее частотные слова из файла:

$ clang++ --std=c++20 -o count_freqs count_freqs.cpp
$ ./count_freqs < text8 | head
the	1061396
of	593677
and	416629
one	411764
in	372201
a	325873
to	316376
zero	264975
nine	250430
two	192644

Контейнеры std::set и std::unordered_set

Контейнеры std::set и std::unordered_set похожи на map и unordered_map по внутреннему устройству, но они хранят только ключи, без ассоциированных значений. Вот как можно выписать повторяющиеся слова текста в алфавитном порядке (по одному разу каждое):

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>

int main() {
    // здесь будем хранить все слова (каждое по одному разу)
    std::unordered_set<std::string> words;

    // здесь будем хранить повторяющиеся слова
    // используем set, а не unordered_set, чтобы потом напечатать их по алфавиту
    std::set<std::string> duplicate_words;

    std::string word;
    while (std::cin >> word) {
        if (words.contains(word)) {
            duplicate_words.insert(word);
        } else {
            words.insert(word);
        }
    }

    for (const auto& word : duplicate_words) {
        std::cout << word << "\n";
    }
}

Здесь мы применили функцию contains, которая появилась только в C++20. При использовании более старого стандарта нужно написать if (words.find(word) != words.end()).

Заметим, что при попадании в else мы ищем слово в words дважды: один раз для проверки в contains, а другой раз — в insert. Можно было бы обойтись только одним поиском, воспользовавшись тем, что insert возвращает пару из итератора на элемент и флажка с результатом поиска:

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>

int main() {
    std::unordered_set<std::string> words;
    std::set<std::string> duplicate_words;
    std::string word;
    while (std::cin >> word) {
        auto [iter, has_been_inserted] = words.insert(word);
        if (!has_been_inserted) {
            duplicate_words.insert(word);
        }
    }
    for (const auto& word : duplicate_words) {
        std::cout << word << "\n";
    }
}

Название set происходит от математического понятия множества, где элементы хранятся только по одному разу. Однако никаких теоретико-множественных операций (объединения, пересечения, разности) у set и unordered_set не предусмотрено. В параграфе «Алгоритмы» мы рассмотрим алгоритмы для выполнения таких операций над отсортированными последовательностями.

Мультиконтейнеры

В стандартной библиотеке C++ есть четыре мультиконтейнера:

• std::multimap (в заголовочном файле map);
• std::multiset (в заголовочном файле set);
• std::unordered_multimap (в заголовочном файле unordered_map);
• std::unordered_multiset (в заголовочном файле unordered_set).

Они аналогичны обычным ассоциативным контейнерам, которые мы рассматривали выше, но в мультиконтейнерах один и тот же ключ может встретиться несколько раз.

Пусть, например, мы хотим сохранять для каждого слова в текстовом файле его порядковый номер. Слова в тексте могут повторяться, поэтому воспользуемся контейнером multimap:

#include <iostream>
#include <map>

int main() {
    std::multimap<std::string, int> positions;

    std::string word;
    int position = 0;
    while (std::cin >> word) {
        positions.insert({word, position});
        ++position;
    }
}

В этом случае мы могли бы применить вместо std::multimap<std::string, int> контейнер std::map<std::string, std::vector<int>>. Разница будет в использовании и в накладных расходах.

Для обхода multimap потребуется один цикл, а для map с вектором — два вложенных цикла (по ключам и по элементам вектора для данного ключа). Вектор имеет накладные расходы на хранение метаинформации и резерва, а в multimap все данные будут храниться в одном сбалансированном дереве.

Наконец, итераторы multimap стабильны, а у вектора могут инвалидироваться. Применять multimap имеет смысл там, где повторы ключей сравнительно редки.

Итераторы ассоциативных контейнеров

Контейнеры map, set и их мультиверсии предоставляют двусторонние итераторы, которые можно сдвигать на соседние позиции вперёд и назад. Как и в случае последовательных контейнеров, запрещено выходить за пределы диапазона, ограниченного begin() и end(), и разыменовывать итератор, равный end(). Итераторы таких контейнеров и ссылки (указатели) на элементы никогда не инвалидируются.

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

int main() {
    std::map<int, std::string> numbers = {
        {100, "hundred"},
        {3, "three"},
        {42, "forty two"},
        {11, "eleven"},
    };

    auto iter = numbers.find(11);

    if (iter != numbers.end()) {
        // печатаем найденный элемент
        const auto& [key, value] = *iter;
        std::cout << "Found: " << key << ": " << value << "\n";  // Found: 11: eleven

        // печатаем предыдущий элемент
        if (iter != numbers.begin()) {
            const auto& [key, value] = *std::prev(iter);
            std::cout << "Previous: " << key << ": " << value << "\n";  // Previous: 3: three
        } else {
            std::cout << "No previous element\n";
        }

        // печатаем следующий элемент
        if (auto nextIter = std::next(iter); nextIter != numbers.end()) {
            const auto& [key, value] = *nextIter;
            std::cout << "Next: " << key << ": " << value << "\n";  // Next: 42: forty two
        } else {
            std::cout << "No next element\n";
        }
    } else {
        std::cout << "Not found\n";
    }
}

Может показаться, что в строке const auto& [key, value] = *std::prev(iter) мы строим висячие ссылки, так как возвращаемое значение функции prev после вычисления всего выражения сразу станет невалидным. Однако константные ссылки продлевают жизнь объекта до конца текущего блока.

Итераторы unordered-контейнеров однонаправленные: их можно сдвигать только вперёд. Это связано с тем, что коллизии в хеш-таблице обычно разрешаются с помощью односвязного списка элементов, а по односвязному списку нельзя двигаться назад. Итераторы unordered-контейнеров могут инвалидироваться только если произошло рехеширование при вставке. Ссылки и указатели никогда не инвалидируются.

Отдельно отметим функцию erase у ассоциативных контейнеров. У неё есть несколько перегруженных версий. Одна версия принимает ключ, другая — итератор удаляемого элемента, третья — диапазон итераторов. Разница будет для мультиконтейнеров: если какой-то ключ повторяется, то первая версия erase удалит все вхождения таких ключей, а вторая — только конкретные:

#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> data = {
        {"a", 1},
        {"a", 2},
        {"a", 3},
        {"b", 4},
    };

    auto iter = data.find("a");
    if (iter != data.end()) {
        data.erase(iter);  // удаляем первое найденное вхождение с ключом "a"
    }

    data.erase("a");  // удаляем все остальные вхождения с ключом "a"
}