Контейнеры: map, set, multiset
std::map (ассоциативный массив)
Ассоциативный массив – структура данных, которая позволяет нам выполнять различные операции
над парами <ключ, значение>. В С++ ассоциативные массивы представлены в стандартной библиотеке
классом std::map
.
Асимптотическая сложность
- Вставка элемента, обновление значения ключа – \(O(\log N)\).
- Удаление по ключу – \(O(\log N)\).
- Поиск по ключу – \(O(\log N)\).
- Поиск по значению – \(O(N)\) (необходимо итерироваться, пока не будет найдено необходимое значение).
- Подсчёт различных ключей на текущий момент – \(O(1)\).
Стоит помнить, что асимптотическая сложность – по сути теоретический параметр, а на практике
разница между временем работы разных операций одинаковой сложности может быть очень ощутима.
В случае map
, операции сложностью \(O(\log N)\) работают гораздо медленнее, чем, например,
бинарный поиск, и при решении задач об этом необходимо помнить.
Использование
Решим простую задачу, используя map
:
Дана строка \(s\) из \(n\) слов. Необходимо вывести наиболее часто встречающееся слово и количество его вхождений в стрку.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int main() {
// Объявление: map<t1, t2>.
// t1 - тип ключа
// t2 - тип значения
map<string, int> cnt;
int n;
string s;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> s;
// Подсчет количества вхождений каждого слова.
cnt[s]++;
}
int entries = 0;
string word = "";
// Итерирование по map:
// обход производится в порядке возрастания ключей.
for (pair<string, int> i: cnt) {
if (entries < i.second) {
entries = i.second;
word = i.first;
}
}
cout << entries << endl;
cout << word << endl;
}
Множества
Множество (set
) - структура данных, предназначенная для хранения значений и быстрого выполнения на них базовых операций, включая поиск и удаление.
Свойства множеств, которые важны для решения олимпиадных задач:
- Элементы во множестве хранятся в отсортированном по возрастанию виде.
- Множество хранит только одно вхождение любого элемента (в отличие от мультимножества).
Большинство операций с множествами с С++ имеют сложность порядка \(O(\log N)\) операций, однако также не стоит забывать про константу, которая эквивалентна константе map
.
Один из способов интерпретации множеств заключается в том, что множества - это частный случай ассоциативных массивов, где значение отсутсвует, или не берётся во внимание. Это выражается в сходствах как в видах поддерживаемых операций, так и в способе реализации этих структур данных в стандартной библиотеке (красно-чёрные деревья).
Основные операции и асимптотическая сложность
- Вставка элемента – \(O(\log N)\).
- Поиск элемента – \(O(\log N)\).
- Удаление элемента – \(O(\log N)\).
- Подсчёт элементов – \(O(1)\).
Использование
Решим простую задачу, используя множество:
Дан массив \(a\) из \(n \le 10^5\) чисел \(a_i \le 10^9\). Необходимо вывести количество различных элементов в данном массиве.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main() {
// Объявление множества:
// set<type>, где type - тип элементов.
set<int> s;
int n, x;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
// Вставка элементов массива во множество.
s.insert(x);
}
// Вывод размера множества,
// т.е. количества различных элементов в нем.
cout << s.size();
}
Мультимножества
Мультимножество (multiset
) обладает теми же свойствами, что и обычное множество,
за исключением того, что один элемент может входить в мультимножество несколько раз.
На мультимножества можно смотреть как на ассоциативные массивы, где значения –
числа, обозначающие количество вхождений соответствующего ключа в мультимножество.
Структуры на хэш-таблицах
Для всех описанных выше структур данных существуют их аналоги с префиксом
unordered_
(неупорядоченный). Отличие их состоит в том, что они реализованы
с использованием хэш-таблиц, а значит асимптотическая сложность операций на них
равна \(O(1)\) (амортизированно), однако константа еще больше, чем в упорядоченных
структурах, обсуждаемых выше.
Под “амортизированной” сложностью понимается, простыми словами, средняя сложность за большое количество операций. То есть даже при амортизированной сложности \(O(1)\), в одиночном худшем случае сложность может достигать \(O(n)\), однако происходит такое крайне редко.
Неупорядоченность проявляется в том, например, что элементы unordered_map
при итерировании не посещаются в порядке возрастания ключей. Это стоит учитывать
при решении задач, где лишний логарифм в асимптотике может быть критичен.
Подключение библиотек
Если вы по какой-либо причине не используете bits/stdc++.h
, то все упомянутые выше
структуры данных находятся в одноименных библиотеках. Т.е. для использования map
необходимо написать #include <map>
.