<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 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 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 FwdIt1, class Diff2, class Ty>
    FwdIt1 search_n(FwdIt1 first1, FwdIt1 last1,
        Diff2 count, const Ty& val);
template<class FwdIt1, class Diff2, class Ty, class Pr>
    FwdIt1 search_n(FwdIt1 first1, FwdIt1 last1,
        Diff2 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);

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

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

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

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

The first template function determines whether a value of N exists in the range [0, last - first) for which *(first + N) has equivalent ordering to val, where the elements designated by iterators in the range [first, last) form a sequence ordered by 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);

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

The template function evaluates *(dest - N - 1) = *(last - N - 1)) once for each N in the range [0, last - first), for strictly oncreasing 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);

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

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

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

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 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)) + 1.

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

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

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

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

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

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

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

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

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

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

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, where the elements designated by iterators in the ranges [first1, last1) and [first2, last2) each form a sequence ordered by 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);

The first template function reorders the sequences designated by iterators in the ranges [first, mid) and [mid, last), each ordered by 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, 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);

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

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

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

The first template function reorders the sequence designated by iterators in the range [first, last) to form a heap ordered by 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);

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

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

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

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

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

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

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 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. No two elements may have equivalent ordering.

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

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

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

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

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

The first template function reorders the sequence designated by iterators in the range [first, last) to form a new heap, ordered by 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);

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 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. No two elements may have equivalent ordering.

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

The first template function reorders the sequence designated by iterators in the range [first, last) to form a new heap ordered by 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);

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

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

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

once for each N in the range [0, last - first). Here, operator== must perform a pairwise comparison 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);

The template function effectively executes the statement:

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

once for each N in the range [0, last - first). Here, operator== must perform a pairwise comparison 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);

The template function effectively executes the statement:

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

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

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

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

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

The template function executes the statement:

if (*(first + N) == oldval)
    *(first + N) = newval;

once for each N in the range [0, last - first). Here, operator== must perform a pairwise comparison 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);

The template function executes the statement:

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

once for each N in the range [0, last - first). Here, operator== must perform a pairwise comparison 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);

The template function executes the statement:

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

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

The template function executes the statement:

if (pred(*(first + N)))
    *(first + N) = val;

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

reverse

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

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

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

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

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

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 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 FwdIt1, class Diff2, class Ty>
    FwdIt1 search_n(FwdIt1 first1, FwdIt1 last1,
        Diff2 count, const Ty& val);
template<class FwdIt1, class Diff2, class Ty, class Pr>
    FwdIt1 search_n(FwdIt1 first1, FwdIt1 last1,
        Diff2 count, const Ty& val, Pr pred);

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

The first template function alternately copies values from two sequences designated by iterators in the ranges [first1, last1) and [first2, last2), both ordered by 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 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);

The first template function alternately copies values from two sequences designated by iterators in the ranges [first1, last1) and [first2, last2), both ordered by 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 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);

The first template function alternately copies values from two sequences designated by iterators in the ranges [first1, last1) and [first2, last2), both ordered by 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 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);

The first template function alternately copies values from two sequences designated by iterators in the ranges [first1, last1) and [first2, last2), both ordered by 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 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);

The first template function reorders the sequence designated by iterators in the range [first, last) to form a sequence ordered by 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);

The first template function reorders the sequence designated by iterators in the range [first, last) to form a sequence that is ordered by operator<. The original sequence must designate a heap, also ordered by 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);

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

The first template function reorders the sequence designated by iterators in the range [first, last) to form a sequence ordered by operator<. It does so without altering the relative order of elements that have equivalent ordering. 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);

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

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

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

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

if (N == 0)
    ++X;
else if (!(*X == *(first + N)))
    *X++ = V;

once for each N in the range [0, 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 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 (N == 0)
    ++X;
else if (!pred(*X, *(first + N)))
    *X++ = V;

Note that for a sequence designated by the range [first, last) and ordered by pred, you can remove all but the first of a sequence of elements that have equivalent ordering 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);

The first template function effectively executes the statement:

if (N == 0 || !(*(first + N) == V))
    V = *(first + N), *dest++ = V;

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 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), V))
    V = *(first + N), *dest++ = V;

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

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 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 and the Index.

Copyright © 1994-2002 by P.J. Plauger. Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights reserved.