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

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.

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.

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

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

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.

##### 带第二个输入序列的算法

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.

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.

 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. 算法的命名规范

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.

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

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:

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

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.

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

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:

```     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 开始的序列中。

## Exercises Section 11.4.2

 Exercise 11.27: The library defines the following algorithms: 标准库定义了下面的算法： ``` replace(beg, end, old_val, new_val); replace_if(beg, end, pred, new_val); replace_copy(beg, end, dest, old_val, new_val); replace_copy_if(beg, end, dest, pred, new_val); ``` Based only on the names and parameters to these functions, describe the operation that these algorithms perform. 只根据这些函数的名字和形参，描述这些算法的功能。 Exercise 11.28: Assume lst is a container that holds 100 elements. Explain the following program fragment and fix any bugs you think are present. 假设 lst 是存储了 100 个元素的容器。请解释下面的程序段，并修正你认为的错误。 ``` vector vec1; reverse_copy(lst.begin(), lst.end(), vec1.begin()); ```