Section 11.1. Overview

11.1. Overview

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:

假设有一个 int 的 vector 对象，名为 vec，我们想知道其中包含某个特定值。解决这个问题最简单的方法是使用标准库提供的 find 运算：

     // 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.

使用两个迭代器和一个值调用 find 函数，检查两个迭代器实参标记范围内的每一个元素。只要找到与给定值相等的元素，find 就会返回指向该元素的迭代器。如果没有匹配的元素，find 就返回它的第二个迭代器实参，表示查找失败。于是，只要检查该函数的返回值是否与它的第二个实参相等，就可得知元素是否找到了。我们在输出语句中使用条件操作符（第 5.7 节）实现这个检查并报告是否找到了给定值。

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:

由于 find 运算是基于迭代器的，因此可在任意容器中使用相同的 find 函数查找值。例如，可在一个名为 lst 的 int 型 list 对象上，使用 find 函数查找一个值：

     // 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.

除了 result 的类型和传递给 find 的迭代器类型之外，这段代码与使用 find 在 vector 对象中查找元素的程序完全相同。

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

类似地，由于指针的行为与作用在内置数组上的迭代器一样，因此也可以使用 find 来搜索数组：

     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.

这里给 find 函数传递了两个指针：指向 ia 数组中第一个元素的指针，以及指向 ia 数组起始位置之后第 6 个元素的指针（即 ia 的最后一个元素的下一位置）。如果返回的指针等于 ia + 6，那么搜索不成功；否则，返回的指针指向找到值。

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:

如果需要传递一个子区间，则传递指向这个子区间的第一个元素以及最后一个元素的下一位置的迭代器（或指针）。例如，在下面对 find 函数的调用中，只搜索了 ia[1] 和 ia[2]：

    // 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:

每个泛型算法的实现都独立于单独的容器。这些算法还是大而不全的，并且不依赖于容器存储的元素类型。为了知道算法如何工作，让我们深入了解 find 操作。该操作的任务是在一个未排序的元素集合中查找特定的元素。从概念上看，find 必须包含以下步骤：

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 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:

这种算法，正如我们所指出的，与容器的类型无关：在前面的描述中，没有任何内容依赖于容器类型。这种算法只在一点上隐式地依赖元素类型：必须能够对元素做比较运算。该算法的明确要求如下：

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

需要某种遍历集合的方式：能够从一个元素向前移到下一个元素。
We need to be able to know when we have reached the end of the collection.

必须能够知道是否到达了集合的末尾。
We need to be able to compare each element to the value we want.

必须能够对容器中的每一个元素与被查找的元素进行比较。
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.

泛型算法用迭代器来解决第一个要求：遍历容器。所有迭代器都支持自增操作符，从一个元素定位下一个元素，并提供解引用操作符访问元素的值。除了第 11.3.5 节将介绍的一个例外情况之外，迭代器还支持相等和不等操作符，用于判断两个迭代是否相等。

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.

大多数情况下，每个算法都需要使用（至少）两个迭代器指出该算法操纵的元素范围。第一个迭代器指向第一个元素，而第二个迭代器则指向最后一个元素的下一位置。第二个迭代器所指向的元素［有时被称为超出末端迭代器］本身不是要操作的元素，而被用作终止遍历的哨兵（sentinel）。

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.

第三个要求——元素值的比较，有两种解决方法。默认情况下，find 操作要元素类型定义了相等（==）操作符，算法使用这个操作符比较元素。如果元素类型不支持相等（==）操作符，或者打算用不同的测试方法来比较元素，则可使用第二个版本的 find 函数。这个版本需要一个额外的参数：实现元素比较的函数名字。

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.

标准库提供了超过 100 种算法。与容器一样，算法有着一致的结构。比起死记全部一百多种算法，了解算法的设计可使我们更容易学习和使用它们。本章除了举例说明这些算法的使用之外，还将描述标准库算法的统一原理。附录 A根据操作分类列出了所有的算法。

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 对象中。

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.

泛型算法本身从不执行容器操作，只是单独依赖迭代器和迭代器操作实现。算法基于迭代器及其操作实现，而并非基于容器操作。这个事实也许比较意外，但本质上暗示了：使用“普通”的迭代器时，算法从不修改基础容器的大小。正如我们所看到的，算法也许会改变存储在容器中的元素的值，也许会在容器内移动元素，但是，算法从不直接添加或删除元素。

第 11.3.1 节将介绍标准库提供的另一种特殊的迭代器类：插入器（inserter），除了用于遍历其所绑定的序列之外，还可实现更多的功能。在给这类迭代器赋值时，在基础容器上将执行插入运算。如果算法操纵这类迭代器，迭代器将可能导致在容器中添加元素。但是，算法本身从不这么做。