Словари - Язык программирования C++ для спортивного программирования
Неделя 11Множества, Словари, Мультимножества и Обработка данных по ключу
Словари
Словарь хранит значение для каждого ключа: добавление и замена, подсчёт через cnt[x]++, обход в порядке ключей, поиск без добавления, удаление ключей в скользящем окне, таблицы соответствия и пары в роли ключей.
Теория
Урок 3 из 7
29 мин чтения
Вопросов: 6
Множество помнит, какие значения оно видело. Словарь (map) помнит что-то
для каждого ключа: номер телефона для каждого имени, счётчик для каждого
слова, цену для каждого блюда в меню. Это таблица пар ключ → значение, где
каждый ключ встречается один раз, а ключи отсортированы.
Значение для каждого ключа
map<K, V> задаёт два типа: тип ключа и тип значения. m[key] = value
добавляет ключ или заменяет его значение, если ключ уже есть, — один и тот же
ключ словарь дважды не хранит. m[key] само по себе читает значение, а
m.size() — это количество ключей.
Подсчёт с помощью словаря
Чаще всего словарь в решении что-то считает:
Когда x встречается впервые, такого ключа ещё нет. Тогда cnt[x]добавляет его со значением 0 — начальным значением для любого числа, — а
++ делает его равным 1. Дальше каждое cnt[x]++ находит ключ и прибавляет
единицу. Посмотрите, как появляются ключи:
Каждый элемент словаря — пара: p.first — ключ, p.second — его значение.
Цикл for по словарю посещает их по возрастанию ключа — и больше этой задаче
ничего не нужно:
В первой строке n, во второй — n слов. Выведите, сколько среди них
различных слов, а затем каждое различное слово в алфавитном порядке вместе с
тем, сколько раз оно встретилось.
Для ввода 7 и sun rain sun snow rain sun fog программа печатает
cnt.size() — число различных слов, а обход идёт по алфавиту без всякой
сортировки с вашей стороны. На Codeforces и AtCoder (C++17 и новее) можно
встретить и for (auto [word, c] : cnt); старые компиляторы, например во
многих установках Code::Blocks, такую строку не принимают, а p.first и
p.second работают везде.
Посмотреть, не добавляя
m[key]добавляет ключ, если его нет, — со значением 0 для числа или
пустой строкой для string. Для подсчёта это ровно то, что нужно, а когда вы
хотели только посмотреть — тихая ошибка:
Программа печатает 0, 3, 0, 3, cake costs 12 и 2. Чтение
price["juice"] дало 0 — и добавило "juice" в словарь; убрал его оттуда
только erase в конце. count и find только смотрят:
m.count(key) равно 1, если ключ есть, и 0, если нет;
m.find(key) даёт позицию ключа или m.end(), если его нет. В этой позиции
it->first — ключ, а it->second — его значение.
Итак: [] — когда вы всё равно будете записывать значение (cnt[x]++,
m[key] = v), а count или find — когда хотите только спросить.
Попробуйте на телефонной книге — и посмотрите, что на самом деле делает с ней
каждая строка:
Телефонная книгапопробуй!
Удаление ключа
m.erase(key) удаляет ключ вместе с его значением; если ключа нет, ничего не
происходит.
Это нужно, когда счётчики не только растут, но и уменьшаются.
Классический пример — окно: k значений подряд, начиная с какой-то
позиции:
Дан массив из n чисел и длина окна k. Для каждого окна из k значений
подряд выведите, сколько в нём различных значений.
Храните в словаре счётчики значений внутри окна. Когда окно сдвигается на шаг
вправо, одно значение входит справа и одно выходит слева — меняются два
счётчика, и больше ничего пересчитывать не нужно. Ответ для каждого окна —
cnt.size(), но с одной ловушкой: ключ, чей счётчик упал до 0, всё равно
остаётся ключом, и cnt.size() его считает. Поэтому, когда счётчик доходит до
нуля, удаляйте ключ — тогда cnt.size() будет числом значений, которые
действительно есть в окне. Вот все окна из 3:
Окно сдвигается: одно значение входит, одно выходит
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a = {5, 7, 5, 9, 9, 5};
9 int k = 3;
10 map<int, int> cnt; // значение -> сколько его копий в окне
11 for (int i = 0; i < (int)a.size(); i++) {
12 cnt[a[i]]++; // a[i] входит в окно
13 if (i >= k) {
14 cnt[a[i - k]]--; // a[i - k] выходит из него
15 if (cnt[a[i - k]] == 0) {
16 cnt.erase(a[i - k]); // копий не осталось: удаляем ключ
17 }
18 }
19 if (i >= k - 1) {
20 cout << cnt.size() << " ";
21 }
22 }
23 cout << "\n";
24 return 0;
25}
Значения
строка 8
Для каждых 3 значений подряд посчитаем, сколько среди них различных.
a6 ячеек
5
7
5
9
9
5
0
1
2
3
4
5
map<int, int> cntСловарь
пусто
k—i—
нажми пуск
1 / 40
Таблицы соответствия
Словарь можно один раз заполнить самому, а потом переводить с его помощью
названия в числа, с которыми можно считать, — дни недели, месяцы, шахматные
фигуры. Например:
В первой строке q. В каждой из следующих q строк — два дня недели,
записанные как Mon, Tue, Wed, Thu, Fri, Sat или Sun. Для каждой
строки выведите, на сколько дней вперёд второй день отстоит от первого.
Для Mon Thu, Fri Tue и Sun Sun программа печатает 3, 4 и 0.
day[to] - day[from] может быть
отрицательным, а в C++ -3 % 7 равно -3, а не 4. Исправить это помогает
прибавление 7 и ещё одно % 7: (d % 7 + 7) % 7 лежит в 0..6 для любого
целого d.
Ключи любого вида
Ключом может быть любой тип, который можно сравнивать через <: int, long long
(номера до 10¹⁸), char, string — и pair, когда один объект описывается
двумя числами, например точка на сетке. Пары сравниваются по first, а при
равных first — по second. Задача, где ключи — точки:
В первой строке n, в следующих n строках — по точке x y; одна и та же
точка может встретиться несколько раз. Выведите каждую различную точку один
раз, по возрастанию x, а при равных x — по y, и сколько раз она
встретилась.
Для точек (1, 2), (3, -1), (1, 2), (0, 0), (1, 2) программа печатает
{x, y} создаёт пару прямо внутри скобок: cnt[{x, y}], cnt.count({x, y}),
cnt.erase({x, y}).
Сколько это стоит
Словарь — это сбалансированное дерево ключей, как и множество: [], count,
find и erase занимают примерно log₂ n шагов каждая, а обход — n. Со
строковыми ключами каждый шаг ещё и сравнивает две строки, так что длинные
ключи обходятся чуть дороже.
В чужих решениях вам встретится unordered_map. Он делает то же самое, но не
держит ключи по порядку и часто работает быстрее — однако на Codeforces под него
можно специально построить тесты, на которых он очень медленный. map —
надёжный выбор.
Проверьте себя
А вы знали?
Первый словарь, объяснявший английские слова по-английски, — A Table
Alphabeticall Роберта Кодри — вышел в 1604 году и содержал около 2 500
«трудных употребительных английских слов». Это был словарь в смысле map: из
слов в значения, отсортированный по ключу. В предисловии читателям советовали
сначала выучить порядок букв, чтобы открывать нужную часть книги, а не читать
с начала, — примерно так и работает find.
map<string, int> phone; // ключ — имя, значение — номерphone["Mia"] = 4021; // добавляет ключ "Mia"phone["Ali"] = 3310;phone["Mia"] = 5577; // "Mia" уже есть среди ключей: значение заменяетсяcout << phone["Mia"]; // 5577cout << phone.size(); // 2
cnt[x]++;
проверь себя1 балл
m — пустой map<string, int>. Что напечатают эти две строки?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
if (cnt[x] > 0) только смотрит в словарь и никогда его не меняет.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Чему равно cnt.size() после этих строк?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает программа?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Ключи добавляют в map<string, int> в порядке "pear", "fig", "apple". Какой ключ цикл for по словарю посетит первым?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В map<pair<int, int>, int> есть ключи {2, 1}, {1, 5} и {1, 2}. Какой ключ идёт первым при обходе?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
4 different words
fog 1
rain 2
snow 1
sun 3
0 0: 1
1 2: 3
3 -1: 1
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; map<string, int> cnt; // слово -> сколько раз оно встретилось for(int i = 0; i < n; i++){ string w; cin >> w; cnt[w]++; // новое слово начинается с 0 и становится 1} cout << cnt.size()<< " different words"<< "\n"; for(auto p : cnt){ // ключи в алфавитном порядке cout << p.first<< " "<< p.second<< "\n";} return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); map<string, int> price; price["tea"] = 5; price["cake"] = 12; cout << price["juice"]<< "\n"; // осторожно: [] добавляет "juice" со значением 0 cout << price.size()<< "\n"; // теперь ключей 3 cout << price.count("milk")<< "\n"; // count() только смотрит: 1 или 0 cout << price.size()<< "\n"; // всё ещё 3 auto it = price.find("cake"); // find() даёт место ключа или end(), если ключа нет if(it != price.end()){ cout << it->first<< " costs "<< it->second<< "\n";} price.erase("juice"); // удаляет ключ и его значение cout << price.size()<< "\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); vector<string> names ={"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"}; map<string, int> day; // таблица соответствия: название -> его номер for(int i = 0; i < 7; i++){ day[names[i]] = i;} int q; cin >> q; for(int i = 0; i < q; i++){ string from, to; cin >> from >> to; int d = day[to] - day[from]; // может быть отрицательным: от Fri до Tue это 1 - 4 = -3 d =(d % 7 + 7) % 7; // превращает любое целое число в 0..6 cout << d << "\n";} return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; map<pair<int, int>, int> cnt; // ключ — точка (x, y) целиком for(int i = 0; i < n; i++){ int x, y; cin >> x >> y; cnt[{x, y}]++; // {x, y} создаёт пару} for(auto p : cnt){ // по x, а при равных x — по y cout << p.first.first<< " "<< p.first.second<< ": "<< p.second<< "\n";} return 0;}