Алгоритмы

Определение: Алгоритм это конечная последовательность действий, приводящая к желаемому результату.

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

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

Для некоторых алгоритмов предусмотрены как оперативные версии (то есть результат сохраняется в указаном итераторами сегменте), так и копирующие версии. Решение, включать ли копирующую версию в библиотеку, было основано на рассмотрении эфективности алгоритма. Когда стоимость выполнения операции доминирует над стоимостью копии, копирующая версия не включена. Например, sort_copy не включена, так как стоимость сортировки намного значительнее, и пользователи могли бы также делать copy перед sort. Копирующая версия алгоритма algorithm называется algorithm_copy (добавляется суффикс _copy). В копирующих алгоритмах не указывается конец второго интервала, так как он может быть вычислен исходя их длины первого интервала.

Кроме того, для некоторых алгоритмов существуют предикатные версии. Алгоритмы, которые берут предикаты, оканчиваются суффиксом _if (который следует за суффиксом _copy в случае копирующего алгоритма).

Класс Predicate используется всякий раз, когда алгоритм ожидает функциональный объект, при применении которого к результату разыменования соответствующего итератора возвращается значение, обратимое в bool. Другими словами, если алгоритм берёт Predicate pred как свой параметр и first как свой параметр итератора, он должен работать правильно в конструкции if (pred(*first)) {...}. Предполагается, что функциональный объект pred не применяет какую-либо непостоянную функцию для разыменованного итератора.

Класс BinaryPredicate используется всякий раз, когда алгоритм ожидает функциональный объект, который при его применении к результату разыменования двух соответствующих итераторов или к разыменованию итератора и типа T, когда T - часть сигнатуры, возвращает значение, обратимое в bool. Другими словами, если алгоритм берёт BinaryPredicate binary_pred как свой параметр и first1 и first2 как свои параметры итераторов, он должен работать правильно в конструкции if (binary_pred(*first, *first2)) {...}. BinaryPredicate всегда берёт тип первого итератора как свой первый параметр, то есть в тех случаях, когда T value - часть сигнатуры, он должен работать правильно в контексте if (binary_pred (*first, value)) {...}. Ожидается, что binary_pred не будет применять какую-либо непостоянную функцию для разыменованных итераторов.

Существуют алгоритмы, меняющие последовательность и не меняющие последовательность. Ниже описаны наиболее часто встречающиеся алгоритмы.

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

Название	синтаксис	Пояснение
for_each	template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);	for_each применяет f к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f. Принято, что f не применяет какую-то непостоянную функцию к разыменованному итератору. f применяется точно last-first раз. Если f возвращает результат, результат игнорируется.
find	template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value); template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);	find возвращает первый итератор i в диапазоне [first, last), для которого соблюдаются следующие соответствующие условия: *i == value, pred (*i) == true. Если такой итератор не найден, возвращается last. Соответствующий предикат применяется точно find(first, last, value) - first раз.
count	template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val); template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, UnaryPredicate pred);	count подсчитывает число итераторов i в диапазоне [first, last), для которых соблюдаются следующие соответствующие условия: *i == value, pred (*i) == true. Соответствующий предикат применяется точно last-first раз.
equal	template <class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);	equal возвращает true, если для каждого итератора i в диапазоне [first1, last1) выполнены следующие соответствующие условия: *i == *(first2 + (i - first1)), binary_pred(*i, *(first2 + (i - first1))) == true. Иначе equal возвращает false. Соответствующий предикат применяется, самое большее, last1 - first1 раз.
search	template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);	search находит подпоследовательность равных значений в последовательности. search возвращает первый итератор i в диапазоне [first1, last1 - (last2 - first2)) такой, что для любого неотрицательного целого числа n, меньшего чем last2 - first2, выполнены следующие соответствующие условия: *(i + n) == *(first2 + n), binary_pred(*(i + n), *(first2 + n)) == true. Если такой итератор не найден, возвращается last1. Соответствующий предикат применяется, самое большее, (last1 - first1) * (last2 - first2) раз. Квадратичное поведение, однако, является крайне маловероятным.

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

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

