# <algorithm>

<head><title>&lt;algorithm&gt;</title></head>

# `<algorithm>`

* * *

**`adjacent_find· binary_search· copy· copy_backward· count· count_if· equal· equal_range· fill· fill_n· find· find_end· find_first_of· find_if· for_each· generate· generate_n· includes· inplace_merge· iter_swap· lexicographical_compare· lower_bound· make_heap· max· max_element· merge· min· min_element· mismatch· next_permutation· nth_element· partial_sort· partial_sort_copy· partition· pop_heap· prev_permutation· push_heap· random_shuffle· remove· remove_copy· remove_copy_if· remove_if· replace· replace_copy· replace_copy_if· replace_if· reverse· reverse_copy· rotate· rotate_copy· search· search_n· set_difference· set_intersection· set_symmetric_difference· set_union· sort· sort_heap· stable_partition· stable_sort· swap· swap_ranges· transform· unique· unique_copy· upper_bound`**

* * *

Include the [STL](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_index.html#STL)
standard header **`<algorithm>`**
to define numerous template functions that perform
useful algorithms. The descriptions that follow
make extensive use of common template parameter names
(or prefixes) to indicate the least powerful category
of iterator permitted as an actual argument type:

- **`OutIt`** --
to indicate an output iterator
- **`InIt`** --
to indicate an input iterator
- **`FwdIt`** --
to indicate a forward iterator
- **`BidIt`** --
to indicate a bidirectional iterator
- **`RanIt`** --
to indicate a random-access iterator

The descriptions of these templates employ a number of
[conventions](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#Algorithm%20Conventions)
common to all algorithms.

    namespace std {
    template<class InIt, class Fn1>
        Fn1 for_each(InIt first, InIt last, Fn1 func);
    template<class InIt, class Ty>
        InIt find(InIt first, InIt last, const Ty& val);
    template<class InIt, class Pr>
        InIt find_if(InIt first, InIt last, Pr pred);
    template<class FwdIt1, class FwdIt2>
        FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2);
    template<class FwdIt1, class FwdIt2, class Pr>
        FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2, Pr pred);
    template<class FwdIt1, class FwdIt2>
        FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2);
    template<class FwdIt1, class FwdIt2, class Pr>
        FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2, Pr pred);
    template<class FwdIt>
        FwdIt adjacent_find(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt adjacent_find(FwdIt first, FwdIt last, Pr pred);
    template<class InIt, class Ty, class Dist>
        typename iterator_traits<InIt>::difference_type
            count(InIt first, InIt last,
                const Ty& val);
    template<class InIt, class Pr, class Dist>
        typename iterator_traits<InIt>::difference_type
            count_if(InIt first, InIt last,
                Pr pred);
    template<class InIt1, class InIt2>
        pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
            InIt2 first2);
    template<class InIt1, class InIt2, class Pr>
        pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
            InIt2 first2, Pr pred);
    template<class InIt1, class InIt2>
        bool equal(InIt1 first1, InIt1 last1, InIt2 first2);
    template<class InIt1, class InIt2, class Pr>
        bool equal(InIt1 first1, InIt1 last1, InIt2 first2, Pr pred);
    template<class FwdIt1, class FwdIt2>
        FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2);
    template<class FwdIt1, class FwdIt2, class Pr>
        FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2, Pr pred);
    template<class FwdIt, class Diff, class Ty>
        FwdIt search_n(FwdIt first, FwdIt last,
            Diff count, const Ty& val);
    template<class FwdIt, class Diff, class Ty, class Pr>
        FwdIt search_n(FwdIt first, FwdIt last,
            Diff count, const Ty& val, Pr pred);
    template<class InIt, class OutIt>
        OutIt copy(InIt first, InIt last, OutIt dest);
    template<class BidIt1, class BidIt2>
        BidIt2 copy_backward(BidIt1 first, BidIt1 last,
            BidIt2 dest);
    template<class Ty>
        void swap(Ty& left, Ty& right);
    template<class FwdIt1, class FwdIt2>
        FwdIt2 swap_ranges(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 last2);
    template<class FwdIt1, class FwdIt2>
        void iter_swap(FwdIt1 left, FwdIt2 right);
    template<class InIt, class OutIt, class Fn1>
        OutIt transform(InIt first, InIt last, OutIt dest,
            Fn1 func);
    template<class InIt1, class InIt2, class OutIt,
        class Fn2>
        OutIt transform(InIt1 first1, InIt1 last1,
            InIt2 first2, OutIt dest, Fn2 func);Copy to clipboard

    template<class FwdIt, class Ty>
        void replace(FwdIt first, FwdIt last,
            const Ty& oldval, const Ty& newval);
    template<class FwdIt, class Pr, class Ty>
        void replace_if(FwdIt first, FwdIt last,
            Pr pred, const Ty& val);
    template<class InIt, class OutIt, class Ty>
        OutIt replace_copy(InIt first, InIt last, OutIt dest,
            const Ty& oldval, const Ty& newval);
    template<class InIt, class OutIt, class Pr, class Ty>
        OutIt replace_copy_if(InIt first, InIt last, OutIt dest,
            Pr pred, const Ty& val);
    template<class FwdIt, class Ty>
        void fill(FwdIt first, FwdIt last, const Ty& val);
    template<class OutIt, class Diff, class Ty>
        void fill_n(OutIt first, Diff count, const Ty& val);
    template<class FwdIt, class Fn0>
        void generate(FwdIt first, FwdIt last, Fn0 func);
    template<class OutIt, class Diff, class Fn0>
        void generate_n(OutIt first, Diff count, Fn0 func);
    template<class FwdIt, class Ty>
        FwdIt remove(FwdIt first, FwdIt last, const Ty& val);
    template<class FwdIt, class Pr>
        FwdIt remove_if(FwdIt first, FwdIt last, Pr pred);
    template<class InIt, class OutIt, class Ty>
        OutIt remove_copy(InIt first, InIt last, OutIt dest,
            const Ty& val);
    template<class InIt, class OutIt, class Pr>
        OutIt remove_copy_if(InIt first, InIt last, OutIt dest,
            Pr pred);
    template<class FwdIt>
        FwdIt unique(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt unique(FwdIt first, FwdIt last, Pr pred);
    template<class InIt, class OutIt>
        OutIt unique_copy(InIt first, InIt last, OutIt dest);
    template<class InIt, class OutIt, class Pr>
        OutIt unique_copy(InIt first, InIt last, OutIt dest,
            Pr pred);
    template<class BidIt>
        void reverse(BidIt first, BidIt last);
    template<class BidIt, class OutIt>
        OutIt reverse_copy(BidIt first, BidIt last, OutIt dest);
    template<class FwdIt>
        void rotate(FwdIt first, FwdIt mid, FwdIt last);
    template<class FwdIt, class OutIt>
        OutIt rotate_copy(FwdIt first, FwdIt mid,
            FwdIt last, OutIt dest);
    template<class RanIt>
        void random_shuffle(RanIt first, RanIt last);
    template<class RanIt, class Fn1>
        void random_shuffle(RanIt first, RanIt last, Fn1& func);
    template<class BidIt, class Pr>
        BidIt partition(BidIt first, BidIt last, Pr pred);
    template<class BidIt, class Pr>
        BidIt stable_partition(BidIt first, BidIt last,
            Pr pred);
    template<class RanIt>
        void sort(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void sort(RanIt first, RanIt last, Pr pred);
    template<class BidIt>
        void stable_sort(BidIt first, BidIt last);
    template<class BidIt, class Pr>
        void stable_sort(BidIt first, BidIt last, Pr pred);
    template<class RanIt>
        void partial_sort(RanIt first, RanIt mid,
            RanIt last);
    template<class RanIt, class Pr>
        void partial_sort(RanIt first, RanIt mid,
            RanIt last, Pr pred);
    template<class InIt, class RanIt>
        RanIt partial_sort_copy(InIt first1, InIt last1,
            RanIt first2, RanIt last2);
    template<class InIt, class RanIt, class Pr>
        RanIt partial_sort_copy(InIt first1, InIt last1,
            RanIt first2, RanIt last2, Pr pred);Copy to clipboard

    template<class RanIt>
        void nth_element(RanIt first, RanIt nth, RanIt last);
    template<class RanIt, class Pr>
        void nth_element(RanIt first, RanIt nth, RanIt last,
            Pr pred);
    template<class FwdIt, class Ty>
        FwdIt lower_bound(FwdIt first, FwdIt last,
            const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        FwdIt lower_bound(FwdIt first, FwdIt last,
            const Ty& val, Pr pred);
    template<class FwdIt, class Ty>
        FwdIt upper_bound(FwdIt first, FwdIt last,
            const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        FwdIt upper_bound(FwdIt first, FwdIt last,
            const Ty& val, Pr pred);
    template<class FwdIt, class Ty>
        pair<FwdIt, FwdIt> equal_range(FwdIt first,
            FwdIt last, const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        pair<FwdIt, FwdIt> equal_range(FwdIt first,
            FwdIt last, const Ty& val, Pr pred);
    template<class FwdIt, class Ty>
        bool binary_search(FwdIt first, FwdIt last,
            const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        bool binary_search(FwdIt first, FwdIt last,
            const Ty& val, Pr pred);
    template<class InIt1, class InIt2, class OutIt>
        OutIt merge(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt merge(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);
    template<class BidIt>
        void inplace_merge(BidIt first, BidIt mid,
            BidIt last);
    template<class BidIt, class Pr>
        void inplace_merge(BidIt first, BidIt mid,
            BidIt last, Pr pred);
    template<class InIt1, class InIt2>
        bool includes(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2);
    template<class InIt1, class InIt2, class Pr>
        bool includes(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, Pr pred);
    template<class InIt1, class InIt2, class OutIt>
        OutIt set_union(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_union(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);
    template<class InIt1, class InIt2, class OutIt>
        OutIt set_intersection(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_intersection(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);
    template<class InIt1, class InIt2, class OutIt>
        OutIt set_difference(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_difference(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);
    template<class InIt1, class InIt2, class OutIt>
        OutIt set_symmetric_difference(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_symmetric_difference(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest,
                Pr pred);
    template<class RanIt>
        void push_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void push_heap(RanIt first, RanIt last, Pr pred);
    template<class RanIt>
        void pop_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void pop_heap(RanIt first, RanIt last, Pr pred);
    template<class RanIt>
        void make_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void make_heap(RanIt first, RanIt last, Pr pred);
    template<class RanIt>
        void sort_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void sort_heap(RanIt first, RanIt last, Pr pred);
    template<class Ty>
        const Ty& max(const Ty& left, const Ty& right);
    template<class Ty, class Pr>
        const Ty& max(const Ty& left, const Ty& right, Pr pred);
    template<class Ty>
        const Ty& min(const Ty& left, const Ty& right);
    template<class Ty, class Pr>
        const Ty& min(const Ty& left, const Ty& right, Pr pred);
    template<class FwdIt>
        FwdIt max_element(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt max_element(FwdIt first, FwdIt last, Pr pred);
    template<class FwdIt>
        FwdIt min_element(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt min_element(FwdIt first, FwdIt last, Pr pred);
    template<class InIt1, class InIt2>
        bool lexicographical_compare(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2);
    template<class InIt1, class InIt2, class Pr>
        bool lexicographical_compare(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2, Pr pred);
    template<class BidIt>
        bool next_permutation(BidIt first, BidIt last);
    template<class BidIt, class Pr>
        bool next_permutation(BidIt first, BidIt last,
            Pr pred);
    template<class BidIt>
        bool prev_permutation(BidIt first, BidIt last);
    template<class BidIt, class Pr>
        bool prev_permutation(BidIt first, BidIt last,
            Pr pred);
    }  // namespace stdCopy to clipboard

## `adjacent_find`

    template<class FwdIt>
        FwdIt adjacent_find(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt adjacent_find(FwdIt first, FwdIt last, Pr pred);Copy to clipboard

The first template function determines the lowest `N`
in the range `[0, last - first)` for which
`N + 1 < last - first` and the predicate
`*(first + N) == *(first + N + 1)` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `first + N`.
If no such value exists, the function returns `last`.
If the sequence contains fewer than two elements, the function
never evaluates the predicate. Otherwise, if it returns
`last`, it evaluates the predicate exactly
`last - first - 1` times. Otherwise,
it evaluates the predicate exactly `N + 1` times.

The second template function behaves the same, except that
the predicate is `pred(*(first + N), *(first + N + 1))`.

## `binary_search`

    template<class FwdIt, class Ty>
        bool binary_search(FwdIt first, FwdIt last,
            const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        bool binary_search(FwdIt first, FwdIt last,
            const Ty& val, Pr pred);Copy to clipboard

The first template function determines whether
a value of `N` exists
in the range `[0, last - first)` for which
`*(first + N)` has
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering)
to `val`, where the elements designated by iterators
in the range `[first, last)` form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
If so, the function returns true.
If no such value exists, it returns false.

Yhe function evaluates the ordering predicate `X < Y` at most
`ceil(log(last - first)) + 2` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `copy`

    template<class InIt, class OutIt>
        OutIt copy(InIt first, InIt last, OutIt dest);Copy to clipboard

The template function evaluates `*(dest + N) = *(first + N))`
once for each `N` in the range `[0, last - first)`,
for strictly increasing values of `N` beginning with
the lowest value. It then returns `dest + N`.
If `dest` and `first` designate regions of storage,
`dest` must not be in the range `[first, last)`.

## `copy_backward`

    template<class BidIt1, class BidIt2>
        BidIt2 copy_backward(BidIt1 first, BidIt1 last,
            BidIt2 dest);Copy to clipboard

The template function evaluates
`*(dest - N - 1) = *(last - N - 1))` once for
each `N` in the range `[0, last - first)`,
for strictly increasing values of `N` beginning with
the lowest value. It then returns `dest - (last - first)`.
If `dest` and `first` designate regions of storage,
`dest` must not be in the range `[first, last)`.

## `count`

    template<class InIt, class Ty>
        typename iterator_traits<InIt>::difference_type
            count(InIt first, InIt last, const Ty& val);Copy to clipboard

The template function sets a count `count` to zero. It then
executes `++count` for
each `N` in the range `[0, last - first)`
for which the predicate `*(first + N) == val` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
The function returns `count`.
It evaluates the predicate exactly `last - first` times.

## `count_if`

    template<class InIt, class Pr, class Dist>
        typename iterator_traits<InIt>::difference_type
            count_if(InIt first, InIt last,
                Pr pred);Copy to clipboard

The template function sets a count `count` to zero. It then
executes `++count` for
each `N` in the range `[0, last - first)`
for which the predicate `pred(*(first + N))` is true.
The function returns `count`.
It evaluates the predicate exactly `last - first` times.

## `equal`

    template<class InIt1, class InIt2>
        bool equal(InIt1 first1, InIt1 last1, InIt2 first2);
    template<class InIt1, class InIt2, class Pr>
        bool equal(InIt1 first1, InIt1 last1, InIt2 first2, Pr pred);Copy to clipboard

The first template function returns true only if, for
each `N` in the range `[0, last1 - first1)`,
the predicate `*(first1 + N) == *(first2 + N)` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
The function evaluates the predicate at most once
for each `N`.

The second template function behaves the same, except that
the predicate is `pred(*(first1 + N), *(first2 + N))`.

## `equal_range`

    template<class FwdIt, class Ty>
        pair<FwdIt, FwdIt> equal_range(FwdIt first,
            FwdIt last, const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        pair<FwdIt, FwdIt> equal_range(FwdIt first,
            FwdIt last, const Ty& val, Pr pred);Copy to clipboard

The first template function effectively returns
`pair(
lower_bound(first, last, val),
upper_bound(first, last, val))`,
where the elements designated by iterators
in the range `[first, last)` form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
Thus, the function determines the largest range of positions
over which `val` can be inserted in the sequence
and still preserve its ordering.

The function evaluates the ordering predicate `X < Y` at most
`ceil(2 * log(last - first)) + 2`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `fill`

    template<class FwdIt, class Ty>
        void fill(FwdIt first, FwdIt last, const Ty& val);Copy to clipboard

The template function evaluates `*(first + N) = val` once for
each `N` in the range `[0, last - first)`.

## `fill_n`

    template<class OutIt, class Diff, class Ty>
        void fill_n(OutIt first, Diff count, const Ty& val);Copy to clipboard

The template function evaluates `*(first + N) = val` once for
each `N` in the range `[0, count)`.

## `find`

    template<class InIt, class Ty>
        InIt find(InIt first, InIt last, const Ty& val);Copy to clipboard

The template function determines the lowest value of `N`
in the range `[0, last - first)` for which the predicate
`*(first + N) == val` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `first + N`.
If no such value exists, the function returns `last`.
It evaluates the predicate at most once
for each `N`.

## `find_end`

    template<class FwdIt1, class FwdIt2>
        FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2);
    template<class FwdIt1, class FwdIt2, class Pr>
        FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2, Pr pred);Copy to clipboard

The first template function determines the highest value of
`N` in the range `[0,
last1 - first1 - (last2 - first2))`
such that for each `M` in the range
`[0, last2 - first2)`,
the predicate `*(first1 + N + M) == *(first2 + N + M)` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `first1 + N`.
If no such value exists, the function returns `last1`.
It evaluates the predicate at most `(last2 - first2) *
(last1 - first1 - (last2 - first2) + 1)` times.

The second template function behaves the same, except that
the predicate is `pred(*(first1 + N + M), *(first2 + N + M))`.

## `find_first_of`

    template<class FwdIt1, class FwdIt2>
        FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2);
    template<class FwdIt1, class FwdIt2, class Pr>
        FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2, Pr pred);Copy to clipboard

The first template function determines the lowest value of
`N` in the range `[0, last1 - first1)` such that
for some `M` in the range `[0, last2 - first2)`,
the predicate `*(first1 + N) == *(first2 + M)` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `first1 + N`.
If no such value exists, the function returns `last1`.
It evaluates the predicate at most
`(last1 - first1) * (last2 - first2)` times.

The second template function behaves the same, except that
the predicate is `pred(*(first1 + N), *(first2 + M))`.

## `find_if`

    template<class InIt, class Pr>
        InIt find_if(InIt first, InIt last, Pr pred);Copy to clipboard

The template function determines the lowest value of `N`
in the range `[0, last - first)` for which the predicate
`pred(*(first + N))` is true.
It then returns `first + N`.
If no such value exists, the function returns `last`.
It evaluates the predicate at most once
for each `N`.

## `for_each`

    template<class InIt, class Fn1>
        Fn1 for_each(InIt first, InIt last, Fn1 func);Copy to clipboard

The template function evaluates `func(*(first + N))` once for
each `N` in the range `[0, last - first)`.
It then returns `func`.

## `generate`

    template<class FwdIt, class Fn0>
        void generate(FwdIt first, FwdIt last, Fn0 func);Copy to clipboard

The template function evaluates `*(first + N) = func()` once for
each `N` in the range `[0, last - first)`.

## `generate_n`

    template<class OutIt, class Pr, class Fn0>
        void generate_n(OutIt first, Diff count, Fn0 func);Copy to clipboard

The template function evaluates `*(first + N) = func()` once for
each `N` in the range `[0, count)`.

## `includes`

    template<class InIt1, class InIt2>
        bool includes(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2);
    template<class InIt1, class InIt2, class Pr>
        bool includes(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, Pr pred);Copy to clipboard

The first template function determines whether
a value of `N` exists
in the range `[0, last2 - first2)` such that,
for each `M` in the range `[0, last1 - first1)`,
`*(first1 + M)` and `*(first2 + N)` do not have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering),
where the elements designated by iterators
in the ranges `[first1, last1)`
and `[first2, last2)` each form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
If so, the function returns false.
If no such value exists, it returns true.
Thus, the function determines whether the ordered sequence
designated by iterators in the range
`[first2, last2)` all have equivalent ordering with some
element designated by iterators in the range
`[first1, last1)`.

The function evaluates the predicate at most
`2 * ((last1 - first1) + (last2 - first2)) - 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `inplace_merge`

    template<class BidIt>
        void inplace_merge(BidIt first, BidIt mid,
            BidIt last);
    template<class BidIt, class Pr>
        void inplace_merge(BidIt first, BidIt mid,
            BidIt last, Pr pred);Copy to clipboard

The first template function reorders the
sequences designated by iterators in the ranges `[first, mid)`
and `[mid, last)`, each
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`,
to form a merged sequence of length `last - first`
beginning at `first` also ordered by `operator<`.
The merge occurs without altering the relative order of
elements within either original sequence. Moreover, for any two elements
from different original sequences that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering),
the element from the ordered range `[first, mid)`
precedes the other.

The function evaluates the ordering predicate
`X < Y` at most
`ceil((last - first) * log(last - first))` times.
(Given enough temporary storage, it can evaluate the predicate at most
`(last - first) - 1` times.)

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `iter_swap`

    template<class FwdIt1, class FwdIt2>
        void iter_swap(FwdIt1 left, FwdIt2 right);Copy to clipboard

The template function leaves the value originally stored in
`*right` subsequently stored in `*left`,
and the value originally stored in `*left`
subsequently stored in `*right`.

## `lexicographical_compare`

    template<class InIt1, class InIt2>
        bool lexicographical_compare(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2);
    template<class InIt1, class InIt2, class Pr>
        bool lexicographical_compare(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2, Pr pred);Copy to clipboard

The first template function determines `K`,
the number of elements to compare as the smaller of
`last1 - first1` and `last2 - first2`.
It then determines the lowest value of `N`
in the range `[0, K)` for which
`*(first1 + N)` and `*(first2 + N)` do not have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering).
If no such value exists, the function returns true only if
`K < (last2 - first2)`. Otherwise, it returns
true only if `*(first1 + N) < *(first2 + N)`.
Thus, the function returns true only if the sequence designated
by iterators in the range `[first1, last1)` is
lexicographically less than the other sequence.

The function evaluates the ordering predicate
`X < Y` at most `2 * K` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `lower_bound`

    template<class FwdIt, class Ty>
        FwdIt lower_bound(FwdIt first, FwdIt last,
            const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        FwdIt lower_bound(FwdIt first, FwdIt last,
            const Ty& val, Pr pred);Copy to clipboard

The first template function determines the highest value of `N`
in the range `(0, last - first]` such that,
for each `M` in the range `[0, N)`
the predicate `*(first + M) < val` is true,
where the elements designated by iterators
in the range `[first, last)` form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
It then returns `first + N`.
Thus, the function determines the lowest position
before which `val` can be inserted in the sequence
and still preserve its ordering.

The function evaluates the ordering predicate `X < Y` at most
`ceil(log(last - first)) + 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `make_heap`

    template<class RanIt>
        void make_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void make_heap(RanIt first, RanIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` to form a heap
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#heap%20ordering) `operator<`.

The function evaluates the ordering predicate
`X < Y` at most
`3 * (last - first)` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `max`

    template<class Ty>
        const Ty& max(const Ty& left, const Ty& right);
    template<class Ty, class Pr>
        const Ty& max(const Ty& left, const Ty& right, Pr pred);Copy to clipboard

The first template function returns `right` if
`left < right`. Otherwise it returns `left`.
`Ty` need supply only a single-argument constructor and a
destructor.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `max_element`

    template<class FwdIt>
        FwdIt max_element(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt max_element(FwdIt first, FwdIt last, Pr pred);Copy to clipboard

The first template function determines the lowest value of `N`
in the range `[0, last - first)` such that,
for each `M` in the range `[0, last - first)`
the predicate `*(first + N) < *(first + M)` is false.
It then returns `first + N`.
Thus, the function determines the lowest position
that contains the largest value in the sequence.

The function evaluates the ordering predicate
`X < Y` exactly
`max((last - first) - 1, 0)` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `merge`

    template<class InIt1, class InIt2, class OutIt>
        OutIt merge(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt merge(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);Copy to clipboard

The first template function determines `K`,
the number of elements to copy as `(last1 - first1) +
(last2 - first2)`. It then alternately
copies two sequences, designated by iterators
in the ranges `[first1, last1)`
and `[first2, last2)` and each
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`,
to form a merged sequence of length `K` beginning
at `dest`, also ordered by `operator<`.
The function then returns `dest + K`.

The merge occurs without altering the relative order of
elements within either sequence. Moreover, for any two elements
from different sequences that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering),
the element from the ordered range `[first1, last1)`
precedes the other. Thus, the function merges two ordered
sequences to form another ordered sequence.

If `dest` and `first1` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first1, last1)`.
If `dest` and `first2` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first2, last2)`.
The function evaluates the ordering predicate `X < Y` at most
`K - 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `min`

    template<class Ty>
        const Ty& min(const Ty& left, const Ty& right);
    template<class Ty, class Pr>
        const Ty& min(const Ty& left, const Ty& right, Pr pred);Copy to clipboard

The first template function returns `right` if
`right < left`. Otherwise it returns `left`.
`Ty` need supply only a single-argument constructor and a
destructor.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `min_element`

    template<class FwdIt>
        FwdIt min_element(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt min_element(FwdIt first, FwdIt last, Pr pred);Copy to clipboard

The first template function determines the lowest value of `N`
in the range `[0, last - first)` such that,
for each `M` in the range `[0, last - first)`
the predicate `*(first + M) < *(first + N)` is false.
It then returns `first + N`.
Thus, the function determines the lowest position
that contains the smallest value in the sequence.

The function evaluates the ordering predicate
`X < Y` exactly
`max((last - first) - 1, 0)` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `mismatch`

    template<class InIt1, class InIt2>
        pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
            InIt2 first2);
    template<class InIt1, class InIt2, class Pr>
        pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
            InIt2 first2, Pr pred);Copy to clipboard

The first template function determines the lowest value of
`N` in the range `[0, last1 - first1)`
for which the predicate
`!(*(first1 + N) == *(first2 + N))` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns
`pair(first1 + N, first2 + N)`.
If no such value exists, N has the value `last1 - first1`.
The function evaluates the predicate at most once
for each `N`.

The second template function behaves the same, except that
the predicate is `pred(*(first1 + N), *(first2 + N))`.

## `next_permutation`

    template<class BidIt>
        bool next_permutation(BidIt first, BidIt last);
    template<class BidIt, class Pr>
        bool next_permutation(BidIt first, BidIt last,
            Pr pred);Copy to clipboard

The first template function determines a repeating
sequence of permutations, whose initial permutation occurs when
the sequence designated by iterators
in the range `[first, last)` is
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
(The elements are sorted in *ascending* order.)
It then reorders the elements in the sequence, by evaluating
`swap(X, Y)` for the elements
`X` and `Y` zero or more times,
to form the next permutation. The function returns true only if the resulting
sequence is not the initial permutation. Otherwise, the resultant
sequence is the one next larger lexicographically than the original
sequence.

The function evaluates `swap(X, Y)`
at most `(last - first) / 2`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `nth_element`

    template<class RanIt>
        void nth_element(RanIt first, RanIt nth, RanIt last);
    template<class RanIt, class Pr>
        void nth_element(RanIt first, RanIt nth, RanIt last,
            Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` such that for each `N`
in the range `[0, nth - first)` and for each `M`
in the range `[nth - first, last - first)` the predicate
`!(*(first + M) < *(first + N))`
is true. Moreover, for `N` equal to
`nth - first` and for each `M`
in the range `(nth - first, last - first)` the predicate
`!(*(first + M) < *(first + N))`
is true. Thus, if `nth != last` the element `*nth`
is in its proper position if elements of the entire sequence
were sorted in *ascending* order,
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
Any elements before this one belong before it in the sort sequence,
and any elements after it belong after it.

The function evaluates the ordering predicate `X < Y`
a number of times proportional to
`last - first`, on average.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `partial_sort`

    template<class RanIt>
        void partial_sort(RanIt first, RanIt mid,
            RanIt last);
    template<class RanIt, class Pr>
        void partial_sort(RanIt first, RanIt mid,
            RanIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` such that for each `N`
in the range `[0, mid - first)` and for each `M`
in the range `(N, last - first)` the predicate
`!(*(first + M) < *(first + N))`
is true. Thus, the smallest `mid - first`
elements of the entire sequence are sorted in *ascending* order,
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
The order of the remaining elements is otherwise unspecified.

The function evaluates
the ordering predicate `X < Y`
a number of times proportional to at most
`ceil((last - first) * log(mid - first))`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `partial_sort_copy`

    template<class InIt, class RanIt>
        RanIt partial_sort_copy(InIt first1, InIt last1,
            RanIt first2, RanIt last2);
    template<class InIt, class RanIt, class Pr>
        RanIt partial_sort_copy(InIt first1, InIt last1,
            RanIt first2, RanIt last2, Pr pred);Copy to clipboard

The first template function determines `K`,
the number of elements to copy as the smaller of
`last1 - first1` and `last2 - first2`. It then
copies and reorders `K` elements of the sequence
designated by iterators in the
range `[first1, last1)` such that
the `K` elements copied to `first2` are
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
Moreover, for each `N`
in the range `[0, K)` and for each `M`
in the range `(0, last1 - first1)` corresponding
to an uncopied element, the predicate
`!(*(first2 + M) < *(first1 + N))`
is true. Thus, the smallest `K`
elements of the entire sequence designated by iterators
in the range `[first1, last1)`
are copied and sorted in *ascending* order to the range
`[first2, first2 + K)`.

The function evaluates
the ordering predicate `X < Y`
a number of times proportional to at most
`ceil((last - first) * log(K))`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `partition`

    template<class BidIt, class Pr>
        BidIt partition(BidIt first, BidIt last, Pr pred);Copy to clipboard

The template function reorders the sequence designated by iterators in the
range `[first, last)` and determines the value
`K` such that for each `N` in the range
`[0, K)` the predicate `pred(*(first + N))`
is true, and for each `N` in the range
`[K, last - first)` the predicate `pred(*(first + N))`
is false. The function then returns `first + K`.

The predicate must not alter its operand.
The function evaluates `pred(*(first + N))` exactly
`last - first` times, and swaps at most
`(last - first) / 2` pairs of elements.

## `pop_heap`

    template<class RanIt>
        void pop_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void pop_heap(RanIt first, RanIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` to form a new heap,
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#heap%20ordering) `operator<` and
designated by iterators in the range
`[first, last - 1)`, leaving the original
element at `*first` subsequently at `*(last - 1)`.
The original sequence must designate an existing heap,
also ordered by `operator<`. Thus, `first !=
last` must be true and `*(last - 1)` is the
element to remove from (pop off) the heap.

The function evaluates the ordering predicate
`X < Y` at most
`ceil(2 * log(last - first))` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `prev_permutation`

    template<class BidIt>
        bool prev_permutation(BidIt first, BidIt last);
    template<class BidIt, class Pr>
        bool prev_permutation(BidIt first, BidIt last,
            Pr pred);Copy to clipboard

The first template function determines a repeating
sequence of permutations, whose initial permutation occurs when
the sequence designated by iterators
in the range `[first, last)` is the *reverse* of one
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
(The elements are sorted in *descending* order.)
It then reorders the elements in the sequence, by evaluating
`swap(X, Y)` for the elements
`X` and `Y` zero or more times,
to form the previous permutation.
The function returns true only if the resulting
sequence is not the initial permutation. Otherwise, the resultant
sequence is the one next smaller lexicographically than the original
sequence.

The function evaluates `swap(X, Y)`
at most `(last - first) / 2`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `push_heap`

    template<class RanIt>
        void push_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void push_heap(RanIt first, RanIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` to form a new heap
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#heap%20ordering) `operator<`.
Iterators in the range
`[first, last - 1)` must designate an existing heap,
also ordered by `operator<`. Thus, `first !=
last` must be true and `*(last - 1)` is the
element to add to (push on) the heap.

The function evaluates the ordering predicate
`X < Y` at most
`ceil(log(last - first))` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `random_shuffle`

    template<class RanIt>
        void random_shuffle(RanIt first, RanIt last);
    template<class RanIt, class Fn1>
        void random_shuffle(RanIt first, RanIt last, Fn1& func);Copy to clipboard

The first template function evaluates
`swap(*(first + N), *(first + M))` once for
each `N` in the range `[1, last - first)`,
where `M` is a value from some uniform random distribution
over the range `[0, N]`.
Thus, the function randomly shuffles
the order of elements in the sequence.

The function evaluates `M` and calls `swap`
exactly `last - first - 1` times.

The second template function behaves the same, except that
`M` is `(Diff)func((Diff)N)`, where
`Diff` is the type
`iterator_traits<RanIt>::
difference_type`.

## `remove`

    template<class FwdIt, class Ty>
        FwdIt remove(FwdIt first, FwdIt last, const Ty& val);Copy to clipboard

The template function effectively assigns `first` to
`X`, then executes the statement:

    if (!(*(first + N) == val))
        *X++ = *(first + N);Copy to clipboard

once for each `N` in the range
`[0, last - first)`.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `X`.
Thus, the function removes from the resulting sequence all elements for
which the predicate `*(first + N) == val` is true,
without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the
resulting sequence.

## `remove_copy`

    template<class InIt, class OutIt, class Ty>
        OutIt remove_copy(InIt first, InIt last, OutIt dest,
            const Ty& val);Copy to clipboard

The template function effectively executes the statement:

    if (!(*(first + N) == val))
        *dest++ = *(first + N);Copy to clipboard

once for each `N` in the range
`[0, last - first)`.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `dest`.
Thus, the function removes from the resulting sequence all elements for
which the predicate `*(first + N) == val` is true,
without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the
resulting sequence.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`.

## `remove_copy_if`

    template<class InIt, class OutIt, class Pr>
        OutIt remove_copy_if(InIt first, InIt last, OutIt dest,
            Pr pred);Copy to clipboard

The template function effectively executes the statement:

    if (!pred(*(first + N)))
        *dest++ = *(first + N);Copy to clipboard

once for each `N` in the range
`[0, last - first)`. It then returns `dest`.
Thus, the function removes from the resulting sequence all elements for
which the predicate `pred(*(first + N))` is true,
without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the
resulting sequence.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`.

## `remove_if`

    template<class FwdIt, class Pr>
        FwdIt remove_if(FwdIt first, FwdIt last, Pr pred);Copy to clipboard

The template function effectively assigns `first` to
`X`, then executes the statement:

    if (!pred(*(first + N)))
        *X++ = *(first + N);Copy to clipboard

once for each `N` in the range
`[0, last - first)`. It then returns `X`.
Thus, the function removes from the resulting sequence all elements for
which the predicate `pred(*(first + N))` is true,
without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the
resulting sequence.

## `replace`

    template<class FwdIt, class Ty>
        void replace(FwdIt first, FwdIt last,
            const Ty& oldval, const Ty& newval);Copy to clipboard

The template function executes the statement:

    if (*(first + N) == oldval)
        *(first + N) = newval;Copy to clipboard

once for each `N` in the range
`[0, last - first)`.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.

## `replace_copy`

    template<class InIt, class OutIt, class Ty>
        OutIt replace_copy(InIt first, InIt last, OutIt dest,
            const Ty& oldval, const Ty& newval);Copy to clipboard

The template function executes the statement:

    if (*(first + N) == oldval)
        *(dest + N) = newval;
    else
        *(dest + N) = *(first + N)Copy to clipboard

once for each `N` in the range
`[0, last - first)`.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands. The function returns the iterator value that
designates the end of the resulting sequence.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`.

## `replace_copy_if`

    template<class InIt, class OutIt, class Pr, class Ty>
        OutIt replace_copy_if(InIt first, InIt last, OutIt dest,
            Pr pred, const Ty& val);Copy to clipboard

The template function executes the statement:

    if (pred(*(first + N)))
        *(dest + N) = val;
    else
        *(dest + N) = *(first + N)Copy to clipboard

once for each `N` in the range
`[0, last - first)`.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`. The function returns the iterator
value that designates the end of the resulting sequence.

## `replace_if`

    template<class FwdIt, class Pr, class Ty>
        void replace_if(FwdIt first, FwdIt last,
            Pr pred, const Ty& val);Copy to clipboard

The template function executes the statement:

    if (pred(*(first + N)))
        *(first + N) = val;Copy to clipboard

once for each `N` in the range
`[0, last - first)`.

## `reverse`

    template<class BidIt>
        void reverse(BidIt first, BidIt last);Copy to clipboard

The template function evaluates
`swap(*(first + N), *(last - 1 - N)` once for
each `N` in the range `[0, (last - first) / 2)`.
Thus, the function reverses the order of elements in the sequence.

## `reverse_copy`

    template<class BidIt, class OutIt>
        OutIt reverse_copy(BidIt first, BidIt last, OutIt dest);Copy to clipboard

The template function evaluates
`*(dest + N) = *(last - 1 - N)` once for
each `N` in the range `[0, last - first)`.
It then returns `dest + (last - first)`.
Thus, the function reverses the order of elements in the sequence
that it copies.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`.

## `rotate`

    template<class FwdIt>
        void rotate(FwdIt first, FwdIt mid, FwdIt last);Copy to clipboard

The template function leaves the value originally stored in
`*(first + (N + (mid - first)) % (last - first))`
subsequently stored in `*(first + N)` for
each `N` in the range `[0, last - first)`.
Thus, if a ``left'' shift by one element leaves the element
originally stored in `*(first + (N + 1) % (last - first))`
subsequently stored in `*(first + N)`, then the function
can be said to rotate the sequence either left by
`mid - first` elements or right by `last - mid`
elements. Both `[first, mid)` and `[mid, last)`
must be valid ranges. The function swaps at most `last - first`
pairs of elements.

## `rotate_copy`

    template<class FwdIt, class OutIt>
        OutIt rotate_copy(FwdIt first, FwdIt mid,
            FwdIt last, OutIt dest);Copy to clipboard

The template function evaluates
`*(dest + N) = *(first + (N + (mid - first)) % (last - first))`
once for each `N` in the range `[0, last - first)`.
Thus, if a ``left'' shift by one element leaves the element
originally stored in `*(first + (N + 1) % (last - first))`
subsequently stored in `*(first + N)`, then the function
can be said to rotate the sequence either left by
`mid - first` elements or right by `last - mid`
elements as it copies.
Both `[first, mid)` and `[mid, last)`
must be valid ranges. The function returns the iterator value
that designates the end of the resulting sequence.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`.

## `search`

    template<class FwdIt1, class FwdIt2>
        FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2);
    template<class FwdIt1, class FwdIt2, class Pr>
        FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2, FwdIt2 last2, Pr pred);Copy to clipboard

The first template function determines the lowest value of
`N` in the range `[0,
(last1 - first1) - (last2 - first2))` such that
for each `M` in the range `[0, last2 - first2)`,
the predicate `*(first1 + N + M) == *(first2 + M)` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `first1 + N`.
If no such value exists, the function returns `last1`.
It evaluates the predicate at most `(last2 - first2) *
(last1 - first1)` times.

The second template function behaves the same, except that
the predicate is `pred(*(first1 + N + M), *(first2 + M))`.

## `search_n`

    template<class FwdIt, class Diff, class Ty>
        FwdIt search_n(FwdIt first, FwdIt last,
            Diff count, const Ty& val);
    template<class FwdIt, class Diff, class Ty, class Pr>
        FwdIt search_n(FwdIt first, FwdIt last,
            Diff count, const Ty& val, Pr pred);Copy to clipboard

The first template function determines the lowest value of
`N` in the range `[0,
(last - first) - count)` such that
for each `M` in the range `[0, count)`,
the predicate `*(first + N + M) == val` is true.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It then returns `first + N`.
If no such value exists, the function returns `last`.
It evaluates the predicate at most `count * (last - first)` times.

The second template function behaves the same, except that
the predicate is `pred(*(first + N + M), val)`.

## `set_difference`

    template<class InIt1, class InIt2, class OutIt>
        OutIt set_difference(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_difference(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);Copy to clipboard

The first template function alternately
copies values from two sequences designated by iterators in the ranges
`[first1, last1)` and `[first2, last2)`, both
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`,
to form a merged sequence of length `K` beginning
at `dest`, also ordered by `operator<`.
The function then returns `dest + K`.

The merge occurs without altering the relative order of
elements within either sequence. Moreover, for two elements
from different sequences that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering)
that would otherwise be copied to adjacent elements,
the function copies only
the element from the ordered range `[first1, last1)`
and skips the other. An element from one sequence that has
equivalent ordering with no element from the other sequence
is copied from the ordered range `[first1, last1)`
and skipped from the other.
Thus, the function merges two ordered
sequences to form another ordered sequence that is effectively
the difference of two sets.

If `dest` and `first1` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first1, last1)`.
If `dest` and `first2` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first2, last2)`.
The function evaluates the ordering predicate `X < Y` at most
`2 * ((last1 - first1) + (last2 - first2)) - 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `set_intersection`

    template<class InIt1, class InIt2, class OutIt>
        OutIt set_intersection(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_intersection(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);Copy to clipboard

The first template function alternately
copies values from two sequences designated by iterators in the ranges
`[first1, last1)` and `[first2, last2)`, both
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`,
to form a merged sequence of length `K` beginning
at `dest`, also ordered by `operator<`.
The function then returns `dest + K`.

The merge occurs without altering the relative order of
elements within either sequence. Moreover, for two elements
from different sequences that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering)
that would otherwise be copied to adjacent elements,
the function copies only
the element from the ordered range `[first1, last1)`
and skips the other. An element from one sequence that has
equivalent ordering with no element from the other sequence
is also skipped.
Thus, the function merges two ordered
sequences to form another ordered sequence that is effectively
the intersection of two sets.

If `dest` and `first1` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first1, last1)`.
If `dest` and `first2` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first2, last2)`.
The function evaluates the ordering predicate `X < Y` at most
`2 * ((last1 - first1) + (last2 - first2)) - 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `set_symmetric_difference`

    template<class InIt1, class InIt2, class OutIt>
        OutIt set_symmetric_difference(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_symmetric_difference(InIt1 first1,
            InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest,
                Pr pred);Copy to clipboard

The first template function alternately
copies values from two sequences designated by iterators in the ranges
`[first1, last1)` and `[first2, last2)`, both
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`,
to form a merged sequence of length `K` beginning
at `dest`, also ordered by `operator<`.
The function then returns `dest + K`.

The merge occurs without altering the relative order of
elements within either sequence. Moreover, for two elements
from different sequences that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering)
that would otherwise be copied to adjacent elements,
the function copies neither element. An element from one sequence that has
equivalent ordering with no element from the other sequence
is copied. Thus, the function merges two ordered
sequences to form another ordered sequence that is effectively
the symmetric difference of two sets.

If `dest` and `first1` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first1, last1)`.
If `dest` and `first2` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first2, last2)`.
The function evaluates the ordering predicate `X < Y` at most
`2 * ((last1 - first1) + (last2 - first2)) - 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `set_union`

    template<class InIt1, class InIt2, class OutIt>
        OutIt set_union(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest);
    template<class InIt1, class InIt2, class OutIt,
        class Pr>
        OutIt set_union(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt dest, Pr pred);Copy to clipboard

The first template function alternately
copies values from two sequences designated by iterators in the ranges
`[first1, last1)` and `[first2, last2)`, both
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`,
to form a merged sequence of length `K` beginning
at `dest`, also ordered by `operator<`.
The function then returns `dest + K`.

The merge occurs without altering the relative order of
elements within either sequence. Moreover, for two elements
from different sequences that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering)
that would otherwise be copied to adjacent elements,
the function copies only
the element from the ordered range `[first1, last1)`
and skips the other.
Thus, the function merges two ordered
sequences to form another ordered sequence that is effectively
the union of two sets.

If `dest` and `first1` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first1, last1)`.
If `dest` and `first2` designate regions of storage,
the range `[dest, dest + K)` must not
overlap the range `[first2, last2)`.
The function evaluates the ordering predicate `X < Y` at most
`2 * ((last1 - first1) + (last2 - first2)) - 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `sort`

    template<class RanIt>
        void sort(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void sort(RanIt first, RanIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` to form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
Thus, the elements are sorted in *ascending* order.

The function evaluates
the ordering predicate `X < Y`
a number of times proportional to at most
`ceil((last - first) * log(last - first))`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `sort_heap`

    template<class RanIt>
        void sort_heap(RanIt first, RanIt last);
    template<class RanIt, class Pr>
        void sort_heap(RanIt first, RanIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` to form a sequence
that is
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
The original sequence must designate a heap, also
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#heap%20ordering) `operator<`.
Thus, the elements are sorted in *ascending* order.

The function evaluates the ordering predicate
`X < Y` at most
`ceil((last - first) * log(last - first))` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `stable_partition`

    template<class BidIt, class Pr>
        BidIt stable_partition(BidIt first, BidIt last,
            Pr pred);Copy to clipboard

The template function reorders the sequence designated by iterators in the
range `[first, last)` and determines the value
`K` such that for each `N` in the range
`[0, K)` the predicate `pred(*(first + N))`
is true, and for each `N` in the range
`[K, last - first)` the predicate `pred(*(first + N))`
is false. It does so without altering the relative order of either
the elements designated by indexes
in the range `[0, K)` or
the elements designated by indexes
in the range `[K, last - first)`.
The function then returns `first + K`.

The predicate must not alter its operand.
The function evaluates `pred(*(first + N))` exactly
`last - first` times, and swaps at most
`ceil((last - first) * log(last - first))`
pairs of elements. (Given enough temporary storage, it can
replace the swaps with at most
`2 * (last - first)` assignments.)

## `stable_sort`

    template<class BidIt>
        void stable_sort(BidIt first, BidIt last);
    template<class BidIt, class Pr>
        void stable_sort(BidIt first, BidIt last, Pr pred);Copy to clipboard

The first template function reorders the sequence
designated by iterators in the
range `[first, last)` to form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
It does so without altering the relative order of
elements that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering).
Thus, the elements are sorted in *ascending* order.

The function evaluates
the ordering predicate `X < Y`
a number of times proportional to at most
`ceil((last - first) * (log(last - first))^2)`.
(Given enough temporary storage, it can evaluate the predicate
a number of times proportional to at most
`ceil((last - first) * log(last - first))`.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

## `swap`

    template<class Ty>
        void swap(Ty& left, Ty& right);Copy to clipboard

The template function leaves the value originally stored in
`right` subsequently stored in `left`,
and the value originally stored in `left`
subsequently stored in `right`.

## `swap_ranges`

    template<class FwdIt1, class FwdIt2>
        FwdIt2 swap_ranges(FwdIt1 first1, FwdIt1 last1,
            FwdIt2 first2);Copy to clipboard

The template function evaluates
`swap(*(first1 + N), *(first2 + N))` once for
each `N` in the range `[0, last1 - first1)`.
It then returns `first2 + (last1 - first1)`.
If `first2` and `first1` designate regions of storage,
the range `[first2, first2 + (last1 - first1))` must not
overlap the range `[first1, last1)`.

## `transform`

    template<class InIt, class OutIt, class Fn1>
        OutIt transform(InIt first, InIt last, OutIt dest,
            Fn1 func);
    template<class InIt1, class InIt2, class OutIt,
        class Fn2>
        OutIt transform(InIt1 first1, InIt1 last1,
            InIt2 first2, OutIt dest, Fn2 func);Copy to clipboard

The first template function evaluates
`*(dest + N) = func(*(first + N))`
once for each `N` in the range `[0, last - first)`.
It then returns `dest + (last - first)`. The call
`func(*(first + N))` must not alter
`*(first + N)`.

The second template function evaluates
`*(dest + N) = func(*(first1 + N), *(first2 + N))`
once for each `N` in the range `[0, last1 - first1)`.
It then returns `dest + (last1 - first1)`. The call
`func(*(first1 + N), *(first2 + N))` must not alter
either `*(first1 + N)` or `*(first2 + N)`.

## `unique`

    template<class FwdIt>
        FwdIt unique(FwdIt first, FwdIt last);
    template<class FwdIt, class Pr>
        FwdIt unique(FwdIt first, FwdIt last, Pr pred);Copy to clipboard

The first template function effectively assigns `first` to
`X`, then executes the statement:

    if (!(*X == *(first + N + 1)))
        *++X = *(first + N + 1);Copy to clipboard

once for each `N` in the range
`[1, last - first)`. It then returns `X`.
Thus, the function repeatedly removes from the resulting sequence
the second of a pair of elements for
which the predicate `*(first + N) == *(first + N + 1)` is true,
until only the first of a sequence of elements survives
that satisfies the comparison.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It does so without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the
resulting sequence. For a non-empty sequence,
the function evaluates the predicate
`last - first - 1` times.

The second template function behaves the same, except that
it executes the statement:

    if (!pred(*(first + N), *(first + N + 1)))
        *++X = *(first + N + 1);Copy to clipboard

Note that for a sequence designated by the range `[first, last)`
and [ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `pred`,
you can remove all but the first of a sequence of elements that have
[equivalent ordering](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#equivalent%20ordering) by calling
`unique(first, last,
not2(pred))`.

## `unique_copy`

    template<class InIt, class OutIt>
        OutIt unique_copy(InIt first, InIt last, OutIt dest);
    template<class InIt, class OutIt, class Pr>
        OutIt unique_copy(InIt first, InIt last, OutIt dest,
            Pr pred);Copy to clipboard

The first template function effectively executes the statement:

    if (N == 0 || !(*(first + N - 1) == *(first + N)))
        *dest++ = *(first + N);Copy to clipboard

once for each `N` in the range
`[0, last - first)`. It then returns `dest`.
Thus, the function repeatedly removes from the resulting sequence
the second of a pair of elements for
which the predicate `*(first + N) == *(first + N - 1)` is true,
until only the first of a sequence of equal elements survives.
Here, `operator==` must perform a
[pairwise comparison](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#pairwise%20comparison)
between its operands.
It does so without altering the relative order of remaining elements,
and returns the iterator value that designates the end of the
copied sequence. For a non-empty sequence,
the function evaluates the predicate
`last - first - 1` times.

If `dest` and `first` designate regions of storage,
the range `[dest, dest + (last - first))` must not
overlap the range `[first, last)`.

The second template function behaves the same, except that
it executes the statement:

    if (N == 0 || !pred(*(first + N - 1), *(first + N)))
        *dest++ = *(first + N);Copy to clipboard

## `upper_bound`

    template<class FwdIt, class Ty>
        FwdIt upper_bound(FwdIt first, FwdIt last,
            const Ty& val);
    template<class FwdIt, class Ty, class Pr>
        FwdIt upper_bound(FwdIt first, FwdIt last,
            const Ty& val, Pr pred);Copy to clipboard

The first template function determines the highest value of `N`
in the range `(0, last - first]` such that,
for each `M` in the range `[0, N)`
the predicate `!(val < *(first + M))` is true,
where the elements designated by iterators
in the range `[first, last)` form a sequence
[ordered by](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_lib_stl.html#sequence%20ordering) `operator<`.
It then returns `first + N`.
Thus, the function determines the highest position
before which `val` can be inserted in the sequence
and still preserve its ordering.

The function evaluates the ordering predicate `X < Y` at most
`ceil(log(last - first)) + 1` times.

The second template function behaves the same, except that
it replaces `operator<(X, Y)` with
`pred(X, Y)`.

* * *

See also the
**[Table of Contents](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_index.html#Table%20of%20Contents)** and the
**[Index](https://docs.qualcomm.com/doc/80-N3040-23/topic/_cpp_index.html)**.

*[Copyright](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_crit_pjp.html) © 1992-2006by P.J. Plauger. Portions derived from work[copyright](https://docs.qualcomm.com/doc/80-N3040-23/topic/cpp_crit_hp.html) © 1994by Hewlett-Packard Company. All rights reserved.*

<!--V5.01:1566-->

Last Published: Oct 06, 2026

[Previous Topic
Preprocessing](https://docs.qualcomm.com/bundle/publicresource/80-N3040-23/topics/cpp_preproc.md) Next Topic

<assert.h></assert.h>