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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Немодифицирующие алгоритмы сохраняют как порядок следования обрабатываемых элементов, так и их значения. Они работают с итераторами ввода и прямыми итераторами и поэтому могут вызываться для всех стандартных контейнеров. В табл. 9.1 перечислены алгоритмы стандартной библиотеки STL, не изменяющие состояния контейнера. На с. 330 приведен список немодифици-рующих алгоритмов, предназначенных для упорядоченных входных интервалов.

Таблица 9.1. Немодифицирующие алгоритмы

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