28 Algorithms library [algorithms]

28.5 Non-modifying sequence operations [alg.nonmodifying]

28.5.1 All of [alg.all_of]

template <class InputIterator, class Predicate> bool all_of(InputIterator first, InputIterator last, Predicate pred); template <class ExecutionPolicy, class ForwardIterator, class Predicate> bool all_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);

Returns:true если [first, last) пусто или если pred(*i) естьtrue для каждого итератораi в диапазоне[first, last), и вfalse противном случае.

Complexity: В большинствеlast - first случаев применения предиката.

28.5.2 Any of [alg.any_of]

template <class InputIterator, class Predicate> bool any_of(InputIterator first, InputIterator last, Predicate pred); template <class ExecutionPolicy, class ForwardIterator, class Predicate> bool any_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);

Returns:false если[first, last) пусто или еслиi в диапазоне нет итератора[first, last) , тоpred(*i) естьtrue, и вtrue противном случае.

Complexity: В большинствеlast - first случаев применения предиката.

28.5.3 None of [alg.none_of]

template <class InputIterator, class Predicate> bool none_of(InputIterator first, InputIterator last, Predicate pred); template <class ExecutionPolicy, class ForwardIterator, class Predicate> bool none_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);

Returns:true если [first, last) пусто или если pred(*i) естьfalse для каждого итератораi в диапазоне[first, last), и вfalse противном случае.

Complexity: В большинствеlast - first случаев применения предиката.

28.5.4 For each [alg.foreach]

template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);

Requires:Function должны соответствовать требованиям MoveConstructible. [ Note:Function не обязательно соответствовать требованиям CopyConstructible. ]end note

Effects: Применяется f к результату разыменования каждого итератора в диапазоне [first, last), начиная с first и продолжаясь до last - 1. [ Note: Если типfirst удовлетворяет требованиям изменяемого итератора,f может применять непостоянные функции через разыменованный итератор. ]end note

Returns: f.

Complexity: Применяетсяf ровно last - first раз.

Remarks: Еслиf возвращает результат, результат игнорируется.

template<class ExecutionPolicy, class ForwardIterator, class Function> void for_each(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Function f);

Requires: Function должны соответствовать требованиямCopyConstructible.

Effects: Применяетсяf к результату разыменования каждого итератора в диапазоне [first, last). [ Note: Если типfirst удовлетворяет требованиям изменяемого итератора, f может применять непостоянные функции через разыменованный итератор. ]end note

Complexity: Применяетсяf ровноlast - first раз.

Remarks: Еслиf возвращает результат, результат игнорируется. Реализации не имеют права[algorithms.parallel.exec] делать произвольные копии элементов из входной последовательности.

[ Note: Не возвращает копию своегоFunction параметра, поскольку распараллеливание может не позволить эффективное накопление состояний. ] end note

template<class InputIterator, class Size, class Function> InputIterator for_each_n(InputIterator first, Size n, Function f);

Requires: Function должны соответствовать требованиямMoveConstructible [ Note:Function не обязательно отвечать требованиям CopyConstructible. ]end note

Requires: n >= 0.

Effects: Применяетсяf к результату разыменования каждого итератора в диапазоне [first, first + n) по порядку. [ Note: Если типfirst удовлетворяет требованиям изменяемого итератора, f может применять непостоянные функции через разыменованный итератор. ]end note

Returns: first + n.

Remarks: Еслиf возвращает результат, результат игнорируется.

template<class ExecutionPolicy, class ForwardIterator, class Size, class Function> ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n, Function f);

Requires: Function должны соответствовать требованиямCopyConstructible.

Requires: n >= 0.

Effects: Применяетсяf к результату разыменования каждого итератора в диапазоне [first, first + n). [ Note: Если типfirst удовлетворяет требованиям изменяемого итератора, f может применять непостоянные функции через разыменованный итератор. ]end note

Returns: first + n.

Remarks: Еслиf возвращает результат, результат игнорируется. Реализации не имеют права[algorithms.parallel.exec] делать произвольные копии элементов из входной последовательности.

28.5.5 Find [alg.find]

template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value); template<class ExecutionPolicy, class ForwardIterator, class T> ForwardIterator find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, const T& value); template<class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator find_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<class InputIterator, class Predicate> InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator find_if_not(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);

Returns: Первый итератора i в диапазоне ,[first, last) для которых выполняются соответствующие условия: *i == value,pred(*i) != false,pred(*i) == false. Возвращает,last если такой итератор не найден.

Complexity: Максимум last - first применений соответствующего предиката.

28.5.6 Find end [alg.find.end]

template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Effects: Находит подпоследовательность равных значений в последовательности.

Returns: Последний итератор i в диапазон ,[first1, last1 - (last2 - first2)) например , что для каждого неотрицательного целого числа n < (last2 - first2), следующие соответствующие условия: *(i + n) == *(​first2 + n), pred(*(i + n), *(first2 + n)) != false. Возвращает,last1 если [first2, last2) пуст или если такой итератор не найден.

Complexity: Максимум (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) применений соответствующего предиката.

28.5.7 Find first [alg.find.first.of]

