A.2. A Brief Tour of the Algorithms

The library defines more than 100 algorithms. Learning to use these algorithms effectively requires understanding their structure rather than memorizing the details of each algorithm. Accordingly, in Chapter 10 we concentrated on describing and understanding that architecture. In this section we’ll briefly describe every algorithm. In the following descriptions,

• beg and end are iterators that denote a range of elements (§ 9.2.1, p. 331). Almost all of the algorithms operate on a sequence denoted by beg and end.
• beg2 is an iterator denoting the beginning of a second input sequence. If present, end2 denotes the end of the second sequence. When there is no end2, the sequence denoted by beg2 is assumed to be as large as the input sequence denoted by beg and end. The types of beg and beg2 need not match. However, it must be possible to apply the specified operation or given callable object to elements in the two sequences.
• dest is an iterator denoting a destination. The destination sequence must be able to hold as many elements as necessary given the input sequence.
• unaryPred and binaryPred are unary and binary predicates (§ 10.3.1, p. 386) that return a type that can be used as a condition and take one and two arguments, respectively, that are elements in the input range.
• comp is a binary predicate that meets the ordering requirements for key in an associative container (§ 11.2.2, p. 425).
• unaryOp and binaryOp are callable objects (§ 10.3.2, p. 388) that can be called with one and two arguments from the input range, respectively.

A.2.1. Algorithms to Find an Object

These algorithms search an input range for a specific value or sequence of values.

Each algorithm provides two overloaded versions. The first version uses equality (==) operator of the underlying type to compare elements; the second version compares elements using the user-supplied unaryPred or binaryPred.

Simple Find Algorithms

These algorithms look for specific values and require input iterators.

find(beg, end, val)
find_if(beg, end, unaryPred)
find_if_not(beg, end, unaryPred)
count(beg, end, val)
count_if(beg, end, unaryPred)

find returns an iterator to the first element in the input range equal to val. find_if returns an iterator to the first element for which unaryPred succeeds; find_if_not returns an iterator to the first element for which unaryPred is false. All three return end if no such element exists.

count returns a count of how many times val occurs; count_if counts elements for which unaryPred succeeds.

all_of(beg, end, unaryPred)
any_of(beg, end, unaryPred)
none_of(beg, end, unaryPred)

Returns a bool indicating whether the unaryPred succeeded for all of the elements, any element, or no element respectively. If the sequence is empty, any_of returns false; all_of and none_of return true.

Algorithms to Find One of Many Values

These algorithms require forward iterators. They look for a repeated elements in the input sequence.

adjacent_find(beg, end)
adjacent_find(beg, end, binaryPred)

Returns an iterator to the first adjacent pair of duplicate elements. Returns end if there are no adjacent duplicate elements.

search_n(beg, end, count, val)
search_n(beg, end, count, val, binaryPred)

Returns an iterator to the beginning of a subsequence of count equal elements. Returns end if no such subsequence exists.

Algorithms to Find Subsequences

With the exception of find_first_of, these algorithms require two pairs of forward iterators. find_first_of uses input iterators to denote its first sequence and forward iterators for its second. These algorithms search for subsequences rather than for a single element.

search(beg1, end1, beg2, end2)
search(beg1, end1, beg2, end2, binaryPred)

Returns an iterator to the first position in the input range at which the second range occurs as a subsequence. Returns end1 if the subsequence is not found.

find_first_of(beg1, end1, beg2, end2)
find_first_of(beg1, end1, beg2, end2, binaryPred)

Returns an iterator to the first occurrence in the first range of any element from the second range. Returns end1 if no match is found.

find_end(beg1, end1, beg2, end2)
find_end(beg1, end1, beg2, end2, binaryPred)

Like search, but returns an iterator to the last position in the input range at which the second range occurs as a subsequence. Returns end1 if the second subsequence is empty or is not found.

A.2.2. Other Read-Only Algorithms

These algorithms require input iterators for their first two arguments.

The equal and mismatch algorithms also take an additional input iterator that denotes the start of a second range. They also provide two overloaded versions. The first version uses equality (==) operator of the underlying type to compare elements; the second version compares elements using the user-supplied unaryPred or binaryPred.

