Section A.2. A Brief Tour of the Algorithms

A.2. A Brief Tour of the Algorithms

Chapter 11 introduced the generic algorithms and outlined their underlying architecture. The library defines more than 100 algorithms. Learning to use them requires understanding their structure rather than memorizing the details of each algorithm. In this section we describe each of the algorithms. In it, we organize the algorithms by the type of action the algorithm performs.

A.2.1. Algorithms to Find an Object

The find and count algorithms search the input range for a specific value. find returns an iterator to an element; count returns the number of matching elements.

Simple Find Algorithms

These algorithms require input iterators. The find and count algorithms look for specific elements. The find algorithms return an iterator referring to the first matching element. The count algorithms return a count of how many times the element occurs in the input sequence.

 find(beg, end, val) count(beg, end, val) 

Looks for element(s) in input range equal to val. Uses the equality (==) operator of the underlying type. find returns an iterator to the first matching element or end if no such element exists. count returns a count of how many times val occurs.

 find_if(beg, end, unaryPred) count_if(beg, end, unaryPred) 

Looks for element(s) in input range for which unaryPred is true. The predicate must take a single parameter of the value_type of the input range and return a type that can be used as a condition.

find returns an iterator to first element for which unaryPred is true, or end if no such element exists. count applies unaryPred to each element and returns the number of elements for which unaryPred was true.

Algorithms to Find One of Many Values

These algorithms require two pairs of forward iterators. They search for the first (or last) element in the first range that is equal to any element in the second range. The types of beg1 and end1 must match exactly, as must the types of beg2 and end2.

There is no requirement that the types of beg1 and beg2 match exactly. However, it must be possible to compare the element types of the two sequences. So, for example, if the first sequence is a list<string>, then the second could be a vector<char*>.

Each algorithm is overloaded. By default, elements are tested using the == operator for the element type. Alternatively, we can specify a predicate that takes two parameters and returns a bool indicating whether the test between these two elements succeeds or fails.

 find_first_of(beg1, end1, beg2, end2) 

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

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

Uses binaryPred to compare elements from each sequence. Returns an iterator to the first element in the first range for which the binaryPred is true when applied to that element and an element from the second sequence. Returns end1 if no such element exits.

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

Operates like find_first_of, except that it searches for the last occurrence of any element from the second sequence.

As an example, if the first sequence is 0,1,1,2,2,4,0,1 and the second sequence is 1,3,5,7,9, then find_end would return an iterator denoting the last element in the input range, and find_first_of would return an iterator to the second elementin this example, it returns the first 1 in the input sequence.

Algorithms to Find a Subsequence

These algorithms require forward iterators. They look for a subsequence rather than a single element. If the subsequence is found, an iterator is returned to the first element in the subsequence. If no subsequence is found, the end iterator from the input range is returned.

Each function is overloaded. By default, the equality (==) operator is used to compare elements; the second version allows the programmer to supply a predicate to test instead.

 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. In the first case, duplicates are found by using ==. In the second, duplicates are those for which the binaryPred is true.

 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. The types of beg1 and beg2 may differ but must be compatible: It must be possible to compare elements in the two sequences.

 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. The first version looks for count occurrences of the given value; the second version count occurrences for which the binaryPred is true.

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 a second range. There must be at least as many elements in the second sequence as there are in the first. If there are more elements in the second, they are ignored. If there are fewer, it is an error and results in undefined run-time behavior.

As usual, the types of the iterators denoting the input range must match exactly. The type of beg2 must be compatible with the type of beg1. That is, it must be possible to compare elements in both sequences.

The equal and mismatch functions are overloaded: One version uses the element equality operator (==) to test pairs of elements; the other uses a predicate.

 for_each(beg, end, f) 

Applies the function (or function object (Section 14.8, p. 530)) f to each element in its input range. The return value, if any, from f is ignored. The iterators are input iterators, so the elements may not be written by f. Typically, for_each is used with a function that has side effects. For example, f might print the values in the range.

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

Compares the elements in two sequences. Returns a pair of iterators denoting the first elements 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.