template<class InputIterator, class ForwardIterator> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_first_of(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class InputIterator, class ForwardIterator, class BinaryPredicate> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_first_of(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Effects: Находит элемент, соответствующий одному из набора значений.

Returns: Первый итератор i в диапазоне[first1, last1) , что для некоторых итератора j в диапазоне[first2, last2) выполняются следующие условия: *i == *j, pred(*i,*j) != false. Возвращает,last1 если[first2, last2) пуст или если такой итератор не найден.

Complexity: Максимум (last1-first1) * (last2-first2) применений соответствующего предиката.

28.5.8 Adjacent find [alg.adjacent.find]

template<class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator adjacent_find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

Returns: Первый итератор ,i такой , что оба i и i + 1 находится в диапазоне ,[first, last) для которых выполняются следующие соответствующие условия: *i == *(i + 1), pred(*i, *(i + 1)) != false. Возвращает,last если такой итератор не найден.

Complexity: Для перегрузок безExecutionPolicy, а именно min((i - first) + 1, (last - first) - 1) применения соответствующего предиката, гдеi - adjacent_­findвозвращаемое значение. Для перегрузок с anExecutionPolicy, O(last - first) применения соответствующего предиката.

28.5.9 Count [alg.count]

template<class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value); template<class ExecutionPolicy, class ForwardIterator, class T> typename iterator_traits<ForwardIterator>::difference_type count(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, const T& value); template<class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> typename iterator_traits<ForwardIterator>::difference_type count_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);

Effects: Возвращает количество итераторов i в диапазоне ,[first, last) для которых выполняются следующие соответствующие условия: *i == value, pred(*i) != false.

Complexity: Точно last - first применения соответствующего предиката.

28.5.10 Mismatch [mismatch]

template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Remarks: Еслиlast2 не было указано в списке аргументов, это обозначается first2 + (last1 - first1) ниже.

Returns: Пара итераторовfirst1 + n и first2 + n, гдеn - наименьшее целое число такое, что соответственно

  • !(*(first1 + n) == *(first2 + n)) или

  • pred(*(first1 + n), *(first2 + n)) == false,

илиmin(last1 - first1, last2 - first2) если такого целого числа не существует.

Complexity: Максимум min(last1 - first1, last2 - first2) применений соответствующего предиката.

28.5.11 Equal [alg.equal]

template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Remarks: Еслиlast2 не было указано в списке аргументов, это обозначается first2 + (last1 - first1) ниже.

Returns: Если last1 - first1 != last2 - first2, вернись false. В противном случае вернуться ,true если для каждого итератора i в диапазоне[first1, last1) выполняются следующие соответствующие условия: *i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false. В противном случае возвращается false.

Complexity:

  • Для перегрузок безExecutionPolicy,

    • если InputIterator1 и InputIterator2 удовлетворяют требованиям итераторов произвольного доступа ([random.access.iterators]) и last1 - first1 != last2 - first2, то применения соответствующего предиката нет; иначе,

    • в большинстве min(last1 - first1,last2 - first2) случаев применения соответствующего предиката.

  • Для перегрузок безExecutionPolicy,

    • если ForwardIterator1 и ForwardIterator2 удовлетворяют требованиям итераторов произвольного доступа и last1 - first1 != last2 - first2, то нет применения соответствующего предиката; иначе,

    • O(min(last1 - first1,last2 - first2)) применения соответствующего предиката.

28.5.12 Is permutation [alg.is_permutation]

template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Requires:ForwardIterator1 иForwardIterator2 должен иметь один и тот же тип значения. Функция сравнения должна быть отношением эквивалентности.

Remarks: Еслиlast2 не было указано в списке аргументов, это обозначается first2 + (last1 - first1) ниже.

Returns: Еслиlast1 - first1 != last2 - first2, вернисьfalse. В противном случае return,true если существует перестановка элементов в диапазоне[first2, first2 + (last1 - first1)), начиная сForwardIterator2 begin, так чтоequal(first1, last1, begin) возвращаетсяtrue или equal(first1, last1, begin, pred) возвращаетсяtrue; в противном случае возвращается false.

Complexity: Нет приложений соответствующего предиката ifForwardIterator1 и,ForwardIterator2 отвечающих требованиям итераторов произвольного доступа и last1 - first1 != last2 - first2. В противном случае точноlast1 - first1 приложения соответствующего предиката ifequal(​first1, last1, first2, last2) вернутся,true еслиpred он не указан в списке аргументов, илиequal(first1, last1, first2, last2, pred) вернутся,true если pred был задан в списке аргументов; в противном случае, в худшем случаеO(N2), гдеN имеет значениеlast1 - first1.

28.5.13 Search [alg.search]

template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ExecutionPolicy&& exec, 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 pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

Effects: Находит подпоследовательность равных значений в последовательности.

Returns: Первый итератор i в диапазон[first1, last1 - (last2-first2)) таким образом, что для каждого неотрицательного целого числа n меньше last2 - first2 следующих соответствующих условий: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Возвращает,first1 если[first2, last2) пусто, в противном случае возвращает,last1 если такой итератор не найден.

Complexity: Максимум (last1 - first1) * (last2 - first2) применений соответствующего предиката.

template<class ForwardIterator, class Size, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); template<class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator, class Size, class T> ForwardIterator search_n(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Size count, const T& value); template<class ExecutionPolicy, class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator search_n(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred);

Requires: Тип Size должен быть преобразован в целочисленный тип ([conv.integral],[class.conv]).

Effects: Находит подпоследовательность равных значений в последовательности.

Returns: Первый итератор i в диапазон[first, last-count) таким образом, что для каждого неотрицательного целого числа n меньше count следующих соответствующих условий: *(i + n) == value, pred(*(i + n),value) != false. Возвращает,last если такой итератор не найден.

Complexity: Максимум last - first применений соответствующего предиката.

template<class ForwardIterator, class Searcher> ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher& searcher);

Effects: Эквивалентен:return searcher(first, last).first;

Remarks: Searcher не обязательно соответствоватьCopyConstructible требованиям.