for_each(beg, end, unaryOp)

Applies the callable object (§ 10.3.2, p. 388) unaryOp to each element in its input range. The return value from unaryOp (if any) is ignored. If the iterators allow writing to elements through the dereference operator, then unaryOp may modify the elements.

mismatch(beg1, end1, beg2)
mismatch(beg1, end1, beg2, binaryPred)

Compares the elements in two sequences. Returns a pair (§ 11.2.3, p. 426) of iterators denoting the first elements in each sequence that do not match. If all the elements match, then the pair returned is end1, and an iterator into beg2 offset by the size of the first sequence.

equal(beg1, end1, beg2)
equal(beg1, end1, beg2, binaryPred)

Determines whether two sequences are equal. Returns true if each element in the input range equals the corresponding element in the sequence that begins at beg2.

A.2.3. Binary Search Algorithms

These algorithms require forward iterators but are optimized so that they execute much more quickly if they are called with random-access iterators. Technically speaking, regardless of the iterator type, these algorithms execute a logarithmic number of comparisons. However, when used with forward iterators, they must make a linear number of iterator operations to move among the elements in the sequence.

These algorithms require that the elements in the input sequence are already in order. These algorithms behave similarly to the associative container members of the same name (§ 11.3.5, p. 438). The equal_range, lower_bound, and upper_bound algorithms return iterators that refer to positions in the sequence at which the given element can be inserted while still preserving the sequence’s ordering. If the element is larger than any other in the sequence, then the iterator that is returned might be the off-the-end iterator.

Each algorithm provides two versions: The first uses the element type’s less-than operator (<) to test elements; the second uses the given comparison operation. In the following algorithms, “x is less than y” means x < y or that comp(x, y) succeeds.

lower_bound(beg, end, val)
lower_bound(beg, end, val, comp)

Returns an iterator denoting the first element such that val is not less than that element, or end if no such element exists.

upper_bound(beg, end, val)
upper_bound(beg, end, val, comp)

Returns an iterator denoting the first element such that is val is less than that element, or end if no such element exists.

equal_range(beg, end, val)
equal_range(beg, end, val, comp)

Returns a pair (§ 11.2.3, p. 426) in which the first member is the iterator that would be returned by lower_bound, and second is the iterator upper_bound would return.

binary_search(beg, end, val)
binary_search(beg, end, val, comp)

Returns a bool indicating whether the sequence contains an element that is equal to val. Two values x and y are considered equal if x is not less than y and y is not less than x.

A.2.4. Algorithms That Write Container Elements

Many algorithms write new values to the elements in the given sequence. These algorithms can be distinguished from one another both by the kinds of iterators they use to denote their input sequence and by whether they write elements in the input range or write to a given destination.

Algorithms That Write but Do Not Read Elements

These algorithms require an output iterator that denotes a destination. The _n versions take a second argument that specifies a count and write the given number of elements to the destination.

fill(beg, end, val)
fill_n(dest, cnt, val)
generate(beg, end, Gen)
generate_n(dest, cnt, Gen)

Assigns a new value to each element in the input sequence. fill assigns the value val; generate executes the generator object Gen(). A generator is a callable object (§ 10.3.2, p. 388) that is expected to produce a different return value each time it is called. fill and generate return void. The _n versions return an iterator that refers to the position immediately following the last element written to the output sequence.

Write Algorithms with Input Iterators

Each of these algorithms reads an input sequence and writes to an output sequence. They require dest to be an output iterator, and the iterators denoting the input range must be input iterators.

copy(beg, end, dest)
copy_if(beg, end, dest, unaryPred)
copy_n(beg, n, dest)

Copies from the input range to the sequence denoted by dest. copy copies all elements, copy_if copies those for which unaryPred succeeds, and copy_n copies the first n elements. The input sequence must have at least n elements.

move(beg, end, dest)

Calls std::move (§ 13.6.1, p. 533) on each element in the input sequence to move that element to the sequence beginning at iterator dest.

transform(beg, end, dest, unaryOp)
transform(beg, end, beg2, dest, binaryOp)

