|
|
11.1. OverviewSuppose 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 WorkEach 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:
The Standard Algorithms Are Inherently Type-IndependentThe 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:
Iterators Bind Algorithms to ContainersThe 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.
 |
|
|