Ассоциативные контейнеры сопоставляют ключам некоторые значения.
В стандартной библиотеке есть ассоциативные контейнеры, основанные на сбалансированных деревьях поиска (map, set) и контейнеры, основанные на хеш-таблицах (unordered_map, unordered_set). В этих контейнерах ключи уникальны, то есть, не могут повторяться. Также существуют и multi-версии этих контейнеров, в которых допускаются повторы ключей.
Так как C++ — статически типизированный язык, типы ключей и значений должны быть строго зафиксированы на этапе компиляции.
Контейнер std::map
Начнём с контейнера std::map. Он определен в заголовочном файле map. Аналогично вектору, std::map является шаблонным: в угловых скобках нужно указать типы ключей и значений.
Рассмотрим пример:
1#include <iostream>
2#include <map>
3#include <string>
4
5int main() {
6 // инициализируем map набором пар {ключ, значение}
7 std::map<std::string, int> years = {
8 {"Moscow", 1147},
9 {"Rome", -753},
10 {"London", 47},
11 };
12
13 for (const auto& [city, year] : years) {
14 std::cout << city << ": " << year << "\n";
15 }
16}
Вывод программы:
London: 47 Moscow: 1147 Rome: -753
При итерации с помощью ranged-based for возвращаются пары std::pair из константного ключа и значения. Для итерации по элементам мы использовали structured binding, прикрепив ссылки city и year к элементам возвращаемой пары, а также auto для автоматического вывода типа. Согласитесь, это удобнее, чем такая форма записи:
1for (const std::pair<const std::string, int>& item : years) {
2 std::cout << item.first << ": " << item.second << "\n";
3}
Контейнер map реализован как красно-чёрное дерево — сбалансированное дерево поиска с особыми свойствами. Поэтому его элементы при итерации обходятся в порядке возрастания ключей, а на самих ключах должен быть определён оператор < для сравнения.
Внутренне устройство красно-чёрных деревьев мы оставим за рамками этого учебника: для нас важнее научиться пользоваться таким контейнером и знать, что три основных операции — поиск, вставка и удаление элемента — выполняются за логарифмическое время () от числа элементов в контейнере. Покажем, как воспользоваться этими операциями.
1#include <iostream>
2#include <map>
3#include <string>
4
5int main() {
6 std::map<std::string, int> data;
7 std::string key;
8 int value;
9
10 while (std::cin >> key >> value) {
11 data[key] = value; // вставка
12 }
13
14 data.erase("hello"); // удаление
15
16 // поиск
17 if (auto iter = data.find("test"); iter != data.end()) {
18 std::cout << "Found the key " << iter->first << " with the value " << iter->second << "\n";
19 } else {
20 std::cout << "Not found\n";
21 }
22}
Рассмотрим эту программу подробнее.
Для вставки мы использовали обращение по ключу в квадратных скобках: 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 — константа:
1void Check(const std::map<std::string, int>& data) {
2 if (data["total"] > 0) { // ошибка компиляции!
3 // ...
4 }
5}
Если мы уверены, что ключ в контейнере есть, то можно воспользоваться функцией at:
1void Check(const std::map<std::string, int>& data) {
2 if (data.at("total") > 0) { // OK, это скомпилируется
3 // ...
4 }
5}
Если же ключа всё же не окажется, то at во время работы программы сгенерирует исключение — «цивилизованную» ошибку, которую можно перехватить и обработать. Исключения мы обсудим в параграфе «Обработка исключений».
Задача о подсчёте частот слов
Рассмотрим классическую задачу: построить частотный словарь из текстового файла. Возьмём для тестирования файл text8 с сайта mattmahoney.net. Это архив со словами статей из английской «Википедии» общим объёмом 100 мегабайт. Его часто используют для оценки эффективности алгоритмов сжатия и для машинного обучения систем обработки текстов.
Напишем программу, которая подсчитывает количество повторов для каждого слова. Слова будем читать со стандартного ввода просто до ближайшего пробельного разделителя.
1#include <iostream>
2#include <map>
3#include <string>
4
5int main() {
6 std::map<std::string, int> freqs;
7 std::string word;
8 while (std::cin >> word) {
9 ++freqs[word];
10 }
11 for (const auto& [word, freq] : freqs) {
12 std::cout << word << "\t" << freq << "\n";
13 }
14}
Посмотрите, как мы элегантно добавляем очередное слово в ассоциативный массив через ++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. Нам будет достаточно заменить только заголовочный файл и имя контейнера:
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5int main() {
6 std::unordered_map<std::string, int> freqs;
7 std::string word;
8 while (std::cin >> word) {
9 ++freqs[word];
10 }
11 for (const auto& [word, freq] : freqs) {
12 std::cout << word << "\t" << freq << "\n";
13 }
14}
Порядок обхода теперь выглядит произвольным (но на самом деле он диктуется хеш-функцией):
$ 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 и избежать лишних рехеширований при вставках. Тем самым можно отыграть дополнительное время:
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5int main() {
6 std::unordered_map<std::string, int> freqs;
7 freqs.reserve(300'000); // можно использовать апостроф для выделения разрядов
8 std::string word;
9 while (std::cin >> word) {
10 ++freqs[word];
11 }
12 for (const auto& [word, freq] : freqs) {
13 std::cout << word << "\t" << freq << "\n";
14 }
15}
$ 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
Из контейнера в контейнер
Вернёмся к сортировке слов по убыванию частоты. Для этого проще всего будет переложить слова с частотами в вектор пар и отсортировать его, используя свою функцию сравнения:
1#include <algorithm>
2#include <iostream>
3#include <string>
4#include <tuple>
5#include <unordered_map>
6#include <vector>
7
8int main() {
9 std::unordered_map<std::string, int> freqs;
10 std::string word;
11 while (std::cin >> word) {
12 ++freqs[word];
13 }
14
15 // копируем пары в вектор, используя шаблонный конструктор от двух итераторов:
16 std::vector<std::pair<std::string, int>> sortedByFreq(
17 freqs.begin(),
18 freqs.end()
19 );
20
21 // сортируем с помощью своей лямбда-функции:
22 std::sort(
23 sortedByFreq.begin(),
24 sortedByFreq.end(),
25 [](const auto& p1, const auto& p2) {
26 // сначала сравниваем частоты по убыванию, потом — слова по возрастанию
27 return std::tie(p2.second, p1.first) < std::tie(p1.second, p2.first);
28 }
29 );
30
31 for (const auto& [word, freq] : sortedByFreq) {
32 std::cout << word << "\t" << freq << "\n";
33 }
34}
Здесь мы элегантно копируем данные из 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 по внутреннему устройству, но они хранят только ключи, без ассоциированных значений. Вот как можно выписать повторяющиеся слова текста в алфавитном порядке (по одному разу каждое):
1#include <iostream>
2#include <set>
3#include <string>
4#include <unordered_set>
5
6int main() {
7 // здесь будем хранить все слова (каждое по одному разу)
8 std::unordered_set<std::string> words;
9
10 // здесь будем хранить повторяющиеся слова
11 // используем set, а не unordered_set, чтобы потом напечатать их по алфавиту
12 std::set<std::string> duplicate_words;
13
14 std::string word;
15 while (std::cin >> word) {
16 if (words.contains(word)) {
17 duplicate_words.insert(word);
18 } else {
19 words.insert(word);
20 }
21 }
22
23 for (const auto& word : duplicate_words) {
24 std::cout << word << "\n";
25 }
26}
Здесь мы применили функцию contains, которая появилась только в C++20. При использовании более старого стандарта нужно написать if (words.find(word) != words.end()).
Заметим, что при попадании в else мы ищем слово в words дважды: один раз для проверки в contains, а другой раз — в insert. Можно было бы обойтись только одним поиском, воспользовавшись тем, что insert возвращает пару из итератора на элемент и флажка с результатом поиска:
1#include <iostream>
2#include <set>
3#include <string>
4#include <unordered_set>
5
6int main() {
7 std::unordered_set<std::string> words;
8 std::set<std::string> duplicate_words;
9 std::string word;
10 while (std::cin >> word) {
11 auto [iter, has_been_inserted] = words.insert(word);
12 if (!has_been_inserted) {
13 duplicate_words.insert(word);
14 }
15 }
16 for (const auto& word : duplicate_words) {
17 std::cout << word << "\n";
18 }
19}
Название set происходит от математического понятия множества, где элементы хранятся только по одному разу. Однако никаких теоретико-множественных операций (объединения, пересечения, разности) у set и unordered_set не предусмотрено. В параграфе «Алгоритмы» мы рассмотрим алгоритмы для выполнения таких операций над отсортированными последовательностями.
Мультиконтейнеры
В стандартной библиотеке C++ есть четыре мультиконтейнера:
std::multimap(в заголовочном файлеmap);std::multiset(в заголовочном файлеset);std::unordered_multimap(в заголовочном файлеunordered_map);std::unordered_multiset(в заголовочном файлеunordered_set).
Они аналогичны обычным ассоциативным контейнерам, которые мы рассматривали выше, но в мультиконтейнерах один и тот же ключ может встретиться несколько раз.
Пусть, например, мы хотим сохранять для каждого слова в текстовом файле его порядковый номер. Слова в тексте могут повторяться, поэтому воспользуемся контейнером multimap:
1#include <iostream>
2#include <map>
3
4int main() {
5 std::multimap<std::string, int> positions;
6
7 std::string word;
8 int position = 0;
9 while (std::cin >> word) {
10 positions.insert({word, position});
11 ++position;
12 }
13}
В этом случае мы могли бы применить вместо std::multimap<std::string, int> контейнер std::map<std::string, std::vector<int>>. Разница будет в использовании и в накладных расходах.
Для обхода multimap потребуется один цикл, а для map с вектором — два вложенных цикла (по ключам и по элементам вектора для данного ключа). Вектор имеет накладные расходы на хранение метаинформации и резерва, а в multimap все данные будут храниться в одном сбалансированном дереве.
Наконец, итераторы multimap стабильны, а у вектора могут инвалидироваться. Применять multimap имеет смысл там, где повторы ключей сравнительно редки.
Итераторы ассоциативных контейнеров
Контейнеры map, set и их мультиверсии предоставляют двусторонние итераторы, которые можно сдвигать на соседние позиции вперёд и назад. Как и в случае последовательных контейнеров, запрещено выходить за пределы диапазона, ограниченного begin() и end(), и разыменовывать итератор, равный end(). Итераторы таких контейнеров и ссылки (указатели) на элементы никогда не инвалидируются.
1#include <iostream>
2#include <iterator>
3#include <map>
4#include <string>
5
6int main() {
7 std::map<int, std::string> numbers = {
8 {100, "hundred"},
9 {3, "three"},
10 {42, "forty two"},
11 {11, "eleven"},
12 };
13
14 auto iter = numbers.find(11);
15
16 if (iter != numbers.end()) {
17 // печатаем найденный элемент
18 const auto& [key, value] = *iter;
19 std::cout << "Found: " << key << ": " << value << "\n"; // Found: 11: eleven
20
21 // печатаем предыдущий элемент
22 if (iter != numbers.begin()) {
23 const auto& [key, value] = *std::prev(iter);
24 std::cout << "Previous: " << key << ": " << value << "\n"; // Previous: 3: three
25 } else {
26 std::cout << "No previous element\n";
27 }
28
29 // печатаем следующий элемент
30 if (auto nextIter = std::next(iter); nextIter != numbers.end()) {
31 const auto& [key, value] = *nextIter;
32 std::cout << "Next: " << key << ": " << value << "\n"; // Next: 42: forty two
33 } else {
34 std::cout << "No next element\n";
35 }
36 } else {
37 std::cout << "Not found\n";
38 }
39}
Может показаться, что в строке const auto& [key, value] = *std::prev(iter) мы строим висячие ссылки, так как возвращаемое значение функции prev после вычисления всего выражения сразу станет невалидным. Однако константные ссылки продлевают жизнь объекта до конца текущего блока.
Итераторы unordered-контейнеров однонаправленные: их можно сдвигать только вперёд. Это связано с тем, что коллизии в хеш-таблице обычно разрешаются с помощью односвязного списка элементов, а по односвязному списку нельзя двигаться назад. Итераторы unordered-контейнеров могут инвалидироваться только если произошло рехеширование при вставке. Ссылки и указатели никогда не инвалидируются.
Отдельно отметим функцию erase у ассоциативных контейнеров. У неё есть несколько перегруженных версий. Одна версия принимает ключ, другая — итератор удаляемого элемента, третья — диапазон итераторов. Разница будет для мультиконтейнеров: если какой-то ключ повторяется, то первая версия erase удалит все вхождения таких ключей, а вторая — только конкретные:
1#include <unordered_map>
2
3int main() {
4 std::unordered_multimap<std::string, int> data = {
5 {"a", 1},
6 {"a", 2},
7 {"a", 3},
8 {"b", 4},
9 };
10
11 auto iter = data.find("a");
12 if (iter != data.end()) {
13 data.erase(iter); // удаляем первое найденное вхождение с ключом "a"
14 }
15
16 data.erase("a"); // удаляем все остальные вхождения с ключом "a"
17}