%!TEX root = std.tex

\rSec0[algorithms]{Algorithms library}

\rSec1[algorithms.general]{General}

\pnum

This Clause describes components that \Cpp programs may use to perform

algorithmic operations on containers (Clause~\ref{containers}) and other sequences.

\pnum

The following subclauses describe components for

non-modifying sequence operation,

modifying sequence operations,

sorting and related operations,

and algorithms from the ISO C library,

as summarized in Table~\ref{tab:algorithms.summary}.

\begin{libsumtab}{Algorithms library summary}{tab:algorithms.summary}

\ref{alg.nonmodifying} & Non-modifying sequence operations & \\

\ref{alg.modifying.operations} & Mutating sequence operations & \tcode{<algorithm>} \\

\ref{alg.sorting} & Sorting and related operations & \\ \hline

\ref{alg.c.library} & C library algorithms & \tcode{<cstdlib>} \\ \hline

\end{libsumtab}

\synopsis{Header \tcode{<algorithm>} synopsis}

\indexlibrary{\idxhdr{algorithm}}%

\begin{codeblock}

#include <initializer_list>

namespace std {

// \ref{alg.nonmodifying}, non-modifying sequence operations:

template <class InputIterator, class Predicate>

bool all_of(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Predicate>

bool any_of(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Predicate>

bool none_of(InputIterator first, InputIterator last, Predicate pred);

template<class InputIterator, class Function>

Function for_each(InputIterator first, InputIterator last, Function f);

template<class InputIterator, class T>

InputIterator find(InputIterator first, InputIterator last,

const T& value);

template<class InputIterator, class Predicate>

InputIterator find_if(InputIterator first, InputIterator last,

Predicate pred);

template<class InputIterator, class Predicate>

InputIterator find_if_not(InputIterator first, InputIterator 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 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 ForwardIterator>

ForwardIterator adjacent_find(ForwardIterator first,

ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>

ForwardIterator adjacent_find(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 InputIterator, class Predicate>

typename iterator_traits<InputIterator>::difference_type

count_if(InputIterator first, InputIterator 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 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 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 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);

// \ref{alg.modifying.operations}, modifying sequence operations:

// \ref{alg.copy}, copy:

template<class InputIterator, class OutputIterator>

OutputIterator copy(InputIterator first, InputIterator last,

OutputIterator result);

template<class InputIterator, class Size, class OutputIterator>

OutputIterator copy_n(InputIterator first, Size n,

OutputIterator result);

template<class InputIterator, class OutputIterator, class Predicate>

OutputIterator copy_if(InputIterator first, InputIterator last,

OutputIterator result, Predicate pred);

template<class BidirectionalIterator1, class BidirectionalIterator2>

BidirectionalIterator2 copy_backward(

BidirectionalIterator1 first, BidirectionalIterator1 last,

BidirectionalIterator2 result);

// \ref{alg.move}, move:

template<class InputIterator, class OutputIterator>

OutputIterator move(InputIterator first, InputIterator last,

OutputIterator result);

template<class BidirectionalIterator1, class BidirectionalIterator2>

BidirectionalIterator2 move_backward(

BidirectionalIterator1 first, BidirectionalIterator1 last,

BidirectionalIterator2 result);

// \ref{alg.swap}, swap:

template<class ForwardIterator1, class ForwardIterator2>

ForwardIterator2 swap_ranges(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 ForwardIterator, class T>

void replace(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 InputIterator, class OutputIterator, class T>

OutputIterator replace_copy(InputIterator first, InputIterator last,

OutputIterator 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 ForwardIterator, class T>

void fill(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 ForwardIterator, class Generator>

void generate(ForwardIterator first, ForwardIterator last,

Generator gen);

template<class OutputIterator, class Size, class Generator>

OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

template<class ForwardIterator, class T>

ForwardIterator remove(ForwardIterator first, ForwardIterator last,

const T& value);

template<class ForwardIterator, class Predicate>

ForwardIterator remove_if(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 InputIterator, class OutputIterator, class Predicate>

OutputIterator remove_copy_if(InputIterator first, InputIterator last,

OutputIterator 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 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 BidirectionalIterator>

void reverse(BidirectionalIterator first, BidirectionalIterator last);

template<class BidirectionalIterator, class OutputIterator>

OutputIterator reverse_copy(BidirectionalIterator first,

BidirectionalIterator last,

OutputIterator result);

template<class ForwardIterator>

ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,

ForwardIterator last);

template<class ForwardIterator, class OutputIterator>

OutputIterator rotate_copy(

ForwardIterator first, ForwardIterator middle,

ForwardIterator last, OutputIterator result);

// \ref{alg.random.shuffle}, shuffle:

template<class RandomAccessIterator, class UniformRandomNumberGenerator>

void shuffle(RandomAccessIterator first,

RandomAccessIterator last,

UniformRandomNumberGenerator&& g);

// \ref{alg.partitions}, partitions:

template <class InputIterator, class Predicate>

bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);

template<class ForwardIterator, class Predicate>

ForwardIterator partition(ForwardIterator first,

ForwardIterator last,

Predicate pred);

template<class BidirectionalIterator, class Predicate>

BidirectionalIterator stable_partition(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 ForwardIterator, class Predicate>

ForwardIterator partition_point(ForwardIterator first,

ForwardIterator last,

Predicate pred);

// \ref{alg.sorting}, sorting and related operations:

// \ref{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 RandomAccessIterator>

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>

void stable_sort(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 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 ForwardIterator>

bool is_sorted(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare>

bool is_sorted(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 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);

// \ref{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);

// \ref{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 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);

// \ref{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 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 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 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 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);

// \ref{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 RandomAccessIterator>

RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>

RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,

Compare comp);

// \ref{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 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 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 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);

// \ref{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);

}

\end{codeblock}

\pnum

All of the algorithms are separated from the particular implementations of data structures and are

parameterized by iterator types.

Because of this, they can work with program-defined data structures, as long

as these data structures have iterator types satisfying the assumptions on the algorithms.

\pnum

For purposes of determining the existence of data races, algorithms shall

not modify objects referenced through an iterator argument unless the

specification requires such modification.

\pnum

Throughout this Clause, the names of template parameters

are used to express type requirements.

\begin{itemize}

\item

If an algorithm's template parameter is named

\tcode{InputIterator},

\tcode{InputIterator1},

or

\tcode{InputIterator2},

the template argument shall satisfy the

requirements of an input iterator~(\ref{input.iterators}).

\item

If an algorithm's template parameter is named

\tcode{OutputIterator},

\tcode{OutputIterator1},

or

\tcode{OutputIterator2},

the template argument shall satisfy the requirements

of an output iterator~(\ref{output.iterators}).

\item

If an algorithm's template parameter is named

\tcode{ForwardIterator},

\tcode{ForwardIterator1},

or

\tcode{ForwardIterator2},

the template argument shall satisfy the requirements

of a forward iterator~(\ref{forward.iterators}).

\item

If an algorithm's template parameter is named

\tcode{BidirectionalIterator},

\tcode{Bidirectional\-Iterator1},

or

\tcode{BidirectionalIterator2},

the template argument shall satisfy the requirements

of a bidirectional iterator~(\ref{bidirectional.iterators}).

\item

If an algorithm's template parameter is named

\tcode{RandomAccessIterator},

\tcode{Random\-AccessIterator1},

or

\tcode{RandomAccessIterator2},

the template argument shall satisfy the requirements

of a random-access iterator~(\ref{random.access.iterators}).

\end{itemize}

\pnum

If an algorithm's

\synopsis{Effects}

section says that a value pointed to by any iterator passed

as an argument is modified, then that algorithm has an additional

type requirement:

The type of that argument shall satisfy the requirements

of a mutable iterator~(\ref{iterator.requirements}).

\enternote

This requirement does not affect arguments that are named

\tcode{OutputIterator},

\tcode{OutputIterator1},

or

\tcode{OutputIterator2},

because output iterators must always be mutable.

\exitnote

\pnum

Both in-place and copying versions are provided for certain

algorithms.\footnote{The decision whether to include a copying version was

usually based on complexity considerations. When the cost of doing the operation

dominates the cost of copy, the copying version is not included. For example,

\tcode{sort_copy} is not included because the cost of sorting is much more

significant, and users might as well do \tcode{copy} followed by \tcode{sort}.}

When such a version is provided for \textit{algorithm} it is called

\textit{algorithm\tcode{_copy}}. Algorithms that take predicates end with the

suffix \tcode{_if} (which follows the suffix \tcode{_copy}).

\pnum

The

\tcode{Predicate}

parameter is used whenever an algorithm expects a function object~(\ref{function.objects})

that, when applied to the result

of dereferencing the corresponding iterator, returns a value testable as

\tcode{true}.

In other words, if an algorithm

takes

\tcode{Predicate pred}

as its argument and \tcode{first}

as its iterator argument, it should work correctly in the

construct

\tcode{pred(*first)} contextually converted to \tcode{bool} (Clause~\ref{conv}).

The function object

\tcode{pred}

shall not apply any non-constant

function through the dereferenced iterator.

\pnum

The

\tcode{BinaryPredicate}

parameter is used whenever an algorithm expects a function object that when applied to

the result of dereferencing two corresponding iterators or to dereferencing an

iterator and type

\tcode{T}

when

\tcode{T}

is part of the signature returns a value testable as

\tcode{true}.

In other words, if an algorithm takes

\tcode{BinaryPredicate binary_pred}

as its argument and \tcode{first1} and \tcode{first2} as

its iterator arguments, it should work correctly in

the construct

\tcode{binary_pred(*first1, *first2)} contextually converted to \tcode{bool} (Clause~\ref{conv}).

\tcode{BinaryPredicate}

always takes the first

iterator's \tcode{value_type}

as its first argument, that is, in those cases when

\tcode{T value}

is part of the signature, it should work

correctly in the

construct \tcode{binary_pred(*first1, value)} contextually converted to \tcode{bool} (Clause~\ref{conv}).

\tcode{binary_pred} shall not

apply any non-constant function through the dereferenced iterators.

\pnum

\enternote

Unless otherwise specified, algorithms that take function objects as arguments

are permitted to copy those function objects freely. Programmers for whom object

identity is important should consider using a wrapper class that points to a

noncopied implementation object such as \tcode{reference_wrapper<T>}~(\ref{refwrap}), or some equivalent solution.

\exitnote

\pnum

When the description of an algorithm gives an expression such as

\tcode{*first == value}

for a condition, the expression shall evaluate to

either true or false in boolean contexts.

\pnum

In the description of the algorithms operators

\tcode{+}

and

\tcode{-}

are used for some of the iterator categories for which

they do not have to be defined.

In these cases the semantics of

\tcode{a+n}

is the same as that of

\begin{codeblock}

X tmp = a;

advance(tmp, n);

return tmp;

\end{codeblock}

and that of

\tcode{b-a}

is the same as of

\begin{codeblock}

return distance(a, b);

\end{codeblock}

\rSec1[alg.nonmodifying]{Non-modifying sequence operations}

\rSec2[alg.all_of]{All of}

\indexlibrary{\idxcode{all_of}}%

\begin{itemdecl}

template <class InputIterator, class Predicate>

bool all_of(InputIterator first, InputIterator last, Predicate pred);

\end{itemdecl}

\begin{itemdescr}

\pnum

\returns \tcode{true} if

\range{first}{last} is empty or if

\tcode{pred(*i)} is \tcode{true} for every iterator \tcode{i} in the range \range{first}{last}, and \tcode{false} otherwise.

\pnum

\complexity At most \tcode{last - first} applications of the predicate.

\end{itemdescr}

\rSec2[alg.any_of]{Any of}

\indexlibrary{\idxcode{any_of}}%

\begin{itemdecl}

template <class InputIterator, class Predicate>

bool any_of(InputIterator first, InputIterator last, Predicate pred);

\end{itemdecl}

\begin{itemdescr}

\pnum

\returns \tcode{false} if \range{first}{last} is empty or

if there is no iterator \tcode{i} in the range

\range{first}{last} such that \tcode{pred(*i)} is \tcode{true}, and \tcode{true} otherwise.

\pnum

\complexity At most \tcode{last - first} applications of the predicate.

\end{itemdescr}

\rSec2[alg.none_of]{None of}

\indexlibrary{\idxcode{none_of}}%

\begin{itemdecl}

template <class InputIterator, class Predicate>

bool none_of(InputIterator first, InputIterator last, Predicate pred);

\end{itemdecl}

\begin{itemdescr}

\pnum

\returns \tcode{true} if

\range{first}{last} is empty or if

\tcode{pred(*i)} is \tcode{false} for every iterator \tcode{i} in the range \range{first}{last}, and \tcode{false} otherwise.

\pnum

\complexity At most \tcode{last - first} applications of the predicate.

\end{itemdescr}

\rSec2[alg.foreach]{For each}

\indexlibrary{\idxcode{for_each}}%

\begin{itemdecl}

template<class InputIterator, class Function>

Function for_each(InputIterator first, InputIterator last, Function f);

\end{itemdecl}

\begin{itemdescr}

\pnum

\requires \tcode{Function} shall meet the requirements of

\tcode{MoveConstructible} (Table~\ref{moveconstructible}).

\enternote \tcode{Function} need not meet the requirements of

\tcode{CopyConstructible} (Table~\ref{copyconstructible}). \exitnote

\pnum

\effects

Applies

\tcode{f} to the result of dereferencing every iterator in the range

\range{first}{last},

starting from

\tcode{first}

and proceeding to

\tcode{last - 1}.

\enternote If the type of \tcode{first} satisfies the

requirements of a mutable iterator, \tcode{f} may apply nonconstant

functions through the dereferenced iterator.\exitnote

\pnum

\returns

\tcode{std::move(f)}.

\pnum

\complexity

Applies \tcode{f}

exactly

\tcode{last - first}

times.

\pnum

\notes

If \tcode{f} returns a result, the result is ignored.

\end{itemdescr}

\rSec2[alg.find]{Find}

\indexlibrary{\idxcode{find}}%

\indexlibrary{\idxcode{find_if}}%

\indexlibrary{\idxcode{find_if_not}}%

\begin{itemdecl}

template<class InputIterator, class T>

InputIterator find(InputIterator first, InputIterator last,

const T& value);

template<class InputIterator, class Predicate>

InputIterator find_if(InputIterator first, InputIterator last,

Predicate pred);

template<class InputIterator, class Predicate>

InputIterator find_if_not(InputIterator first, InputIterator last,

Predicate pred);

\end{itemdecl}

\begin{itemdescr}

\pnum

\returns

The first iterator

\tcode{i}

in the range

\range{first}{last}

for which the following corresponding

conditions hold:

\tcode{*i == value}, \tcode{pred(*i) != false}, \tcode{pred(*i) == false}.

Returns \tcode{last} if no such iterator is found.

\pnum

\complexity

At most

\tcode{last - first}

applications of the corresponding predicate.

\end{itemdescr}

\rSec2[alg.find.end]{Find end}

\indexlibrary{\idxcode{find_end}}%

\begin{itemdecl}

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);

\end{itemdecl}

\begin{itemdescr}

\pnum

\effects

Finds a subsequence of equal values in a sequence.

\pnum

\returns

The last iterator

\tcode{i}

in the range \range{first1}{last1 - (last2 - first2)}

such that for every non-negative integer

\tcode{n < (last2 - first2)},

the following corresponding conditions hold:

\tcode{*(i + n) == *(\brk{}first2 + n), pred(*(i + n), *(first2 + n)) != false}.

Returns \tcode{last1}

if

\range{first2}{last2} is empty or if

no such iterator is found.

\pnum

\complexity

At most

\tcode{(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)}

applications of the corresponding predicate.

\end{itemdescr}

\rSec2[alg.find.first.of]{Find first}

\indexlibrary{\idxcode{find_first_of}}%

\begin{itemdecl}

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);

\end{itemdecl}

\begin{itemdescr}

\pnum

\effects

Finds an element that matches one of a set of values.

\pnum

\returns

The first iterator

\tcode{i}

in the range \range{first1}{last1}

such that for some

iterator

\tcode{j}

in the range \range{first2}{last2}

the following conditions hold:

\tcode{*i == *j, pred(*i,*j) != false}.

Returns \tcode{last1}

if \range{first2}{last2} is empty or

if no such iterator is found.

\pnum

\complexity

At most

\tcode{(last1-first1) * (last2-first2)}

applications of the corresponding predicate.

\end{itemdescr}

\rSec2[alg.adjacent.find]{Adjacent find}

\indexlibrary{\idxcode{adjacent_find}}%

\begin{itemdecl}

template<class ForwardIterator>

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,

BinaryPredicate pred);

\end{itemdecl}

\begin{itemdescr}

\pnum

\returns

The first iterator

\tcode{i}

such that both

\tcode{i}

and

\tcode{i + 1}

are in

the range

\range{first}{last}

for which

the following corresponding conditions hold:

\tcode{*i == *(i + 1), pred(*i, *(i + 1)) != false}.

Returns \tcode{last}

if no such iterator is found.

\pnum

\complexity

For a nonempty range, exactly

\tcode{min((i - first) + 1, (last - first) - 1)}

applications of the corresponding predicate, where \tcode{i} is

\tcode{adjacent_find}'s

return value.

\end{itemdescr}

\rSec2[alg.count]{Count}

\indexlibrary{\idxcode{count}}%

\indexlibrary{\idxcode{count_if}}%

\begin{itemdecl}