produces a binary function object which compares its first and second arguments:

return first > second;

and returns a bool. But we don’t want a binary predicate, and we want to compare against the constant value “b.” So bind2nd( ) says: create a new function object which only takes one argument, by taking this greater<NString>( ) function and forcing the second argument to always be “b.” The first argument (the only argument) will be the one from the vector ns.

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.

Searching & replacing

All of these algorithms are used for searching for one or more objects within a range defined by the first two iterator arguments.

InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value);

Searches for value within a range of elements. Returns an iterator in the range [first, last) that points to the first occurrence of value. If value isn’t in the range, then find( ) returns last. This is a linear search, that is, it starts at the beginning and looks at each sequential element without making any assumptions about the way the elements are ordered. In contrast, a binary_search( ) (defined later) works on a sorted sequence and can thus be much faster.

InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

Just like find( ), find_if( ) performs a linear search through the range. However, instead of searching for value, find_if( ) looks for an element such that the Predicate pred returns true when applied to that element. Returns last if no such element can be found.

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,

BinaryPredicate binary_pred);

Like find( ), performs a linear search through the range, but instead of looking for only one element it searches for two elements that are right next to each other. The first form of the function looks for two elements that are equivalent (via operator==). The second form looks for two adjacent elements that, when passed together to binary_pred, produce a true result. If two adjacent elements cannot be found, last is returned.

ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);

Chapter 15: Multiple Inheritance

299

Like find( ), performs a linear search through the range. The first form finds the first element in the first range that is equivalent to any of the elements in the second range. The second form finds the first element in the first range that produces true when passed to binary_pred along with any of the elements in the second range. When a BinaryPredicate is used with two ranges in the algorithms, the element from the first range becomes the first argument to binary_pred, and the element from the second range becomes the second argument.

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 BinaryPredicate binary_pred);

Attempts to find the entire range [first2, last2) within the range [first1, last1). That is, it checks to see if the second range occurs (in the exact order of the second range) within the first range, and if so returns an iterator pointing to the place in the first range where the second range begins. Returns last1 if no subset can be found. The first form performs its test using operator==, while the second checks to see if each pair of objects being compared causes binary_pred to return true.

ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);

The forms and arguments are just like search( ) in that it looks for the second range within the first range, but while search( ) looks for the first occurrence of the second range, find_end( ) looks for the last occurrence of the second range within the first.

ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);

ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate binary_pred);

Looks for a group of count consecutive values in [first, last) that are all equal to value (in the first form) or that all cause a return value of true when passed into binary_pred along with value (in the second form). Returns last if such a group cannot be found.

ForwardIterator min_element(ForwardIterator first, ForwardIterator last); ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);

Returns an iterator pointing to the first occurrence of the smallest value in the range (there may be multiple occurrences of the smallest value). Returns last if the range is empty. The first version performs comparisons with operator< and the value r returned is such that *e < *r

is false for every element e in the range. The second version compares using binary_pred and the value r returned is such that binary_pred (*e, *r) is false for every element e in the range.

Chapter 15: Multiple Inheritance

300

ForwardIterator max_element(ForwardIterator first, ForwardIterator last); ForwardIterator max_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);

Returns an iterator pointing to the first occurrence of the largest value in the range (there may be multiple occurrences of the largest value). Returns last if the range is empty. The first version performs comparisons with operator< and the value r returned is such that

*r < *e

is false for every element e in the range. The second version compares using binary_pred and the value r returned is such that binary_pred (*r, *e) is false for every element e in the range.

void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

Each of the “replace” forms moves through the range [first, last), finding values that match a criterion and replacing them with new_value. Both replace( ) and replace_copy( ) simply look for old_value to replace, while replace_if( ) and replace_copy_if( ) look for values that satisfy the predicate pred. The “copy” versions of the functions do not modify the original range but instead make a copy with the replacements into result (incrementing result after each assignment).

Example

To provide easy viewing of the results, this example will manipulate vectors of int. Again, not every possible version of each algorithm will be shown (some that should be obvious have been omitted).

//: C05:SearchReplace.cpp

// The STL search and replace algorithms #include "PrintSequence.h"

#include <vector> #include <algorithm> #include <functional> using namespace std;

struct PlusOne {

bool operator()(int i, int j) { return j == i + 1;

}

Chapter 15: Multiple Inheritance

301

};

class MulMoreThan { int value;

public:

MulMoreThan(int val) : value(val) {} bool operator()(int v, int m) {

return v * m > value;

}

};

