Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
These algorithms let you move sequences around.
OutputIterator copy(InputIterator
first, InputIterator
last, OutputIterator destination);
Using assignment, copies from [first, last) to destination,
incrementing destination after each assignment. This is essentially a
shuffle-left operation, and so the source sequence must not contain the
destination. Because assignment is used, you cannot directly insert elements
into an empty container or at the end of a container, but instead you must wrap
the destination iterator in an insert_iterator (typically by using back_inserter( ) or by using inserter( ) in the case of an associative container).
BidirectionalIterator2 copy_backward(BidirectionalIterator1
first, BidirectionalIterator1 last,
BidirectionalIterator2 destinationEnd);
Like copy( ), but copies the elements in reverse
order. This is essentially a shuffle-right operation, and, like copy( ),
the source sequence must not contain the destination. The source range [first,
last) is copied to the destination, but the first destination element is destinationEnd
- 1. This iterator is then decremented after each assignment. The space in
the destination range must already exist (to allow assignment), and the
destination range cannot be within the source range.
void reverse(BidirectionalIterator
first,
BidirectionalIterator last);
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last, OutputIterator destination);
Both forms of this function reverse the range [first,
last). reverse( ) reverses the range in place, and reverse_copy( ) leaves the original range alone and copies the reversed elements
into destination, returning the past-the-end iterator of the resulting
range.
ForwardIterator2 swap_ranges(ForwardIterator1
first1,
ForwardIterator1 last1, ForwardIterator2 first2);
Exchanges the contents of two ranges of equal size by
swapping corresponding elements.
void rotate(ForwardIterator
first, ForwardIterator middle,
ForwardIterator last);
OutputIterator rotate_copy(ForwardIterator first,
ForwardIterator middle, ForwardIterator last,
OutputIterator destination);
Moves the contents of [first, middle) to the end of
the sequence, and the contents of [middle, last) to the beginning. With rotate( ),
the swap is performed in place; and with rotate_copy( ) the original range is untouched, and the rotated version is copied into destination,
returning the past-the-end iterator of the resulting range. Note that while swap_ranges( )
requires that the two ranges be exactly the same size, the rotate functions do
not.
bool next_permutation(BidirectionalIterator
first,
BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, StrictWeakOrdering
binary_pred);
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, StrictWeakOrdering
binary_pred);
A permutation is one unique ordering of a set of
elements. If you have n unique elements, there are n! (n
factorial) distinct possible combinations of those elements. All these
combinations can be conceptually sorted into a sequence using a lexicographical
(dictionary-like) ordering and thus produce a concept of a next and
previous permutation. So whatever the current ordering of elements in the
range, there is a distinct next and previous permutation in the sequence of
permutations.
The next_permutation( ) and prev_permutation( ) functions rearrange the elements into their next or previous
permutation and, if successful, return true. If there are no more next
permutations, the elements are in sorted order so next_permutation( )
returns false. If there are no more previous permutations, the
elements are in descending sorted order so previous_permutation( )
returns false.
The versions of the functions that have a StrictWeakOrdering argument perform the comparisons using binary_pred instead of operator<.
void random_shuffle(RandomAccessIterator
first,
RandomAccessIterator last);
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last RandomNumberGenerator& rand);
This function randomly rearranges the elements in the range.
It yields uniformly distributed results if the random-number generator does.
The first form uses an internal random number generator, and the second uses a
user-supplied random-number generator. The generator must return a value in the
range [0, n) for some positive n.
BidirectionalIterator partition(BidirectionalIterator
first, BidirectionalIterator last, Predicate pred);
BidirectionalIterator stable_partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);
The partition functions move elements that satisfy pred
to the beginning of the sequence. An iterator pointing one past the last of
those elements is returned (which is, in effect, an end iterator for the
initial subsequence of elements that satisfy pred). This location is
often called the partition point.
With partition( ), the order of the elements in each resulting subsequence after the function call is not specified, but with
stable_partition( ), the relative order of the elements
before and after the partition point will be the same as before the
partitioning process.
Example
This gives a basic demonstration of sequence manipulation:
//: C06:Manipulations.cpp
// Shows basic manipulations.
//{L} Generators
// NString
#include <vector>
#include <string>
#include <algorithm>
#include "PrintSequence.h"
#include "NString.h"
#include "Generators.h"
using namespace std;
int main() {
vector<int> v1(10);
// Simple counting:
generate(v1.begin(), v1.end(), SkipGen());
print(v1.begin(), v1.end(), "v1", "
");
vector<int> v2(v1.size());
copy_backward(v1.begin(), v1.end(), v2.end());
print(v2.begin(), v2.end(),
"copy_backward", " ");
reverse_copy(v1.begin(), v1.end(), v2.begin());
print(v2.begin(), v2.end(), "reverse_copy",
" ");
reverse(v1.begin(), v1.end());
print(v1.begin(), v1.end(), "reverse",
" ");
int half = v1.size() / 2;
// Ranges must be exactly the same size:
swap_ranges(v1.begin(), v1.begin() + half,
v1.begin() + half);
print(v1.begin(), v1.end(), "swap_ranges",
" ");
// Start with a fresh sequence:
generate(v1.begin(), v1.end(), SkipGen());
print(v1.begin(), v1.end(), "v1", "
");
int third = v1.size() / 3;
for(int i = 0; i < 10; i++) {
rotate(v1.begin(), v1.begin() + third, v1.end());
print(v1.begin(), v1.end(), "rotate",
" ");
}
cout << "Second rotate example:"
<< endl;
char c[] = "aabbccddeeffgghhiijj";
const char CSZ = strlen(c);
for(int i = 0; i < 10; i++) {
rotate(c, c + 2, c + CSZ);
print(c, c + CSZ, "", "");
}
cout << "All n! permutations of abcd:"
<< endl;
int nf = 4 * 3 * 2 * 1;
char p[] = "abcd";
for(int i = 0; i < nf; i++) {
next_permutation(p, p + 4);
print(p, p + 4, "", "");
}
cout << "Using prev_permutation:"
<< endl;
for(int i = 0; i < nf; i++) {
prev_permutation(p, p + 4);
print(p, p + 4, "", "");
}
cout << "random_shuffling a word:"
<< endl;
string s("hello");
cout << s << endl;
for(int i = 0; i < 5; i++) {
random_shuffle(s.begin(), s.end());
cout << s << endl;
}
NString sa[] = { "a", "b",
"c", "d", "a", "b",
"c", "d", "a",
"b", "c", "d", "a", "b",
"c"};
const int SASZ = sizeof sa / sizeof *sa;
vector<NString> ns(sa, sa + SASZ);
print(ns.begin(), ns.end(),
"ns", " ");
vector<NString>::iterator it =
partition(ns.begin(), ns.end(),
bind2nd(greater<NString>(),
"b"));
cout << "Partition point: " <<
*it << endl;
print(ns.begin(), ns.end(), "", "
");
// Reload vector:
copy(sa, sa + SASZ, ns.begin());
it = stable_partition(ns.begin(), ns.end(),
bind2nd(greater<NString>(), "b"));
cout << "Stable partition" <<
endl;
cout << "Partition point: " <<
*it << endl;
print(ns.begin(), ns.end(), "", "
");
} ///:~
The best way to see the results of this program is to run
it. (You ll probably want to redirect the output to a file.)
The vector<int> v1 is initially loaded with a
simple ascending sequence and printed. You ll see that the effect of copy_backward( )
(which copies into v2, which is the same size as v1) is the same
as an ordinary copy. Again, copy_backward( ) does the same thing as
copy( ) it just performs the operations in reverse order.
reverse_copy( ) actually does create a reversed
copy, and reverse( ) performs the reversal in place. Next, swap_ranges( )
swaps the upper half of the reversed sequence with the lower half. The ranges
could be smaller subsets of the entire vector, as long as they are of
equivalent size.
After re-creating the ascending sequence, rotate( )
is demonstrated by rotating one third of v1 multiple times. A second rotate( )
example uses characters and just rotates two characters at a time. This also
demonstrates the flexibility of both the STL algorithms and the print( )
template, since they can both be used with arrays of char as easily as
with anything else.
To demonstrate next_permutation( ) and prev_permutation( ),
a set of four characters abcd is permuted through all n! (n
factorial) possible combinations. You ll see from the output that the
permutations move through a strictly defined order (that is, permuting is a
deterministic process).
A quick-and-dirty demonstration of random_shuffle( )
is to apply it to a string and see what words result. Because a string
object has begin( ) and end( ) member functions that
return the appropriate iterators, it too can be easily used with many of the
STL algorithms. An array of char could also have been used.
Finally, the partition( ) and stable_partition( )
are demonstrated, using an array of NString. You ll note that the
aggregate initialization expression uses char arrays, but NString
has a char* constructor that is automatically used.
You ll see from the output that with the unstable partition,
the objects are correctly above and below the partition point, but in no
particular order; whereas with the stable partition, their original order is maintained.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |