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

13.4 In-Place Transformations

The next category of algorithms that we examine is used to modify and transform sequences without moving them from their original storage locations.

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

A few of these routines, such as std::replace(), include a copy version as well as the original in-place transformation algorithms. For the others, should it be necessary to preserve the original, a copy of the sequence should be created before the transformations are applied. For example, the following code illustrates how one can place the reversal of one vector into another newly allocated vector:

Many of the algorithms described as sequence generating operations, such as std::transform() or std::partial_sum(), can also modify a value in place by simply using the same iterator as both input and output specification (see Section 13.7.1 and Section 13.7.2).

13.4.1 Reverse Elements in a Sequence

The algorithm std::reverse() reverses the elements in a sequence so that the last element becomes the new first, and the first element the new last. The arguments are assumed to be bidirectional iterators, and no value is returned.

The example program illustrates two uses of this algorithm. In example 1, an array of character values is reversed. The algorithm std::reverse() can also be used with list values, as shown in example 2. In this example, a list is initialized with the values 2 to 11 in increasing order. (This is accomplished using the iotaGen function object introduced in Section The list is then reversed, which results in the list holding the values 11 to 2 in decreasing order. Note, however, that the list data structure also provides its own std::reverse() member function.

13.4.2 Replace Certain Elements With Fixed Value

The algorithms std::replace() and std::replace_if() are used to replace occurrences of certain elements with a new value. For both algorithms, the new value is the same, no matter how many replacements are performed. Using the algorithm std::replace(), all occurrences of a particular test value are replaced with the new value. In the case of std::replace_if(), all elements that satisfy a predicate function are replaced by a new value. The iterator arguments must be forward iterators.

The algorithms std::replace_copy() and std::replace_copy_if() are similar to std::replace() and std::replace_if(), however, they leave the original sequence intact and place the revised values into a new sequence, which may be a different type.

In the example program, a vector is initially assigned the values 0 1 2 3 4 5 4 3 2 1 0. A call on std::replace() replaces the value 3 with the value 7, resulting in the vector 0 1 2 7 4 5 4 7 2 1 0. The invocation of std::replace_if() replaces all even numbers with the value 9, resulting in the vector 9 1 9 7 9 5 9 7 9 1 9.

The example program also illustrates the use of the std::replace_copy() algorithms. First, an array containing the values 2 1 4 3 2 5 is created. This is modified by replacing the 2 values with 7, resulting in the array 7 1 4 3 7 5. Next, all values larger than 3 are replaced with the value 8, resulting in the array values 8 1 8 3 8 8. In the latter case the std::bind2nd() adaptor is used to modify the binary greater-than function by binding the second argument to the constant value 3, thereby creating the unary function x > 3.

13.4.3 Rotate Elements Around a Midpoint

A rotation of a sequence divides the sequence into two sections and swaps the order of the sections, while maintaining the order of elements within each section. Suppose, for example, that we have the values 1 to 10 in sequence:

1 2 3 4 5 6 7 8 9 10

If we were to rotate around the element 7, the values 7 to 10 would be moved to the beginning, while the elements 1 to 6 would be moved to the end. This would result in the following sequence:

7 8 9 10 1 2 3 4 5 6

When you invoke the algorithm std::rotate(), the starting point, midpoint, and past-the-end location are all denoted by forward iterators:

The prefix portion, the set of elements following the start and not including the midpoint, is swapped with the suffix, the set of elements between the midpoint and the past-the-end location. Note, as in the previous example, that these two segments need not be the same length.

The example program first creates a list of the integers in order from 1 to 10. Next, the std::find() algorithm (Section 13.3.1) is used to find the location of the element 7. This is used as the midpoint for the rotation.

A second form of std::rotate() copies the elements into a new sequence, rather than rotating the values in place. This is also shown in the example program, which once again rotates around the middle position that now contains a 3. The resulting list is 3 4 5 6 7 8 9 10 1 2. The values held in iList remain unchanged.

13.4.4 Partition a Sequence into Two Groups

A partition is formed by moving all the elements that satisfy a predicate to one end of a sequence, and all the elements that fail to satisfy the predicate to the other end. Partitioning elements is a fundamental step in certain sorting algorithms, such as quicksort.

There are two forms of partition supported in the C++ Standard Library. The first, provided by the algorithm std::partition(), guarantees only that the elements are divided into two groups. The result value is an iterator that describes the final midpoint between the two groups; it is one past the end of the first group.

In the example program, the initial vector contains the values 1 to 10 in order. The partition moves the even elements to the front, and the odd elements to the end. This results in the vector holding the values 10 2 8 4 6 5 7 3 9 1, and the midpoint iterator pointing to the element 5.

The relative order of the elements within a partition in the resulting vector may not be the same as the values in the original vector. For example, the value 4 preceded the element 8 in the original, but may follow the element 8 in the result. A second version of partition, named std::stable_partition(), guarantees the ordering of the resulting values. For the input shown in the example, the stable partition would result in the sequence 2 4 6 8 10 1 3 5 7 9. The std::stable_partition() algorithm is slightly slower and uses more memory than the std::partition() algorithm, so when the order of elements is not important you should use std::partition().

While there is a unique std::stable_ partition() for any sequence, the std::partition() algorithm can return any number of values. For example, the following are all legal partitions of the sample problem:

13.4.5 Generate Permutations in Sequence

A permutation is a rearrangement of values. If values such as integers, characters, or words can be compared against each other, then it is possible to systematically construct all permutations of a sequence. For example, there are two permutations of two values, six permutations of three values, and 24 permutations of four values.

The permutation generating algorithms have the following definition:

The second example in the sample program illustrates the same idea, using pointers to character arrays instead of integers. In this case, a different comparison function must be supplied, since the default operator would simply compare pointer addresses.

Example 3 in the sample program illustrates the use of the reverse permutation algorithm, which generates values in reverse sequence. This example also begins in the middle of a sequence, rather than at the beginning. The remaining permutations of the word bela are: beal, bale, bael, aleb, albe, aelb, aebl, able, and abel.

Permutations can also be ordered so that the smallest permutation lists values smallest to largest, and the largest sequence lists values largest to smallest. For example, consider the permutations of the integers 1 2 3. Taken in order, the six permutations of these values are:

Notice that in the first permutation the values are all ascending, while in the last permutation they are all descending.

13.4.6 Merge Two Adjacent Sequences into One

A merge takes two ordered sequences and combines them into a single ordered sequence, interleaving elements from each collection as necessary to generate the new list. The inplace_merge() algorithm assumes a sequence is divided into two adjacent sections, each of which is ordered. The merge combines the two sections into one, moving elements as necessary. The alternative merge() algorithm (Section and Section 14.5) can be used to merge two separate sequences into one.

The arguments to inplace_merge() must be bidirectional iterators.

The example program illustrates the use of the inplace_merge() algorithm with a vector and with a list. The sequence 0 2 4 6 8 1 3 5 7 9 is placed into a vector. A find() call (Section 13.3.1) is used to locate the beginning of the odd number sequence. The two calls on inplace_merge() then combine the two sequences into one.

13.4.7 Randomly Rearrange Elements in a Sequence

The algorithm std::random_shuffle() randomly rearranges the elements in a sequence. Exactly n swaps are performed, where n represents the number of elements in the sequence. Of course, the results are unpredictable. Because the arguments must be random access iterators, this algorithm can only be used with vectors, deques, or ordinary pointers; it cannot be used with lists, sets, or maps.

An alternative version of the algorithm uses the optional third argument. This value must be a random number generator. This generator must take as an argument a positive value m and return a value between 0 and m-1. As with the std::generate() algorithm, this random number function can be any type of object that responds to the function invocation operator.

Previous fileTop of DocumentContentsIndex pageNext file