Обобщенные алгоритмы

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

Алгоритмы STL делятся на четыре категории, которые рассмотрены в следующем порядке:

немодифицирующие последовательные алгоритмы;

модифицирующие последовательные алгоритмы;

алгоритмы, связанные с сортировкой;

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

Хотя алгоритмы в STL определены в виде шаблонов, мы обычно представляем их себе как функции, поскольку их использование практически не отличается от использования обычных функций. В примерах, где требуются последовательные контейнеры, мы будем использовать массивы целых чисел. Вместо них мы могли бы использовать и другие контейнеры в зависимости от категории итераторов их аргументов. Например, поскольку алгоритм sort требует в качестве аргументов итераторы произвольного доступа, он не будет работать с контейнером list, как уже упоминалось в разделе 1.3. Поэтому каждый раздел этой главы начинается с краткого обзора рассматриваемых алгоритмов; при этом указаны категории итераторов, используемые

в качестве аргументов. Это перечисление приводится в виде списка прототипов деклараций шаблонов, но в этих прототипах для краткости опущены ключевое слово template и список параметров в угловых скобках. Имена алгоритмов выделены курсивом в конце строки, чтобы их было легче найти.

При первом чтении эти прототипы могут показаться скучными из-за их однообразия и длинных имен типов (которые являются параметрами шаблона) наподобие RandomAccessIterator. Однако, когда вы немного освоитесь с рассмотренными алгоритмами, эти прототипы помогут быстро находить нужную информацию. Возьмем, к примеру, параметры алгоритма sort, записанные в прототипе как RandomAccessIterator first, RandomAccessIterator last. Поскольку список не определяет итераторы произвольного доступа {random access), из этого прототипа видно, что для списков мы не можем применять алгоритм sort. Если вы забыли, какие итераторы используются с контейнерами различных типов, то будет полезно перечитать раздел 1.9. Особенно важно помнить иерархию итераторов. Чем выше находится тип параметра алгоритма в иерархии итераторов, тем более ограничено использование этого алгоритма. Итераторы произвольного доступа, относящиеся к более высокому уровню, разрешают операции вроде i + п, что делает невозможным применение алгоритмов для списков, использующих такие итераторы.

7.1. Немодифицирующие последовательные алгоритмы

Алгоритмы в этом разделе просматривают последовательности, не изменяя их.

7.1.1. Алгоритмы find, count, fi)r each, findJirstof и find end

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

Inputlterator find 11 Обсуждался в разделе 1.5

(Inputlterator first, Inputlterator last, const T& value) ;

Inputlterator find if II Обсуждался в разделе 1.13

(Inputlterator first, Inputlterator last. Predicate pred);

void for each II Обсуждался в разделе 2.2

(Inputlterator first, Inputlterator last. Function f);

difference type count Обсуждался в разделе 2.3

(Inputlterator first, Inputlterator last, const T& value);

difference type count if Обсуждался в разделе 2.3

(Inputlterator first, Inputlterator last. Predicate pred);

Forwardlteratorl find first of

(Forwardlteratorl firstl, Forwardlteratorl lastl,

ForwardIterator2 first2, ForwardIterator2 last2); Forwardlteratorl find first of

(Forwardlteratorl firstl, Forwardlteratorl lastl,

ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); Forwardlteratorl find end

(Forwardlteratorl firstl, Forwardlteratorl lastl,

ForwardIterator2 first2, ForwardIterator2 last2); Forwardlteratorl find end

(Forwardlteratorl firstl, Forwardlteratorl lastl,

ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Мы не будем повторять предыдущее обсуждение алгоритмов find, findjf, for each, count и count if.

Алгоритм find Jirstjof похож на find, но вместо поиска элемента с заданным значением он ищет в первом диапазоне элемент, значение которого равно какому-либо элементу из второго диапазона. Если такие элементы присутствуют в диапазоне, он возвращает итератор, ссылающийся на первый из них. Алгоритм findjsnd, напротив, возвращает итератор, указывающий на начало последнего полного вхождения второго диапазона в первый. (Если нужно найти первое вхождение, используйте алгоритм search, который рассмотрен далее в разделе 7.1.5.) В случае неудачи find Jirst of и /гЫ егг возвращают lastX. Следующая программа демонстрирует работу обоих алгоритмов:

find end: Алгоритмы find first of и find end. iinclude <iostream> iinclude <algorithin>

using namespace std; int main()

{ int a[10] = {3, 2, 5, 7, 5, 8, 7, 5, 8, 5}, b[2] = {5, 8}, *pl, *p2; pi = find first of(a, a+7, b, b+3); p2 = find end(a, a+10, b, b+2); cout pi - a p2 - a endl; return 0;

Вывод этой программы:

объясняется тем, что а[2] (=5) является первым элементом а, который входит также и в а а[7] (=5) является начальным элементом последней полной последовательности 5,8 (заданной массивом Ь), которая встречается в а.