DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

# algorithm(3C++std)

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 - templates that implement useful algorithms (standard template library)

## Synopsis

```   namespace std {
template<class InIt, class Fun>
Fun for_each(InIt first, InIt last, Fun f);
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
template<class InIt, class Pred>
InIt find_if(InIt first, InIt last, Pred pr);
template<class FwdIt1, class FwdIt2>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
template<class FwdIt1, class FwdIt2>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
template<class FwdIt>
template<class FwdIt, class Pred>
FwdIt adjacent_find(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class T, class Dist>
typename iterator_traits<InIt>::difference_type
count(InIt first, InIt last,
const T& val);
template<class InIt, class Pred, class Dist>
typename iterator_traits<InIt>::difference_type
count_if(InIt first, InIt last,
Pred pr);
template<class InIt1, class InIt2>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x);
template<class InIt1, class InIt2, class Pred>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x, Pred pr);
template<class InIt1, class InIt2>
bool equal(InIt1 first, InIt1 last, InIt2 x);
template<class InIt1, class InIt2, class Pred>
bool equal(InIt1 first, InIt1 last, InIt2 x, Pred pr);
template<class FwdIt1, class FwdIt2>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
template<class FwdIt, class Dist, class T>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val);
template<class FwdIt, class Dist, class T, class Pred>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val, Pred pr);
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
template<class BidIt1, class BidIt2>
BidIt2 copy_backward(BidIt1 first, BidIt1 last,
BidIt2 x);
template<class T>
void swap(T& x, T& y);
template<class FwdIt1, class FwdIt2>
FwdIt2 swap_ranges(FwdIt1 first, FwdIt1 last,
FwdIt2 x);
template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 x, FwdIt2 y);
template<class InIt, class OutIt, class Unop>
OutIt transform(InIt first, InIt last, OutIt x,
Unop uop);
template<class InIt1, class InIt2, class OutIt,
class Binop>
OutIt transform(InIt1 first1, InIt1 last1,
InIt2 first2, OutIt x, Binop bop);

template<class FwdIt, class T>
void replace(FwdIt first, FwdIt last,
const T& vold, const T& vnew);
template<class FwdIt, class Pred, class T>
void replace_if(FwdIt first, FwdIt last,
Pred pr, const T& val);
template<class InIt, class OutIt, class T>
OutIt replace_copy(InIt first, InIt last, OutIt x,
const T& vold, const T& vnew);
template<class InIt, class OutIt, class Pred, class T>
OutIt replace_copy_if(InIt first, InIt last, OutIt x,
Pred pr, const T& val);
template<class FwdIt, class T>
void fill(FwdIt first, FwdIt last, const T& x);
template<class OutIt, class Size, class T>
void fill_n(OutIt first, Size n, const T& x);
template<class FwdIt, class Gen>
void generate(FwdIt first, FwdIt last, Gen g);
template<class OutIt, class Pred, class Gen>
void generate_n(OutIt first, Dist n, Gen g);
template<class FwdIt, class T>
FwdIt remove(FwdIt first, FwdIt last, const T& val);
template<class FwdIt, class Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class OutIt, class T>
OutIt remove_copy(InIt first, InIt last, OutIt x,
const T& val);
template<class InIt, class OutIt, class Pred>
OutIt remove_copy_if(InIt first, InIt last, OutIt x,
Pred pr);
template<class FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class OutIt>
OutIt unique_copy(InIt first, InIt last, OutIt x);
template<class InIt, class OutIt, class Pred>
OutIt unique_copy(InIt first, InIt last, OutIt x,
Pred pr);
template<class BidIt>
void reverse(BidIt first, BidIt last);
template<class BidIt, class OutIt>
OutIt reverse_copy(BidIt first, BidIt last, OutIt x);
template<class FwdIt>
void rotate(FwdIt first, FwdIt middle, FwdIt last);
template<class FwdIt, class OutIt>
OutIt rotate_copy(FwdIt first, FwdIt middle,
FwdIt last, OutIt x);
template<class RanIt>
void random_shuffle(RanIt first, RanIt last);
template<class RanIt, class Fun>
void random_shuffle(RanIt first, RanIt last, Fun& f);
template<class BidIt, class Pred>
BidIt partition(BidIt first, BidIt last, Pred pr);
template<class BidIt, class Pred>
BidIt stable_partition(BidIt first, BidIt last,
Pred pr);
template<class RanIt>
void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
template<class BidIt>
void stable_sort(BidIt first, BidIt last);
template<class BidIt, class Pred>
void stable_sort(BidIt first, BidIt last, Pred pr);
template<class RanIt>
void partial_sort(RanIt first, RanIt middle,
RanIt last);
template<class RanIt, class Pred>
void partial_sort(RanIt first, RanIt middle,
RanIt last, Pred pr);
template<class InIt, class RanIt>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2);
template<class InIt, class RanIt, class Pred>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2, Pred pr);

template<class RanIt>
void nth_element(RanIt first, RanIt nth, RanIt last);
template<class RanIt, class Pred>
void nth_element(RanIt first, RanIt nth, RanIt last,
Pred pr);
template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
template<class FwdIt, class T>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
template<class FwdIt, class T>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val);
template<class FwdIt, class T, class Pred>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val, Pred pr);
template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
bool binary_search(FwdIt first, FwdIt last,
const T& val, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class BidIt>
void inplace_merge(BidIt first, BidIt middle,
BidIt last);
template<class BidIt, class Pred>
void inplace_merge(BidIt first, BidIt middle,
BidIt last, Pred pr);
template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
template<class InIt1, class InIt2, class OutIt>
OutIt set_symmetric_difference(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_symmetric_difference(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, OutIt x,
Pred pr);
template<class RanIt>
void push_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void push_heap(RanIt first, RanIt last, Pred pr);
template<class RanIt>
void pop_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void pop_heap(RanIt first, RanIt last, Pred pr);
template<class RanIt>
void make_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void make_heap(RanIt first, RanIt last, Pred pr);
template<class RanIt>
void sort_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort_heap(RanIt first, RanIt last, Pred pr);
template<class T>
const T& max(const T& x, const T& y);
template<class T, class Pred>
const T& max(const T& x, const T& y, Pred pr);
template<class T>
const T& min(const T& x, const T& y);
template<class T, class Pred>
const T& min(const T& x, const T& y, Pred pr);
template<class FwdIt>
FwdIt max_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt max_element(FwdIt first, FwdIt last, Pred pr);
template<class FwdIt>
FwdIt min_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt min_element(FwdIt first, FwdIt last, Pred pr);
template<class InIt1, class InIt2>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);
template<class BidIt>
bool next_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool next_permutation(BidIt first, BidIt last,
Pred pr);
template<class BidIt>
bool prev_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool prev_permutation(BidIt first, BidIt last,
Pred pr);
};

```

