Obtaining the Source
The next category of algorithms in the standard library that we examine are those used to modify and transform sequences without moving them from their original storage locations. A few of these routines, such as 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 illustrates how one can place the reversal of one vector into another newly allocated vector.
vector<int> newVec(aVec.size());
copy (aVec.begin(), aVec.end(), newVec.begin()); // first copy
reverse (newVec.begin(), newVec.end()); // then reverse
Many of the algorithms described as sequence generating operations, such as transform() (Transform One or Two Sequences), or partial_sum(), can also be used to modify a value in place by simply using the same iterator as both input and output specification.
The algorithm 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.
void reverse (BidirectionalIterator first,
BidirectionalIterator last);
The example program illustrates two uses of this algorithm. In the first, an array of characters values is reversed. The algorithm reverse() can also be used with list values, as shown in the second example. 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 Chapter 3: Functions Objects). 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 reverse() member function.
void reverse_example ()
// illustrate the use of the reverse algorithm
{
// example 1, reversing a string
char * text = "Rats live on no evil star";
reverse (text, text + strlen(text));
cout << text << endl;
// example 2, reversing a list
list<int> iList;
generate_n (inserter(iList, iList.begin()), 10, iotaGen(2));
reverse (iList.begin(), iList.end());
}
The algorithms replace() and replace_if() are used to replace occurrences of certain elements with a new value. In both cases the new value is the same, no matter how many replacements are performed. Using the algorithm replace(), all occurrences of a particular test value are replaced with the new value. In the case of replace_if(), all elements that satisfy a predicate function are replaced by a new value. The iterator arguments must be forward iterators.
The algorithms replace_copy() and replace_copy_if() are similar to replace() and replace_if(), however they leave the original sequence intact and place the revised values into a new sequence, which may be a different type.
void replace (ForwardIterator first, ForwardIterator last,
const T&, const T&);
void replace_if (ForwardIterator first, ForwardIterator last,
Predicate, const T&);OutputIterator replace_copy (InputIterator, InputIterator,
OutputIterator, const T&, const T&);OutputIterator replace_copy (InputIterator, InputIterator,
OutputIterator, Predicate, const T&);
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 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 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.
void replace_example ()
// illustrate the use of the replace algorithm
{
// make vector 0 1 2 3 4 5 4 3 2 1 0
vector<int> numbers(11);
for (int i = 0; i < 11; i++)
numbers[i] = i < 5 ? i : 10 - i;
// replace 3 by 7
replace (numbers.begin(), numbers.end(), 3, 7);
// replace even numbers by 9
replace_if (numbers.begin(), numbers.end(), isEven, 9);
// illustrate copy versions of replace
int aList[] = {2, 1, 4, 3, 2, 5};
int bList[6], cList[6], j;
replace_copy (aList, aList+6, &bList[0], 2, 7);
replace_copy_if (bList, bList+6, &cList[0],
bind2nd(greater<int>(), 3), 8);
}
The example program also illustrates the use of the 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 bind2nd() adaptor is used, to modify the binary greater-than function by binding the 2nd argument to the constant value 3, thereby creating the unary function x > 3.
A rotation of a sequence divides the sequence into two sections, then swaps the order of the sections, maintaining the relative ordering of the elements within the two sections. 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 rotate(), the starting point, midpoint, and past-the-end location are all denoted by forward iterators:
void rotate (ForwardIterator first, ForwardIterator middle,
ForwardIterator last);
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 illustration presented earlier, that these two segments need not be the same length.
void rotate_example()
// illustrate the use of the rotate algorithm
{
// create the list 1 2 3 ... 10
list<int> iList;
generate_n(inserter(iList, iList.begin()), 10, iotaGen(1));
// find the location of the seven
list<int>::iterator & middle =
find(iList.begin(), iList.end(), 7);
// now rotate around that location
rotate (iList.begin(), middle, iList.end());
// rotate again around the same location
list<int> cList;
rotate_copy (iList.begin(), middle, iList.end(),
inserter(cList, cList.begin()));
}
The example program first creates a list of the integers in order from 1 to 10. Next, the find() algorithm (Find an Element Satisfying a Condition) is used to find the location of the element 7. This is used as the midpoint for the rotation.
A second form of 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 (now containing a 3). The resulting list is 3 4 5 6 7 8 9 10 1 2. The values held in iList remain unchanged.
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."
BidirectionalIterator partition
(BidirectionalIterator, BidirectionalIterator, Predicate);
BidirectionalIterator stable_partition
(BidirectionalIterator, BidirectionalIterator, Predicate);
There are two forms of partition supported in the standard library. The first, provided by the algorithm partition(), guarantees only that the elements will be 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.
Partitions
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.
void partition_example ()
// illustrate the use of the partition algorithm
{
// first make the vector 1 2 3 ... 10
vector<int> numbers(10);
generate(numbers.begin(), numbers.end(), iotaGen(1));
// now put the even values low, odd high
vector<int>::iterator result =
partition(numbers.begin(), numbers.end(), isEven);
cout << "middle location " << result - numbers.begin() << endl;
// now do a stable partition
generate (numbers.begin(), numbers.end(), iotaGen(1));
stable_partition (numbers.begin(), numbers.end(), isEven);
}
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, yet in the result it may follow the element 8. A second version of partition, named stable_partition(), guarantees the ordering of the resulting values. For the sample input shown in the example, the stable partition would result in the sequence 2 4 6 8 10 1 3 5 7 9. The stable_partition() algorithm is slightly slower and uses more memory than the partition() algorithm, so when the order of elements is not important you should use partition().
Ordering Permutations
A permutation is a rearrangement of values. If values can be compared against each other (such as integers, characters, or words) then it is possible to systematically construct all permutations of a sequence. There are 2 permutations of two values, for example, and six permutations of three values, and 24 permutations of four values.
The permutation generating algorithms have the following definition:
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, [ Compare ] );
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last, [ Compare ] );
The second example in the sample program illustrates the same idea, only 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.
bool nameCompare (char * a, char * b) { return strcmp(a, b) <= 0; }
void permutation_example ()
// illustrate the use of the next_permutation algorithm
{
// example 1, permute the values 1 2 3
int start [] = { 1, 2, 3};
do
copy (start, start + 3,
ostream_iterator<int> (cout, " ")), cout << endl;
while (next_permutation(start, start + 3));
// example 2, permute words
char * words = {"Alpha", "Beta", "Gamma"};
do
copy (words, words + 3,
ostream_iterator<char *> (cout, " ")), cout << endl;
while (next_permutation(words, words + 3, nameCompare));
// example 3, permute characters backwards
char * word = "bela";
do
cout << word << ' ';
while (prev_permutation (word, &word[4]));
cout << endl;
}
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 finally, abel.
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, described elsewhere, can be used to merge two separate sequences into one.) The arguments to inplace_merge() must be bidirectional iterators.
void inplace_merge (BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last [, BinaryFunction ] );
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 (Find an Element Satisfying a Condition) is used to locate the beginning of the odd number sequence. The two calls on inplace_merge() then combine the two sequences into one.
void inplace_merge_example ()
// illustrate the use of the inplace_merge algorithm
{
// first generate the sequence 0 2 4 6 8 1 3 5 7 9
vector<int> numbers(10);
for (int i = 0; i < 10; i++)
numbers[i] = i < 5 ? 2 * i : 2 * (i - 5) + 1;
// then find the middle location
vector<int>::iterator midvec =
find(numbers.begin(), numbers.end(), 1);
// copy them into a list
list<int> numList;
copy (numbers.begin(), numbers.end(),
inserter (numList, numList.begin()));
list<int>::iterator midList =
find(numList.begin(), numList.end, 1);
// now merge the lists into one
inplace_merge (numbers.begin(), midvec, numbers.end());
inplace_merge (numList.begin(), midList, numList.end());
}
The algorithm random_shuffle() randomly rearranges the elements in a sequence. Exactly n swaps are performed, where n represents the number of elements in the sequence. The results are, of course, 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.
void random_shuffle (RandomAccessIterator first,
RandomAccessIterator last [, Generator ] );
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 generate() algorithm, this random number function can be any type of object that will respond to the function invocation operator.
void random_shuffle_example ()
// illustrate the use of the random_shuffle algorithm
{
// first make the vector containing 1 2 3 ... 10
vector<int> numbers;
generate(numbers.begin(), numbers.end(), iotaGen(1));
// then randomly shuffle the elements
random_shuffle (numbers.begin(), numbers.end());
// do it again, with explicit random number generator
struct RandomInteger {
{
operator() (int m) { return rand() % m; }
} random;
random_shuffle (numbers.begin(), numbers.end(), random);
}