Алгоритмы STL

в данной главе описаны все алгоритмы стандартной библиотеки STL. Глава начинается с общего обзора алгоритмов и принципов их работы. Затем приводятся точные сигнатуры всех алгоритмов н примеры их использования.

Заголовочные файлы алгоритмов

Чтобы использовать алгоритмы стандартной библиотеки С++, необходимо включить в программу заголовочный файл <algorithm>:

#lnclude <algorithfTi>

В этом заголовочном файле также определяются вспомогательные функции min(), max() и swap(), представленные иа с. 79 и 81. Итераториая функция iter swap() описана на с. 269.

Некоторые алгоритмы STL, предназначенные для обработки числовых данных, определяются в заголовочном файле <numeric>:

#include <numeric>

Вообще говоря, математическим компонеитам стандартиой библиотеки С++ посвящена глава 12, однако численные алгоритмы рассматриваются в этой главе. На взгляд автора, то, что они являются алгоритмами STL, важнее их численной специализации.

При работе с алгоритмами также часто применяются объекты функций и функциональные адаптеры. Они были описаны в главе 8, а их определения находятся в файле <functional>:

#inc1ude <functional>

В исходной версии STL все алгоритмы отфеделялись в заголовочном файле <algo,h>, В исходной версии STL все алгоритмы определялись н заголовочном ()айла <algo.h>. В исходной версии STL объекты футгкций и функциональные адаптеры определялись в заголовочном файле <function.h>.

Общий обзор алгоритмов

в этом разделе приведен обзор всех алгоритмов стандартной библиотеки С++. Этот обзор даст читателю представление о возможностях алгоритмов и поможет выбрать лучший алгоритм для решения конкретной проблемы.

Введение

Алгоритмы уже были представлены в главе 5. На с. 106 и 121 рассматривалась роль алгоритмов и некоторые важные ограничения, связанные с их использованием. Любой алгоритм STL работает с одним или несколькими интервалами, заданными при помощи итераторов. Для первого интервала обычно задаются обе границы (начало и конец), а для остальных интервалов часто достаточно одного начала, потому что конец определяется количеством элементов в первом интервале. Перед вызовом необходимо убедиться в том, что заданные интервалы действительны, то есть начало интервала предшествует концу или совпадает с ним, а оба итератора относятся к одному контейнеру. Кроме того, дополнительные интервалы должны содержать достаточное количество элементов.

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

Для повышения мощи и гибкости некоторые алгоритмы позволяют передавать пользовательские операции, которые вызываются при внутренней работе алгоритма. Такие операции оформляются в виде функций или объектов функций. Функция, возвращающая логическое значение, называется предикатом. Предикаты применяются в следующих ситуациях.

О Функция (или объект функции), определяющая унарный предикат, может передаваться а.1горитму поиска в качестве критерия поиска. Унарный предикат проверяет, соответствует ли элемент заданному критерию. Например, это позволяет найти первый элемент со значением, меньшим 50.

О Функция (или объект функции), определяющая бинарный предикат, может передаваться алгоритму сортировки в качестве критерия сортировки. Бинарный предикат сравнивает два элемента. Например, с помощью бинарного предиката можно отсортировать объекты, представляющие людей, по фамилиям и по именам (см. пример на с. 296).

О Унарный предикат может использоваться как критерий, определяющий, к каким элементам должна применяться операция. Например, из коллекции можно удалить только элементы с нечетными значениями.

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

Помните, что состояние предиката не должно изменяться вследствие вызова функции (см. с. 303).

Примеры функций и объектов функций, передаваемых в виде параметров алгоритмов, приводятся иа с. 129 и 134, а также в главе 8.

Классификация алгоритмов

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

По названию алгоритма можно получить первое представление о его назначении. Проектировщики STL ввели два специальных суффикса.

О Суффикс jf. Суффикс Jf используется при наличии двух похожих форм алгоритма с одинаковым количеством параметров; первой форме передается значение, а второй - функция или объект функции. В этом случае версия без суффикса Jf используется при передаче значения, а версия с суффиксом, Jf - при передаче функции или объекта функции. Например, алгоритм findO ищет элемент с заданным значением, а алгоритм findjf() - элемент, удовлетворяющий критерию, определенному в виде функции или объекта функции.

Впрочем, не все алгоритмы, получающие функции и объекты функций, имеют суффикс Jf. Если такая версия вызывается с дополнительными аргументами, отличающими ее от других версий, за пей сохраняется прежнее имя. Например, версия алгоритма min element() с двумя аргументами находит в интервале минимальный элемент, при этом элементы сравниваются оператором <. В версии min element() с тремя аргументами третий аргумент определяет критерий сравнения.

О Суффикс сору. Суффикс сору означает, что алгоритм ие только обрабатывает элементы, по и копирует их в приемный интервал. Например, алгоритм reverse() переставляет элементы интервала в обратном порядке, а reverse соруО копирует элементы в другой интервал в обратном порядке.

Приводимые ниже описания алгоритмов делятся на группы:

О немодифицирующие алгоритмы;

О модифицирующие алгоритмы;

О алгоритмы удаления;

О перестановочные алгоритмы;

О алгоритмы сортировки;

О алгоритмы упорядоченных интервалов;

О численные алгоритмы.

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