## Description

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.

### Algorithm Conventions

The descriptions of the algorithm template functions employ several shorthand phrases:

• The phrase ``in the range `[A, B)`'' means the sequence of zero or more discrete values beginning with `A` up to but not including `B`. A range is valid only if `B` is reachable from `A` -- you can store `A` in an object `N` (`N = A`), increment the object zero or more times (`++N`), and have the object compare equal to `B` after a finite number of increments (`N == B`).
• The phrase ``each `N` in the range `[A, B)`'' means that `N` begins with the value `A` and is incremented zero or more times until it equals the value `B`. The case `N == B` is not in the range.
• The phrase ``the lowest value of `N` in the range `[A, B)` such that X'' means that the condition X is determined for each `N` in the range `[A, B)` until the condition X is met.
• The phrase ``the highest value of `N` in the range `[A, B)` such that X'' usually means that X is determined for each `N` in the range `[A, B)`. The function stores in `K` a copy of `N` each time the condition X is met. If any such store occurs, the function replaces the final value of `N` (which equals `B`) with the value of `K`. For a bidirectional or random-access iterator, however, it can also mean that `N` begins with the highest value in the range and is decremented over the range until the condition X is met.
• Expressions such as `X - Y`, where `X` and `Y` can be iterators other than random-access iterators, are intended in the mathematical sense. The function does not necessarily evaluate `operator-` if it must determine such a value. The same is also true for expressions such as `X + N` and `X - N`, where `N` is an integer type.

