}

int lc = count_if(v.begin(), v.end(), bind2nd(greater<char>(), 'a'));

cout << "\nLowercase letters: " << lc << endl; sort(v.begin(), v.end());

print(v, "sorted", ""); } ///:~

The count_if( ) algorithm is demonstrated by counting all the lowercase letters; the predicate is created using the bind2nd( ) and greater function object templates.

Manipulating sequences

These algorithms allow you to move sequences around.

OutputIterator copy(InputIterator, first InputIterator last, OutputIterator destination);

Using assignment, copies from [first, last) to destination, incrementing destination after each assignment. Works with almost any type of source range and almost any kind of 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 inserter( ) in the case of an associative container).

The copy algorithm is used in many examples in this book.

BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 destinationEnd);

Like copy( ), but performs the actual copying of the elements in reverse order. That is, the resulting sequence is the same, it’s just that the copy happens in a different way. 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, while 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);

Chapter 15: Multiple Inheritance

294

Exchanges the contents of two ranges of equal size, by moving from the beginning to the end of each range and swapping each set of elements.

void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,

ForwardIterator last, OutputIterator destination);

Swaps the two ranges [first, middle) and [middle, last). 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, then there are n! (n factorial) distinct possible combinations of those elements. All these combinations can be conceptually sorted into a sequence using a lexicographical ordering, and thus produce a concept of a “next” and “previous” permutation. Therefore, 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 re-arrange the elements into their next or previous permutation, and if successful return true. If there are no more “next” permutations, it means that the elements are in sorted order so next_permutation( ) returns false. If there are no more “previous” permutations, it means that the elements are in descending sorted order so previous_permutation( ) returns false.

The versions of the functions which 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. The first form uses an internal random number generator and the second uses a usersupplied random-number generator.

BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

Chapter 15: Multiple Inheritance

295

The “partition” functions use pred to organize the elements in the range [first, last) so they are before or after the partition (a point in the range). The partition point is given by the returned iterator. If pred(*i) is true (where i is the iterator pointing to a particular element), then that element will be placed before the partition point, otherwise it will be placed after the partition point.

With partition( ), the order of the elements is after the function call is not specified, but with stable_parition( ) 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:

//: C05:Manipulations.cpp

// Shows basic manipulations #include "PrintSequence.h" #include "NString.h" #include "Generators.h" #include <vector>

#include <string> #include <algorithm> using namespace std;

int main() { vector<int> v1(10); // Simple counting:

generate(v1.begin(), v1.end(), SkipGen()); print(v1, "v1", " ");

vector<int> v2(v1.size()); copy_backward(v1.begin(), v1.end(), v2.end()); print(v2, "copy_backward", " "); reverse_copy(v1.begin(), v1.end(), v2.begin()); print(v2, "reverse_copy", " "); reverse(v1.begin(), v1.end());

print(v1, "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, "swap_ranges", " ");

//Start with fresh sequence: generate(v1.begin(), v1.end(), SkipGen()); print(v1, "v1", " ");

int third = v1.size() / 3;

Chapter 15: Multiple Inheritance

296

for(int i = 0; i < 10; i++) { rotate(v1.begin(), v1.begin() + third,

v1.end());

print(v1, "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, "ns", " "); vector<NString>::iterator it =

partition(ns.begin(), ns.end(), bind2nd(greater<NString>(), "b"));

cout << "Partition point: " << *it << endl; print(ns, "", " ");

// Reload vector:

copy (sa, sa + sasz, ns.begin());

Chapter 15: Multiple Inheritance

297

it = stable_partition(ns.begin(), ns.end(), bind2nd(greater<NString>(), "b"));

cout << "Stable partition" << endl;

cout << "Partition point: " << *it << endl; print(ns, "", " ");

} ///:~

The best way to see the results of the above 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 backward order.

reverse_copy( ), however, actually does created a reversed copy, while reverse( ) performs the reversal in place. Next, swap_ranges( ) swaps the upper half of the reversed sequence with the lower half. Of course, 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 may be easily used with many of the STL algorithms. Of course, 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 which is automatically used.

When partitioning a sequence, you need a predicate which will determine whether the object belongs above or below the partition point. This takes a single argument and returns true (the object is above the partition point) or false (it isn’t). I could have written a separate function or function object to do this, but for something simple, like “the object is greater than ‘b’”, why not use the built-in function object templates? The expression is:

bind2nd(greater<NString>(), "b")

And to understand it, you need to pick it apart from the middle outward. First,

greater<NString>()

Chapter 15: Multiple Inheritance

298