int main() {

int a[] = { 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 11, 11, 11, 11, 11 };

const int asz = sizeof a / sizeof *a; vector<int> v(a, a + asz);

print(v, "v", " "); vector<int>::iterator it =

find(v.begin(), v.end(), 4); cout << "find: " << *it << endl; it = find_if(v.begin(), v.end(), bind2nd(greater<int>(), 8));

cout << "find_if: " << *it << endl;

it = adjacent_find(v.begin(), v.end()); while(it != v.end()) {

cout << "adjacent_find: " << *it << ", " << *(it + 1) << endl;

it = adjacent_find(it + 2, v.end());

}

it = adjacent_find(v.begin(), v.end(), PlusOne());

while(it != v.end()) {

cout << "adjacent_find PlusOne: " << *it << ", " << *(it + 1) << endl;

it = adjacent_find(it + 1, v.end(), PlusOne());

}

int b[] = { 8, 11 };

const int bsz = sizeof b / sizeof *b; print(b, b + bsz, "b", " ");

it = find_first_of(v.begin(), v.end(), b, b + bsz);

print(it, it + bsz, "find_first_of", " ");

Chapter 15: Multiple Inheritance

302

it = find_first_of(v.begin(), v.end(), b, b + bsz, PlusOne());

print(it,it + bsz,"find_first_of PlusOne"," "); it = search(v.begin(), v.end(), b, b + bsz); print(it, it + bsz, "search", " ");

int c[] = { 5, 6, 7 };

const int csz = sizeof c / sizeof *c; print(c, c + csz, "c", " ");

it = search(v.begin(), v.end(), c, c + csz, PlusOne());

print(it, it + csz,"search PlusOne", " "); int d[] = { 11, 11, 11 };

const int dsz = sizeof d / sizeof *d; print(d, d + dsz, "d", " ");

it = find_end(v.begin(), v.end(), d, d + dsz); print(it, v.end(),"find_end", " ");

int e[] = { 9, 9 }; print(e, e + 2, "e", " ");

it = find_end(v.begin(), v.end(), e, e + 2, PlusOne());

print(it, v.end(),"find_end PlusOne"," "); it = search_n(v.begin(), v.end(), 3, 7); print(it, it + 3, "search_n 3, 7", " "); it = search_n(v.begin(), v.end(),

6, 15, MulMoreThan(100)); print(it, it + 6,

"search_n 6, 15, MulMoreThan(100)", " "); cout << "min_element: " <<

*min_element(v.begin(), v.end()) << endl; cout << "max_element: " <<

*max_element(v.begin(), v.end()) << endl; vector<int> v2;

replace_copy(v.begin(), v.end(), back_inserter(v2), 8, 47);

print(v2, "replace_copy 8 -> 47", " "); replace_if(v.begin(), v.end(),

bind2nd(greater_equal<int>(), 7), -1); print(v, "replace_if >= 7 -> -1", " ");

} ///:~

The example begins with two predicates: PlusOne which is a binary predicate that returns true if the second argument is equivalent to one plus the first argument, and MulMoreThan which returns true if the first argument times the second argument is greater than a value stored in the object. These binary predicates are used as tests in the example.

Chapter 15: Multiple Inheritance

303

In main( ), an array a is created and fed to the constructor for vector<int> v. This vector will be used as the target for the search and replace activities, and you’ll note that there are duplicate elements – these will be discovered by some of the search/replace routines.

The first test demonstrates find( ), discovering the value 4 in v. The return value is the iterator pointing to the first instance of 4, or the end of the input range (v.end( )) if the search value is not found.

find_if( ) uses a predicate to determine if it has discovered the correct element. In the above example, this predicate is created on the fly using greater<int> (that is, “see if the first int argument is greater than the second”) and bind2nd( ) to fix the second argument to 8. Thus, it returns true if the value in v is greater than 8.

Since there are a number of cases in v where two identical objects appear next to each other, the test of adjacent_find( ) is designed to find them all. It starts looking from the beginning and then drops into a while loop, making sure that the iterator it has not reached the end of the input sequence (which would mean that no more matches can be found). For each match it finds, the loop prints out the matches and then performs the next adjacent_find( ), this time using it + 2 as the first argument (this way, it moves past the two elements that it already found).

You might look at the while loop and think that you can do it a bit more cleverly, to wit:

while(it != v.end()) {

cout << "adjacent_find: " << *it++ << ", " << *it++ << endl;

it = adjacent_find(it, v.end());

}

Of course, this is exactly what I tried at first. However, I did not get the output I expected, on any compiler. This is because there is no guarantee about when the increments occur in the above expression. A bit of a disturbing discovery, I know, but the situation is best avoided now that you’re aware of it.

The next test uses adjacent_find( ) with the PlusOne predicate, which discovers all the places where the next number in the sequence v changes from the previous by one. The same while approach is used to find all the cases.

find_first_of( ) requires a second range of objects for which to hunt; this is provided in the array b. Notice that, because the first range and the second range in find_first_of( ) are controlled by separate template arguments, those ranges can refer to two different types of containers, as seen here. The second form of find_first_of( ) is also tested, using PlusOne.

search( ) finds exactly the second range inside the first one, with the elements in the same order. The second form of search( ) uses a predicate, which is typically just something that defines equivalence, but it also opens some interesting possibilities – here, the PlusOne predicate causes the range { 4, 5, 6 } to be found.

Chapter 15: Multiple Inheritance

304