### 11.1. 概述

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);
```

#### 算法如何工作

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. 否则，检查下一个元素，重复步骤 2，直到找到这个值，或者检查完所有的元素为止。 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 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.

需要一个类型指出元素在容器中的位置，或者表示找不到该元素。

#### 迭代器将算法和容器绑定起来

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. algorithm 头文件定义了一个名为 count 的函数，其功能类似于 find。这个函数使用一对迭代器和一个值做参数，返回这个值出现次数的统计结果。编写程序读取一系列 int 型数据，并将它们存储到 vector 对象中，然后统计某个指定的值出现了多少次。 Exercise 11.2: Repeat the previous program, but read values into a list of strings. 重复前面的程序，但是，将读入的值存储到一个 string 类型的 list 对象中。

## 关键概念：算法永不执行容器提供的操作

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.