АЛГОРИТМЫ

АЛГОРИТМЫ

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

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