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

string search_item("Alain de Botton"); // искомый автор

auto entries = authors.count(search_item); // количество записей

auto iter = authors.find(search_item); // первая запись для этого

                                       // автора

// перебор записей данного автора

while (entries) {

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

 ++iter;    // переход к следующему заглавию

 --entries; // отследить количество выведенных записей

}

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

Гарантируется, что перебор контейнера 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 из предыдущего упражнения, напишите программу вывода списка авторов и их работ в алфавитном порядке.

11.3.6. Карта преобразования слов

Завершим этот раздел программой, иллюстрирующей создание, поиск и перебор карты. Программа получает одну строку и преобразует ее в другую. Программе передаются два файла: первый содержит правила, используемые для преобразования текста во втором файле. Каждое правило состоит из слова, которое может встретиться во входном файле, и фразы, используемой вместо него. Идея в том, чтобы, встретив во вводе некое слово, заменить его соответствующей фразой. Второй файл содержит преобразуемый текст.

Вот содержимое файла преобразования слов.

brb be right back

k okay?

y why

r are

u you

pic picture

thk thanks!

l8r later

Подлежащий преобразованию текст таков:

where r u

y dont u send me a pic

k thk l8r

Программа должна создать следующий вывод:

where are you

why dont you send me a picture

okay? thanks! later

Решение подразумевает использование трех функций. Функция word_transform() будет осуществлять общую обработку. Потребуются два аргумента типа ifstream: первый будет связан с файлом преобразования слов, а второй — с текстовым файлом, который предстоит преобразовать. Функция buildMap() будет читать файл правил преобразования и создавать элемент карты для каждого слова и результата его преобразования. Функция transform() получит строку и, если она есть в карте, возвратит результат преобразования.