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

Контейнеры map и unordered_map предоставляют оператор индексирования и соответствующую функцию at() (см. раздел 9.3.2), представленные в табл. 11.6. Типы контейнеров set не поддерживают индексацию, поскольку в наборе нет никакого "значения", связанного с ключом. Элементы сами являются ключами, поэтому операция "доступа к значению, связанному с ключом", бессмысленна. Нельзя индексировать контейнер multimap или unordered_multimap, поскольку с заданным ключом может быть ассоциировано несколько значений.

Таблица 11.6. Операторы индексирования контейнеров map и unordered_map

c[k] Возвращает элемент с ключом k; если ключа k нет в контейнере с, добавляется новый элемент, инициализированный значением с ключом k c.at(k) Проверяет наличие элемента с ключом k; если его нет в контейнере с, передает исключение out_of_range (см. раздел 5.6)

Подобно другим использованным ранее операторам индексирования, оператор индексирования карт получает индекс (т.е. ключ) и возвращает связанное с ним значение. Однако, в отличие от других операторов индексирования, если такого ключа еще нет, создается новый элемент и добавляется в карту для того ключа. Ассоциированное значение инициализируется значением по умолчанию (см. раздел 3.3.1).

Рассмотрим следующий код:

map <string, size_t> word_count; // пустая карта

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

// с ключом Anna; а затем установить для него значение 1

word_count["Anna"] = 1;

Ниже приведена имеющая место последовательность действий.

• В контейнере word_count происходит поиск элемента с ключом Anna. Элемент не найден.

• В контейнер word_count добавляется новая пара ключ-значение. Ключ (константная строка) содержит текст Anna. Значение инициализируется по умолчанию, в данном случае нулем.

• Вновь созданному элементу присваивается значение 1.

Поскольку оператор индексирования способен вставить элемент, его можно использовать только для карты, которая не является константной.

Индексация карт существенно отличается от индексации массивов или векторов: использование отсутствующего ключа приводит к добавлению элемента с таким ключом в карту.

Использование значения, возвращенного оператором индексирования

Иной способ индексирования карт, отличающий его от других использованных ранее операторов индексирования, влияет на тип возвращаемого значения. Обычно тип, возвращенный в результате обращения к значению итератора, и тип, возвращенный оператором индексирования, совпадают. У карт все не так: при индексировании возвращается объект типа mapped_type, а при обращении к значению итератора карты — объект типа value_type (см. раздел 11.3).

Общим у всех операторов индексирования является то, что они возвращают l-значение (см. раздел 4.1.1). Поскольку возвращается l-значение, возможно чтение и запись в элемент:

cout << word_count["Anna"]; // получить элемент по индексу Anna;

                            // выводит 1

++word_count["Anna"];       // получить элемент и добавить к нему 1

cout << word_count["Anna"]; // получить элемент и вывести его;

                            // выводит 2

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

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

Упражнения раздела 11.3.4

Упражнение 11.24. Что делает следующая программа?

map<int, int> m;

m[0] = 1;

Упражнение 11.25. Сравните следующую программу с предыдущей:

vector<int> v;

v[0] = 1;

Упражнение 11.26. Какой тип применяется при индексировании карты? Какой тип возвращает оператор индексирования? Приведите конкретный пример, т.е. создайте карту, используйте типы, которые применимы для ее индексирования, а затем выявите типы, которые будет возвращать оператор индексирования.

11.3.5. Доступ к элементам

Ассоциативные контейнеры предоставляют различные способы поиска заданных элементов, описанные в табл. 11.7. Используемый способ зависит от решаемой задачи. Если нужно лишь выяснить, находится ли некий элемент в контейнере, то, вероятно, лучше использовать функцию find(). Для контейнеров, способных содержать только уникальные ключи, вероятно, не имеет значения, используется ли функция find() или count(). Но для контейнеров с не уникальными ключами функция count() выполняет больше работы: если элемент присутствует, ей все еще нужно подсчитать количество элементов с тем же ключом. Если знать количество не обязательно, лучше использовать функцию find():

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

iset.find(1);   // возвращает итератор на элемент с ключом == 1

iset.find(11);  // возвращает итератор == iset.end()

iset.count(1);  // возвращает 1

iset.count(11); // возвращает 0

Таблица 11.7. Функции поиска элементов в ассоциативном контейнере

Функции lower_bound() и upper_bound() неприменимы для неупорядоченных контейнеров. Оператор индексирования и функция at() применимы только для тех контейнеров map и unordered_map, которые не являются константами. c.find(k) Возвращает итератор на (первый) элемент с ключом k или итератор после конца, если такого элемента нет в контейнере c.count(k) Возвращает количество элементов с ключом k. Для контейнеров с уникальными ключами результат всегда нуль или единица c.lower_bound(k) Возвращает итератор на первый элемент, значение ключа которого не меньше, чем k c.upper_bound(k) Возвращает итератор на первый элемент, значение ключа которого больше, чем k c.equal_range(k) Возвращает пару итераторов, обозначающих элементы с ключом k. Если такового элемента нет, значение обеих переменных-членов равно c.end() Использование функции find() вместо индексирования карт

Для контейнеров map и unordered_map оператор индексирования представляет простейший способ поиска значения. Но, как уже упоминалось, у оператора индексирование есть серьезный побочный эффект: если искомого ключа еще нет в карте, индексирование добавляет элемент с таким ключом. Насколько правильно такое поведение, зависит от обстоятельств. Программа подсчета слов полагалась на тот факт, что использование несуществующего ключа при индексировании приводило к вставке элемента с этим ключом и значением 0.

Иногда мы хотим знать, присутствует ли элемент с заданным ключом, не изменяя карту. Нельзя использовать оператор индексирования для определения наличия элемента, поскольку при его отсутствии оператор индексирования добавит новый элемент с таким ключом. В таких случаях следует использовать функцию find():

if (word_count.find("foobar") == word_count.end())

 cout << "foobar is not in the map" << endl;

Поиск элементов в контейнерах multimap и multiset

Поиск элемента в ассоциативном контейнере с уникальными ключами довольно прост — элемент либо есть в контейнере, либо нет. Для контейнеров с не уникальными ключами все несколько сложнее, так как может существовать несколько элементов с заданным ключом. Когда в контейнере multimap или multiset содержится несколько элементов с одинаковым ключом, они располагаются в контейнере рядом.

Предположим, например, что, имея карту авторов и их книг, следует вывести все книги некоего автора. Эту задачу можно решить тремя способами. Самый очевидный из них — использовать функции find() и count():