Алгоритмы

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

     Для некоторых алгоритмов предусмотрены и оперативные и копирующие версии. Решение, включать ли копирующую версию, было обычно основано на рассмотрении сложности. Когда стоимость выполнения операции доминирует над стоимостью копии, копирующая версия не включена. Например, sort_copy не включена, так как стоимость сортировки намного значительнее, и пользователи могли бы также делать copy перед sort. Когда такая версия предусмотрена для какого-то алгоритма algorithm, он называется algorithm_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 не будет применять какую-либо непостоянную функцию для разыменованных итераторов.

     В описании алгоритмов операторы + и - используются для некоторых категорий итераторов, для которых они не должны быть определены. В этих случаях семантика a+n такая же, как семантика {X tmp = a; advance(tmp, n); return tmp;}, а семантика a-b такая же, как семантика {Distance n; distance(a, b, n); return n;}.