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

 

Вектор, связные списки, дек и массив относятся к контейнерам- последовательностям (sequential containers). Их основная общая черта состоит в явном соблюдении порядка хранения элементов. Этот порядок взаимного расположения элементов определяется извне пользователями контейнера, а сами контейнеры-последовательности никак на порядок элементов не влияют.

 

В STL существует принципиально другая категория контейнеров - ассоциативные (associative containers). К таким контейнерам относятся отображения и множества, реализуемые на основе бинарных деревьев и хэш-таблиц. В отличие от последовательностей, порядок вставки и удаления элементов не влияет на порядок, в котором эти элементы хранятся внутри обеспечивающей структуры данных. Напротив, контейнеры на основе бинарных деревьев упорядочивают элементы по возрастанию, а порядок в контейнерах на основе хэш-таблиц вообще заранее не предсказать.

 

Всего предусмотрено 8 ассоциативных контейнеров, отличающихся по 3 признакам:

● базовая структура данных: бинарное дерево поиска или хэш-таблица;

● наличие значений: отображение или множество;

● уникальность либо возможность повторения ключей.

 

Все ассоциативные контейнеры объединяет понятие ключа (key), по которому осуществляются операции поиска, вставки и удаления. Контейнеры -отображения (map) предполагают поиск некоторого значения, связанного с ключом. В контейнерах -множествах (set) значения не используются, а интересует лишь факт наличия или отсутствия ключа. Все контейнеры-отображения в названии содержат суффикс “map”, а все контейнеры-множества - суффикс “set”.

 

В качестве ключей и значений могут быть использованы различные встроенные типы, а также пользовательские типы, при условии, что они отвечают ряду критериев. Набор критериев для типов значений такой же как и для обычных контейнеров-последовательностей: должна быть возможность копирования или перемещения таких объектов. Критерии для типа ключа более жесткие, и имеют различные дополнительные требования в зависимости от базовой структуры данных (бинарные деревья поиска или хэш-таблицы).

 

Контейнеры на основе бинарных деревьев существовали в стандартной библиотеке С++ изначально, потому для названий таких контейнеров не предусмотрено никакого специального префикса/суффикса. Напротив, контейнеры на основе хэш-таблиц были добавлены в стандартную библиотеку лишь начиная с С++11, после окончательного преодоления многолетних разногласий по стандартизации. Все такие контейнеры начинаются с префикса “unordered_”, а не с префикса “hash_” как этого можно было бы ожидать. Это связано с широким распространением нестандартных реализаций хэш-таблиц, пока они не были официально включены в стандарт языка.

 

Чаще всего используют ассоциативные контейнеры без повтора ключей, и такие контейнеры не имеют третьей части в названии. Если ранее использованный ключ добавляется в контейнер повторно, то отображения перезаписывают старое значение новым, а множества - никак не меняют своего состояния. Таким образом, ключ всегда остается уникальным.

 

Допускающие повторения ключей контейнеры получают в названии промежуточный фрагмент “multi”. В мульти-отображениях допускается, что одному ключу может соответствовать несколько значений. Все операции поиска, удаления работают с первым найденным вхождением ключа, а операции вставки не контролируют его уникальность. При необходимости можно просмотреть все значения, соответствующие одному и тому же ключу. Понятие мульти-множества хотя и несколько расходится с теорией дискретной математики, где, по определению, множество может содержать только уникальный набор элементов, однако добавлено в библиотеку для полноты.

 

Таким образом, формируется следующая картина вариантов ассоциативных контейнеров:

● std::map - отображение на основе бинарных деревьев;

● std::set - множество на основе бинарных деревьев;

● std::multimap - - отображение на основе бинарных деревьев с повторением ключей;

● std::multiset - множество на основе бинарных деревьев с повторением ключей;

● std::unordered_map - отображение на основе хэш-таблиц;

● std::unordered_set - множество на основе хэш-таблиц;

● std::unordered_multimap - - отображение на основе хэш-таблиц с повторением ключей;

● std::unordered_multiset - множество на основе хэш-таблиц с повторением ключей.

 

Std::map

 

Контейнер std::map является одним из наиболее часто используемых ассоциативных контейнеров. Поскольку в его основе лежат бинарные деревья поиска, итерирование содержимого должно перебирать пары элементов ключ-значение в порядке возрастания ключа. В связи с этим, std::map часто называют отсортированным отображением. Кроме того, все операции поиска, вставки и удаления в std::map должны характеризоваться логарифмической вычислительной сложностью.

 

Чтобы объявить отображение std::map, минимально необходимо перечислить обязательные аргументы шаблона: тип ключа и тип значения:

 

#include <map>

 

std::map< std::string, double > countriesSquare;

^ ^

тип тип

ключа значения

 

Чтобы разместить в отображении пару ключ-значение, можно использовать синтаксис индексной выборки, как будто присвоение элемента массива:

 

countriesSquare[ “Ukraine” ] = 603.628;

 

Повторная вставка элемента при помощи перегруженного оператора индексной выборки просто перезапишет значение. Существует также более сложная форма вставки при помощи метода insert:

 

countriesSquare.insert(std::make_pair(“Ukraine”, 603.628));

 

Как известно, отображения хранят пары ключ-значения. В стандартной библиотеке С++ этот факт моделируется буквально при помощи утилитарного типа std::pair<K,V>. Такой тип содержит всего 2 элемента: first и second - соответствующих типов, указываемых в угловых скобках. При этом, для обращения к ключу в отображении используется элемент first, а для обращения к значению - элемент second. Это не сложно увидеть при итерировании отображений при помощи интервального цикла for:

 

for (std::pair< std::string, double > p: countriesSquare)