Название	синтаксис	Пояснение
copy	template <class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);template <class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);	Алгоритм copy копирует элементы из полуинтервала [first, last) в полуинтервал [result, result + (last-first)). Полуинтервалы должны существовать и не пересекаться.Алгоритм copy_backward копирует элементы полуинтервала в обратном порядке.
swap	template < class T > void swap (T& a , T& b );template < class ForwardIterator1 , class ForwardIterator2 > ForwardIterator2 swap_ranges ( ForwardIterator1 first1 , ForwardIterator1 last1 , ForwardIterator2 first2 );template < class ForwardIterator1 , class ForwardIterator2 > void iter_swap ( ForwardIterator1 a , ForwardIterator2 b );	Этот алгоритм предназначен для обмена значений между двумя переменными (объектами). Также существует реализация для обмена значений итераторов и полуинтервалов.
replace	template < class ForwardIterator , class T> void replace ( ForwardIterator first , ForwardIterator last , const T& old_value , const T& new_value );template < class ForwardIterator , class Predicate , class T> void replace_if ( ForwardIterator first , ForwardIterator last , Predicate pred , const T& new_value );template < class InputIterator , class OutputIterator , class T> OutputIterator replace_copy ( InputIterator first , InputIterator last , OutputIterator result , const T& old_value , const T& new_value );template < class InputIterator , class OutputIterator , class Predicate , class T> OutputIterator replace_copy_if ( InputIterator first , InputIterator last ,OutputIterator result , Predicate pred , const T& new_value );	Алгоритм replace заменяет все элементы из указываемого полуинтервала, равные old_value, на new_value. Предикатная форма алгоритма заменяет все элементы, которые удовлетворяют условию предиката.
transform	template < class InputIterator , class OutputIterator , class UnaryOperation > OutputIterator transform ( InputIterator first , InputIterator last , OutputIterator result , UnaryOperation op );template < class InputIterator1 , class InputIterator2 , class OutputIterator , class BinaryOperation > OutputIterator transform ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result , BinaryOperation binary_op);	Данный алгоритм применяет функтор к элементам полуинтервала [first, last) и результат unary_op(*it) записывает в полуинтервал [result, result + (last-first)).Вторая форма олгоритма transform выбирает значения из двух полуинтервалов, и результат и результат binary_op(*it1, *it2) аписывает в полуинтервал [result, result + (last-first)).
fill	template < class ForwardIterator , class T> void fill ( ForwardIterator first , ForwardIterator last , const T& value );template < class OutputIterator , class Size , class T> void fill_n ( OutputIterator first , Size n , const T& value );	1
generate	template < class ForwardIterator , class Generator > void generate ( ForwardIterator first , ForwardIterator last , Generator gen );template < class OutputIterator , class Size , class Generator > void generate_n ( OutputIterator first , Size n , Generator gen );	1
remove	template < class ForwardIterator , class T> ForwardIterator remove ( ForwardIterator first , ForwardIterator last , const T& value );template < class ForwardIterator , class Predicate > ForwardIterator remove_if ( ForwardIterator first , ForwardIterator last , Predicate pred );template < class InputIterator , class OutputIterator , class T> OutputIterator remove_copy ( InputIterator first , InputIterator last , OutputIterator result , const T& value );template < class InputIterator , class OutputIterator , class Predicate > OutputIterator remove_copy_if ( InputIterator first , InputIterator last , OutputIterator result , Predicate pred );	Удаляет из полуинтервала все элементы, равные value, или удовлетворяющие предикату, в случае предикатной формы.Есть копирующие формы алгоритмов.
unique	template < class ForwardIterator > ForwardIterator unique ( ForwardIterator first , ForwardIterator last );template < class ForwardIterator , class BinaryPredicate > ForwardIterator unique ( ForwardIterator first , ForwardIterator last , BinaryPredicate pred );template < class InputIterator , class OutputIterator > OutputIterator unique_copy ( InputIterator first , InputIterator last , OutputIterator result );template < class InputIterator , class OutputIterator , class BinaryPredicate > OutputIterator unique_copy ( InputIterator first , InputIterator last , OutputIterator result , BinaryPredicate pred );	1
reverse	template < class BidirectionalIterator > void reverse ( BidirectionalIterator first , BidirectionalIterator last );template < class BidirectionalIterator , class OutputIterator > OutputIterator reverse_copy ( BidirectionalIterator first , BidirectionalIterator last , OutputIterator result );	переворачивает полуинтервал.Есть копирующая форма алгоритма.
rotate	template < class ForwardIterator > void rotate ( ForwardIterator first , ForwardIterator middle , ForwardIterator last );template < class ForwardIterator , class OutputIterator > OutputIterator rotate_copy ( ForwardIterator first , ForwardIterator middle , ForwardIterator last , OutputIterator result );	1
random_shuffle	template < class RandomAccessIterator > void random_shuffle ( RandomAccessIterator first , RandomAccessIterator last );template < class RandomAccessIterator , class RandomNumberGenerator > void random_shuffle ( RandomAccessIterator first , RandomAccessIterator last , RandomNumberGenerator & rand );	Перемешивает псевдослучайным образом элементы полуинтервала. Третьим параметром алгоритма может быть генератор случайных чисел.