On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com
Answertopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions
Privacy Policy

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

### Searching and replacing

All 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, 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 adjacent elements that are equivalent. 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. An iterator to the first of the two elements is returned if a pair is found; otherwise, 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);

Like find( ), performs a linear search through the range. Both forms search for an element in the second range that s equivalent to one in the first, the first form using operator==, and the second using the supplied predicate. In the second form, the current 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);

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==, and 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 they look for the second range appearing as a subset of the first range, but while search( ) looks for the first occurrence of the subset, find_end( ) looks for the last occurrence and returns an iterator to its first element.

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 (as explained below there may be multiple occurrences of this 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 [first, r). 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 [first, r).

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 [first, r). 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 [first, r).

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; 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 manipulates vectors of int. Again, not every possible version of each algorithm is shown. (Some that should be obvious have been omitted.)

//: C06:SearchReplace.cpp
// The STL search and replace algorithms.
#include <algorithm>
#include <functional>
#include <vector>
#include "PrintSequence.h"
using namespace std;

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

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.begin(), v.end(), "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 + 1, 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", " ");
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.begin(), v2.end(), "replace_copy 8 -> 47", " ");
replace_if(v.begin(), v.end(),
bind2nd(greater_equal<int>(), 7), -1);
print(v.begin(), v.end(), "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.

In main( ), an array a is created and fed to the constructor for vector<int> v. This vector is the target for the search and replace activities, and you ll note that there are duplicate elements these are 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.

The find_if( ) algorithm uses a predicate to determine if it has discovered the correct element. In this 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 two identical objects appear next to each other in a number of cases in v, 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 the matches and then performs the next adjacent_find( ), this time using it + 1 as the first argument (this way, it will still find two pairs in a triple).

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

while(it != v.end()) {
cout << "adjacent_find: " << *it++
<< ", " << *it++ << endl;
it = adjacent_find(it, v.end());
}

This is exactly what we tried first. However, we did not get the output we expected, on any compiler. This is because there is no guarantee about when the increments occur in this expression.

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 finds all the cases.

The find_first_of( ) algorithm requires a second range of objects for which to hunt; this is provided in the array b. 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.

The search( ) algorithm 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 presents some interesting possibilities here, the PlusOne predicate causes the range { 4, 5, 6 } to be found.

The find_end( ) test discovers the last occurrence of the entire sequence { 11, 11, 11 }. To show that it has in fact found the last occurrence, the rest of v starting from it is printed.

The first search_n( ) test looks for 3 copies of the value 7, which it finds and prints. When using the second version of search_n( ), the predicate is ordinarily meant to be used to determine equivalence between two elements, but we ve taken some liberties and used a function object that multiplies the value in the sequence by (in this case) 15 and checks to see if it s greater than 100. That is, the search_n( ) test says find me 6 consecutive values that, when multiplied by 15, each produce a number greater than 100. Not exactly what you normally expect to do, but it might give you some ideas the next time you have an odd searching problem.

The min_element( ) and max_element( ) algorithms are straightforward, but they look odd, as if the function is being dereferenced with a * . Actually, the returned iterator is being dereferenced to produce the value for printing.

To test replacements, replace_copy( ) is used first (so it doesn t modify the original vector) to replace all values of 8 with the value 47. Notice the use of back_inserter( ) with the empty vector v2. To demonstrate replace_if( ), a function object is created using the standard template greater_equal along with bind2nd to replace all the values that are greater than or equal to 7 with the value -1.

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

 Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire