#include <initializer_list>
namespace std {
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);
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);
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);
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, 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, ForwardIterator first, Size n, Function f);
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);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1,
class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
find_end(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
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);
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, ForwardIterator first,
ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ExecutionPolicy&& exec, ForwardIterator first,
ForwardIterator last,
BinaryPredicate pred);
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);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
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 ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
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);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
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);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search(
ExecutionPolicy&& exec, 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, 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);
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);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(ExecutionPolicy&& exec, 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, 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);
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(
BidirectionalIterator1 first, BidirectionalIterator1 last,
BidirectionalIterator2 result);
template<class InputIterator, class OutputIterator>
OutputIterator move(InputIterator first, InputIterator last,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1,
class ForwardIterator2>
ForwardIterator2 move(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 move_backward(
BidirectionalIterator1 first, BidirectionalIterator1 last,
BidirectionalIterator2 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);
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
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, ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, UnaryOperation 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);
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);
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);
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);
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);
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);
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);
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, ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ExecutionPolicy&& exec, 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, ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator2 unique_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, BinaryPredicate pred);
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void reverse(ExecutionPolicy&& exec, 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, BidirectionalIterator first,
BidirectionalIterator last,
ForwardIterator result);
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);
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);
template<class PopulationIterator, class SampleIterator,
class Distance, class UniformRandomBitGenerator>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
SampleIterator out, Distance n,
UniformRandomBitGenerator&& g);
template<class RandomAccessIterator, class UniformRandomBitGenerator>
void shuffle(RandomAccessIterator first,
RandomAccessIterator last,
UniformRandomBitGenerator&& g);
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);
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);
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);
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);
template<class ForwardIterator, class Predicate>
ForwardIterator partition_point(ForwardIterator first,
ForwardIterator last,
Predicate pred);
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, RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(ExecutionPolicy&& exec, 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, RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void stable_sort(ExecutionPolicy&& exec, 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, RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void partial_sort(ExecutionPolicy&& exec, 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, 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, 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, ForwardIterator first, ForwardIterator last);
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 ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator is_sorted_until(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
Compare comp);
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, RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
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);
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, 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, 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, BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Compare>
bool includes(ExecutionPolicy&& exec, 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, 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, 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, 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, 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, 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, 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, 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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
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, RandomAccessIterator first, RandomAccessIterator last);
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 RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
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, ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator min_element(ExecutionPolicy&& exec, 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, ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(ExecutionPolicy&& exec, 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, ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp);
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);
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, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Compare>
bool lexicographical_compare(
ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
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);
}28.7 Sorting and related operations [alg.sorting]
All the operations in [alg.sorting] have two versions: one that takes a function object of type Compare and one that uses an operator<.
Compare is a function object type. The return value of the function call operation applied to an object of type Compare, when contextually converted to bool, yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.
For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in [alg.binary.search], comp shall induce a strict weak ordering on the values.
The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:
comp(a, b) && comp(b, c) implies comp(a, c)
equiv(a, b) && equiv(b, c) implies equiv(a, c)
[ Note: Under these conditions, it can be shown that
equiv is an equivalence relation
comp induces a well-defined relation on the equivalence classes determined by equiv
The induced relation is a strict total ordering.
— end note ]
A sequence is sorted with respect to a comparator comp if for every iterator i pointing to the sequence and every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, comp(*(i + n), *i) == false.
A sequence [start, finish) is partitioned with respect to an expression f(e) if there exists an integer n such that for all 0 <= i < (finish - start), f(*(start + i)) is true if and only if i < n.
In the descriptions of the functions that deal with ordering relationships we frequently use a notion of equivalence to describe concepts such as stability. The equivalence to which we refer is not necessarily an operator==, but an equivalence relation induced by the strict weak ordering. That is, two elements a and b are considered equivalent if and only if !(a < b) && !(b < a).
28.7.1 Sorting [alg.sort] 28.7.1.1 sort [sort]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);
Effects: Sorts the elements in the range [first, last).
Complexity: O(NlogN) comparisons, where N=last - first.
28.7.1.2 stable_sort [stable.sort]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);
Effects: Sorts the elements in the range [first, last).
Complexity: At most Nlog2(N) comparisons, where N=last - first, but only NlogN comparisons if there is enough extra memory.
28.7.1.3 partial_sort [partial.sort]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);
Effects: Places the first middle - first sorted elements from the range [first, last) into the range [first, middle). The rest of the elements in the range [middle, last) are placed in an unspecified order.
Complexity: Approximately (last - first) * log(middle - first) comparisons.
28.7.1.4 partial_sort_copy [partial.sort.copy]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);
Effects: Places the first min(last - first, result_last - result_first) sorted elements into the range [result_first, result_first + min(last - first, result_last - result_first)).
Returns: The smaller of: result_last or result_first + (last - first).
Complexity: Approximately (last - first) * log(min(last - first, result_last - result_first)) comparisons.
28.7.1.5 is_sorted [is.sorted]template<class ForwardIterator> bool is_sorted(ForwardIterator first, ForwardIterator last);
Returns: is_sorted_until(first, last) == last
template<class ExecutionPolicy, class ForwardIterator> bool is_sorted(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last);
Returns: is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last
template<class ForwardIterator, class Compare> bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
Returns: is_sorted_until(first, last, comp) == last
template<class ExecutionPolicy, class ForwardIterator, class Compare> bool is_sorted(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Compare comp);
Returns:
is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
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: If (last - first) < 2, returns last. Otherwise, returns the last iterator i in [first, last] for which the range [first, i) is sorted.
28.7.2 Nth element [alg.nth.element]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);
Effects: After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted, unless nth == last. Also for every iterator i in the range [first, nth) and every iterator j in the range [nth, last) it holds that: !(*j < *i) or comp(*j, *i) == false.
Complexity: For the overloads with no ExecutionPolicy, linear on average. For the overloads with an ExecutionPolicy, O(N) applications of the predicate, and O(NlogN) swaps, where N=last - first.
28.7.3 Binary search [alg.binary.search]All of the algorithms in this section are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the implied or explicit comparison function. They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure. For non-random access iterators they execute a linear number of steps.
28.7.3.1 lower_bound [lower.bound]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: The elements e of [first, last) shall be partitioned with respect to the expression e < value or comp(e, value).
Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.
Complexity: At most log2(last - first)+O(1) comparisons.
28.7.3.2 upper_bound [upper.bound]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: The elements e of [first, last) shall be partitioned with respect to the expression !(value < e) or !comp(value, e).
Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.
Complexity: At most log2(last - first)+O(1) comparisons.
28.7.3.3 equal_range [equal.range]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: The elements e of [first, last) shall be partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first, last), e < value shall imply !(value < e) or comp(e, value) shall imply !comp(value, e).
Returns:
make_pair(lower_bound(first, last, value),
upper_bound(first, last, value))
or
make_pair(lower_bound(first, last, value, comp),
upper_bound(first, last, value, comp))
Complexity: At most 2∗log2(last - first)+O(1) comparisons.
28.7.3.4 binary_search [binary.search]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: The elements e of [first, last) are partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first, last), e < value implies !(value < e) or comp(e, value) implies !comp(value, e).
Returns: true if there is an iterator i in the range [first, last) that satisfies the corresponding conditions: !(*i < value) && !(value < *i) or comp(*i, value) == false && comp(value, *i) == false.
Complexity: At most log2(last - first)+O(1) comparisons.
28.7.4 Partitions [alg.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, ForwardIterator first, ForwardIterator last, Predicate pred);
Requires: For the overload with no ExecutionPolicy, InputIterator's value type shall be convertible to Predicate's argument type. For the overload with an ExecutionPolicy, ForwardIterator's value type shall be convertible to Predicate's argument type.
Returns: true if [first, last) is empty or if [first, last) is partitioned by pred, i.e. if all elements that satisfy pred appear before those that do not.
Complexity: Linear. At most last - first applications of 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 shall satisfy the requirements of ValueSwappable.
Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.
Returns: An iterator i such that for every iterator j in the range [first, i) pred(*j) != false, and for every iterator k in the range [i, last), pred(*k) == false.
Complexity: Let N=last - first:
For the overload with no ExecutionPolicy, exactly N applications of the predicate. At most N/2 swaps if ForwardIterator meets the BidirectionalIterator requirements and at most N swaps otherwise.
For the overload with an ExecutionPolicy, O(NlogN) swaps and O(N) applications of the predicate.
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);
Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.
Returns: An iterator i such that for every iterator j in the range [first, i), pred(*j) != false, and for every iterator k in the range [i, last), pred(*k) == false. The relative order of the elements in both groups is preserved.
Complexity: Let N = last - first:
For the overload with no ExecutionPolicy, at most NlogN swaps, but only O(N) swaps if there is enough extra memory. Exactly N applications of the predicate.
For the overload with an ExecutionPolicy, O(NlogN) swaps and O(N) applications of the predicate.
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:
For the overload with no ExecutionPolicy, InputIterator's value type shall be CopyAssignable (Table 26), and shall be writable ([iterator.requirements.general]) to the out_true and out_false OutputIterators, and shall be convertible to Predicate's argument type.
For the overload with an ExecutionPolicy, ForwardIterator's value type shall be CopyAssignable, and shall be writable to the out_true and out_false ForwardIterators, and shall be convertible to Predicate's argument type. [ Note: There may be a performance cost if ForwardIterator's value type is not CopyConstructible. — end note ]
For both overloads, the input range shall not overlap with either of the output ranges.
Effects: For each iterator i in [first, last), copies *i to the output range beginning with out_true if pred(*i) is true, or to the output range beginning with out_false otherwise.
Returns: A pair p such that p.first is the end of the output range beginning at out_true and p.second is the end of the output range beginning at out_false.
Complexity: Exactly last - first applications of pred.
template<class ForwardIterator, class Predicate> ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
Requires: ForwardIterator's value type shall be convertible to Predicate's argument type. [first, last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.
Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.
Complexity: O(log(last - first)) applications of pred.
28.7.5 Merge [alg.merge]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: The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator< or comp. The resulting range shall not overlap with either of the original ranges.
Effects: Copies all the elements of the two ranges [first1, last1) and [first2, last2) into the range [result, result_last), where result_last is result + (last1 - first1) + (last2 - first2), such that the resulting range satisfies is_sorted(result, result_last) or is_sorted(result, result_last, comp), respectively.
Returns: result + (last1 - first1) + (last2 - first2).
Complexity: Let N=(last1 - first1) + (last2 - first2):
For the overloads with no ExecutionPolicy, at most N−1 comparisons.
For the overloads with an ExecutionPolicy, O(N) comparisons.
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: The ranges [first, middle) and [middle, last) shall be sorted with respect to operator< or comp. BidirectionalIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.
Effects: Merges two sorted consecutive ranges [first, middle) and [middle, last), putting the result of the merge into the range [first, last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first, last) other than first, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.
Complexity: Let N=last - first:
For the overloads with no ExecutionPolicy, if enough additional memory is available, exactly N−1 comparisons.
For the overloads with no ExecutionPolicy if no additional memory is available, O(NlogN) comparisons.
For the overloads with an ExecutionPolicy, O(NlogN) comparisons.
This section defines all the basic set operations on sorted structures. They also work with multisets containing multiple copies of equivalent elements. The semantics of the set operations are generalized to multisets in a standard way by defining set_union() to contain the maximum number of occurrences of every element, set_intersection() to contain the minimum, and so on.
28.7.6.1 includes [includes]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 if [first2, last2) is empty or if every element in the range [first2, last2) is contained in the range [first1, last1). Returns false otherwise.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
28.7.6.2 set_union [set.union]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);
Requires: The resulting range shall not overlap with either of the original ranges.
Effects: Constructs a sorted union of the elements from the two ranges; that is, the set of elements that are present in one or both of the ranges.
Returns: The end of the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, then all m elements from the first range shall be copied to the output range, in order, and then max(n−m,0) elements from the second range shall be copied to the output range, in order.
28.7.6.3 set_intersection [set.intersection]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);
Requires: The resulting range shall not overlap with either of the original ranges.
Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements that are present in both of the ranges.
Returns: The end of the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, the first min(m,n) elements shall be copied from the first range to the output range, in order.
28.7.6.4 set_difference [set.difference]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);
Requires: The resulting range shall not overlap with either of the original ranges.
Effects: Copies the elements of the range [first1, last1) which are not present in the range [first2, last2) to the range beginning at result. The elements in the constructed range are sorted.
Returns: The end of the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, the last max(m−n,0) elements from [first1, last1) shall be copied to the output range.
28.7.6.5 set_symmetric_difference [set.symmetric.difference]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);
Requires: The resulting range shall not overlap with either of the original ranges.
Effects: Copies the elements of the range [first1, last1) that are not present in the range [first2, last2), and the elements of the range [first2, last2) that are not present in the range [first1, last1) to the range beginning at result. The elements in the constructed range are sorted.
Returns: The end of the constructed range.
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
Remarks: If [first1, last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, then |m−n| of those elements shall be copied to the output range: the last m−n of these elements from [first1, last1) if m>n, and the last n−m of these elements from [first2, last2) if m<n.
28.7.7 Heap operations [alg.heap.operations]A heap is a particular organization of elements in a range between two random access iterators [a, b) such that:
With N = b - a, for all i, 0<i<N, comp(a[⌊i−12⌋], a[i]) is false.
*a may be removed by pop_heap(), or a new element added by push_heap(), in O(logN) time.
These properties make heaps useful as priority queues.
make_heap() converts a range into a heap and sort_heap() turns a heap into a sorted sequence.
28.7.7.1 push_heap [push.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);
Effects: Places the value in the location last - 1 into the resulting heap [first, last).
Complexity: At most log(last - first) comparisons.
28.7.7.2 pop_heap [pop.heap]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: The range [first, last) shall be a valid non-empty heap. RandomAccessIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.
Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first, last - 1) into a heap.
Complexity: At most 2log(last - first) comparisons.
28.7.7.3 make_heap [make.heap]template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Effects: Constructs a heap out of the range [first, last).
Complexity: At most 3(last - first) comparisons.
28.7.7.4 sort_heap [sort.heap]template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Effects: Sorts elements in the heap [first, last).
Complexity: At most NlogN comparisons, where N=last - first.
28.7.7.5 is_heap [is.heap]template<class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
Returns: is_heap_until(first, last) == last
template<class ExecutionPolicy, class RandomAccessIterator> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last);
Returns: is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last
template<class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Returns: is_heap_until(first, last, comp) == last
template<class ExecutionPolicy, class RandomAccessIterator, class Compare> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Returns:
is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
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: If (last - first) < 2, returns last. Otherwise, returns the last iterator i in [first, last] for which the range [first, i) is a heap.
28.7.8 Minimum and maximum [alg.min.max]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);
Returns: The smaller value.
Remarks: Returns the first argument when the arguments are equivalent.
Complexity: Exactly one comparison.
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 shall be CopyConstructible and t.size() > 0. For the first form, type T shall be LessThanComparable.
Returns: The smallest value in the initializer_list.
Remarks: Returns a copy of the leftmost argument when several arguments are equivalent to the smallest.
Complexity: Exactly t.size() - 1 comparisons.
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);
Returns: The larger value.
Remarks: Returns the first argument when the arguments are equivalent.
Complexity: Exactly one comparison.
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 shall be CopyConstructible and t.size() > 0. For the first form, type T shall be LessThanComparable.
Returns: The largest value in the initializer_list.
Remarks: Returns a copy of the leftmost argument when several arguments are equivalent to the largest.
Complexity: Exactly t.size() - 1 comparisons.
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);
Returns: pair<const T&, const T&>(b, a) if b is smaller than a, and pair<const T&, const T&>(a, b) otherwise.
Remarks: Returns pair<const T&, const T&>(a, b) when the arguments are equivalent.
Complexity: Exactly one comparison.
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 shall be CopyConstructible and t.size() > 0. For the first form, type T shall be LessThanComparable.
Returns: pair<T, T>(x, y), where x has the smallest and y has the largest value in the initializer list.
Remarks: x is a copy of the leftmost argument when several arguments are equivalent to the smallest. y is a copy of the rightmost argument when several arguments are equivalent to the largest.
Complexity: At most (3/2)t.size() applications of the corresponding predicate.
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: The first iterator i in the range [first, last) such that for every iterator j in the range [first, last) the following corresponding conditions hold: !(*j < *i) or comp(*j, *i) == false. Returns last if first == last.
Complexity: Exactly max(last - first - 1,0) applications of the corresponding comparisons.
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: The first iterator i in the range [first, last) such that for every iterator j in the range [first, last) the following corresponding conditions hold: !(*i < *j) or comp(*i, *j) == false. Returns last if first == last.
Complexity: Exactly max(last - first - 1,0) applications of the corresponding comparisons.
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) if [first, last) is empty, otherwise make_pair(m, M), where m is the first iterator in [first, last) such that no iterator in the range refers to a smaller element, and where M is the last iterator266 in [first, last) such that no iterator in the range refers to a larger element.
Complexity: At most max(⌊32(N−1)⌋,0) applications of the corresponding predicate, where N is last - first.
28.7.9 Bounded value [alg.clamp]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: The value of lo shall be no greater than hi. For the first form, type T shall be LessThanComparable.
Returns: lo if v is less than lo, hi if hi is less than v, otherwise v.
[ Note: If NaN is avoided, T can be a floating-point type. — end note ]
Complexity: At most two comparisons.
28.7.10 Lexicographical comparison [alg.lex.comparison]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 if the sequence of elements defined by the range [first1, last1) is lexicographically less than the sequence of elements defined by the range [first2, last2) and false otherwise.
Complexity: At most 2min(last1 - first1, last2 - first2) applications of the corresponding comparison.
Remarks: If two sequences have the same number of elements and their corresponding elements (if any) are equivalent, then neither sequence is lexicographically less than the other. If one sequence is a prefix of the other, then the shorter sequence is lexicographically less than the longer sequence. Otherwise, the lexicographical comparison of the sequences yields the same result as the comparison of the first corresponding pair of elements that are not equivalent.
[ Example: The following sample implementation satisfies these requirements:
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 ]
[ Note: An empty sequence is lexicographically less than any non-empty sequence, but not less than any empty sequence. — end note ]
28.7.11 Permutation generators [alg.permutation.generators]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 shall satisfy the requirements of ValueSwappable.
Effects: Takes a sequence defined by the range [first, last) and transforms it into the next permutation. The next permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to operator< or comp.
Returns: true if such a permutation exists. Otherwise, it transforms the sequence into the smallest permutation, that is, the ascendingly sorted one, and returns false.
Complexity: At most (last - first) / 2 swaps.
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 shall satisfy the requirements of ValueSwappable.
Effects: Takes a sequence defined by the range [first, last) and transforms it into the previous permutation. The previous permutation is found by assuming that the set of all permutations is lexicographically sorted with respect to operator< or comp.
Returns: true if such a permutation exists. Otherwise, it transforms the sequence into the largest permutation, that is, the descendingly sorted one, and returns false.
Complexity: At most (last - first) / 2 swaps.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4