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:
std::vector<int> newVec(aVec.size()); std::copy(aVec.begin(), aVec.end(), newVec.begin());// first copy std::reverse(newVec.begin(), newVec.end()); // then reverse
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).
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.
namespace std {
void reverse (BidirectionalIterator first,
BidirectionalIterator last);
}
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 3.2.2.3). 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.
void reverse_example()
// illustrates the use of the reverse algorithm
// see alg3.cpp for complete source code
{
// example 1, reversing a string
char *text = "Rats live on no evil star";
std::reverse(text, text + strlen(text));
std::cout << text << std::endl;
// example 2, reversing a list
std::list<int> iList;
std::generate_n(std::inserter(iList, iList.begin()),
10, iotaGen(2));
std::reverse(iList.begin(), iList.end());
}
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.
namespace std {
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 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.
void replace_example()
// illustrates the use of the replace algorithm
// see alg3.cpp for complete source code
{
// make vector 0 1 2 3 4 5 4 3 2 1 0
std::vector<int> numbers(11);
for (int i = 0; i < 11; i++)
numbers[i] = i < 5 ? i : 10 - i;
// replace 3 by 7
std::replace(numbers.begin(), numbers.end(), 3, 7);
// replace even numbers by 9
std::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;
std::replace_copy(aList, aList+6, &bList[0], 2, 7);
std::replace_copy_if(bList, bList+6, &cList[0],
std::bind2nd(greater<int>(), 3), 8);
}
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.
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:
namespace std{
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 previous example, that these two segments need not be the same length.
void rotate_example()
// illustrates the use of the rotate algorithm
// see alg3.cpp for complete source code
{
// create the list 1 2 3 ... 10
std::list<int> iList;
std::generate_n(std::inserter(iList, iList.begin()), 10,
iotaGen(1));
// find the location of the seven
std::list<int>::iterator& middle =
std::find(iList.begin(), iList.end(), 7);
// now rotate around that location
std::rotate(iList.begin(), middle, iList.end());
// rotate again around the same location
std::list<int> cList;
std::rotate_copy(iList.begin(), middle, iList.end(),
std::inserter(cList, cList.begin()));
}
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.
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.
namespace std {
BidirectionalIterator partition
(BidirectionalIterator, BidirectionalIterator, Predicate);
BidirectionalIterator stable_partition
(BidirectionalIterator, BidirectionalIterator, Predicate);
}
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.
void partition_example()
// illustrates the use of the partition algorithm
// see alg3.cpp for complete source code
{
// first make the vector 1 2 3 ... 10
std::vector<int> numbers(10);
std::generate(numbers.begin(), numbers.end(), iotaGen(1));
// now put the even values low, odd high
std::vector<int>::iterator result =
std::partition(numbers.begin(), numbers.end(), isEven);
std::cout << "middle location "
<< result - numbers.begin() << std::endl;
// now do a stable partition
std::generate(numbers.begin(), numbers.end(), iotaGen(1));
std::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, 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:
2 4 6 8 10 1 3 5 7 9 10 8 6 4 2 5 7 9 3 1 2 6 4 8 10 3 5 7 9 1 6 4 2 10 8 5 3 7 9 1
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:
namespace std {
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, 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()
// illustrates the use of the next_permutation algorithm
// see alg3.cpp for complete source code
{
// example 1
int start [] = { 1, 2, 3 };
do {
std::copy(start, start + 3, ostrm_iter_type (std::cout, " "));
std::cout << std::endl;
} while (std::next_permutation (start, start + 3));
// example 2
const char alpha[] = "Alpha";
const char beta[] = "Beta";
const char gamma[] = "Gamma";
const char* names[] = { alpha, beta, gamma };
typedef std::ostream_iterator<const char*, char,
std::char_traits<char> > Iter;
do {
std::copy (names, names + 3, Iter (std::cout, " "));
std::cout << std::endl;
} while (std::next_permutation (names, names + 3, nameCompare));
// example 3
char word[] = "bela";
do
std::cout << word << ' ';
while (std::prev_permutation (word, &word[4]));
std::cout << std::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 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:
123
132
213
231
312
321
Notice that in the first permutation the values are all ascending, while in the last permutation they are all descending.
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 6.2.3.1 and Section 14.5) can be used to merge two separate sequences into one.
The arguments to inplace_merge() must be bidirectional iterators.
namespace std {
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 (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.
void inplace_merge_example()
// illustrate the use of the inplace_merge algorithm
// see alg3.cpp for complete source code
{
// first generate the sequence 0 2 4 6 8 1 3 5 7 9
std::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
std::vector<int>::iterator midvec =
std::find(numbers.begin(), numbers.end(), 1);
// copy them into a list
std::list<int> numList;
std::copy(numbers.begin(), numbers.end(),
std::inserter (numList, numList.begin()));
std::list<int>::iterator midList =
std::find(numList.begin(), numList.end, 1);
// now merge the lists into one
std::inplace_merge(numbers.begin(), midvec, numbers.end());
std::inplace_merge(numList.begin(), midList, numList.end());
}
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.
namespace std {
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 std::generate() algorithm, this random number function can be any type of object that responds to the function invocation operator.
void random_shuffle_example()
// illustrates the use of the random_shuffle algorithm
// see alg3.cpp fr complete source code
{
// first make the vector containing 1 2 3 ... 10
std::vector<int> numbers;
std::generate(numbers.begin(), numbers.end(), iotaGen(1));
// then randomly shuffle the elements
std::random_shuffle(numbers.begin(), numbers.end());
// do it again, with explicit random number generator
struct RandomInteger {
operator() (int m) { return rand() % m; }
} random;
std::random_shuffle(numbers.begin(), numbers.end(), random);
}