Section 11.1. Overview

11.1. Overview

Suppose we have a vector of ints, named vec, and we want to know if it holds a particular value. The easiest way to answer this question is to use the library find operation:

      // value we'll look for      int search_value = 42;      // call find to see if that value is present      vector<int>::const_iterator result =              find(vec.begin(), vec.end(), search_value);      // report the result      cout << "The value " << search_value           << (result == vec.end()                 ? " is not present" : " is present")           << endl; 

The call to find takes two iterators and a value. It tests each element in the range (Section 9.2.1, p. 314) denoted by its iterator arguments. As soon as it sees an element that is equal to the given value, find returns an iterator referring to that element. If there is no match, then find returns its second iterator to indicate failure. We can test whether the return is equal to the second argument to determine whether the element was found. We do this test in the output statement, which uses the conditional operator (Section 5.7, p. 165) to report whether the value was found.

Because find operates in terms of iterators, we can use the same find function to look for values in any container. For example, we can use find to look for a value in a list of int named lst:

      // call find to look through elements in a list      list<int>::const_iterator result =               find(lst.begin(), lst.end(), search_value);      cout << "The value " << search_value            << (result == lst.end()                  ? " is not present" : " is present")            << endl; 

Except for the type of result and the iterators passed to find, this code is identical to the program that used find to look at elements of a vector.

Similarly, because pointers act like iterators on built-in arrays, we can use find to look in an array:

      int ia[6] = {27, 210, 12, 47, 109, 83};      int search_value = 83;      int *result = find(ia, ia + 6, search_value);      cout << "The value " << search_value           << (result == ia + 6                 ? " is not present" : " is present")           << endl; 

Here we pass a pointer to the first element in ia and another pointer that is six elements past the start of ia (that is, one past the last element of ia). If the pointer returned is equal to ia + 6 then the search is unsuccessful; otherwise, the pointer points to the value that was found.

If we wish to pass a subrange, we pass iterators (or pointers) to the first and one past the last element of that subrange. For example, in this invocation of find, only the elements ia [1] and ia [2] are searched:

     // only search elements ia[1] and ia[2]     int *result = find(ia + 1, ia + 3, search_value); 

How the Algorithms Work

Each generic algorithm is implemented independently of the individual container types. The algorithms are also largely, but not completely, independent of the types of the elements that the container holds. To see how the algorithms work, let's look a bit more closely at find. Its job is to find a particular element in an unsorted collection of elements. Conceptually the steps that find must take include:

1.	Examine each element in turn.
2.	If the element is equal to the value we want, then return an iterator that refers to that element.
3.	Otherwise, examine the next element, repeating step 2 until either the value is found or all the elements have been examined.
4.	If we have reached the end of the collection and we have not found the value, return a value that indicates that the value was not found.

The Standard Algorithms Are Inherently Type-Independent

The algorithm, as we've stated it, is independent of the type of the container: Nothing in our description depends on the container type. Implicitly, the algorithm does have one dependency on the element type: We must be able to compare elements. More specifically, the requirements of the algorithm are:

1. We need a way to traverse the collection: We need to be able to advance from one element to the next.

2. We need to be able to know when we have reached the end of the collection.

3. We need to be able to compare each element to the value we want.

4. We need a type that can refer to an element's position within the container or that can indicate that the element was not found.

Iterators Bind Algorithms to Containers

The generic algorithms handle the first requirement, container traversal, by using iterators. All iterators support the increment operator to navigate from one element to the next, and the dereference operator to access the element value. With one exception that we'll cover in Section 11.3.5 (p. 416), the iterators also support the equality and inequality operators to determine whether two iterators are equal.

For the most part, the algorithms each take (at least) two iterators that denote the range of elements on which the algorithm is to operate. The first iterator refers to the first element, and the second iterator marks one past the last element. The element addressed by the second iterator, sometimes referred to as the off-the-end iterator, is not itself examined; it serves as a sentinel to terminate the traversal.

The off-the-end iterator also handles requirement 4 by providing a convenient return value that indicates that the search element wasn't found. If the value isn't found, then the off-the-end iterator is returned; otherwise, the iterator that refers to the matching element is returned.

Requirement 3, value comparison, is handled in one of two ways. By default, the find operation requires that the element type define operator ==. The algorithm uses that operator to compare elements. If our type does not support the == operator, or if we wish to compare elements using a different test, we can use a second version of find. That version takes an extra argument that is the name of a function to use to compare the elements.

The algorithms achieve type independence by never using container operations; rather, all access to and traversal of the elements is done through the iterators. The actual container type (or even whether the elements are stored in a container) is unknown.

The library provides more than 100 algorithms. Like the containers, the algorithms have a consistent architecture. Understanding the design of the algorithms makes learning and using them easier than memorizing all 100+ algorithms. In this chapter we'll both illustrate the use of the algorithms and describe the unifying principles used by the library algorithms. Appendix A lists all the algorithms classified by how they operate.

Exercises Section 11.1

Exercise 11.1:	The algorithm header defines a function named count that is similar to find. It takes a pair of iterators and a value and returns a count of how often that value appears. Read a sequence of ints into a vector. Count how many elements have a given value.
Exercise 11.2:	Repeat the previous program, but read values into a list of strings.

Key Concept: Algorithms Never Execute Container Operations

The generic algorithms do not themselves execute container operations. They operate solely in terms of iterators and iterator operations. The fact that the algorithms operate in terms of iterators and not container operations has a perhaps surprising but essential implication: When used on "ordinary" iterators, algorithms never change the size of the underlying container. As we'll see, algorithms may change the values of the elements stored in the container, and they may move elements around within the container. They do not, however, ever add or remove elements directly.

As we'll see in Section 11.3.1 (p. 406), there is a special class of iterator, the inserters, that do more than traverse the sequence to which they are bound. When we assign to these iterators, they execute insert operations on the underlying container. When an algorithm operates on one of these iterators, the iterator may have the effect of adding elements to the container. The algorithm itself, however, never does so.