11.4. Structure of Generic Algorithms

11.4. 泛型算法的结构

Just as there is a consistent design pattern behind the containers, there is a common design underlying the algorithms. Understanding the design behind the library makes it easier to learn and easier to use the algorithms. Because there are more than 100 algorithms, it is much better to understand their structure than to memorize the whole list of algorithms.

正如所有的容器都建立在一致的设计模式上一样，算法也具有共同的设计基础。理解标准算法库的设计基础有利于学习和使用算法。C++ 提供了超过一百个算法，了解它们的结构显然要比死记所有的算法更好。

The most fundamental property of any algorithm is the kind(s) of iterators it expects. Each algorithm specifies for each of its iterator parameters what kind of iterator can be supplied. If a parameter must be a random-access iterator, then we can provide an iterator for a vector or a deque, or we can supply a pointer into an array. Iterators on the other containers cannot be used with such algorithms.

算法最基本的性质是需要使用的迭代器种类。所有算法都指定了它的每个迭代器形参可使用的迭代器类型。如果形参必须为随机访问迭代器则可提供 vector 或 deque 类型的迭代器，或者提供指向数组的指针。而其他容器的迭代器不能用在这类算法上。

A second way is to classify the algorithms is as we did in the beginning of this chapter. We can categorize them by what actions they take on the elements:

另一种算法分类的方法，则如本章开头介绍的一样，根据对元素的操作将算法分为下面几种：

• Some are read-only and leave element values and ordering unchanged.

  只读算法，不改变元素的值顺序。

• Others assign new values to specific elements.

  给指定元素赋新值的算法。

• Others move values from one element to another.

  将一个元素的值移给另一个元素的算法。

As we'll see in the remainder of this section, there are two additional patterns to the algorithms: One pattern is defined by the parameters the algorithms take; the other is defined by two function naming and overloading conventions.

正如本节后续部分所介绍的，C++ 还提供了另外两种算法模式：一种模式由算法所带的形参定义；另一种模式则通过两种函数命名和重载的规范定义。

11.4.1. Algorithm Parameter Patterns

11.4.1. 算法的形参模式

Superimposed on any other classification of the algorithms is a set of parameter conventions. Understanding these parameter conventions can aid in learning new algorithmsby knowing what the parameters mean, you can concentrate on understanding the operation the algorithm performs. Most of algorithms take one of the following four forms:

任何其他的算法分类都含有一组形参规范。理解这些形参规范有利于学习新的算法——只要知道形参的含义，就可专注于了解算法实现的操作。大多数算法采用下面四种形式之一：

     alg (beg, end, other parms);
     alg (beg, end, dest, other parms);
     alg (beg, end, beg2, other parms);
     alg (beg, end, beg2, end2, other parms);

where alg is the name of the algorithm, and beg and end denote the range of elements on which the algorithm operates. We typically refer to this range as the "input range" of the algorithm. Although nearly all algorithms take an input range, the presence of the other parameters depends on the work being performed. The common ones listed heredest, beg2 and end2are all iterators. When used, these iterators fill similar roles. In addition to these iterator parameters, some algorithms take additional, noniterator parameters that are algorithm-specific.

其中，alg 是算法的名字，beg 和 end 指定算法操作的元素范围。我们通常将该范围称为算法的“输入范围”。尽管几乎所有算法都有输入范围，但算法是否使用其他形参取决于它所执行的操作。这里列出了比较常用的其他形参：dest、beg2 和 end2，它们都是迭代器。这些迭代器在使用时，充当类似的角色。除了这些迭代器形参之外，有些算法还带有其他的菲迭代器形参，它们是这些算法特有的。

Algorithms with a Single Destination Iterator

带有单个目标迭代器的算法

A dest parameter is an iterator that denotes a destination used to hold the output. Algorithms assume that it is safe to write as many elements as needed.

dest 形参是一个迭代器，用于指定存储输出数据的目标对象。算法假定无论需要写入多少个元素都是安全的。

When calling these algorithms, it is essential to ensure that the output container is sufficiently large to hold the output, which is why they are frequently called with insert iterators or ostream_iterators. If we call these algorithms with a container iterator, the algorithm assumes there are as many elements as needed in that container. 调用这些算法时，必须确保输出容器有足够大的容量存储输出数据，这正是通常要使用插入迭代器或者 ostream_iterator 来调用这些算法的原因。如果使用容器迭代器调用这些算法，算法将假定容器里有足够多个需要的元素。

If dest is an iterator on a container, then the algorithm writes its output to existing elements within the container. More commonly, dest is bound to an insert iterator (Section 11.3.1, p. 406) or an ostream_iterator. An insert iterator adds elements to the container, ensuring that there is enough space. An ostream_iterator writes to an output stream, again presenting no problem regardless of how many elements are written.

如果 dest 是容器上的迭代器，则算法将输出内容写到容器中已存在的元素上。更普遍的用法是，将 dest 与某个插入迭代器（第 11.3.1 节）或者 ostream_iterator 绑定在一起。插入迭代器在容器中添加元素，以确保容器有足够的空间存储输出。ostream_iterator 则实现写输出流的功能，无需要考虑所写的元素个数。

Algorithms with a Second Input Sequence

带第二个输入序列的算法

Algorithms that take either beg2 alone or beg2 and end2 use these iterators to denote a second input range. These algorithms typically use the elements from the second range in combination with the input range to perform a computation. When an algorithm takes both beg2 and end2, these iterators are used to denote the entire second range. That is, the algorithm takes two completely specified ranges: the input range denoted by beg and end, and a second input range denoted by beg2 and end2.