Calls the given operation and writes the result of that operation to dest. The first version applies a unary operation to each element in the input range. The second applies a binary operation to elements from the two input sequences.

replace_copy(beg, end, dest, old_val, new_val)
replace_copy_if(beg, end, dest, unaryPred, new_val)

Copies each element to dest, replacing the specified elements with new_val. The first version replaces those elements that are == old_val. The second version replaces those elements for which unaryPred succeeds.

merge(beg1, end1, beg2, end2, dest)
merge(beg1, end1, beg2, end2, dest, comp)

Both input sequences must be sorted. Writes a merged sequence to dest. The first version compares elements using the < operator; the second version uses the given comparison operation.

Write Algorithms with Forward Iterators

These algorithms require forward iterators because they write to elements in their input sequence. The iterators must give write access to the elements.

iter_swap(iter1, iter2)
swap_ranges(beg1, end1, beg2)

Swaps the element denoted by iter1 with the one denoted by iter2; or swaps all of the elements in the input range with those in the second sequence beginning at beg2. The ranges must not overlap. iter_swap returns void; swap_ranges returns beg2 incremented to denote the element just after the last one swapped.

replace(beg, end, old_val, new_val)
replace_if(beg, end, unaryPred, new_val)

Replaces each matching element with new_val. The first version uses == to compare elements with old_val; the second version replaces those elements for which unaryPred succeeds.

Write Algorithms with Bidirectional Iterators

These algorithms require the ability to go backward in the sequence, so they require bidirectional iterators.

copy_backward(beg, end, dest)
move_backward(beg, end, dest)

Copies or moves elements from the input range to the given destination. Unlike other algorithms, dest is the off-the-end iterator for the output sequence (i.e., the destination sequence will end immediately beforedest). The last element in the input range is copied or moved to the last element in the destination, then the second-to-last element is copied/moved, and so on. Elements in the destination have the same order as those in the input range. If the range is empty, the return value is dest; otherwise, the return denotes the element that was copied or moved from *beg.

inplace_merge(beg, mid, end)
inplace_merge(beg, mid, end, comp)

Merges two sorted subsequences from the same sequence into a single, ordered sequence. The subsequences from beg to mid and from mid to end are merged and written back into the original sequence. The first version uses < to compare elements; the second version uses a given comparison operation. Returns void.

A.2.5. Partitioning and Sorting Algorithms

The sorting and partitioning algorithms provide various strategies for ordering the elements of a sequence.

Each of the sorting and partitioning algorithms provides stable and unstable versions (§ 10.3.1, p. 387). A stable algorithm maintains the relative order of equal elements. The stable algorithms do more work and so may run more slowly and use more memory than the unstable counterparts.

Partitioning Algorithms

A partition divides elements in the input range into two groups. The first group consists of those elements that satisfy the specified predicate; the second, those that do not. For example, we can partition elements in a sequence based on whether the elements are odd, or on whether a word begins with a capital letter, and so forth. These algorithms require bidirectional iterators.

is_partitioned(beg, end, unaryPred)

Returns true if all the elements for which unaryPred succeeds precede those for which unaryPred is false. Alsoreturns true if the sequence is empty.

partition_copy(beg, end, dest1, dest2, unaryPred)

Copies elements for which unaryPred succeeds to dest1 and copies those for which unaryPred fails to dest2. Returns a pair (§ 11.2.3, p. 426) of iterators. The first member denotes the end of the elements copied to dest1, and the second denotes the end of the elements copied to dest2. The input sequence may not overlap either of the destination sequences.

partition_point(beg, end, unaryPred)

The input sequence must be partitioned by unaryPred. Returns an iterator one past the subrange for which unaryPred succeeds. If the returned iterator is not end, then unaryPred must be false for the returned iterator and for all elements that follow that point.

stable_partition(beg, end, unaryPred)
partition(beg, end, unaryPred)

Uses unaryPred to partition the input sequence. Elements for which unaryPred succeeds are put at the beginning of the sequence; those for which the predicate is false are at the end. Returns an iterator just past the last element for which unaryPred succeeds, or beg if there are no such elements.

