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.
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:
namespace std {
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 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.
int square(int n) { return n * n; }
void transform_example()
// illustrates the use of the transform algorithm
// see alg6.cpp for complete source code
{
// generate a list of values 1 to 6
std::list<int> aList;
std::generate_n(std::inserter(aList, aList.begin()),
6, iotaGen(1));
// transform elements by squaring, copy into vector
std::vector<int> aVec(6);
std::transform(aList.begin(), aList.end(), aVec.begin(),
square);
// transform vector again, in place, yielding 4th powers
std::transform(aVec.begin(), aVec.end(), aVec.begin(), square);
// transform in parallel, yielding cubes
std::vector<int> cubes(6);
std::transform(aVec.begin(), aVec.end(), aList.begin(),
cubes.begin(), std::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 be any arbitrary function. The example program illustrates this by computing partial products.
The arguments to the partial sum function are described as follows:
namespace std {
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()
// illustrates the use of the partial sum algorithm
//see alg6.cpp for complete source code
{
// generate values 1 to 5
std::vector<int> aVec(5);
std::generate(aVec.begin(), aVec.end(), iotaGen(1));
// output partial sums
std::partial_sum(aVec.begin(), aVec.end(),
std::ostream_iterator<int> (std::cout, " "));
std::cout << std::endl;
// output partial products
std::partial_sum(aVec.begin(), aVec.end(),
std::ostream_iterator<int> (std::cout, " "),
std::multiplies<int>() );
std::cout << std::endl;
}
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:
namespace std{
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()
// illustrates the use of the adjacent difference algorithm
//see alg6.cpp for complete source code
{
// generate values 1 to 5
std::vector<int> aVec(5);
std::generate(aVec.begin(), aVec.end(), iotaGen(1));
// output adjacent differences
std::adjacent_difference(aVec.begin(), aVec.end(),
std::ostream_iterator<int,char>(std::cout," ")),
std::cout << std::endl;
// output adjacent sums
std::adjacent_difference(aVec.begin(), aVec.end(),
std::ostream_iterator<int,char>(std::cout," "),
std::plus<int>() );
std::cout << std::endl;
}