有一些算法带有一个 beg2 迭代器形参，或者同时带有 beg2 和 end2 迭代器形参，来指定它的第二个输入范围。这类算法通常将联合两个输入范围的元素来完成计算功能。算法同时使用 beg2 和 end2 时，这些迭代器用于标记完整的第二个范围。也就是说，此时，算法完整地指定了两个范围：beg 和 end 标记第一个输入范围，而 beg2 和 end2 则标记第二个输入范围。

Algorithms that take beg2 but not end2 treat beg2 as the first element in the second input range. The end of this range is not specified. Instead, these algorithms assume that the range starting at beg2 is at least as large as the one denoted by beg, end.

带有 beg2 而不带 end2 的算法将 beg2 视为第二个输入范围的首元素，但没有指定该范围的最后一个元素。这些算法假定以 beg2 开始的范围至少与 beg 和 end 指定的范围一样大。

As with algorithms that write to dest, algorithms that take beg2 alone assume that the sequence beginning at beg2 is as large as the range denoted by beg and end. 与写入 dest 的算法一样，只带有 beg2 的算法也假定以 beg2 开始的序列与 beg 和 end 标记的序列一样大。

11.4.2. Algorithm Naming Conventions

11.4.2. 算法的命名规范

The library uses a set of consistent naming and overload conventions that can simplify learning the library. There are two important patterns. The first involves algorithms that test the elements in the input range, and the second applies to those that reorder elements within the input range.

标准库使用一组相同的命名和重载规范，了解这些规范有助于更容易地学习标准库。它们包括两种重要模式：第一种模式包括测试输入范围内元素的算法，第二种模式则应用于对输入范围内元素重新排序的算法。

Distinguishing Versions that Take a Value or a Predicate

区别带有一个值或一个谓词函数参数的算法版本

Many algorithms operate by testing elements in their input range. These algorithms typically use one of the standard relational operators, either == or <. Most of the algorithms provide a second version that allows the programmer to override the use of the operator and instead to supply a comparison or test function.

很多算法通过检查其输入范围内的元素实现其功能。这些算法通常要用到标准关系操作符：== 或 <。其中的大部分算法会提供第二个版本的函数，允许程序员提供比较或测试函数取代操作符的使用。

Algorithms that reorder the container elements use the < operator. These algorithms define a second, overloaded version that takes an additional parameter representing a different operation to use to order the elements:

重新对容器元素排序的算法要使用 < 操作符。这些算法的第二个重载版本带有一个额外的形参，表示用于元素排序的不同运算：

     sort (beg, end);         // use < operator to sort the elements
     sort (beg, end, comp);   // use function named comp to sort the elements

Algorithms that test for a specific value use the == operator by default. These algorithms provide a second namednot overloadedversion with a parameter that is a predicate (Section 11.2.3, p. 402). Algorithms that take a predicate have the suffix _if appended:

检查指定值的算法默认使用 == 操作符。系统为这类算法提供另外命名的（而非重载的）版本，带有谓词函数（第 11.2.3 节）形参。带有谓词函数形参的算法，其名字带有后缀 _if：

     find(beg, end, val);       // find first instance of val in the input range
     find_if(beg, end, pred);   // find first instance for which pred is true

These algorithms both find the first instance of a specific element in the input range. The find algorithm looks for a specific value; the find_if algorithm looks for a value for which pred returns a nonzero value.

上述两个算法都在输入范围内寻找指定元素的第一个实例。其中，find 算法查找一个指定的值，而 find_if 算法则用于查找一个使谓词函数 pred 返回非零值的元素。

The reason these algorithms provide a named version rather than an over-loaded one is that both versions take the same number of parameters. In the case of the ordering algorithms, it is easy to disambiguate a call based solely on the number of parameters. In the case of algorithms that look for a specific element, the number of parameters is the same whether testing for a value or testing a predicate. Overloading ambiguities (Section 7.8.2, p. 269) would therefore be possible, albeit rare, and so the library provides two named versions for these algorithms rather than relying on overloading.

标准库为这些算法提供另外命名的版本，而非重载版本，其原因在于这个两种版本的算法带有相同数目的形参。对于排序算法，只要根据参数的个数就很容易消除函数调用的歧义。而对于查找指定元素的算法，不管检查的是一个值还是谓词函数，函数调用都需要相同个数的参数。此时，如果使用重载版本，则可能导致二义性（第 7.8.2 节），尽管这个可能出现的几率很低。因此，标准库为这些算法提供两种不同名字的版本，而没有使用重载。

Distinguishing Versions that Copy from Those that Do Not

区别是否实现复制的算法版本

Independently of whether an algorithm tests its elements, the algorithm may re-arrange elements within the input range. By default, such algorithms write the rearranged elements back into their input range. These algorithms also provide a second, named version that writes to a specified output destination. These algorithms append _copy to their names:

无论算法是否检查它的元素值，都可能重新排列输入范围内的元素。在默认情况下，这些算法将重新排列的元素写回其输入范围。标准库也为这些算法提供另外命名的版本，将元素写到指定的输出目标。此版本的算法在名字中添加了 _copy 后缀：

     reverse(beg, end);
     reverse_copy(beg, end, dest);

The reverse function does what its name implies: It reverses the order of the elements in the input sequence. The first version reverses the elements in the input sequence itself. The second version, reverse_copy, makes a copy of the elements, placing them in reverse order in the sequence that begins at dest.

reverse 函数的功能就如它的名字所意味的：将输入序列中的元素反射重新排列。其中，第一个函数版本将自己的输入序列中的元素反向重排。而第二个版本，reverse_copy，则复制输入序列的元素，并将它们逆序存储到 dest 开始的序列中。