Several algorithms make use of a predicate, using `operator==`, that must impose an equivalence relationship on pairs of elements from a sequence. For all elements `X`, `Y`, and `Z`:

• `X == X` is true.
• If `X == Y` is true, then `Y == X` is true.
• If `X == Y && Y == Z` is true, then `X == Z` is true.

Several algorithms make use of a predicate that must impose a strict weak ordering on pairs of elements from a sequence. For the predicate `pr(X, Y)`:

• ``strict'' means that `pr(X, X)` is false
• ``weak'' means that `X` and `Y` have an equivalent ordering if `!pr(X, Y) && !pr(Y, X)` (`X == Y` need not be defined)
• ``ordering'' means that ```pr(X, Y) && pr(Y, Z)``` implies `pr(X, Z)`

Some of these algorithms implicitly use the predicate `X < Y`. Other predicates that typically satisfy the ``strict weak ordering'' requirement are `X > Y`, `less(X, Y)`, and `greater(X, Y)`. Note, however, that predicates such as `X <= Y` and `X >= Y` do not satisfy this requirement.

A sequence of elements designated by iterators in the range `[first, last)` is ``a sequence ordered by `operator<`'' if, for each `N` in the range `[0, last - first)` and for each `M` in the range `(N, last - first)` the predicate `!(*(first + M) < *(first + N))` is true. (Note that the elements are sorted in ascending order.) The predicate function `operator<`, or any replacement for it, must not alter either of its operands. Moreover, it must impose a strict weak ordering on the operands it compares.

A sequence of elements designated by iterators in the range `[first, last)` is ``a heap ordered by `operator<`'' if, for each `N` in the range `[1, last - first)` the predicate `!(*first < *(first + N))` is true. (The first element is the largest.) Its internal structure is otherwise known only to the template functions `make_heap`, `pop_heap`, and `push_heap`. As with an ordered sequence, the predicate function `operator<`, or any replacement for it, must not alter either of its operands, and it must impose a strict weak ordering on the operands it compares.

```   template<class FwdIt>
template<class FwdIt, class Pred>
FwdIt adjacent_find(FwdIt first, FwdIt last, Pred pr);
```

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 impose an equivalence relationship between its operands. It then returns `first + N`. If no such value exists, the function returns `last`. It evaluates the predicate exactly `N + 1` times.

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

### binary_search

```   template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
bool binary_search(FwdIt first, FwdIt last,
const T& val, Pred pr);
```

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.

If `FwdIt` is a random-access iterator type, the function evaluates the ordering predicate `X < Y` at most `ceil(log(last - first)) + 2` times. Otherwise, the function evaluates the predicate a number of times proportional to `last - first`.

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

### copy

```   template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
```

