Стенли Липпман - Язык программирования C++. Пятое издание

Упражнение 11.14. Дополните карту фамилий семей и их детей, написанную для упражнения в разделе 11.2.1, вектором пар, содержащих имя ребенка и день его рождения.

В дополнение к типам, перечисленным в табл. 9.2 (стр. 423), ассоциативные контейнеры определяют типы, перечисленные в табл. 11.3. Они представляют типы ключа и значения контейнера.

Таблица 11.3. Псевдонимы дополнительных типов ассоциативных контейнеров

Для контейнеров типа setтипы key_typeи value_typeсовпадают; содержащиеся в наборе данные являются ключами. Элементами карты являются пары ключ-значение. Таким образом, каждый ее элемент — объект класса pair, содержащий ключ и связанное с ним значение. Поскольку ключ элемента изменить нельзя, ключевая часть этих пар константна:

set::value_type v1; // v1 - string

set::key_type v2; // v2 - string

map::value_type v3; // v3 - pair

map::key_type v4; // v4 - string

map::mapped_type v5; // v5 - int

Подобно последовательным контейнерам (см. раздел 9.2.2), для доступа к члену класса, например типа map::key_type, используется оператор области видимости.

Тип mapped_typeопределен только для типов карт ( unordered_map, unordered_multimap, multimapи map).

При обращении к значению итератора возвращается ссылка на значение типа value_typeконтейнера. В случае карты типом value_typeявляется пара, переменная-член firstкоторой содержит константный ключ, а переменная-член second— значение:

// получить итератор на элемент контейнера word_count

auto map_it = word_count.begin();

// *map_it - ссылка на объект типа pair

cout << map_it->first; // отобразить ключ элемента

cout << " " << map_it->second; // отобразить значение элемента

map_it->first = "new key"; // ошибка: ключ является константой

++map_it->second; // ok: значение можно изменить, используя итератор

Не следует забывать, что типом value_typeкарты является pairи что можно изменять ее значение, но не ключ.

Хотя типы наборов определяют типы iteratorи const_iterator, оба типа итераторов предоставляют доступ к элементам в наборе только для чтения. Подобно тому, как нельзя изменить ключевую часть элемента карты, ключи в наборе также константны. Итератор набора можно использовать только для чтения, но не для записи значения элемента:

set iset = {0,1,2,3,4,5,6,7,8,9};

set::iterator set_it = iset.begin();

if (set_it != iset.end()) {

*set_it = 42; // ошибка: ключи набора только для чтения

cout << *set_it << endl; // ok: позволяет читать ключ

}

Типы mapи setподдерживают все функции begin()и end()из табл. 9.2. Как обычно, эти функции можно использовать для получения итераторов, позволяющих перебрать контейнер. Например, цикл вывода результатов программы подсчета слов из раздела 11.1 можно переписать следующим образом:

// получить итератор на первый элемент

auto map_it = word_count.cbegin();

// сравнить текущий итератор с итератором после конца

while (map_it != word_count.cend()) {

// обратиться к значению итератора, чтобы отобразить

// пару ключ-значение элемента

cout << map_it->first << " occurs "

<< map_it->second << " times" << endl;

++map_it; // прирастить итератор, чтобы перейти на следующий элемент

}

Условие цикла whileи инкремент итератора в теле цикла такие же как в программах вывода содержимого векторов или строк. Итератор map_itинициализирован позицией первого элемента контейнера word_count. Пока итератор не равен значению, возвращенному функцией end(), возвращается текущий элемент, а затем происходит приращение итератора. Оператор вывода обращается к значению итератора map_itдля получения членов пары, оставаясь в остальном тем же, что и в первоначальной программе.

Вывод этой программы имеет алфавитный порядок. При использовании итераторов для перебора контейнеров map, multimap, setи multisetони возвращают элементы в порядке возрастания ключа.

Как правило, с ассоциативными контейнерами обобщенные алгоритмы (см. главу 10) не используются. Тот факт, что ключи константны, означает невозможность передачи итераторов ассоциативных контейнеров алгоритмам, которые пишут или переупорядочивают элементы контейнеров. Таким алгоритмам нужна возможность записи в элементы. Элементы всех типов наборов константны, а у всех типов карт константным является первый член пары.

Ассоциативные контейнеры применимы с теми алгоритмами, которые только читают элементы. Однако большинство этих алгоритмов осуществляет поиск в последовательности. Поскольку поиск элементов в ассоциативном контейнере осуществляется быстро (по ключу), как правило, не имеет смысла использовать для них обобщенный алгоритм поиска. Например, как будет продемонстрировано в разделе 11.3.5, ассоциативные контейнеры определяют функцию-член find(), позволяющую непосредственно выбрать элемент с заданным ключом. Для поиска элемента можно использовать обобщенный алгоритм find(), но он осуществляет последовательный поиск. Поэтому намного быстрее использовать функцию-член find()класса контейнера, чем вызывать обобщенную версию.

На практике, если это вообще происходит, ассоциативный контейнер используется с алгоритмами в качестве исходной последовательности или последовательности назначения. Например, обобщенный алгоритм copy()можно использовать для копирования элементов ассоциативного контейнера в другую последовательность. Точно так же адаптер inserterможно использовать для связи итератора вставки (см. раздел 10.4.1) с ассоциативным контейнером. Адаптер inserterпозволяет использовать ассоциативный контейнер как место назначения для другого алгоритма.

Упражнение 11.15. Каковы типы mapped_type, key_typeи value_typeкарты, переменные-члены пар которой имеют типы intи vector?