28 Algorithms library [algorithms]

28.3 Algorithms requirements [algorithms.requirements]

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

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

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

  • Если параметр шаблона алгоритма назван InputIterator, InputIterator1или InputIterator2, аргумент шаблона должен удовлетворять требованиям input iterator.

  • Если параметр шаблона алгоритма назван OutputIterator, OutputIterator1или OutputIterator2, аргумент шаблона должен удовлетворять требованиям output iterator.

  • Если параметр шаблона алгоритма назван ForwardIterator, ForwardIterator1или ForwardIterator2, аргумент шаблона должен удовлетворять требованиям a forward iterator.

  • Если параметр шаблона алгоритма назван BidirectionalIterator, BidirectionalIterator1или BidirectionalIterator2, аргумент шаблона должен удовлетворять требованиям a bidirectional iterator.

  • Если параметр шаблона алгоритма назван RandomAccessIterator, RandomAccessIterator1или RandomAccessIterator2, аргумент шаблона должен удовлетворять требованиям a random-access iterator.

Если вEffects: разделе алгоритма указано, что значение, на которое указывает любой итератор, переданный в качестве аргумента, изменяется, тогда этот алгоритм имеет дополнительное требование типа: тип этого аргумента должен удовлетворять требованиям a mutable iterator. [ Note: Это требование не влияет на аргументы, которые названы OutputIterator, OutputIterator1или OutputIterator2, поскольку выходные итераторы всегда должны быть изменяемыми. ]end note

Для определенных алгоритмов предусмотрены как версия на месте, так и версия для копирования.262 Когда такая версия предусмотрена, algorithm это называется algorithm_­copy. Алгоритмы, которые принимают предикаты, заканчиваются суффиксом _­if (который следует за суффиксом _­copy).

Predicate Параметр используется всякий раз , когда алгоритм ожидает , function object что, когда применяется к результату разыменования соответствующего итератора, возвращает значение проверяемые как true. Другими словами, если алгоритм принимает в Predicate pred качестве аргумента и аргумента first итератора, он должен правильно работать в конструкции, pred(*first) контекстно преобразованной в bool (Предложение [conv]). Функциональный объект pred не должен применять какие-либо непостоянные функции через разыменованный итератор.

BinaryPredicate Параметр используется всякий раз , когда алгоритм ожидает функциональный объекта , который при применении к результату разыменования двух соответствующих итераторов или к разыменованию итератора и типа ,T когда T является частью подписи возвращает значение , как тестируемая true. Другими словами, если алгоритм принимает вBinaryPredicate binary_­pred качестве аргумента и first1 а first2 также его итератор аргументы, он должен работать правильно в конструкции binary_­pred(*first1, *first2) контекстуально преобразуется в bool (п [conv]). BinaryPredicate всегда принимает первый итератор в value_­type качестве своего первого аргумента, то есть в тех случаях, когда он T value является частью подписи, он должен правильно работать в конструкции, binary_­pred(*first1, value) контекстно преобразованной в bool (Clause [conv]). binary_­pred не должен применять какие-либо непостоянные функции через разыменованные итераторы.

[ Note: Если не указано иное, алгоритмы, которые принимают объекты функций в качестве аргументов, могут свободно копировать эти объекты функций. Программисты, для которых важна идентичность объекта, должны рассмотреть возможность использования класса-оболочки, который указывает на нескопированный объект реализации, например reference_­wrapper<T>, или какое-либо эквивалентное решение. ]end note

Когда описание алгоритма дает выражение, как *first == value для условия, выражение должно вычисляться либо true или false в логических контекстах.

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

X tmp = a;
advance(tmp, n);
return tmp;

и это b-a то же самое, что и

return distance(a, b);

Решение о включении копируемой версии обычно принималось из соображений сложности. Когда стоимость выполнения операции превышает стоимость копирования, версия для копирования не включается. Например, sort_­copy не включен, потому что стоимость сортировки намного более значительна, и пользователи могут также copy следовать за ним sort.