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

Гарантируется, что перебор контейнера multimapили multisetвозвратит все элементы с заданным ключом.

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

Безусловно, возвращенный этими функциями итератор может указывать на элемент непосредственно после конца контейнера. Если искомый элемент имеет самый большой ключ в контейнере, вызов функции upper_bound()возвратит итератор на элемент после последнего элемента контейнера. Если элемент отсутствует и ключ является самым большим в контейнере, то вызов функции lower_bound()также возвратит итератор на элемент после последнего элемента контейнера.

Итератор, возвращенный функцией lower_bound(), может указывать, а может и не указывать на элемент с заданным ключом. Если такового элемента в контейнере нет, функция lower_bound()возвращает итератор на первую позицию, в которую, согласно порядку расположения элементов, мог бы быть вставлен элемент с данным ключом.

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

// определения authors и search_item как прежде

// итераторы beg и end обозначают диапазон элементов данного автора

for (auto beg = authors.lower_bound(search_item),

end = authors.upper_bound(search_item);

beg != end; ++beg)

cout << beg->second << endl; // вывод каждого заглавия

Эта программа делает то же, что и предыдущая, использовавшая функции count()и find(), но более непосредственно. Вызов функции lower_bound()устанавливает итератор begтак, чтобы он указывал на первый элемент, соответствующий search_item, если он есть. Если его нет, то итератор begукажет на первый элемент с ключом, большим, чем search_item, который может оказаться итератором после конца. Вызов функции upper_bound()присвоит итератору endпозицию элемента непосредственно после последнего элемента с заданным ключом. Эти функции ничего не говорят о том, присутствует ли данный ключ в контейнере. Важный момент заключается в том, что возвращаемые значения формируют диапазон итераторов (см. раздел 9.2.1).

Если элемента с искомым ключом нет, то возвращаемые функциями lower_bound()и upper_bound()значения будут равны. Оба, по сути, укажут позицию вставки элемента с указанным ключом при сохранении текущего порядка элементов контейнера.

Если элементы с заданным ключом есть, то итератор begукажет на первый такой элемент. Приращение итератора begпозволит перебрать элементы с этим ключом. Равенство итератора begитератору end свидетельствует о завершении перебора всех элементов с этим ключом.

Поскольку эти итераторы формируют диапазон, для его перебора можно использовать цикл for. Цикл выполняется нуль или большее количество раз, выводя записи для данного автора, если таковые вообще имеются. Если таких элементов нет, то итераторы begи endравны и цикл не выполняется ни разу. В противном случае инкремент итератора begв процессе вывода каждой связанной с данным автором записи сравняет его в конечном счете с итератором end.

Если функции lower_bound()и upper_bound()возвращают тот же итератор, то заданного ключа в контейнере нет.

Последний способ решения этой задачи самый простой из всех: вместо функций upper_bound()и lower_bound()можно вызвать функцию equal_range().

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

Функцию equal_range()можно использовать для еще одного изменения программы:

// определения authors и search_item, как прежде

// pos содержит итераторы, обозначающие диапазон элементов

// с заданным ключом

for (auto pos = authors.equal_range(search_item);

pos.first != pos.second; ++pos.first)

cout << pos.first->second << endl; // вывод каждого заглавия

Эта программа очень похожа на предыдущую, где использовались функции upper_bound()и lower_bound(). Для хранения диапазона итераторов вместо локальных переменных begи endиспользуется пара, возвращенная функцией equal_range(). Переменная-член firstэтой пары содержит тот же итератор, который возвратила бы функция lower_bound(), а переменная-член second— итератор, который возвратила бы функция upper_bound(). Таким образом, в этой программе значение pos.firstэквивалентно значению beg, a pos.second— значению end.

Упражнение 11.27. Для решения каких видов задач используется функция count()? Когда вместо нее можно использовать функцию find()?

Упражнение 11.28. Определите и инициализируйте переменную, содержащую результат вызова функции find()для карты строк и векторов целых чисел.

Упражнение 11.29. Что возвращают функции upper_bound(), lower_bound()и equal_range(), когда им передается ключ, отсутствующий в контейнере?

Упражнение 11.30. Объясните значение операнда pos.first->second, использованного в выражении вывода последней программы данного раздела.

Упражнение 11.31. Напишите программу, определяющую контейнер multimapавторов и их работ. Используйте функцию find()для поиска элемента и его удаления. Убедитесь в корректности работы программы, когда искомого элемента нет в карте.

Упражнение 11.32. Используя контейнер multimapиз предыдущего упражнения, напишите программу вывода списка авторов и их работ в алфавитном порядке.