Obtaining the Source
The algorithms described in this section are all 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 Chapter 2), the algorithms can insert the new elements into a variable length structure, such as a set or list. Finally, in some cases which we will note, 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 partial_sum() and adjacent_difference() are declared in the header file numeric, while the other functions are described in the header file algorithm.
The algorithm 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:
OutputIterator transform (InputIterator first, InputIterator last,
OutputIterator result, UnaryFunction);
OutputIterator transform
(InputIterator first1, InputIterator last1,
InputIterator first2, OutputIterator result, BinaryFunction);
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 integer 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 either of the two input sequences.
int square(int n) { return n * n; }
void transform_example ()
// illustrate the use of the transform algorithm
{
// generate a list of value 1 to 6
list<int> aList;
generate_n (inserter(aList, aList.begin()), 6, iotaGen(1));
// transform elements by squaring, copy into vector
vector<int> aVec(6);
transform (aList.begin(), aList.end(), aVec.begin(), square);
// transform vector again, in place, yielding 4th powers
transform (aVec.begin(), aVec.end(), aVec.begin(), square);
// transform in parallel, yielding cubes
vector<int> cubes(6);
transform (aVec.begin(), aVec.end(), aList.begin(),
cubes.begin(), divides<int>());
}
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, in fact, be any arbitrary function. The example program illustrates this by computing partial products. The arguments to the partial sum function are described as follows:
OutputIterator partial_sum
(InputIterator first, InputIterator last,
OutputIterator result [, BinaryFunction] );
By using the same value for both the input iterator and the result the partial sum can be changed into an in-place transformation.
void partial_sum_example ()
// illustrate the use of the partial sum algorithm
{
// generate values 1 to 5
vector<int> aVec(5);
generate (aVec.begin(), aVec.end(), iotaGen(1));
// output partial sums
partial_sum (aVec.begin(), aVec.end(),
ostream_iterator<int> (cout, " ")), cout << endl;
// output partial products
partial_sum (aVec.begin(), aVec.end(),
ostream_iterator<int> (cout, " "),
times<int>() );
}
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 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:
OutputIterator adjacent_difference (InputIterator first,
InputIterator last, OutputIterator result [, BinaryFunction ]);
By using the same iterator as both input and output iterator, the adjacent difference operation can be performed in place.
void adjacent_difference_example ()
// illustrate the use of the adjacent difference algorithm
{
// generate values 1 to 5
vector<int> aVec(5);
generate (aVec.begin(), aVec.end(), iotaGen(1));
// output adjacent differences
adjacent_difference (aVec.begin(), aVec.end(),
ostream_iterator<int> (cout, " ")), cout << endl;
// output adjacent sums
adjacent_difference (aVec.begin(), aVec.end(),
ostream_iterator<int> (cout, " "),
plus<int>() );
}