Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

13.7 Sequence-Generating Algorithms

All of the algorithms described in this section are used to generate a new sequence from an existing sequence by performing some type of transformation. In most cases, the output sequence is described by an output iterator. This means these algorithms can be used to overwrite an existing structure, such as a vector. Alternatively, by using an insert iterator (see Section 2.4), the algorithms can insert the new elements into a variable length structure, such as a set or list. Finally, in some cases that we will discuss, the output iterator can be the same as one of the sequences specified by an input iterator, thereby providing the ability to make an in-place transformation.

The functions std::partial_sum() and std::adjacent_difference() are declared in the header file <numeric>, while the other functions are described in the header file <algorithm>.

NOTE -- The example functions described in the following sections can be found in the file alg6.cpp.

13.7.1 Transform One or Two Sequences

The algorithm std::transform() is used either to make a general transformation of a single sequence, or to produce a new sequence by applying a binary function in a pair-wise fashion to corresponding elements from two different sequences. The general definition of the argument and result types are as follows:

The first form applies a unary function to each element of a sequence. In the example program given below, this is used to produce a vector of int values that hold the arithmetic negation of the values in a linked list. The input and output iterators can be the same, in which case the transformation is applied in-place, as shown in the example program.

The second form takes two sequences and applies the binary function in a pair-wise fashion to corresponding elements. The transaction assumes, but does not verify, that the second sequence has at least as many elements as the first sequence. Once more, the result can either be a third sequence, or one of the two input sequences.

13.7.2 Partial Sums

A partial sum of a sequence is a new sequence in which every element is formed by adding the values of all prior elements. For example, the partial sum of the vector 1 3 2 4 5 is the new vector 1 4 6 10 15. The element 4 is formed from the sum 1 + 3, the element 6 from the sum 1 + 3 + 2, and so on. Although the term sum is used in describing the operation, the binary function can be any arbitrary function. The example program illustrates this by computing partial products.

The arguments to the partial sum function are described as follows:

By using the same value for both the input iterator and the result, the partial sum can be changed into an in-place transformation.

13.7.3 Adjacent Differences

An adjacent difference of a sequence is a new sequence formed by replacing every element with the difference between the element and the immediately preceding element. The first value in the new sequence remains unchanged. For example, a sequence such as (1, 3, 2, 4, 5) is transformed into (1, 3-1, 2-3, 4-2, 5-4), and in this manner becomes the sequence (1, 2, -1, 2, 1).

As with the algorithm std::partial_sum(), the term difference is not necessarily accurate, as an arbitrary binary function can be employed. The adjacent sums for this sequence are (1, 4, 5, 6, 9), for example. The adjacent difference algorithm has the following declaration:

By using the same iterator as both input and output iterator, the adjacent difference operation can be performed in place.

Previous fileTop of DocumentContentsIndex pageNext file