В этом разделе описаны компоненты, которые программы C ++ могут использовать для выполнения алгоритмических операций containers и других последовательностей.
В следующих подпунктах описываются компоненты для немодифицирующих операций последовательности, операций модификации последовательности, сортировки и связанных операций, а также алгоритмы из библиотеки ISO C, как показано в таблице 100.
Подпункт | Заголовок (ы) | |
[alg.nonmodifying] | Немодифицирующие операции последовательности | |
[alg.modifying.operations] | Операции мутирующей последовательности | <algorithm> |
[alg.sorting] | Сортировка и сопутствующие операции | |
[alg.c.library] | Алгоритмы библиотеки C | <cstdlib> |
#include <initializer_list> namespace std { // [alg.nonmodifying], non-modifying sequence operations // [alg.all_of], 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, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); // [alg.any_of], 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, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); // [alg.none_of], 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, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); // [alg.foreach], for each template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f); template<class ExecutionPolicy, class ForwardIterator, class Function> void for_each(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Function f); template<class InputIterator, class Size, class Function> InputIterator for_each_n(InputIterator first, Size n, Function f); template<class ExecutionPolicy, class ForwardIterator, class Size, class Function> ForwardIterator for_each_n(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, Size n, Function f); // [alg.find], 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, // see [algorithms.parallel.overloads] 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, // see [algorithms.parallel.overloads] 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, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); // [alg.find.end], find end template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(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> ForwardIterator1 find_end(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); // [alg.find.first.of], find first template<class InputIterator, class ForwardIterator> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator 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> ForwardIterator1 find_first_of(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_first_of(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); // [alg.adjacent.find], adjacent find template<class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator adjacent_find(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, BinaryPredicate pred); // [alg.count], 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, // see [algorithms.parallel.overloads] 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, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); // [mismatch], mismatch template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 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> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> pair<ForwardIterator1, ForwardIterator2> mismatch(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); // [alg.equal], 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 pred); template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 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> bool equal(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool equal(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool equal(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool equal(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); // [alg.is_permutation], 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); // [alg.search], 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 pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 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, // see [algorithms.parallel.overloads] 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, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred); template <class ForwardIterator, class Searcher> ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher& searcher); // [alg.modifying.operations], modifying sequence operations // [alg.copy], copy template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result); template<class InputIterator, class Size, class OutputIterator> OutputIterator copy_n(InputIterator first, Size n, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2> ForwardIterator2 copy_n(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, Size n, ForwardIterator2 result); template<class InputIterator, class OutputIterator, class Predicate> OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate> ForwardIterator2 copy_if(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, Predicate pred); template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); // [alg.move], move template<class InputIterator, class OutputIterator> OutputIterator move(InputIterator first, InputIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 move(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result); template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 move_backward( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result); // [alg.swap], swap template<class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ForwardIterator1, class ForwardIterator2> void iter_swap(ForwardIterator1 a, ForwardIterator2 b); // [alg.transform], 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); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class UnaryOperation> ForwardIterator2 transform(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, UnaryOperation op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class BinaryOperation> ForwardIterator transform(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator result, BinaryOperation binary_op); // [alg.replace], replace template<class ForwardIterator, class T> void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); template<class ExecutionPolicy, class ForwardIterator, class T> void replace(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] 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 ExecutionPolicy, class ForwardIterator, class Predicate, class T> void replace_if(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] 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 ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> ForwardIterator2 replace_copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 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); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate, class T> ForwardIterator2 replace_copy_if(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, Predicate pred, const T& new_value); // [alg.fill], fill template<class ForwardIterator, class T> void fill(ForwardIterator first, ForwardIterator last, const T& value); template<class ExecutionPolicy, class ForwardIterator, class T> void fill(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, const T& value); template<class OutputIterator, class Size, class T> OutputIterator fill_n(OutputIterator first, Size n, const T& value); template<class ExecutionPolicy, class ForwardIterator, class Size, class T> ForwardIterator fill_n(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, Size n, const T& value); // [alg.generate], generate template<class ForwardIterator, class Generator> void generate(ForwardIterator first, ForwardIterator last, Generator gen); template<class ExecutionPolicy, class ForwardIterator, class Generator> void generate(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Generator gen); template<class OutputIterator, class Size, class Generator> OutputIterator generate_n(OutputIterator first, Size n, Generator gen); template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator> ForwardIterator generate_n(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, Size n, Generator gen); // [alg.remove], remove template<class ForwardIterator, class T> ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value); template<class ExecutionPolicy, class ForwardIterator, class T> ForwardIterator remove(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class Predicate> ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator remove_if(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] 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 ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> ForwardIterator2 remove_copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, const T& value); template<class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate> ForwardIterator2 remove_copy_if(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, Predicate pred); // [alg.unique], 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 ExecutionPolicy, class ForwardIterator> ForwardIterator unique(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] 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); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 unique_copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator2 unique_copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryPredicate pred); // [alg.reverse], reverse template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last); template<class ExecutionPolicy, class BidirectionalIterator> void reverse(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] BidirectionalIterator first, BidirectionalIterator last); template<class BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); template<class ExecutionPolicy, class BidirectionalIterator, class ForwardIterator> ForwardIterator reverse_copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] BidirectionalIterator first, BidirectionalIterator last, ForwardIterator result); // [alg.rotate], rotate template<class ForwardIterator> ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator rotate(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator middle, ForwardIterator last); template<class ForwardIterator, class OutputIterator> OutputIterator rotate_copy( ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 rotate_copy( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first, ForwardIterator1 middle, ForwardIterator1 last, ForwardIterator2 result); // [alg.random.sample], sample template<class PopulationIterator, class SampleIterator, class Distance, class UniformRandomBitGenerator> SampleIterator sample(PopulationIterator first, PopulationIterator last, SampleIterator out, Distance n, UniformRandomBitGenerator&& g); // [alg.random.shuffle], shuffle template<class RandomAccessIterator, class UniformRandomBitGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomBitGenerator&& g); // [alg.partitions], partitions template <class InputIterator, class Predicate> bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); template <class ExecutionPolicy, class ForwardIterator, class Predicate> bool is_partitioned(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); template<class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator partition(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Predicate pred); template<class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template<class ExecutionPolicy, class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] BidirectionalIterator first, BidirectionalIterator last, Predicate pred); template <class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> pair<OutputIterator1, OutputIterator2> partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred); template <class ExecutionPolicy, class ForwardIterator, class ForwardIterator1, class ForwardIterator2, class Predicate> pair<ForwardIterator1, ForwardIterator2> partition_copy(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred); template<class ForwardIterator, class Predicate> ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); // [alg.sorting], sorting and related operations // [alg.sort], sorting template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator> void sort(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void sort(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator> void stable_sort(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void stable_sort(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator> void partial_sort(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void partial_sort(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); template<class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template<class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); template<class ForwardIterator> bool is_sorted(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); template<class ExecutionPolicy, class ForwardIterator> bool is_sorted(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class Compare> bool is_sorted(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Compare comp); template<class ForwardIterator> ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator is_sorted_until(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class Compare> ForwardIterator is_sorted_until(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Compare comp); // [alg.nth.element], Nth element template<class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator> void nth_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void nth_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); // [alg.binary.search], binary search template<class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<class ForwardIterator, class T> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<class ForwardIterator, class T> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); template<class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); // [alg.merge], merge template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator merge(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator merge(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<class BidirectionalIterator> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); template<class ExecutionPolicy, class BidirectionalIterator> void inplace_merge(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template<class ExecutionPolicy, class BidirectionalIterator, class Compare> void inplace_merge(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); // [alg.set.operations], set operations template<class InputIterator1, class InputIterator2> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class InputIterator1, class InputIterator2, class Compare> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool includes(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare> bool includes(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp); template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_union(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_union(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_intersection( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_intersection( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_difference( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_difference( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator set_symmetric_difference( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator set_symmetric_difference( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); // [alg.heap.operations], heap operations template<class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator> bool is_heap(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> bool is_heap(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class RandomAccessIterator> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator> RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] RandomAccessIterator first, RandomAccessIterator last, Compare comp); // [alg.min.max], minimum and maximum template<class T> constexpr const T& min(const T& a, const T& b); template<class T, class Compare> constexpr const T& min(const T& a, const T& b, Compare comp); template<class T> constexpr T min(initializer_list<T> t); template<class T, class Compare> constexpr T min(initializer_list<T> t, Compare comp); template<class T> constexpr const T& max(const T& a, const T& b); template<class T, class Compare> constexpr const T& max(const T& a, const T& b, Compare comp); template<class T> constexpr T max(initializer_list<T> t); template<class T, class Compare> constexpr T max(initializer_list<T> t, Compare comp); template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b); template<class T, class Compare> constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp); template<class T> constexpr pair<T, T> minmax(initializer_list<T> t); template<class T, class Compare> constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp); template<class ForwardIterator> constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator min_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class Compare> ForwardIterator min_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Compare comp); template<class ForwardIterator> constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator max_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class Compare> ForwardIterator max_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Compare comp); template<class ForwardIterator> constexpr pair<ForwardIterator, ForwardIterator> minmax_element(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class Compare> constexpr pair<ForwardIterator, ForwardIterator> minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); template<class ExecutionPolicy, class ForwardIterator> pair<ForwardIterator, ForwardIterator> minmax_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator, class Compare> pair<ForwardIterator, ForwardIterator> minmax_element(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator first, ForwardIterator last, Compare comp); // [alg.clamp], bounded value template<class T> constexpr const T& clamp(const T& v, const T& lo, const T& hi); template<class T, class Compare> constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // [alg.lex.comparison], lexicographical comparison template<class InputIterator1, class InputIterator2> bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class InputIterator1, class InputIterator2, class Compare> bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool lexicographical_compare( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare> bool lexicographical_compare( ExecutionPolicy&& exec, // see [algorithms.parallel.overloads] ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Compare comp); // [alg.permutation.generators], permutations template<class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); template<class BidirectionalIterator> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); }
Все алгоритмы отделены от конкретных реализаций структур данных и параметризуются типами итераторов. Благодаря этому они могут работать со структурами данных, определяемыми программой, если эти структуры данных имеют типы итераторов, удовлетворяющие предположениям об алгоритмах.
В целях определения наличия гонок данных алгоритмы не должны изменять объекты, на которые ссылается аргумент итератора, если только спецификация не требует такой модификации.
В этом разделе имена параметров шаблона используются для выражения требований к типу.
Если параметр шаблона алгоритма назван 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.
В этом разделе описаны компоненты, которые программы C ++ могут использовать для параллельного выполнения операций с контейнерами и другими последовательностями.
A parallel algorithm - это шаблон функции, указанный в этом международном стандарте, с параметром шаблона с именем ExecutionPolicy.
Параллельные алгоритмы получают доступ к объектам, косвенно доступным через их аргументы, путем вызова следующих функций:
Все операции категорий итераторов, с которыми реализуется алгоритм.
Операции над теми элементами последовательности, которые требуются его спецификацией.
Предоставленные пользователем функциональные объекты, которые будут применяться во время выполнения алгоритма, если этого требует спецификация.
Операции над теми функциональными объектами, которые требуются спецификацией. [ Note: См [algorithms.general]. ] — end note
Эти функции здесь называются element access functions. [ Функция может вызывать следующие функции доступа элемента: Example: sort
Операции итератора произвольного доступа фактического аргумента шаблона (согласно [random.access.iterators]), как подразумевается именем параметра шаблона RandomAccessIterator.
swap Функции на элементах последовательности (согласно предварительным условиям , указанных в [sort]).
Предоставленный пользователем Compare функциональный объект.
— end example ]
Если не указано иное, функции объектов , передаваемых в параллельные алгоритмы как объекты типа Predicate, BinaryPredicate, Compare, UnaryOperation, BinaryOperation, BinaryOperation1, BinaryOperation2, и операторы , используемые аналогичными перегрузках в этих параллельных алгоритмов , которые могут быть образованы с помощью вызова с указанным предиката или операции по умолчанию (где применимо ) не должны прямо или косвенно изменять объекты через их аргументы, а также не должны полагаться на идентичность предоставленных объектов.
Параллельные алгоритмы имеют параметры шаблона, названные, ExecutionPolicy которые описывают способ, которым выполнение этих алгоритмов может быть распараллелено, и способ, которым они применяют функции доступа к элементам.
Если не указано иное, реализации могут делать произвольные копии элементов (с типом T) из последовательностей where is_trivially_copy_constructible_v<T> и is_trivially_destructible_v<T> are true. [ Note: Это означает, что объекты функций, предоставляемые пользователем, не должны полагаться на идентичность объекта аргументов для таких входных последовательностей. Пользователи, для которых важна идентичность аргументов этих функциональных объектов, должны рассмотреть возможность использования итератора-оболочки, который возвращает не скопированный объект реализации, такой как reference_wrapper<T> ([refwrap]), или какое-либо эквивалентное решение. ] — end note
Вызов функций доступа к элементам в параллельных алгоритмах, вызываемых с помощью объекта политики выполнения типа, execution::sequenced_policy все происходит в вызывающем потоке выполнения. [ Note: Вызовы не чередуются; см [intro.execution]. ] — end note
Вызов функций доступа к элементам в параллельных алгоритмах, вызываемых с помощью объекта политики выполнения типа execution::parallel_policy , разрешается выполнять либо в вызывающем потоке выполнения, либо в потоке выполнения, неявно созданном библиотекой для поддержки выполнения параллельного алгоритма. Если потоки выполнения, созданные с помощью thread provide concurrent forward progress guarantees, то поток выполнения, неявно созданный библиотекой, будет обеспечивать параллельные гарантии продвижения вперед; в противном случае предоставленная гарантия продвижения вперед определяется реализацией. Любые такие вызовы, выполняемые в одном и том же потоке выполнения, имеют неопределенную последовательность относительно друг друга. [ Note: Вызывающая сторона несет ответственность за то, чтобы вызов не привел к скачкам данных или взаимоблокировкам. ] [ — end note Example:
int a[] = {0,1};
std::vector<int> v;
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int i) {
v.push_back(i*2+1); // incorrect: data race
});
Программа выше имеет гонку данных из-за несинхронизированного доступа к контейнеру v. ] [ — end example Example:
std::atomic<int> x{0}; int a[] = {1,2}; std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) { x.fetch_add(1, std::memory_order_relaxed); // spin wait for another iteration to change the value of x while (x.load(std::memory_order_relaxed) == 1) { } // incorrect: assumes execution order });
Приведенный выше пример зависит от порядка выполнения итераций и не завершится, если обе итерации выполняются последовательно в одном и том же потоке выполнения. ] [ — end example Example:
int x = 0; std::mutex m; int a[] = {1,2}; std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) { std::lock_guard<mutex> guard(m); ++x; });
В приведенном выше примере синхронизируется доступ к объекту, x гарантируя, что он увеличивается правильно. ] — end example
Вызовы функций доступа к элементам в параллельных алгоритмах, вызываемых политикой выполнения типа execution::parallel_unsequenced_policy , разрешается выполнять неупорядоченным образом в неуказанных потоках выполнения и неупорядоченно по отношению друг к другу в каждом потоке выполнения. Эти потоки выполнения являются либо вызывающим потоком выполнения, либо потоками выполнения, неявно созданными библиотекой; последний будет обеспечивать слабо параллельные гарантии продвижения вперед. [ Note: Это означает, что вызовы нескольких функциональных объектов могут чередоваться в одном потоке выполнения, что отменяет обычную гарантию того, [intro.execution] что выполнение функций не чередуется друг с другом. ] Поскольку позволяет чередовать выполнение функций доступа к элементам в одном потоке выполнения, блокирующая синхронизация, включая использование мьютексов, может привести к тупиковой ситуации. Таким образом, синхронизация с ограничивается следующим образом: стандартная библиотечная функция - это если она указана для синхронизации с вызовом другой функции, или если для синхронизации с ней указан вызов другой функции, и если это не функция выделения или освобождения памяти. Небезопасные для векторизации функции стандартной библиотеки не могут быть вызваны пользовательским кодом, вызываемым из алгоритмов. [ Реализации должны гарантировать, что внутренняя синхронизация внутри стандартных библиотечных функций не препятствует продвижению вперед, когда эти функции выполняются потоками исполнения со слабо параллельными гарантиями продвижения вперед. ] [ — end note execution::parallel_unsequenced_policy execution::parallel_unsequenced_policy vectorization-unsafe execution::parallel_unsequenced_policy Note: — end note Example:
int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par_unseq, std::begin(a), std::end(a), [&](int) {
std::lock_guard<mutex> guard(m); // incorrect: lock_guard constructor calls m.lock()
++x;
});
Вышеупомянутая программа может привести к двум последовательным вызовам m.lock() в одном и том же потоке выполнения (что может привести к взаимной блокировке), потому что приложения объекта функции не гарантированно работают в разных потоках выполнения. ] [ Семантика вызова или позволяет реализации вернуться к последовательному выполнению, если система не может распараллелить вызов алгоритма из-за нехватки ресурсов. ] — end example Note: execution::parallel_policy execution::parallel_unsequenced_policy — end note
Если при вызове параллельного алгоритма используются потоки выполнения, неявно созданные библиотекой, то вызывающий поток выполнения будет либо
временно блокировать с делегированием гарантии продвижения вперед ([intro.progress]) по завершении этих управляемых библиотекой потоков выполнения, или
в конечном итоге выполнить функцию доступа к элементу;
поток выполнения будет продолжать делать это до тех пор, пока алгоритм не будет завершен. [ Note: При блокировке с делегированием гарантии продвижения вперед в этом контексте поток выполнения, созданный библиотекой, считается завершенным, как только он завершил выполнение конкретной функции доступа к элементу, от которой логически зависит вызывающий поток выполнения. ] — end note
Если во время выполнения параллельного алгоритма для распараллеливания требуются временные ресурсы памяти, а их нет, алгоритм генерирует bad_alloc исключение.
Параллельные алгоритмы - это перегрузки алгоритмов. Каждая перегрузка параллельного алгоритма имеет дополнительный параметр типа шаблона с именем ExecutionPolicy, который является первым параметром шаблона. Кроме того, каждая перегрузка параллельного алгоритма имеет дополнительный параметр функции типа ExecutionPolicy&&, который является первым параметром функции. [ Note: Не все алгоритмы имеют перегрузки параллельных алгоритмов. ] — end note
Если не указано иное, семантика ExecutionPolicy перегрузок алгоритмов идентична их перегрузкам без.
Если не указано иное, требования к сложности ExecutionPolicy перегрузок алгоритмов смягчаются из требований сложности перегрузок без следующего: когда в гарантии указано «максимум expr» или «точно expr» и не указано количество назначений или перестановок, и expr это еще не сделано. выражается в O() обозначениях, сложность алгоритма должна быть O(expr).
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 противном случае.
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 противном случае.
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 противном случае.
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
template<class ExecutionPolicy, class ForwardIterator, class Function>
void for_each(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Function f);
Effects: Применяется f к результату разыменования каждого итератора в диапазоне [first, last). [ Note: Если тип first удовлетворяет требованиям изменяемого итератора, f может применять непостоянные функции через разыменованный итератор. ] — end note
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
Effects: Применяется f к результату разыменования каждого итератора в диапазоне [first, first + n) по порядку. [ Note: Если тип first удовлетворяет требованиям изменяемого итератора, f может применять непостоянные функции через разыменованный итератор. ] — end note
template<class ExecutionPolicy, class ForwardIterator, class Size, class Function>
ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n,
Function f);
Effects: Применяется f к результату разыменования каждого итератора в диапазоне [first, first + n). [ Note: Если тип first удовлетворяет требованиям изменяемого итератора, f может применять непостоянные функции через разыменованный итератор. ] — end note
Remarks: Если f возвращает результат, результат игнорируется. Реализации не имеют права [algorithms.parallel.exec] делать произвольные копии элементов из входной последовательности.
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 если такой итератор не найден.
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);
Returns: Последний итератор i в диапазон , [first1, last1 - (last2 - first2)) например , что для каждого неотрицательного целого числа n < (last2 - first2), следующие соответствующие условия: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Возвращает, last1 если [first2, last2) пуст или если такой итератор не найден.
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);
Returns: Первый итератор i в диапазоне [first1, last1) , что для некоторых итератора j в диапазоне [first2, last2) выполняются следующие условия: *i == *j, pred(*i,*j) != false. Возвращает, last1 если [first2, last2) пуст или если такой итератор не найден.
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 если такой итератор не найден.
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.
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) ниже.
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)) применения соответствующего предиката.
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: Нет приложений соответствующего предиката if ForwardIterator1 и, ForwardIterator2 отвечающих требованиям итераторов произвольного доступа и last1 - first1 != last2 - first2. В противном случае точно last1 - first1 приложения соответствующего предиката if equal(first1, last1, first2, last2) вернутся, true если pred он не указан в списке аргументов, или equal(first1, last1, first2, last2, pred) вернутся, true если pred был задан в списке аргументов; в противном случае, в худшем случае O(N2), где N имеет значение last1 - first1.
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);
Returns: Первый итератор i в диапазон [first1, last1 - (last2-first2)) таким образом, что для каждого неотрицательного целого числа n меньше last2 - first2 следующих соответствующих условий: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Возвращает, first1 если [first2, last2) пусто, в противном случае возвращает, last1 если такой итератор не найден.
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]).
Returns: Первый итератор i в диапазон [first, last-count) таким образом, что для каждого неотрицательного целого числа n меньше count следующих соответствующих условий: *(i + n) == value, pred(*(i + n),value) != false. Возвращает, last если такой итератор не найден.
template<class ForwardIterator, class Searcher>
ForwardIterator search(ForwardIterator first, ForwardIterator last,
const Searcher& searcher);
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
Effects: Копирует элементы диапазона [first, last) в диапазон, [result, result + (last - first)) начиная с first и до last. Для каждого неотрицательного целого числа n < (last - first)выполняется *(result + n) = *(first + n).
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(ExecutionPolicy&& policy,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
Effects: Копирует элементы диапазона [first, last) в диапазон [result, result + (last - first)). Для каждого неотрицательного целого числа n < (last - first)выполняется *(result + n) = *(first + n).
template<class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size n,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
ForwardIterator2 copy_n(ExecutionPolicy&& exec,
ForwardIterator1 first, Size n,
ForwardIterator2 result);
template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate>
ForwardIterator2 copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, Predicate pred);
Effects: Копирует все элементы, на которые ссылается итератор, i в диапазоне, [first, last) для которого pred(*i) есть true.
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
copy_backward следует использовать вместо копирования, когда он last находится в диапазоне [result - (last - first), result).
template<class InputIterator, class OutputIterator>
OutputIterator move(InputIterator first, InputIterator last, OutputIterator result);
Effects: Перемещает элементы диапазона [first, last) в диапазон, [result, result + (last - first)) начиная с первого и заканчивая последним. Для каждого неотрицательного целого числа n < (last-first)выполняется *(result + n) = std::move(*(first + n)).
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 move(ExecutionPolicy&& policy,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
Effects: Перемещает элементы из диапазона [first, last) в диапазон [result, result + (last - first)). Для каждого неотрицательного целого числа n < (last - first)выполняется *(result + n) = std::move(*(first + n)).
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
move_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
move_backward следует использовать вместо move, когда последний находится в диапазоне [result - (last - first), result).
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
Requires: Эти два диапазона , [first1, last1) и [first2, first2 + (last1 - first1)) не должны перекрывать. *(first1 + n) будет swappable with *(first2 + n).
Effects: Для каждого неотрицательных целого числа n < (last1 - first1) выполняет: swap(*(first1 + n), *(first2 + n)).
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
Requires: a и b должно быть разыменовано. *a будет swappable with *b.
template<class InputIterator, class OutputIterator,
class UnaryOperation>
OutputIterator
transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class UnaryOperation>
ForwardIterator2
transform(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 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);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class BinaryOperation>
ForwardIterator
transform(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator result,
BinaryOperation binary_op);
Effects: Назначает каждому итератору i в диапазоне [result, result + (last1 - first1)) новое соответствующее значение, равное op(*(first1 + (i - result))) или binary_op(*(first1 + (i - result)), *(first2 + (i - result))).
Complexity: Собственно last1 - first1 приложения op или binary_op. Это требование также распространяется на перегрузку с расширением ExecutionPolicy .
Remarks: result может быть равно first в случае унарного преобразования, first1 или first2 в случае двоичного преобразования.
Использование полностью замкнутых диапазонов является преднамеренным.
template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator, class T>
void replace(ExecutionPolicy&& exec,
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 ExecutionPolicy, class ForwardIterator, class Predicate, class T>
void replace_if(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);
Effects: Заменяет элементы, на которые ссылается итератор i в диапазоне [first, last) с new_value, при выполнении следующих соответствующих условий: *i == old_value, pred(*i) != false.
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 ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
ForwardIterator2
replace_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 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);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Predicate, class T>
ForwardIterator2
replace_copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result,
Predicate pred, const T& new_value);
Effects: Присваивается каждому итератору i в диапазоне [result, result + (last - first)) либо, new_value либо в *(first + (i - result)) зависимости от того, выполняются ли следующие соответствующие условия:
*(first + (i - result)) == old_value pred(*(first + (i - result))) != false
template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
void fill(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, const T& value);
template<class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value);
template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
ForwardIterator fill_n(ExecutionPolicy&& exec,
ForwardIterator first, Size n, const T& value);
Requires: Выражение value должно быть writable передано итератору вывода. Тип Size должен быть преобразован в целочисленный тип ([conv.integral], [class.conv]).
Effects: Эти fill алгоритмы назначения value через все итераторы в диапазоне [first, last). Эти fill_n алгоритмы назначение value через все итераторы в диапазоне , [first, first + n) если n положительно, в противном случае они ничего не делают.
Returns: fill_n возвращает first + n для неотрицательных значений n и first для отрицательных значений.
template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Generator>
void generate(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Generator gen);
template<class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator>
ForwardIterator generate_n(ExecutionPolicy&& exec,
ForwardIterator first, Size n, Generator gen);
Requires: gen не принимает аргументов, Size может быть преобразован в целочисленный тип ([conv.integral], [class.conv]).
Effects: Эти generate алгоритмы вызвать объект функции gen и присвоить возвращаемое значение gen через все итераторы в диапазоне [first, last). Эти generate_n алгоритмы вызов функции объекта gen и присвоить возвращаемое значение gen через все итераторы в диапазоне , [first, first + n) если n положительно, в противном случае они ничего не делают.
Returns: generate_n возвращает first + n для неотрицательных значений n и first для отрицательных значений.
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
ForwardIterator remove(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator remove_if(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Predicate pred);
Requires: Тип *first должен удовлетворять требованиям MoveAssignable requirements.
Effects: Устраняет все элементы ссылаются итератором i в диапазоне , [first, last) для которых выполняются следующие соответствующие условия: *i == value, pred(*i) != false.
[ Note: Каждый элемент в диапазоне [ret, last), где ret - возвращаемое значение, имеет допустимое, но неуказанное состояние, потому что алгоритмы могут исключать элементы, перемещаясь из элементов, которые изначально находились в этом диапазоне. ] — end note
template<class InputIterator, class OutputIterator, class T>
OutputIterator
remove_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& value);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
ForwardIterator2
remove_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, const T& value);
template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator
remove_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Predicate>
ForwardIterator2
remove_copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, Predicate pred);
Requires: Диапазоны [first, last) и [result, result + (last - first)) не должны перекрываться. Выражение *result = *first действительно. [ Note: Для перегрузок с a ExecutionPolicyможет возникнуть снижение производительности, если iterator_traits<ForwardIterator1>::value_type это не так MoveConstructible (таблица 23). ] — end note
Effects: Копирование всех элементов , упомянутых в итератор i в диапазоне ,[first, last) для которых выполняются соответствующие условия не выполняются: *i == value, pred(*i) != false.
template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator unique(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
Requires: Функция сравнения должна быть отношением эквивалентности. Тип *first должен удовлетворять требованиям MoveAssignable requirements.
Effects: Для непустого диапазона удаляет все элементы, кроме первого, из каждой последующей группы эквивалентных элементов, на которые ссылается итератор, i в диапазоне, [first + 1, last) для которого выполняются следующие условия: *(i - 1) == *i или pred(*(i - 1), *i) != false.
Complexity: Для непустых диапазонов - в точности (last - first) - 1 применения соответствующего предиката.
template<class InputIterator, class OutputIterator>
OutputIterator
unique_copy(InputIterator first, InputIterator last,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
unique_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
template<class InputIterator, class OutputIterator,
class BinaryPredicate>
OutputIterator
unique_copy(InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator2
unique_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, BinaryPredicate pred);
Requires:
Функция сравнения должна быть отношением эквивалентности.
Диапазоны [first, last) и [result, result+(last-first)) не должны перекрываться.
Выражение *result = *first действительно.
Для перегрузок без значения ExecutionPolicyпозвольте T быть типом значения InputIterator. Если InputIterator соответствует требованиям прямого итератора, то дополнительных требований для T. В противном случае, если OutputIterator соответствует требованиям прямого итератора и его тип значения такой же, как T, то T должно быть CopyAssignable. В противном случае T должны быть оба CopyConstructible и CopyAssignable. [ Note: Для перегрузок с an ExecutionPolicyможет возникнуть снижение производительности, если тип значения ForwardIterator1 не является одновременно CopyConstructible и CopyAssignable. ] — end note
Effects: Копирует только первый элемент из каждой последовательной группы равных элементов, на которую ссылается итератор, i в диапазоне, [first, last) для которого выполняются следующие соответствующие условия: *i == *(i - 1) или pred(*i, *(i - 1)) != false.
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void reverse(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last);
Effects: Для каждого неотрицательного целого числа i < (last - first) / 2применяется iter_swap ко всем парам итераторов first + i, (last - i) - 1.
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable.
template<class BidirectionalIterator, class OutputIterator>
OutputIterator
reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
OutputIterator result);
template<class ExecutionPolicy, class BidirectionalIterator, class ForwardIterator>
ForwardIterator
reverse_copy(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last,
ForwardIterator result);
Effects: Копирование диапазона [first, last) к диапазону [result, result + (last - first)) , что для любого целого неотрицательного числа i < (last - first) следующего присваивания происходит: *(result + (last - first) - 1 - i) = *(first + i).
template<class ForwardIterator>
ForwardIterator
rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
rotate(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator middle, ForwardIterator last);
Requires: [first, middle) и [middle, last) должны быть допустимые диапазоны. ForwardIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и требованиям MoveAssignable.
Effects: Для каждого неотрицательного целого числа i < (last - first)помещает элемент из позиции first + i в позицию first + (i + (last - middle)) % (last - first).
template<class ForwardIterator, class OutputIterator>
OutputIterator
rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
rotate_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 middle, ForwardIterator1 last,
ForwardIterator2 result);
Effects: Копирование диапазона [first, last) к диапазону [result, result + (last - first)) , что для каждого неотрицательного целого числа i < (last - first) следующего присваивания происходит: *(result + i) = *(first + (i + (middle - first)) % (last - first)).
template<class PopulationIterator, class SampleIterator,
class Distance, class UniformRandomBitGenerator>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
SampleIterator out, Distance n,
UniformRandomBitGenerator&& g);
Requires:
PopulationIterator должны удовлетворять требованиям input iterator.
SampleIterator должны удовлетворять требованиям output iterator.
SampleIterator должен удовлетворять дополнительным требованиям а, random access iterator если не PopulationIterator удовлетворяет дополнительным требованиям а forward iterator.
PopulationIteratorТип значения должен быть writable to out.
Distance должен быть целочисленным типом.
remove_reference_t<UniformRandomBitGenerator> должен соответствовать требованиям uniform random bit generator типа, возвращаемый тип которого может быть преобразован в Distance.
out не должно быть в диапазоне [first, last).
Effects: Копирует min(last - first, n) элементы (the sample) из [first, last) (the population) в так out , чтобы каждый возможный образец имел равную вероятность появления. [ Note: Алгоритмы, обеспечивающие такие эффекты, включают selection sampling и reservoir sampling. ] — end note
template<class RandomAccessIterator, class UniformRandomBitGenerator>
void shuffle(RandomAccessIterator first,
RandomAccessIterator last,
UniformRandomBitGenerator&& g);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип remove_reference_t<UniformRandomBitGenerator> должен соответствовать требованиям uniform random bit generator типа, в который можно преобразовать возвращаемый тип iterator_traits<RandomAccessIterator>::difference_type.
Effects: Переставляет элементы в диапазоне [first, last) таким образом, чтобы каждая возможная перестановка этих элементов имела равную вероятность появления.
У всех операций [alg.sorting] есть две версии: одна использует объект функции типа, Compare а другая - объект operator<.
Compare это а function object type. Возвращаемое значение операции вызова функции, примененной к объекту типа Comparewhen contextually converted to bool, дает результат, true если первый аргумент вызова меньше второго, и в false противном случае. Compare comp везде используется для алгоритмов, предполагающих отношение порядка. Предполагается, что comp через разыменованный итератор не будет применяться какая-либо непостоянная функция.
Для всех используемых алгоритмов Compareсуществует версия, которая использует operator< вместо них. То есть по comp(*i, *j) != false умолчанию *i < *j != false. Для алгоритмов, отличных от описанных в [alg.binary.search], comp должен вызывать строгий слабый порядок значений.
Этот термин strict относится к требованию иррефлексивного отношения (!comp(x, x) для всех x), а термин - weak к требованиям, которые не такие строгие, как требования для полного упорядочения, но более сильные, чем требования для частичного упорядочения. Если мы определяем equiv(a, b) как !comp(a, b) && !comp(b, a), то требования таковы, comp и equiv оба должны быть транзитивными отношениями:
comp(a, b) && comp(b, c) подразумевает comp(a, c)
equiv(a, b) && equiv(b, c) подразумевает equiv(a, c)
[ Note: В этих условиях можно показать, что
equiv является отношением эквивалентности
comp индуцирует корректно определенное отношение на классах эквивалентности, определяемых equiv
Индуцированное отношение - это строгий тотальный порядок.
— end note ]
Последовательность является ,sorted with respect to a comparator comp если для каждого итератора ,i указывающей последовательность , и каждый неотрицательное целое число n такое , что i + n является действительным итератора , указывающий на элемент последовательности, comp(*(i + n), *i) == false.
Последовательность [start, finish) - partitioned with respect to это выражение, f(e) если существует такое целое число n , что для всех 0 <= i < (finish - start), f(*(start + i)) есть true тогда и только тогда, когда i < n.
В описаниях функций, которые имеют дело с отношениями упорядочения, мы часто используем понятие эквивалентности для описания таких понятий, как стабильность. Эквивалентность, о которой мы говорим, не обязательно является operator==отношением эквивалентности, индуцированным строгим слабым порядком. То есть два элемента a и b считаются эквивалентными тогда и только тогда, когда !(a < b) && !(b < a).
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void stable_sort(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Complexity: Максимум Nlog2(N) сравнений, где N=last - first, но только NlogN сравнения, если достаточно дополнительной памяти.
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void partial_sort(ExecutionPolicy&& exec,
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *result_first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Помещает первые min(last - first, result_last - result_first) отсортированные элементы в диапазон [result_first, result_first + min(last - first, result_last - result_first)).
template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
bool is_sorted(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
Returns: Если (last - first) < 2, вернется last. В противном случае, возвращает последний итератор i в [first, last] течение которого диапазон [first, i) сортируется.
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void nth_element(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: После nth_element элемента в позиции, на которую указывает, nth находится элемент, который был бы в этой позиции, если бы весь диапазон был отсортирован, если только nth == last. Также для каждого итератора i в диапазоне [first, nth) и каждого итератора j в диапазоне [nth, last) он содержит: !(*j < *i) или comp(*j, *i) == false.
Все алгоритмы в этом разделе являются версиями двоичного поиска и предполагают, что просматриваемая последовательность разделена по отношению к выражению, сформированному путем привязки ключа поиска к аргументу неявной или явной функции сравнения. Они работают с итераторами с неслучайным доступом, сводя к минимуму количество сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов с произвольным доступом, поскольку эти алгоритмы выполняют логарифмическое количество шагов через структуру данных. Для итераторов с неслучайным доступом они выполняют линейное количество шагов.
template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires: Элементы e из [first, last) должны быть разделены по отношению к экспрессии e < value или comp(e, value).
Returns: Самыйi дальний итератор в диапазоне, [first, last] такой, что для каждого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) != false.
template<class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires: Элементы e из [first, last) должны быть разделены по отношению к экспрессии !(value < e) или !comp(value, e).
Returns: Самыйi дальний итератор в диапазоне, [first, last] такой, что для каждого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value < *j) или comp(value, *j) == false.
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value,
Compare comp);
Requires: Элементы e из [first, last) должны быть разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value влечет !(value < e) или comp(e, value) влечет !comp(value, e).
Returns:
make_pair(lower_bound(first, last, value), upper_bound(first, last, value))
или
make_pair(lower_bound(first, last, value, comp), upper_bound(first, last, value, comp))
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires: Элементы e из [first, last) разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value предполагает !(value < e) или comp(e, value) подразумевает !comp(value, e).
Returns: true еслиi в диапазоне есть итератор [first, last) , удовлетворяющий соответствующим условиям: !(*i < value) && !(value < *i) или comp(*i, value) == false && comp(value, *i) == false.
template <class InputIterator, class Predicate>
bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
template <class ExecutionPolicy, class ForwardIterator, class Predicate>
bool is_partitioned(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
Requires: Для перегрузки с нет ExecutionPolicy, InputIterator«s тип значения должен быть конвертирован в Predicate» S типа аргумента. Для перегрузки с ExecutionPolicy, ForwardIterator«с типом значения должны быть конвертированы в Predicate» S типа аргумента.
Returns: true if [first, last) пуст или если [first, last) разделен на pred, то есть если все элементы, удовлетворяющие условиям, pred появляются перед теми, которые этого не делают.
template<class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first, ForwardIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator
partition(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
Requires: ForwardIterator должны удовлетворять требованиям ValueSwappable.
Effects: Помещает все элементы в диапазоне, [first, last) которые удовлетворяют, pred перед всеми элементами, которые ему не удовлетворяют.
Returns: Итератора i таким образом, что для каждого итератора j в диапазоне [first, i) pred(*j) != false, и для каждого итератора k в диапазоне [i, last), pred(*k) == false.
Complexity: Пусть N=last - first:
Для перегрузки без ExecutionPolicy, как раз N применения предиката. В большинстве N/2 случаев меняет местами, если ForwardIterator соответствует BidirectionalIterator требованиям, и не больше, в N противном случае.
Для перегрузки с ExecutionPolicy, O(NlogN) свопами и O(N) приложениями предиката.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first, BidirectionalIterator last,
Predicate pred);
template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last,
Predicate pred);
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Помещает все элементы в диапазоне, [first, last) которые удовлетворяют, pred перед всеми элементами, которые ему не удовлетворяют.
Returns: Итератора i таким образом, что для каждого итератора j в диапазоне [first, i), pred(*j) != falseи для каждого итератора k в диапазоне [i, last), pred(*k) == false. Относительный порядок элементов в обеих группах сохраняется.
Complexity: Пусть N = last - first:
Для перегрузки без подкачки, ExecutionPolicyсамое большее NlogN подкачки, но только O(N) подкачки, если достаточно дополнительной памяти. Собственно N применения сказуемого.
Для перегрузки с ExecutionPolicy, O(NlogN) свопами и O(N) приложениями предиката.
template <class InputIterator, class OutputIterator1,
class OutputIterator2, class Predicate>
pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last,
OutputIterator1 out_true, OutputIterator2 out_false,
Predicate pred);
template <class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
class ForwardIterator2, class Predicate>
pair<ForwardIterator1, ForwardIterator2>
partition_copy(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
ForwardIterator1 out_true, ForwardIterator2 out_false,
Predicate pred);
Requires:
Для перегрузки без каких - либо ExecutionPolicy, InputIterator«с типом значение должно быть CopyAssignable (таблица 26), и должны быть доступны для записи ([iterator.requirements.general]) к out_true и out_false OutputIteratorс, и должны быть конвертированы в Predicate» с аргументом типа.
Для перегрузки с ExecutionPolicy, ForwardIterator«с типом значения должны быть CopyAssignable, и должны быть доступны для записи на out_true и out_false ForwardIteratorс, и должны быть конвертированы в Predicate» с аргументом типа. [ Note: Если ForwardIteratorтип значения не является типом значения, это может повлиять на производительностьCopyConstructible. ] — end note
Для обеих перегрузок входной диапазон не должен перекрываться ни с одним из выходных диапазонов.
Effects: Для каждого итератора i в [first, last)копии *i в начале диапазона выходной мощности с , out_true если pred(*i) это true, или в диапазоне , начиная с выхода в out_false противном случае.
Returns: Такая пара p , которая p.first является концом выходного диапазона, начинающегося с, out_true и p.second является концом выходного диапазона, начинающегося с out_false.
template<class ForwardIterator, class Predicate>
ForwardIterator partition_point(ForwardIterator first,
ForwardIterator last,
Predicate pred);
Requires: ForwardIteratorТип значения должен быть преобразован в Predicateтип аргумента. [first, last) должны быть разделены на pred, т. е. все элементы, которые удовлетворяют, pred должны появляться перед теми, которые не удовлетворяют .
Returns: Итератор mid такой, что all_of(first, mid, pred) и none_of(mid, last, pred) есть оба true.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
merge(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
merge(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Requires: Диапазоны [first1, last1) и [first2, last2) должны быть отсортированы относительно operator< или comp. Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.
Effects: Копирует все элементы двух диапазонов [first1, last1) и [first2, last2) в диапазон [result, result_last), где result_last есть result + (last1 - first1) + (last2 - first2), так что результирующий диапазон удовлетворяет is_sorted(result, result_last) или is_sorted(result, result_last, comp), соответственно.
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
Requires: Диапазоны [first, middle) и [middle, last) должны быть отсортированы относительно operator< или comp. BidirectionalIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Объединяет два отсортированных последовательных диапазона [first, middle) и [middle, last), помещая результат слияния в диапазон [first, last). Результирующий диапазон будет в порядке неубывания; то есть, для каждого итератора i в [first, last) другом чем first, состояние *i < *(i - 1) или, соответственно, comp(*i, *(i - 1)) будет false.
Complexity: Пусть N=last - first:
Для перегрузок с отсутствием ExecutionPolicy, если доступно достаточно дополнительной памяти, именно N−1 сравнения.
Для перегрузок с нет, ExecutionPolicy если дополнительная память недоступна, O(NlogN) сравнения.
Для перегрузок ExecutionPolicy, O(NlogN) сравнений.
В этом разделе определены все основные операции над сортированными структурами. Они также работают с multisets несколькими копиями эквивалентных элементов. Семантика заданных операций обобщается на multisets стандартным способом, определяя set_union() максимальное количество вхождений каждого элемента, set_intersection() минимальное и т. Д.
template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool includes(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
bool includes(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
Returns: true если [first2, last2) пусто или если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Вfalse противном случае возвращается .
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_union(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_union(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Создает отсортированное объединение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в одном или обоих диапазонах.
Remarks: Если [first1, last1) содержит m элементы, которые эквивалентны друг другу , и [first2, last2) содержит n элементы, которые эквивалентны их, то все m элементы из первого диапазона должны быть скопированы в выходном диапазоне, в порядке, а затем max(n−m,0) элементы из второго диапазона должны быть скопированы в выходном диапазоне , чтобы.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_intersection(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_intersection(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Создает отсортированное пересечение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в обоих диапазонах.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Копирует элементы диапазона [first1, last1) , отсутствующие в диапазоне, [first2, last2) в диапазон, начинающийся с result. Элементы в построенном диапазоне сортируются.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
Effects: Копирует элементы диапазона [first1, last1) , отсутствующие в диапазоне [first2, last2), и элементы диапазона [first2, last2) , отсутствующие в диапазоне, [first1, last1) в диапазон, начинающийся с result. Элементы в построенном диапазоне сортируются.
Remarks: Если [first1, last1) содержит m элементы, которые эквивалентны друг другу и [first2, last2) содержит n элементы, которые приравненных к ним, то |m−n| из этих элементов должны быть скопированы в выходной диапазон: последний m−n из этих элементов от [first1, last1) если m>n, и последний n−m из этих элементов , [first2, last2) если m<n.
A heap - это особая организация элементов в диапазоне между двумя итераторами произвольного доступа, [a, b) такая что:
С N = b - a, для всех i, 0<i<N, comp(a[⌊i−12⌋], a[i]) есть false.
*a может быть удалено pop_heap(), или новый элемент добавляет push_heap()в O(logN) время.
make_heap() преобразует диапазон в кучу и sort_heap() превращает кучу в отсортированную последовательность.
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Диапазон [first, last - 1) должен быть допустимой кучей. Тип *first должен удовлетворять MoveConstructible requirements и MoveAssignable requirements.
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Диапазон [first, last) должен быть действительной непустой кучей. RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
Effects: Меняет местами значение в местоположении first со значением в местоположении last - 1 и превращается [first, last - 1) в кучу.
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Тип *first должен удовлетворять MoveConstructible requirements и MoveAssignable requirements.
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Requires: Диапазон [first, last) должен быть допустимой кучей. RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.
template<class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
bool is_heap(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last, Compare comp);
template<class RandomAccessIterator>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator>
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Returns: Если (last - first) < 2, вернется last. В противном случае, возвращает последний итератор i в [first, last] течение которого диапазон [first, i) является пирамидой.
template<class T> constexpr const T& min(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& min(const T& a, const T& b, Compare comp);
Requires: Для первой формы тип T должен быть LessThanComparable.
template<class T>
constexpr T min(initializer_list<T> t);
template<class T, class Compare>
constexpr T min(initializer_list<T> t, Compare comp);
Requires: T должно быть CopyConstructible и t.size() > 0. Для первой формы тип T должен быть LessThanComparable.
Remarks: Возвращает копию самого левого аргумента, если несколько аргументов эквивалентны наименьшему.
template<class T> constexpr const T& max(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& max(const T& a, const T& b, Compare comp);
Requires: Для первой формы тип T должен быть LessThanComparable.
template<class T>
constexpr T max(initializer_list<T> t);
template<class T, class Compare>
constexpr T max(initializer_list<T> t, Compare comp);
Requires: T должно быть CopyConstructible и t.size() > 0. Для первой формы тип T должен быть LessThanComparable.
Remarks: Возвращает копию самого левого аргумента, если несколько аргументов эквивалентны самому большому.
template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
Requires: Для первой формы тип T должен быть LessThanComparable.
Returns: pair<const T&, const T&>(b, a) если b меньше a, и в pair<const T&, const T&>(a, b) противном случае.
template<class T>
constexpr pair<T, T> minmax(initializer_list<T> t);
template<class T, class Compare>
constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
Requires: T должно быть CopyConstructible и t.size() > 0. Для первой формы тип T должен быть LessThanComparable.
Returns: pair<T, T>(x, y), где x имеет наименьшее и y наибольшее значение в списке инициализаторов.
Remarks: x является копией самого левого аргумента, когда несколько аргументов эквивалентны наименьшему. y является копией самого правого аргумента, когда несколько аргументов эквивалентны самому большому.
template<class ForwardIterator>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator min_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator min_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
Returns: Первый итератор i в диапазоне, [first, last) такой, что для каждого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*j < *i) или comp(*j, *i) == false. Возвращает, last если first == last.
template<class ForwardIterator>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator max_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Compare comp);
Returns: Первый итератор i в диапазоне, [first, last) такой, что для каждого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*i < *j) или comp(*i, *j) == false. Возвращает, last если first == last.
template<class ForwardIterator>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Compare comp);
Returns: make_pair(first, first) если [first, last) пусто, в противном случае make_pair(m, M)где m - первый итератор в [first, last) таком, что ни один итератор в диапазоне не ссылается на меньший элемент, а где M - последний итератор266 в [first, last) таком, что ни один итератор в диапазоне не ссылается на больший элемент.
Complexity: В большинстве max(⌊32(N−1)⌋,0) случаев применения соответствующего предиката, где N есть last - first.
Это поведение намеренно отличается от max_element().
template<class T>
constexpr const T& clamp(const T& v, const T& lo, const T& hi);
template<class T, class Compare>
constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
Requires: Значение lo не должно быть больше hi. Для первой формы тип T должен быть LessThanComparable.
template<class InputIterator1, class InputIterator2>
bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool
lexicographical_compare(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class Compare>
bool
lexicographical_compare(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
Returns: true если последовательность элементов, определенная диапазоном [first1, last1) , лексикографически меньше, чем последовательность элементов, определенных диапазоном, [first2, last2) и в false противном случае.
Complexity: По большинству 2min(last1 - first1, last2 - first2) приложений соответствующее сравнение.
Remarks: Если две последовательности имеют одинаковое количество элементов и их соответствующие элементы (если есть) эквивалентны, то ни одна из последовательностей не является лексикографически меньшей, чем другая. Если одна последовательность является префиксом другой, то более короткая последовательность лексикографически меньше, чем более длинная последовательность. В противном случае лексикографическое сравнение последовательностей дает тот же результат, что и сравнение первой соответствующей пары неэквивалентных элементов.
[ Example: Следующий пример реализации удовлетворяет этим требованиям:
for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) { if (*first1 < *first2) return true; if (*first2 < *first1) return false; } return first1 == last1 && first2 != last2;
— end example ]
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable.
Effects: Принимает последовательность, определенную диапазоном, [first, last) и преобразует ее в следующую перестановку. Следующая перестановка находится в предположении, что множество всех перестановок лексикографически отсортировано относительно operator< или comp.
Returns: true если такая перестановка существует. В противном случае он преобразует последовательность в наименьшую перестановку, то есть в сортированную по возрастанию, и возвращает false.
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Requires: BidirectionalIterator должны удовлетворять требованиям ValueSwappable.
Effects: Принимает последовательность, определенную диапазоном, [first, last) и преобразует ее в предыдущую перестановку. Предыдущая перестановка находится в предположении, что набор всех перестановок лексикографически отсортирован относительно operator< или comp.
Returns: true если такая перестановка существует. В противном случае он преобразует последовательность в наибольшую перестановку, то есть отсортированную по убыванию, и возвращает false.
void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
c-compare-pred* compar);
void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
compare-pred* compar);
void qsort(void* base, size_t nmemb, size_t size, c-compare-pred* compar);
void qsort(void* base, size_t nmemb, size_t size, compare-pred* compar);
Remarks: Поведение не определено, если только объекты в массиве, на который указывает, не base имеют тривиального типа.
Throws: Любое исключение, созданное compar() ([res.on.exception.handling]).
См. Также: ISO C 7.22.5.