The template function evaluates `*(x + 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 `x + N`. If `x` and `first` designate regions of storage, `x` must not be in the range `[first, last)`.

### copy_backward

```   template<class BidIt1, class BidIt2>
BidIt2 copy_backward(BidIt1 first, BidIt1 last,
BidIt2 x);
```

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

### count

```   template<class InIt, class T>
typename iterator_traits<InIt>::difference_type
count(InIt first, InIt last, const T& val);
```

The template function sets a count `n` to zero. It then executes `++n` for each `N` in the range `[0, last - first)` for which the predicate `*(first + N) == val` is true. Here, `operator==` must impose an equivalence relationship between its operands. The function returns `n`. It evaluates the predicate exactly `last - first` times.

### count_if

```   template<class InIt, class Pred, class Dist>
typename iterator_traits<InIt>::difference_type
count_if(InIt first, InIt last,
Pred pr);
```

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

### equal

```   template<class InIt1, class InIt2>
bool equal(InIt1 first, InIt1 last, InIt2 x);
template<class InIt1, class InIt2, class Pred>
bool equal(InIt1 first, InIt1 last, InIt2 x, Pred pr);
```

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 impose an equivalence relationship 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 `pr(*(first1 + N), *(first2 + N))`.

### equal_range

```   template<class FwdIt, class T>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val);
template<class FwdIt, class T, class Pred>
pair<FwdIt, FwdIt> equal_range(FwdIt first,
FwdIt last, const T& val, Pred pr);
```

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.

If `FwdIt` is a random-access iterator type, the function evaluates the ordering predicate `X < Y` at most `ceil(2 * log(last - first)) + 1`. Otherwise, the function evaluates the predicate a number of times proportional to `last - first`.

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

### fill

```   template<class FwdIt, class T>
void fill(FwdIt first, FwdIt last, const T& x);
```

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

### fill_n

```   template<class OutIt, class Size, class T>
void fill_n(OutIt first, Size n, const T& x);
```

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

### find

```   template<class InIt, class T>
InIt find(InIt first, InIt last, const T& 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 impose an equivalence relationship 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 Pred>
FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
```

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 impose an equivalence relationship 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 `pr(*(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 Pred>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
```

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 impose an equivalence relationship 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 `pr(*(first1 + N), *(first2 + M))`.

### find_if

```   template<class InIt, class Pred>
InIt find_if(InIt first, InIt last, Pred pr);
```

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 Fun>
Fun for_each(InIt first, InIt last, Fun f);
```

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

### generate

```   template<class FwdIt, class Gen>
void generate(FwdIt first, FwdIt last, Gen g);
```

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

### generate_n

```
template<class OutIt, class Pred, class Gen>
void generate_n(OutIt first, Dist n, Gen g);

```

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

### includes

```   template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool includes(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, Pred pr);
```

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)`, `*(first + M)` and `*(first + 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 `pr(X, Y)`.

### inplace_merge

```   template<class BidIt>
void inplace_merge(BidIt first, BidIt middle,
BidIt last);
template<class BidIt, class Pred>
void inplace_merge(BidIt first, BidIt middle,
BidIt last, Pred pr);
```

The first template function reorders the sequences designated by iterators in the ranges `[first, middle)` and `[middle, 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, middle)` 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 `pr(X, Y)`.

### iter_swap

```   template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 x, FwdIt2 y);
```

The template function leaves the value originally stored in `*y` subsequently stored in `*x`, and the value originally stored in `*x` subsequently stored in `*y`.

### lexicographical_compare

```   template<class InIt1, class InIt2>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2);
template<class InIt1, class InIt2, class Pred>
bool lexicographical_compare(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);
```

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 `pr(X, Y)`.

### lower_bound

```   template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt lower_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
```

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.

If `FwdIt` is a random-access iterator type, the function evaluates the ordering predicate `X < Y` at most `ceil(log(last - first)) + 1` times. Otherwise, the function evaluates the predicate a number of times proportional to `last - first`.

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

### make_heap

```   template<class RanIt>
void make_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void make_heap(RanIt first, RanIt last, Pred pr);
```

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 `pr(X, Y)`.

### max

```   template<class T>
const T& max(const T& x, const T& y);
template<class T, class Pred>
const T& max(const T& x, const T& y, Pred pr);
```

The first template function returns `y` if `x < y`. Otherwise it returns `x`. `T` 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 `pr(X, Y)`.

### max_element

```   template<class FwdIt>
FwdIt max_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt max_element(FwdIt first, FwdIt last, Pred pr);
```

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 `pr(X, Y)`.

### merge

```   template<class InIt1, class InIt2, class OutIt>
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt merge(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
```

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 `x`, also ordered by `operator<`. The function then returns `x + 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 `x` and `first1` designate regions of storage, the range `[x, x + K)` must not overlap the range `[first1, last1)`. If `x` and `first2` designate regions of storage, the range `[x, x + 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 `pr(X, Y)`.

### min

```   template<class T>
const T& min(const T& x, const T& y);
template<class T, class Pred>
const T& min(const T& x, const T& y, Pred pr);
```

The first template function returns `y` if `y < x`. Otherwise it returns `x`. `T` 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 `pr(X, Y)`.

### min_element

```   template<class FwdIt>
FwdIt min_element(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt min_element(FwdIt first, FwdIt last, Pred pr);
```

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 `pr(X, Y)`.

### mismatch

```   template<class InIt1, class InIt2>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x);
template<class InIt1, class InIt2, class Pred>
pair<InIt1, InIt2> mismatch(InIt1 first, InIt1 last,
InIt2 x, Pred pr);
```

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 impose an equivalence relationship 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 `pr(*(first1 + N), *(first2 + N))`.

### next_permutation

```   template<class BidIt>
bool next_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool next_permutation(BidIt first, BidIt last,
Pred pr);
```

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 `pr(X, Y)`.

### nth_element

```   template<class RanIt>
void nth_element(RanIt first, RanIt nth, RanIt last);
template<class RanIt, class Pred>
void nth_element(RanIt first, RanIt nth, RanIt last,
Pred pr);
```

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 `pr(X, Y)`.

### partial_sort

```   template<class RanIt>
void partial_sort(RanIt first, RanIt middle,
RanIt last);
template<class RanIt, class Pred>
void partial_sort(RanIt first, RanIt middle,
RanIt last, Pred pr);
```

The first template function reorders the sequence designated by iterators in the range `[first, last)` such that for each `N` in the range `[0, middle - first)` and for each `M` in the range `(N, last - first)` the predicate `!(*(first + M) < *(first + N))` is true. Thus, the smallest `middle - 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` at most `ceil((last - first) * log(middle - first))` times.

The second template function behaves the same, except that it replaces `operator<(X, Y)` with `pr(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 Pred>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2, Pred pr);
```

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` 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` at most `ceil((last - first) * log(K))` times.

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

### partition

```   template<class BidIt, class Pred>
BidIt partition(BidIt first, BidIt last, Pred pr);
```

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 `pr(*(first + N))` is true, and for each `N` in the range `[K, last - first)` the predicate `pr(*(first + N))` is false. The function then returns `first + K`.

The predicate must not alter its operand. The function evaluates `pr(*(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 Pred>
void pop_heap(RanIt first, RanIt last, Pred pr);
```

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 `pr(X, Y)`.

### prev_permutation

```   template<class BidIt>
bool prev_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
bool prev_permutation(BidIt first, BidIt last,
Pred pr);
```

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 next 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 `pr(X, Y)`.

### push_heap

```   template<class RanIt>
void push_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void push_heap(RanIt first, RanIt last, Pred pr);
```

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 `pr(X, Y)`.

### random_shuffle

```   template<class RanIt>
void random_shuffle(RanIt first, RanIt last);
template<class RanIt, class Fun>
void random_shuffle(RanIt first, RanIt last, Fun& f);
```

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 second template function behaves the same, except that `M` is `(Dist)f((Dist)N)`, where `Dist` is the type ```iterator_traits:: difference_type```.

### remove

```   template<class FwdIt, class T>
FwdIt remove(FwdIt first, FwdIt last, const T& 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 impose an equivalence relationship between its operands. It then returns `X`. Thus, the function removes from the 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 revised sequence.

### remove_copy

```   template<class InIt, class OutIt, class T>
OutIt remove_copy(InIt first, InIt last, OutIt x,
const T& val);
```

The template function effectively executes the statement:

```   if (!(*(first + N) == val))
*x++ = *(first + N);
```

once for each `N` in the range `[0, last - first)`. Here, `operator==` must impose an equivalence relationship between its operands. It then returns `x`. Thus, the function removes from the 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 revised sequence.

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

### remove_copy_if

```   template<class InIt, class OutIt, class Pred>
OutIt remove_copy_if(InIt first, InIt last, OutIt x,
Pred pr);
```

The template function effectively executes the statement:

```   if (!pr(*(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 sequence all elements for which the predicate `pr(*(first + N))` is true, without altering the relative order of remaining elements, and returns the iterator value that designates the end of the revised sequence.

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

### remove_if

```   template<class FwdIt, class Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);
```

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

```   if (!pr(*(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 sequence all elements for which the predicate `pr(*(first + N))` is true, without altering the relative order of remaining elements, and returns the iterator value that designates the end of the revised sequence.

### replace

```   template<caass FwdIt, class T>
void replace(FwdIt first, FwdIt last,
const T& vold, const T& vnew);
```

The template function executes the statement:

```   if (*(first + N) == vold)
*(first + N) = vnew;
```

once for each `N` in the range `[0, last - first)`. Here, `operator==` must impose an equivalence relationship between its operands.

### replace_copy

```   template<class InIt, class OutIt, class T>
OutIt replace_copy(InIt first, InIt last, OutIt x,
const T& vold, const T& vnew);
```

The template function executes the statement:

```   if (*(first + N) == vold)
*(x + N) = vnew;
else
*(x + N) = *(first + N)
```

once for each `N` in the range `[0, last - first)`. Here, `operator==` must impose an equivalence relationship between its operands.

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

### replace_copy_if

```   template<class InIt, class OutIt, class Pred, class T>
OutIt replace_copy_if(InIt first, InIt last, OutIt x,
Pred pr, const T& val);
```

The template function executes the statement:

```   if (pr(*(first + N)))
*(x + N) = val;
else
*(x + N) = *(first + N)
```

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

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

### replace_if

```   template<class FwdIt, class Pred, class T>
void replace_if(FwdIt first, FwdIt last,
Pred pr, const T& val);
```

The template function executes the statement:

```   if (pr(*(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 x);
```

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

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

### rotate

```   template<class FwdIt>
void rotate(FwdIt first, FwdIt middle, FwdIt last);
```

The template function leaves the value originally stored in `*(first + (N + (middle - 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 `middle - first` elements or right by `last - middle` elements. Both `[first, middle)` and `[middle, 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 middle,
FwdIt last, OutIt x);
```

The template function evaluates `*(x + N) = *(first + (N + (middle - 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 `middle - first` elements or right by `last - middle` elements as it copies. Both `[first, middle)` and `[middle, last)` must be valid ranges.

If `x` and `first` designate regions of storage, the range `[x, x + (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 Pred>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1,
FwdIt2 first2, FwdIt2 last2, Pred pr);
```

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 impose an equivalence relationship 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 `pr(*(first1 + N + M), *(first2 + M))`.

### search_n

```   template<class FwdIt, class Dist, class T>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val);
template<class FwdIt, class Dist, class T, class Pred>
FwdIt search_n(FwdIt first, FwdIt last,
Dist n, const T& val, Pred pr);
```

The first template function determines the lowest value of `N` in the range ```[0, (last - first) - n)``` such that for each `M` in the range `[0, n)`, the predicate `*(first + N + M) == val` is true. Here, `operator==` must impose an equivalence relationship between its operands. It then returns `first + N`. If no such value exists, the function returns `last`. It evaluates the predicate at most ```n * (last - first)``` times.

The second template function behaves the same, except that the predicate is `pr(*(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 x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_difference(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
```

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 `x`, also ordered by `operator<`. The function then returns `x + 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 `x` and `first1` designate regions of storage, the range `[x, x + K)` must not overlap the range `[first1, last1)`. If `x` and `first2` designate regions of storage, the range `[x, x + 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 `pr(X, Y)`.

### set_intersection

```   template<class InIt1, class InIt2, class OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_intersection(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
```

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 `x`, also ordered by `operator<`. The function then returns `x + 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 `x` and `first1` designate regions of storage, the range `[x, x + K)` must not overlap the range `[first1, last1)`. If `x` and `first2` designate regions of storage, the range `[x, x + 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 `pr(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 x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_symmetric_difference(InIt1 first1,
InIt1 last1, InIt2 first2, InIt2 last2, OutIt x,
Pred pr);
```

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 `x`, also ordered by `operator<`. The function then returns `x + 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 `x` and `first1` designate regions of storage, the range `[x, x + K)` must not overlap the range `[first1, last1)`. If `x` and `first2` designate regions of storage, the range `[x, x + 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 `pr(X, Y)`.

### set_union

```   template<class InIt1, class InIt2, class OutIt>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x);
template<class InIt1, class InIt2, class OutIt,
class Pred>
OutIt set_union(InIt1 first1, InIt1 last1,
InIt2 first2, InIt2 last2, OutIt x, Pred pr);
```

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 `x`, also ordered by `operator<`. The function then returns `x + 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 `x` and `first1` designate regions of storage, the range `[x, x + K)` must not overlap the range `[first1, last1)`. If `x` and `first2` designate regions of storage, the range `[x, x + 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 `pr(X, Y)`.

### sort

```   template<class RanIt>
void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
```

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` at most `ceil((last - first) * log(last - first))` times.

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

### sort_heap

```   template<class RanIt>
void sort_heap(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort_heap(RanIt first, RanIt last, Pred pr);
```

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 `pr(X, Y)`.

### stable_partition

```   template<class BidIt, class Pred>
BidIt stable_partition(BidIt first, BidIt last,
Pred pr);
```

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 `pr(*(first + N))` is true, and for each `N` in the range `[K, last - first)` the predicate `pr(*(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 `pr(*(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 Pred>
void stable_sort(BidIt first, BidIt last, Pred pr);
```

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` at most `ceil((last - first) * (log(last - first))^2)` times. (Given enough temporary storage, it can evaluate the predicate at most `ceil((last - first) * log(last - first))` times.)

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

### swap

```   template<class T>
void swap(T& x, T& y);
```

The template function leaves the value originally stored in `y` subsequently stored in `x`, and the value originally stored in `x` subsequently stored in `y`.

### swap_ranges

```   template<class FwdIt1, class FwdIt2>
FwdIt2 swap_ranges(FwdIt1 first, FwdIt1 last,
FwdIt2 x);
```

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

### transform

```   template<class InIt, class OutIt, class Unop>
OutIt transform(InIt first, InIt last, OutIt x,
Unop uop);
template<class InIt1, class InIt2, class OutIt,
class Binop>
OutIt transform(InIt1 first1, InIt1 last1,
InIt2 first2, OutIt x, Binop bop);
```

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

The second template function evaluates `*(x + N) = bop(*(first1 + N), *(first2 + N))` once for each `N` in the range `[0, last1 - first1)`. It then returns `x + (last1 - first1)`. The call `bop(*(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 Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);
```

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

```   if (N == 0 || !(*(first + N) == V))
V = *(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 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 impose an equivalence relationship 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 revised sequence. The function evaluates the predicate at most `last - first` times.

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

```   if (N == 0 || !pr(*(first + N), V))
V = *(first + N), *X++ = V;
```

### unique_copy

```   template<class InIt, class OutIt>
OutIt unique_copy(InIt first, InIt last, OutIt x);
template<class InIt, class OutIt, class Pred>
OutIt unique_copy(InIt first, InIt last, OutIt x,
Pred pr);
```

The first template function effectively executes the statement:

```   if (N == 0 || !(*(first + N) == V))
V = *(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 sequence it copies 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 impose an equivalence relationship 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.

If `x` and `first` designate regions of storage, the range `[x, x + (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 || !pr(*(first + N), V))
V = *(first + N), *x++ = V;
```

### upper_bound

```   template<class FwdIt, class T>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val);
template<class FwdIt, class T, class Pred>
FwdIt upper_bound(FwdIt first, FwdIt last,
const T& val, Pred pr);
```

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.

If `FwdIt` is a random-access iterator type, the function evaluates the ordering predicate `X < Y` at most `ceil(log(last - first)) + 1` times. Otherwise, the function evaluates the predicate a number of times proportional to `last - first`.

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

## References

iterator(3C++std) , utility(3C++std)
18 February 2000