For example, given the sequences meet and meat, a call to mismatch would return a pair containing iterators referring to the second e in the first sequence and to the element a in the second sequence. If, instead, the second sequence were meeting, and we called equal, then the pair returned would be end1 and an iterator denoting the element i in the second range.

A.2.3. Binary-Search Algorithms

Although these algorithms may be used with forward iterators, they offer specialized versions that are much faster when used with random-access iterators.

These algorithms perform a binary search, which means that the input sequence must be sorted. These algorithms behave similarly to the associative container members of the same name (Section 10.5.2, p. 377). The equal_range, lower_bound, and upper_bound algorithms return an iterator that refers to the positions in the container at which the given element could be inserted while still preserving the container's ordering. If the element is larger than any other in the container, 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 specified comparison.

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

Returns an iterator to the first position in which val can be inserted while preserving the ordering.

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

Returns an iterator to the last position in which val can be inserted while preserving the ordering.

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

Returns an iterator pair indicating the subrange in which val could be inserted while preserving the ordering.

 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 < y and y <x both yield false.

A.2.4. Algorithms that Write Container Elements

Many algorithms write container elements. These algorithms can be distinguished both by the kinds of iterators on which they operate and by whether they write elements in the input range or write to a specified destination.

The simplest algorithms read elements in sequence, requiring only input iterators. Those that write back to the input sequence require forward iterators. Some read the sequence backward, thus requiring bidirectional iterators. Algorithms that write to a separate destination, as usual, assume the destination is large enough to hold the output.

Algorithms that Write but do Not Read Elements

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

 fill_n(dest, cnt, val) generate_n(dest, cnt, Gen) 

Write cnt values to dest. The fill_n function writes cnt copies of the value val; generate_n evaluates the generator Gen() cnt times. A generator is a function (or function object (Section 14.8, p. 530)) that is expected to produce a different return value each time it is called.

Algorithms that Write Elements Using Input Iterators

Each of these operations reads an input sequence and writes to an output sequence denoted by dest. They require dest to be an output iterator, and the iterators denoting the input range must be input iterators. The caller is responsible for ensuring that dest can hold as many elements as necessary given the input sequence. These algorithms return dest incremented to denote one past the last element written.

 copy(beg, end, dest) 

Copies the input range to the sequence beginning at iterator dest.

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

Applies the specified operation to each element in the input range, writing the result to dest. The first version applies a unary operation to each element in the input range. The second applies a binary operation to pairs of elements. It takes the first argument to the binary operation from the sequence denoted by beg and end and takes the second argument from the sequence beginning at beg2. The programmer must ensure that the sequence beginning at beg2 has at least as many elements as are in the first sequence.

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

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

 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.

Algorithms that Write Elements Using Forward Iterators

These algorithms require forward iterators because they write elements in their input sequence.

 swap(elem1, elem2) iter_swap(iter1, iter2) 

Parameters to these functions are references, so the arguments must be writable. Swaps the specified element or elements denoted by the given iterators.

 swap_ranges(beg1, end1, beg2) 

Swaps the elements in the input range with those in the second sequence beginning at beg2. The ranges must not overlap. The programmer must ensure that the sequence starting at beg2 is at least as large as the input sequence. Returns beg2 incremented to denote the element just after the last one swapped.

 fill(beg, end, val) generate(beg, end, Gen) 

Assigns a new value to each element in the input sequence. fill assigns the value val; generate executes Gen() to create new values.

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

Replace each matching element by new_val. The first version uses == to compare elements with old_val; the second version executes unaryPred on each element, replacing those for which unaryPred is true.

Algorithms that Write Elements Using Bidirectional Iterators

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

 copy_backward(beg, end, dest) 

Copies elements in reverse order to the output iterator dest. Returns dest incremented to denote one past the last element copied.

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

Merges two adjacent subsequences from the same sequence into a single, ordered sequence: The subsequences from beg to mid and from mid to end are merged into beg to end. First version uses < to compare elements; second version uses a specified comparison. Returns void.

A.2.5. Partitioning and Sorting Algorithms

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

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 container based on whether the elements are odd, or on whether a word begins with a capital letter, and so forth.

