/лава и. Библиотека стандартных шаблонов 453

return 0;

В данном примере любой объект, который вводится в ассоциативный список, представляет собой символьный массив для хранения заканчивающейся

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

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

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

3. Нужно ли определять для объектов оператор <, если эти объекты используются в качестве ключей ассоциативного списка?

14.6. Алгоритмы

Как уже объяснялось, алгоритмы предназначены для разнообразной обработки контейнеров. Хотя в каждом контейнере поддерживается собственный базовый набор операций, стандартные алгоритмы обеспечивают более широкие и комплексные действия. Кроме этого, они позволяют одновременно работать с двумя контейнерами разных типов. Для доступа к алгоритмам библиотеки стандартных шаблонов в программу необходимо включить заголовок <algorithm>.

В библиотеке стандартных шаблонов определяется большое число алгоритмов, которые систематизированы в табл. 14.5. Все алгоритмы представляют собой функции-шаблоны. Это означает, что их можно использовать с контейнерами любых типов. Наиболее показательные варианты такого использования приведены в примерах данного раздела.

Таблица 14.5 ы библиотеки стандартных шаблонов

Алгоритм Назначение

adjacent flnd Выполняет поиск смежных парных элементов в

последовательности. Возвращает итератор первой пары

blnary search Выполняет бинарный поиск в упорядоченной после-

довательности

Таблица Ы. 5 (продолжение)

Алгоритм

Назначение

copy

copy.backward

count count If

equal

equal range

fill

fill n

find

flnd end

find first of findjf

for each

generate generate.ii

includes inp1ace merge

iter swap.

lexicographical compare lower bound

make heap

Копирует последовательность ,

Аналогична функции y(), за исключением того, что перемещает в начало последовательности элементы из ее конца

Возвращает число элементов в последовательности

Возвращает число элементов в последовательности, удовлетворяющих некоторому предикату

Определяет идентичность двух диапазонов

Возвращает диапазон, в который можно вставить элемент, не нарушив при этом порядок следования элементов в последовательности

Заполняет диапазон заданным значением

Выполняет поиск диапазона для значения и возвращает первый найденный элемент

Выполняет поиск диапазона для подпоследовательности. Функция возвращает итератор конца подпоследовательности внутри диапазона

Находит первый элемент внутри последовательности, парный элементу внутри диапазона

Выполняет поиск диапазона для для кото-

рого определенный пользователем унарный предикат возвращает истину

Назначает функцию диапазону элементов

Присваивает элементам в диапазоне значения, вращаемые порождающей функцией

воз-

Определяет, включает ли одна последовательность все элементы другой последовательности

Выполняет слияние одного диапазона с другим. Оба диапазона должны быть отсортированы в порядке возрастания элементов. Результирующая последовательность сортируется

Меняет местами значения, на которые указывают два итератора, являющиеся аргументами функции

Сравнивает две последовательности в алфавитном порядке

Обнаруживает первое значение в последовательности, которое не меньше заданного значения

Выполняет пирамидальную сортировку последовательности (пирамида, на английском языке heap, - полное двоичное дерево, обладающее тем свойством, что значение каждого узла не меньше значения любого из его дочерних узлов. - Примеч. пер.)

Таблица 14.5 (продолжение)

Алгоритм

Назначение

max element merge

- ч ... -mm .tt.uiK: -

min element

mismatch

next perinutat[on nth.element

parti al sort partial sort copy

It-!

partition

IPop heap

prev.pertnutatian

push heap

random shuffle

remove remove lf reiTiove copy remove co py if

replace

replacejf

replace copy

replace copy if

reverse reverse.copy

Возвращает максимальное из двух значений

Возвращает итератор максимального элемента внутри диапазона

Выполняет слияние двух упорядоченных последовательностей, а результат размещает в третьей последовательности

Возвращает минимальное из двух значений

Возвращает итератор минимального элемента внутри диапазона

Обнаруживает первое несовпадение между элементами в двух последовательностях. Возвращает итераторы обоих несовпадающих элементов

Образует следующую последовательности

перестановку

Упорядочивает последовательность таким образом, чтобы все элементы, меньшие заданного элемента Е, располагались перед ним, а все элементы, большие заданного элемента Е, - после него

Сортирует диапазон

Сортирует диапазон, а затем копирует столько элементов, сколько войдет в результирующую последовательность

Упорядочивает последовательность таким образом, чтобы все элементы, для которых предикат возвращает истину, располагались перед элементами, для которых предикат возвращает ложь

Меняет местами первый и предыдущий перед последним элементы, а затем восстанавливает пирамиду

Образует тельности

предыдущую перестановку последова-

Размещает элемент на конце пирамиды f.i - Беспорядочно перемешивает последовательность Удаляет элементы из заданного диапазона

Заменяет элементы внутри диапазона jl. . >

Меняет порядок сортировки элементов диапазона на обратный