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

Ассоциативные контейнеры реализуют упорядоченные структуры данных с возможностью быстрого поиска по ключу. К ассоциативным контейнерам относятся шаблонные классы std::set, std::multiset, std::map и std::multimap. Для хранения элементов в таких контейнерах используются сбалансированные деревья, что обеспечивает логарифмическую сложность операций поиска, вставки и удаления элементов.

Начиная с C++11, в стандартную библиотеку языка были также добавлены неупорядоченные ассоциативные контейнеры, основанные на хеш-таблицах − классы std::unordered_set, std::unordered_multiset, std::unordered_map и std::unordered_multimap. Данные контейнеры обеспечивают среднюю скорость поиска, вставки и удаления O(1). Однако, в худшем случае вычислительная сложность достигает O(N), поэтому неупорядоченные контейнеры стоит использовать с осторожностью.

Шаблонный класс std::set реализует абстрактный тип данных "множество". Из его методов наиболее часто требуются следующие:

• insert − вставляет элементы в множество

• erase − удаляет элементы из множества

• find − выполняет поиск элемента и возвращает итератор на него. Если элемент не найден, возвращается set::end()

• count − возвращает количество элементов с заданным значением. Поскольку в множестве не может быть дубликатов, то результатом может быть только 0 или 1.

• lower_bound − ищет в множестве самый маленький элемент, больший или равный заданному, и возвращает итератор на него

• upper_bound − ищет в множестве самый маленький элемент, строго больший заданного, и возвращает итератор на него

• clear − очищает содержимое контейнера

• size − возвращает количество элементов

• empty − возвращает true, если множество пусто

• begin − возвращает итератор на первый элемент

• end − возвращает итератор на "псевдоэлемент" после последнего

Множество может содержать элементы любого типа, для которого определена операция сравнения '<' (меньше). Если элементами будут объекты нашего собственного класса, то мы либо должны определить в этом классе operator <, либо задать способ сравнения элементов c помощью второго параметра шаблона std::set.

Рассмотрим примеры решения задач с использованием множества. Первая задача звучит так: вводится N чисел, требуется вывести их в порядке возрастания без повторов. Для решения поместим все числа во множество, при этом повторы уберутся автоматически. Далее, поскольку множество − упорядоченный контейнер, то, пройдясь последовательно циклом по его элементам, мы как раз получим их в порядке возрастания.

// Пример 5.17 - вывод входных чисел по возрастанию без повторов

#include <iostream>

#include <set>

int main() {

int n;

std::cin >> n;

std::set<int> s;

for (int i = 0; i < n; i++) {

int x;

std::cin >> x;

s.insert(x);

}

for (int x : s)

std::cout << x << " ";

}

Вторая задача чуть посложнее. Вводится N чисел. Нужно вывести те из них, которые встречаются только один раз. Для решения создадим два множества s1 и s2. Входные числа будем заносить в s1. Если обнаружилось, что число уже имеется в s1, то поместим его в s2. В конце выведем все числа из s1, которые отсутствуют в s2.

// Пример 5.18 - поиск чисел, встречающихся в одном экземпляре

#include <iostream>

#include <set>

int main() {

std::set<int> s1, s2;

int n;

std::cin >> n;

for (int i = 0; i < n; i++) {

int x;

std::cin >> x;

if (s1.count(x) > 0)

s2.insert(x);

s1.insert(x);

}

for (int x : s1)

if (s2.count(x) == 0)

std::cout << x << " ";

}

Третья задача является модификацией предыдущей. Пусть требуется найти такие числа, у которых последняя цифра не встречается ни в одном другом числе. Например, для входных данных 34, 245, 74, 528, 15 ответом будет 528, так как только восьмёрка на конце числа у нас встречается в одном экземпляре.

Для решения этой задачи просто изменим способ сравнения элементов − будем сравнивать числа не обычным образом, а по их последней цифре. Для этого напишем функтор с операцией сравнения по последней цифре и укажем его в качестве второго аргумента шаблонного класса std::set:

// Пример 5.19 - поиск чисел с уникальной последней цифрой

struct lastDigitLess { // функтор для сравнения по последней цифре

bool operator() (int a, int b) const {

return a % 10 < b % 10;

}

};

int main() {

std::set<int, lastDigitLess> s1, s2;

// остальная часть программы не изменилась

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

Шаблонный класс std::multiset реализует абстрактный тип данных "мультимножество". По своему использованию он очень похож на std::set. Основное отличие состоит в том, что мультимножество может содержать дубликаты элементов. Это нужно учитывать при выполнении операций − например, вызов s.erase(5) удалит все пятёрки из множества s, а не одну.

Шаблонный класс std::map реализует абстрактный тип данных "ассоциативный массив" или "словарь". Он хранит упорядоченные пары "ключ-значение" и обеспечивает быстрый поиск по ключу, а также быструю вставку и удаление элементов. Из методов данного класса наиболее часто требуются следующие:

• operator[] − возвращает ссылку на значение элемента по заданному ключу. Если элемент с таким ключом отсутствует в контейнере, то он будет автоматически создан со значением по умолчанию. Поэтому нужно с осторожностью использовать данный оператор, чтобы не получить повышенное потребление памяти.

• at − возвращает ссылку на значение элемента по заданному ключу. Если элемент с таким ключом отсутствует в контейнере, будет возбуждено исключение. Данный метод появился в C++11.

• find − ищет элемент с заданным ключом и возвращает итератор на него. Если элемент не найден, возвращается map::end()

• count − возвращает количество элементов с заданным ключом (0 или 1)

• insert − вставляет элементы в контейнер

• erase − удаляет элементы из контейнера

• clear − очищает содержимое контейнера

• size − возвращает размер контейнера (количество элементов)

• empty − возвращает true, если контейнер пуст

• begin − возвращает итератор на первый элемент

• end − возвращает итератор на "псевдоэлемент" после последнего

Как уже говорилось, элементами словаря являются пары "ключ-значение" (используется класс std::pair). Для обращения к ключу используется поле first, для обращения к значению − поле second.

В качестве примера рассмотрим следующую задачу. Вводится N чисел. Требуется найти число (или числа, если их несколько), которые повторяются наиболее часто. Для решения данной задачи создадим словарь, где ключами будут входные числа, а значениями − количество их повторений. Заполнив словарь, найдём в нём элемент с максимальным значением:

// Пример 5.20 - поиск самых часто повторяющихся чисел

#include <iostream>

#include <map>

#include <algorithm>

int main() {

int n;

std::cin >> n;

std::map<int, int> nums;

for (int i = 0; i < n; i++) {

int x;

std::cin >> x;

nums[x]++;

}

int maxCount = 0;

for (auto &elem : nums)

maxCount = std::max(maxCount, elem.second);

for (auto elem : nums)

if (elem.second == maxCount)

std::cout << elem.first << " ";

}

Класс std::multimap похож на класс std::map. Основное отличие состоит в том, что в нём допускаются дубликаты ключей.