Each of the sorting and partitioning algorithms provides stable and unstable versions. A stable algorithm maintains the relative order of equal elements. For example, given the sequence

       { "pshew", "Honey", "tigger", "Pooh" } 

a stable partition based on whether a word begins with a capital letter generates the sequence in which the relative order of the two word categories is maintained:

      { "Honey", "Pooh", "pshew", "tigger" } 

The stable algorithms do more work and so may run more slowly and use more memory than the unstable counterparts.

Partitioning Algorithms

These algorithms require bidirectional iterators.

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

Uses unaryPred to partition the input sequence. Elements for which unaryPred is true 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 is true.

Sorting Algorithms

These algorithms require random-access iterators. Each of the sorting algorithms provides two overloaded versions. One version uses element operator < to compare elements; the other takes an extra parameter that specifies the comparison. These algorithms require random-access iterators. With one exception, these algorithms return void; partial_sort_copy returns an itertor into the destination.

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 operations 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.

 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.

As an example, we might have a collection of race scores and want to know what the first-, second- and third-place scores are but don't care about the order of the other times. We might sort such a sequence as follows:

      partial_sort(scores.begin(),                  scores.begin() + 3, scores.end()); 

 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 after the last element that was sorted. The returned iterator will be destEnd if that destination sequence is smaller 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 container are also 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. We might use nth_element to find the value closest to the median:

      nth_element(scores.begin(), scores.begin() +               scores.size()/2, scores.end()); 

A.2.6. General Reordering Operations

Several algorithms reorder the elements in a specified way. The first two, remove and unique, reorder the container 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.

These algorithms operate "in place;" they rearrange the elements in the input sequence itself. Three of the reordering algorithms offer "copying" versions. These algorithms, remove_copy, rotate_copy, and unique_copy, write the reordered sequence to a destination rather than rearranging elements directly.

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) 

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

For example, if the input sequence is hello world and val is o, then a call to remove will overwrite the two elements that are the letter 'o' by shifting the sequence to the left twice. The new sequence will be hell wrldld. The returned iterator will denote the element after the first d.

 unique(beg, end) unique(beg, end, binaryPred) 

"Removes" all but the first of each consecutive group of matching elements. Returns an iterator just past the last unique element. First version uses == to determine whether two elements are the same; second version uses the predicate to test adjacent elements.

For example, if the input sequence is boohiss, then after the call to unique, the first sequence will contain bohisss. The iterator returned will point to the element after the first s. The value of the remaining two elements in the sequence is unspecified.

 rotate(beg, mid, end) 

Rotates the elements around the element denoted by mid. The element at mid becomes the first element; those from mid + 1 through end come next, followed by the range from beg to mid. Returns void.

For example, given the input sequence hissboo, if mid denotes the character b, then rotate would reorder the sequence as boohiss.

Reordering Algorithms Using Bidirectional Iterators

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

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

Reverses the elements in the sequence. reverse operates in place; it writes the rearranged elements back into the input sequence. reverse_copy copies the elements in reverse order to the output iterator dest. As usual, the programmer must ensure that dest can be used safely. reverse returns void; reverse_copy returns an iterator just past the last element copied into the destination.

Reordering Algorithms Writing to Output Iterators

These algorithms require forward iterators for the input sequence and an output iterator for the destination.

Each of the preceding general reordering algorithms has an _copy version. These _copy versions perform the same reordering but write the reordered elements to a specified destination sequence rather than changing the input sequence. Except for rotate_copy, which requires forward iterators, the input range is specified by input iterators. The dest iterator must be an output iterator and, as usual, the programmer must guarantee that the destination can be written safely. The algorithms return the dest iterator incremented to denote one past the last element copied.

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

Copies elements except those matching val or for which unaryPred return true into dest.

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

Copies unique elements to dest.

 rotate_copy(beg, mid, end, dest) 

Like rotate except that it leaves its input sequence unchanged and writes the rotated sequence to dest. Returns void.

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) 

Shuffles the elements in the input sequence. The second version takes a random-number generator. That function must take and return a value of the iterator's difference_type. Both versions return void.

A.2.7. Permutation Algorithms

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. Those 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. 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.

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

