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>.