Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |

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
**vector**s 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 |