Sorting Algorithms

These algorithms require random-access iterators. Each of the sorting algorithms provides two overloaded versions. One version uses the element’s operator < to compare elements; the other takes an extra parameter that specifies an ordering relation (§ 11.2.2, p. 425). partial_sort_copy returns an iterator into the destination; the other sorting algorithms return void.

The partial_sort and nth_element algorithms do only part of the job of sorting the sequence. They are often used to solve problems that might otherwise be handled by sorting the entire sequence. Because these algorithms do less work, they typically are faster than sorting the entire input range.

sort(beg, end)
stable_sort(beg, end)
sort(beg, end, comp)
stable_sort(beg, end, comp)

Sorts the entire range.

is_sorted(beg, end)
is_sorted(beg, end, comp)
is_sorted_until(beg, end)
is_sorted_until(beg, end, comp)

is_sorted returns a bool indicating whether the entire input sequence is sorted. is_sorted_until finds the longest initial sorted subsequence in the input and returns an iterator just after the last element of that subsequence.

partial_sort(beg, mid, end)
partial_sort(beg, mid, end, comp)

Sorts a number of elements equal to mid – beg. That is, if mid – beg is equal to 42, then this function puts the lowest-valued elements in sorted order in the first 42 positions in the sequence. After partial_sort completes, the elements in the range from beg up to but not including mid are sorted. No element in the sorted range is larger than any element in the range after mid. The order among the unsorted elements is unspecified.

partial_sort_copy(beg, end, destBeg, destEnd)
partial_sort_copy(beg, end, destBeg, destEnd, comp)

Sorts elements from the input range and puts as much of the sorted sequence as fits into the sequence denoted by the iterators destBeg and destEnd. If the destination range is the same size or has more elements than the input range, then the entire input range is sorted and stored starting at destBeg. If the destination size is smaller, then only as many sorted elements as will fit are copied.

Returns an iterator into the destination that refers just past the last element that was sorted. The returned iterator will be destEnd if that destination sequence is smaller than or equal in size to the input range.

nth_element(beg, nth, end)
nth_element(beg, nth, end, comp)

The argument nth must be an iterator positioned on an element in the input sequence. After nth_element, the element denoted by that iterator has the value that would be there if the entire sequence were sorted. The elements in the sequence are partitioned around nth: Those before nth are all smaller than or equal to the value denoted by nth, and the ones after it are greater than or equal to it.

A.2.6. General Reordering Operations

Several algorithms reorder the elements of the input sequence. The first two, remove and unique, reorder the sequence so that the elements in the first part of the sequence meet some criteria. They return an iterator marking the end of this subsequence. Others, such as reverse, rotate, and random_shuffle, rearrange the entire sequence.

The base versions of these algorithms operate “in place”; they rearrange the elements in the input sequence itself. Three of the reordering algorithms offer “copying” versions. These _copy versions perform the same reordering but write the reordered elements to a specified destination sequence rather than changing the input sequence. These algorithms require output iterator for the destination.

Reordering Algorithms Using Forward Iterators

These algorithms reorder the input sequence. They require that the iterators be at least forward iterators.

remove(beg, end, val)
remove_if(beg, end, unaryPred)
remove_copy(beg, end, dest, val)
remove_copy_if(beg, end, dest, unaryPred)

“Removes” elements from the sequence by overwriting them with elements that are to be kept. The removed elements are those that are == val or for which unaryPred succeeds. Returns an iterator just past the last element that was not removed.

unique(beg, end)
unique(beg, end, binaryPred)
unique_copy(beg, end, dest)
unique_copy_if(beg, end, dest, binaryPred)

Reorders the sequence so that adjacent duplicate elements are “removed” by overwriting them. Returns an iterator just past the last unique element. The first version uses == to determine whether two elements are the same; the second version uses the predicate to test adjacent elements.

rotate(beg, mid, end)
rotate_copy(beg, mid, end, dest)

Rotates the elements around the element denoted by mid. The element at mid becomes the first element; elements from mid + 1 up to but not including end come next, followed by the range from beg up to but not including mid. Returns an iterator denoting the element that was originally at beg.

Reordering Algorithms Using Bidirectional Iterators

Because these algorithms process the input sequence backward, they require bidirectional iterators.

reverse(beg, end)
reverse_copy(beg, end, dest)

Reverses the elements in the sequence. reverse returns void; reverse_copy returns an iterator just past the element copied to the destination.

Reordering Algorithms Using Random-Access Iterators

Because these algorithms rearrange the elements in a random order, they require random-access iterators.

random_shuffle(beg, end)
random_shuffle(beg, end, rand)
shuffle(beg, end, Uniform_rand)

Shuffles the elements in the input sequence. The second version takes a callable that must take a positive integer value and produce a uniformly distributed random integer in the exclusive range from 0 to the given value. The third argument to shuffle must meet the requirements of a uniform random number generator (§ 17.4, p. 745). All three versions return void.

A.2.7. Permutation Algorithms

The permutation algorithms generate lexicographical permutations of a sequence. These algorithms reorder a permutation to produce the (lexicographically) next or previous permutation of the given sequence. They return a bool that indicates whether there was a next or previous permutation.

To understand what is meant by next or previous permutaion, consider the following sequence of three characters: abc. There are six possible permutations on this sequence: abc, acb, bac, bca, cab, and cba. These permutations are listed in lexicographical order based on the less-than operator. That is, abc is the first permutation because its first element is less than or equal to the first element in every other permutation, and its second element is smaller than any permutation sharing the same first element. Similarly, acb is the next permutation because it begins with a, which is smaller than the first element in any remaining permutation. Permutations that begin with b come before those that begin with c.

For any given permutation, we can say which permutation comes before it and which after it, assuming a particular ordering between individual elements. Given the permutation bca, we can say that its previous permutation is bac and that its next permutation is cab. There is no previous permutation of the sequence abc, nor is there a next permutation of cba.

These algorithms assume that the elements in the sequence are unique. That is, the algorithms assume that no two elements in the sequence have the same value.

To produce the permutation, the sequence must be processed both forward and backward, thus requiring bidirectional iterators.

is_permutation(beg1, end1, beg2)
is_permutation(beg1, end1, beg2, binaryPred)

Returns true if there is a permutation of the second sequence with the same number of elements as are in the first sequence and for which the elements in the permutation and in the input sequence are equal. The first version compares elements using ==; the second uses the given binaryPred.

next_permutation(beg, end)
next_permutation(beg, end, comp)

If the sequence is already in its last permutation, then next_permutation reorders the sequence to be the lowest permutation and returns false. Otherwise, it transforms the input sequence into the lexicographically next ordered sequence, and returns true. The first version uses the element’s < operator to compare elements; the second version uses the given comparison operation.

prev_permutation(beg, end)
prev_permutation(beg, end, comp)

Like next_permutation, but transforms the sequence to form the previous permutation. If this is the smallest permutation, then it reorders the sequence to be the largest permutation and returns false.

A.2.8. Set Algorithms for Sorted Sequences

The set algorithms implement general set operations on a sequence that is in sorted order. These algorithms are distinct from the library set container and should not be confused with operations on sets. Instead, these algorithms provide setlike behavior on an ordinary sequential container (vector, list, etc.) or other sequence, such as an input stream.

These algorithms process elements sequentially, requiring input iterators. With the exception of includes, they also take an output iterator denoting a destination. These algorithms return their dest iterator incremented to denote the element just after the last one that was written to dest.

Each algorithm is overloaded. The first version uses the < operator for the element type. The second uses a given comparison operation.

includes(beg, end, beg2, end2)
includes(beg, end, beg2, end2, comp)

Returns true if every element in the second sequence is contained in the input sequence. Returns false otherwise.

set_union(beg, end, beg2, end2, dest)
set_union(beg, end, beg2, end2, dest, comp)

Creates a sorted sequence of the elements that are in either sequence. Elements that are in both sequences occur in the output sequence only once. Stores the sequence in dest.

set_intersection(beg, end, beg2, end2, dest)
set_intersection(beg, end, beg2, end2, dest, comp)

