Язык программирования C++. Пятое издание полностью

Задачу можно решить иначе, используя функции 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 содержит итераторы, обозначающие диапазон элементов

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