std::cout << p.first << ‘-’ << p.second << std::endl;

 

Запись можно чуть сократить при помощи ключевого слова auto:

 

for (auto p: m1)

std::cout << p.first << ‘-’ << p.second << std::endl;

 

Вспомогательная функция std::make_pair возвращает объект-пару с аргументами-типами на основе типов фактически переданных параметров, чем немного сокращает запись при создании пары. Такой эффект связан с возможностью автоматического вывода типов аргументов шаблонов функций, отсутствующий для классов. В частности нельзя написать следующий код:

std::pair(“Ukraine”, 603.628) // НЕЛЬЗЯ!

 

поскольку при создании объектов шаблонных классов необходимо указывать аргументы-типы:

 

std::pair< std::string, double >(“Ukraine”, 603.628) // ОК, НО ГРОМОЗДКО

 

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

 

std::make_pair(“Ukraine’, 603.628) // ОК + КОМПАКТНО

 

Синоним типа value_type для контейнера map определен следующим образом (где K и V - типы ключа и значения соответственно):

 

typedef std::pair< K, V > value_type;

 

Чтобы считать значение, размещенное в отображении, также можно использовать оператор []:

 

// Ключа существует в отображении, вернет ранее сохраненное значение 603.628

std::cout << countriesSquare[ “Ukraine” ] << std::endl;

 

Если ключ не найден, возвращается значение по умолчанию, предусмотренное для типа значения, кроме того такая новая пара ключ-значение будет вставлена в контейнер:

 

// Ключа не существует в отображении, вернет значение 0.0 и

// вставит новую пару <”Laplandia”,0.0> в отображение

std::cout << countriesSquare[ “Laplandia” ] << std::endl;

 

Если такое поведение не устраивает, можно воспользоваться более строгой формой - метод at(), который выбросит исключение, если ключ отсутствует в отображении:

 

// Если такого ключа нет, будет выброшено исключение

std::cout << countriesSquare.at(“Laplandia”) << std::endl;

 

Такой же метод перегружен и в варианте для записи. Он не подходит для первой вставки пары ключ-значения, а только лишь для ситуации с обновлением значения для ранее размещенного в отображении ключа. Если ключа не существует, аналогично, выбрасывается исключение:

 

countriesSquare.at(“Ukraine”) = 603.629; // ОК: ключ найден, значение обновлено

countriesSquare.at(“Laplandia”) = 1.015; // Исключение: ключа не существует

 

Если программист хочет выяснить наличие того или иного ключа в отображении, можно воспользоваться методом count, возвращающим 1, когда ключ существует, и 0, если ключ не найден:

 

// Ключ найден, метод count вернет 1

std::cout << countriesSquare.count(“Ukraine”) << std::endl;

 

// Ключ не найден, метод count вернет 0

std::cout << countriesSquare.count(“Laplandia”) << std::endl;

 

Метод count() может возвращать значение больше 1 только для мульти-отображений или мульти-множеств, допускающих повторение ключей.

 

В случае, когда необходимо не только выяснить наличие, но и извлечь либо изменить связанное с ключом значение, рекомендуется использовать метод find. Данный метод возвращает итератор:

 

std::map< std::string, double >::iterator it = countriesSquare.find(“Ukraine”)

 

С ключевым словом auto запись заметно преображается:

 

auto it = countriesSquare.find(“Ukraine”)

 

При этом, поскольку отображения хранят пары ключ-значение, итератор std::map также перебирает объекты std::pair< K, V >:

 

// Если ключ найден (результат find не равен end()), выводим сообщение

auto it = countriesSquare.find(“Ukraine”)

if (it!= countriesSquare.end())

std::cout << “Country “ << it->first << “ has square of “

// ^
// обращение к ключу
<< it->second << “ km^2” << std::endl;

// ^
// обращение к значению

 

Также, в ряде задач интерес представляют методы lower_bound, upper_bound и equal_ranges, возвращающие итератор на элемент с ключом не меньшим искомого, не большим искомого и пару из первых двух соответственно. Такие методы привлекательны в задачах, где требуется поиск ближайших соседствующих существующих в отображении ключей.

 

Итераторы отображений относятся к категории двунаправленных (bidirectional). Соответственно, доступны продвижение вперед (++) и назад (--), но не доступны операции, свойственные итераторам с произвольным доступом. Помимо метода find(), итераторы возвращаются стандартной парой методов begin()/end(). Благодаря возможности передвижения в обратном направлении, для std::map также существуют реверс-итераторы, возвращаемые методами rbegin()/rend().

 

При разыменовании итератора std::map с целью записи допускается изменение только значения, но не ключа. Изменение ключа не допускается, поскольку это бы разрушило работу обеспечивающей структуры данных, повлияв на определяемый самим контейнером порядок хранения ключей. Разумеется, для отображений также определены и константные итераторы, которые не допускают модификации ни ключа, ни значения. Такие итераторы возвращаются либо методами begin()/end() на константном контейнере, либо методами cbegin()/cend(), а их эквивалентные реверс-версии - методами crbegin()/crend().

 

Удаление пары ключ-значение осуществляется при помощи метода erase, определенного в 3 вариантах (по ключу, по итератору, по интервалу итераторов):

 

// Удаление по ключу

countriesSquare.erase(“Ukraine”);

 

// Удаление по итератору

countriesSquare.erase(it);

 

// Удаление по интервалу итераторов

auto it2 = it;

for (int i = 0; i < 3; i++)

++it2;

countriesSquare.erase(it, it2);

 

Удаление элементов отображения является единственным сценарием, при котором итератор может оказаться недействительным. В такое состояние может попасть исключительно тот итератор, который ссылается на удаленный элемент.