Creates a sorted sequence of elements present in both sequences. Stores the sequence in dest.

set_difference(beg, end, beg2, end2, dest)
set_difference(beg, end, beg2, end2, dest, comp)

Creates a sorted sequence of elements present in the first sequence but not in the second.

set_symmetric_difference(beg, end, beg2, end2, dest)
set_symmetric_difference(beg, end, beg2, end2, dest, comp)

Creates a sorted sequence of elements present in either sequence but not in both.

A.2.9. Minimum and Maximum Values

These algorithms use either the < operator for the element type or the given comparison operation. The algorithms in the first group operate on values rather than sequences. The algorithms in the second set take a sequence that is denoted by input iterators.

min(val1, val2)
min(val1, val2, comp)
min(init_list)
min(init_list, comp)

max(val1, val2)
max(val1, val2, comp)
max(init_list)
max(init_list, comp)

Returns the minimum/maximum of val1 and val2 or the minimum/maximum value in the initializer_list. The arguments must have exactly the same type as each other. Arguments and the return type are both references to const, meaning that objects are not copied.

minmax(val1, val2)
minmax(val1, val2, comp)
minmax(init_list)
minmax(init_list, comp)

Returns a pair (§ 11.2.3, p. 426) where the first member is the smaller of the supplied values and the second is the larger. The initializer_list version returns a pair in which the first member is the smallest value in the list and the second member is the largest.

min_element(beg, end)
min_element(beg, end, comp)
max_element(beg, end)
max_element(beg, end, comp)
minmax_element(beg, end)
minmax_element(beg, end, comp)

min_element and max_element return iterators referring to the smallest and largest element in the input sequence, respectively. minmax_element returns a pair whose first member is the smallest element and whose second member is the largest.

Lexicographical Comparison

This algorithm compares two sequences based on the first unequal pair of elements. Uses either the < operator for the element type or the given comparison operation. Both sequences are denoted by input iterators.

lexicographical_compare(beg1, end1, beg2, end2)
lexicographical_compare(beg1, end1, beg2, end2, comp)

Returns true if the first sequence is lexicographically less than the second. Otherwise, returns false. If one sequence is shorter than the other and all its elements match the corresponding elements in the longer sequence, then the shorter sequence is lexicographically smaller. If the sequences are the same size and the corresponding elements match, then neither is lexicographically less than the other.

A.2.10. Numeric Algorithms

The numeric algorithms are defined in the numeric header. These algorithms require input iterators; if the algorithm writes output, it uses an output iterator for the destination.

accumulate(beg, end, init)
accumulate(beg, end, init, binaryOp)

Returns the sum of all the values in the input range. The summation starts with the initial value specified by init. The return type is the same type as the type of init. The first version applies the + operator for the element type; the second version applies the specified binary operation.

inner_product(beg1, end1, beg2, init)
inner_product(beg1, end1, beg2, init, binOp1, binOp2)

Returns the sum of the elements generated as the product of two sequences. The two sequences are processed in tandem, and the elements from each sequence are multiplied. The product of that multiplication is summed. The initial value of the sum is specified by init. The type of init determines the return type.

The first version uses the element’s multiplication (*) and addition (+) operators. The second version applies the specified binary operations, using the first operation in place of addition and the second in place of multiplication.

partial_sum(beg, end, dest)
partial_sum(beg, end, dest, binaryOp)

Writes a new sequence to dest in which the value of each new element represents the sum of all the previous elements up to and including its position within the input range. The first version uses the + operator for the element type; the second version applies the specified binary operation. Returns the dest iterator incremented to refer just past the last element written.

adjacent_difference(beg, end, dest)
adjacent_difference(beg, end, dest, binaryOp)

Writes a new sequence to dest in which the value of each new element other than the first represents the difference between the current and previous elements. The first version uses the element type’s - operation; the second version applies the specified binary operation.

iota(beg, end, val)

Assigns val to the first element and increments val. Assigns the incremented value to the next element, and again increments val, and assigns the incremented value to the next element in the sequence. Continues incrementing val and assigning its new value to successive elements in the input sequence.