The algorithms each have two versions: One uses the element type < operator, and the other takes an extra argument that specifies a comparison to use to compare the elements. 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.

Permutation Algorithms Require Bidirectional Iterators

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

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

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

 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.

With the exception of includes, they also take an output iterator. As usual, the programmer must ensure that the destination is large enough to hold the generated sequence. These algorithms return their dest iterator incremented to denote the element just after the last one that was written to dest.

Each algorithm provides two forms: The first uses the < operator for the element type to compare elements in the two input sequences. The second takes a comparison, which is used to compare the elements.

Set Algorithms Require Input Iterators

These algorithms process elements sequentially, requiring input iterators.

 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 container 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 container but not in both.

A.2.9. Minimum and Maximum Values

The first group of these algorithms are unique in the library in that they operate on values rather than sequences. The second set takes a sequence that is denoted by input iterators.

 min(val1, val2) min(val1, val2, comp) max(val1, val2) max(val1, val2, comp) 

Returns the minimum/maximum of val1 and val2. The arguments must have exactly the same type as each other. Uses either < operator for the element type or the specified comparison. Arguments and the return type are both const references, meaning that objects are not copied.

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

Returns an iterator referring to the smallest/largest element in the input sequence. Uses either < operator for the element type or the specified comparison.

Lexicographical Comparison

Lexicographical comparison examines corresponding elements in two sequences and determines the comparison based on the first unequal pair of elements. Because the algorithms process elements sequentially, they require input iterators. 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.

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

Does an element by element comparison of the elements in the two sequences. Returns true if the first sequence is lexicographically less than the second sequence. Otherwise, returns false. Uses either < operator for the element type or the specified comparison.

A.2.10. Numeric Algorithms

Numeric algorithms require input iterators; if the algorithm writes output, it uses an output iterator for the destination

These functions perform simple arithmetic manipulations of their input sequence. To use the numeric algorithms, the numeric header must be included.

 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.

Given the sequence 1,1,2,3,5,8 and an initial value of 0, the result is 20. The first version applies the + operator for the element type; 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 examined in step, 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 second sequence beginning at beg2 is assumed to have at least as many elements as are in the first sequence; any elements in the second sequence beyond the size of the first sequence are ignored. The type of init determines the return type.

The first version uses the element's multiplication (*) and addition (+) operators: Given the two sequences 2,3,5,8 and 1,2,3,4,5,6,7, the result is the sum of the initial value plus the following product pairs:

      initial_value + (2 * 1) + (3 * 2) + (5 * 3) + (8 * 4) 

If we provide an initial value of 0, then the result is 55.

The second version applies the specified binary operations, using the first operation in place of addition and the second in place of multiplication. As an example, we might use inner_product to produce a list of parenthesized namevalue pairs of elements, where the name is taken from the first input sequence and the corresponding value is in the second:

      // combine elements into a parenthesized, comma-separated pair      string combine(string x, string y)      {          return "(" + x + ", " + y + ")";      }      // add two strings, each separated by a comma      string concatenate(string x, string y)      {          if (x.empty())              return y;          return x + ", " + y;      }          cout << inner_product(names.begin(), names.end(),                                      values.begin(), string(),                                      concatenate, combine); 

If the first sequence contains if, string, and sort, and the second contains keyword, library type, and algorithm, then the output would be

    (if, keyword), (string, library type), (sort, algorithm)    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. The programmer must ensure that dest is at least as large as the input sequence. Returns the dest iterator incremented to refer just after the last element written.

Given the input sequence 0,1,1,2,3,5,8, the destination sequence will be 0,1,2,4,7,12,20. The fourth element, for example, is the partial sum of the three previous values (0,1,1) plus its own( 2), yielding a value of 4.

 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 of the current and previous element. The first version uses the element type's - operation; the second version applies the specified binary operation. The programmer must ensure that dest is at least as large as the input sequence.

Given the sequence 0,1,1,2,3,5,8, the first element of the new sequence is a copy of the first element of the original sequence: 0. The second element is the difference between the first two elements: 1. The third element is the difference between the second and third element, which is 0, and so on. The new sequence is 0,1,0,1,1,2,3.