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

11.3.1. Итераторы ассоциативных контейнеров

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

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

auto map_it = word_count.begin();

// *map_it - ссылка на объект типа pair<const string, size_t>

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

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

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

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

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

Итераторы наборов константны

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

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

set<int>::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.3.1

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

Упражнение 11.16. Используя итератор карты, напишите выражение, присваивающее значение элементу.

Упражнение 11.17. С учетом того, что с — контейнер multiset строк, a v — вектор строк, объясните следующие вызовы. Укажите, допустим ли каждый из них:

copy(v.begin(), v.end(), inserter(с, c.end()));

copy(v.begin(), v.end(), back inserter(c));

copy(c.begin(), c.end(), inserter(v, v.end()));

copy(c.begin(), c.end(), back inserter(v));

Упражнение 11.18. Перепишите определение типа map_it из цикла в данном разделы, не используя ключевое слово auto или decltype.

Упражнение 11.19. Определите переменную, инициализированную вызовом функции begin() контейнера multiset по имени bookstore из раздела 11.2.2. Определите тип переменной, не используя ключевое слово auto или decltype.

11.3.2. Добавление элементов

Функция-член insert() (табл. 11.4) добавляет один элемент или диапазон элементов в контейнер. Поскольку карта и набор (и их неупорядоченные версии) содержат уникальные ключи, попытка вставки уже присутствующего элемента не имеет никакого эффекта:

vector<int> ivec = {2,4,6,8,2,4,6,8};    // ivec содержит

                                         // восемь элементов

set<int> set2;                           // пустой набор

set2.insert(ivec.cbegin(), ivec.cend()); // set2 имеет четыре элемента

set2.insert({1,3,5,7,1,3,5,7}); // теперь set2 имеет восемь элементов

Таблица 11.4. Функция insert() ассоциативного контейнера

с.insert(v) с.emplace(args) v — объект типа value_type; аргументы args используются при создании элемента. Элементы карты и набора вставляются (или создаются), только если элемента с данным ключом еще нет в контейнере с. Возвращает пару, содержащую итератор на элемент с заданным ключом и логическое значение, указывающее, был ли вставлен элемент. У контейнеров multimap и multiset осуществляется вставка (или создание) заданного элемента и возвращение итератора на новый элемент с.insert(b, e) с.insert(il) Итераторы b и е обозначают диапазон значений типа с::value_type; il — заключенный в скобки список таких значений. Возвращает void. У карты и набора вставляются элементы с ключами, которых еще нет в контейнере с. У контейнеров multimap и multiset вставляются все элементы диапазона c.insert(p, v) с.emplace(p, args) Подобны функциям insert(v) и emplace(args), но используют итератор p как подсказку для начала поиска места хранения нового элемента. Возвращает итератор на элемент с заданным ключом

Версии функции insert(), получающие пару итераторов или список инициализации, работают подобно соответствующим конструкторам (см. раздел 11.2.1), но добавляется только первый элемент с заданным ключом.

Добавление элементов в карту

При вставке в карту следует помнить, что типом элемента является pair. Зачастую объекта pair, подлежащего вставке, нет. В этом случае пара создается в списке аргументов функции insert():

// четыре способа добавления слова в word_count