Section A.2. A Brief Tour of the Algorithms

Chapter 11 introduced the generic algorithms and outlined their underlying architecture. The library defines more than 100 algorithms. Learning to use them requires understanding their structure rather than memorizing the details of each algorithm. In this section we describe each of the algorithms. In it, we organize the algorithms by the type of action the algorithm performs.

第十一章介绍一般算法并列出了它们的底层体系结构。标准库定义了 100 多个算法，学习如何使用它们需要理解它们的结构，而不是记住每个算法的细节。本节描述每个算法，其中，按算法执行行为的类型组织这些算法。

A.2.1. Algorithms to Find an Object

A.2.1. 查找对象的算法

The find and count algorithms search the input range for a specific value. find returns an iterator to an element; count returns the number of matching elements.

find 和 count 算法在输入范围中查找指定值。find 返回元素的迭代器，count 返回匹配元素的数目。

Simple Find Algorithms

简单查找算法

These algorithms require input iterators. The find and count algorithms look for specific elements. The find algorithms return an iterator referring to the first matching element. The count algorithms return a count of how many times the element occurs in the input sequence.

这些算法要求输入迭代器。find 和 count 算法查找特定元素，find 算法返回引用第一个匹配元素的迭代器，count 算法返回元素在输入序列中出现次数的计数。

Looks for element(s) in input range equal to val. Uses the equality (==) operator of the underlying type. find returns an iterator to the first matching element or end if no such element exists. count returns a count of how many times val occurs.

在输入范围中查找等于 val 的元素，使用基础类型的相等（==）操作符。find 返回第一个匹配元素的迭代器，如果不存在在匹配元素就返回 end。count 返回 val 出现次数的计数。

Looks for element(s) in input range for which unaryPred is true. The predicate must take a single parameter of the value_type of the input range and return a type that can be used as a condition.

在 unaryPred 为真的输入范围中查找。谓词必须接受一个形参，形参类型为输入范围的 value_type，并且返回可以用作条件的类型。

find_if returns an iterator to first element for which unaryPred is true, or end if no such element exists. count_if applies unaryPred to each element and returns the number of elements for which unaryPred was true.

find_if 返回第一个使 unaryPred 为真的元素的迭代器，如果不存在这样的元素就返回 end。count_if 对每个元素应用 unaryPred。并返回使 unaryPred 为真的元素的数目。

Algorithms to Find One of Many Values

查找许多值中的一个的算法

These algorithms require two pairs of forward iterators. They search for the first (or last) element in the first range that is equal to any element in the second range. The types of beg1 and end1 must match exactly, as must the types of beg2 and end2.

这些算法要求两对前向迭代器。它们在第一个范围中查找与第二个范围中任意元素相等的第一个（或最后一个）元素。beg1 和 end1 的类型必须完全匹配，beg2 和 end2 的类型也必须完全匹配。

There is no requirement that the types of beg1 and beg2 match exactly. However, it must be possible to compare the element types of the two sequences. So, for example, if the first sequence is a list<string>, then the second could be a vector<char*>.

不要求 beg1 和 beg2 的类型完全匹配，但是，必须有可能对这两个序列的元素类型进行比较。例如，如果第一个序列是 list<string>，则第二个可以是 vector<char*>。

Each algorithm is overloaded. By default, elements are tested using the == operator for the element type. Alternatively, we can specify a predicate that takes two parameters and returns a bool indicating whether the test between these two elements succeeds or fails.

每个算法都是重载的。默认情况下，使用元素类型的 == 操作符测试元素，或者，可以指定一个谓词，该谓词接受两个形参，并返回表示这两个元素间的测试成功或失败的 bool 值。

Returns an iterator to the first occurrence in the first range of any element from the second range. Returns end1 if no match found.

返回第二个范围的任意元素在第一个范围的首次出现的迭代器，如果找不到匹配就返回 end1。

Uses binaryPred to compare elements from each sequence. Returns an iterator to the first element in the first range for which the binaryPred is true when applied to that element and an element from the second sequence. Returns end1 if no such element exits.

使用 binaryPred 比较来自两个序列的元素，返回第一个范围中第一个这种元素的迭代器：当对该元素和来自第二个范围的一个元素应用 binaryPred 的时候，binaryPred 为真。如果不存在这样的元素，就返回 end1。

Operates like find_first_of, except that it searches for the last occurrence of any element from the second sequence.

与 find_first_of 想像的操作符，只不过它查找来自第二个序列的任意元素的最后一次出现。

As an example, if the first sequence is 0,1,1,2,2,4,0,1 and the second sequence is 1,3,5,7,9, then find_end would return an iterator denoting the last element in the input range, and find_first_of would return an iterator to the second elementin this example, it returns the first 1 in the input sequence.

作为例子，如果第一个序列是 0, 1, 1, 2, 2, 4, 0, 1 而第二个序列是 1, 3, 5, 7, 9，则 find_end 返回表示输入范围中最后一个元素的迭代器，而 find_first_of 将返回第二个元素的迭代器——本例中，它返回输入序列中的第一个 1。

Algorithms to Find a Subsequence

查找子序列的算法

These algorithms require forward iterators. They look for a subsequence rather than a single element. If the subsequence is found, an iterator is returned to the first element in the subsequence. If no subsequence is found, the end iterator from the input range is returned.

这些算法要求前向迭代器。它们查找子序列而不是单个元素。如果找到了子序列，就返回子序列中第一个元素的迭代器；如果找不到子序列，就返回输入范围的 end 迭代器。

Each function is overloaded. By default, the equality (==) operator is used to compare elements; the second version allows the programmer to supply a predicate to test instead.

每个函数都是重载的。默认情况下，使用相等操作符（==）比较元素；第二个版本允许程序员提供一个谓词代替（==）进行测试。

Returns an iterator to the first adjacent pair of duplicate elements. Returns end if there are no adjacent duplicate elements. In the first case, duplicates are found by using ==. In the second, duplicates are those for which the binaryPred is true.

返回重复元素的第一个相邻对。如果没有相邻的重复元素。就返回 end。在第一种情况下，使用 == 找到重复元素，第二种情况下，重复元素是使 binaryPred 为真的那些元素。

Returns an iterator to the first position in the input range at which the second range occurs as a subsequence. Returns end1 if the subsequence is not found. The types of beg1 and beg2 may differ but must be compatible: It must be possible to compare elements in the two sequences.

返回输入范围中第二个范围作为子序列出现的第一个位置。如果找不到子序列，就返回 end1。beg1 和 beg2 的类型可以不同，但必须是兼容的：必须能够比较两个序列中的元素。

Returns an iterator to the beginning of a subsequence of count equal elements. Returns end if no such subsequence exists. The first version looks for count occurrences of the given value; the second version count occurrences for which the binaryPred is true.

返回 count 个相等元素的子串的开关迭代器。如果不存在这样的子串，就返回 end。第一个版本查找给定 val 的 count 次出现，第二个版本查找使 binaryPred 为真的 count 次出现。

A.2.2. Other Read-Only Algorithms

A.2.2. 其他只读算法

These algorithms require input iterators for their first two arguments. The equal and mismatch algorithms also take an additional input iterator that denotes a second range. There must be at least as many elements in the second sequence as there are in the first. If there are more elements in the second, they are ignored. If there are fewer, it is an error and results in undefined run-time behavior.

这些算法要求用于前两个实参的输入迭代器。equal 和 mismatch 算法还接受一个附加输入迭代器，该迭代器表示第二个范围。第二个序列中的元素至少与第一个序列一样多，如果第二个序列元素较多，就忽略多余元素；如果第二个序列元素较少，就会出错并导致未定义的运行时行为。

As usual, the types of the iterators denoting the input range must match exactly. The type of beg2 must be compatible with the type of beg1. That is, it must be possible to compare elements in both sequences.

照常，表示输入范围的迭代器的类型必须完全匹配。beg2 的类型必须与 beg1 的类型兼容，即必须能够比较两个序列中的元素。

The equal and mismatch functions are overloaded: One version uses the element equality operator (==) to test pairs of elements; the other uses a predicate.

equal 和 mismatch 函数是重载的：一个版本使用元素相等操作符（==）测试元素对，另一个使用谓词。

Applies the function (or function object (Section 14.8, p. 530)) f to each element in its input range. The return value, if any, from f is ignored. The iterators are input iterators, so the elements may not be written by f. Typically, for_each is used with a function that has side effects. For example, f might print the values in the range.

对其输入范围中的每个元素应用函数（或函数对象（第 14.8 节））f。如果 f 有返回值，就忽略该返回值。迭代器是输入迭代器，所以 f 不能写元素。通常，用有副作用的函数使用 for_each。例如，f 可以显示范围中的值。

Compares the elements in two sequences. Returns a pair of iterators denoting the first elements that do not match. If all the elements match, then the pair returned is end1, and an iterator into beg2 offset by the size of the first sequence.

比较两个序列中的元素，返回一对表示第一个不匹配元素的迭代器。如果所有元素都匹配，则返回的 pair 是 end1，以及 beg2 中偏移量为第一个序列长度的迭代器。

Determines whether two sequences are equal. Returns true if each element in the input range equals the corresponding element in the sequence that begins at beg2.

确定两个序列是否相等。如果输入范围中的每个元素都与从 beg2 开始的序列中的对应元素相等，就返回 true。

For example, given the sequences meet and meat, a call to mismatch would return a pair containing iterators referring to the second e in the first sequence and to the element a in the second sequence. If, instead, the second sequence were meeting, and we called equal, then the pair returned would be end1 and an iterator denoting the element i in the second range.

例如，给定序列 meet 和 meat，对 mismatch 的调用将返回一个 pair 对象，其中包含指向第一个序列中第二个 e 的迭代器，以及指向第二个序列中元素 a 的迭代器。如果，第二个序列是 meeting，并调用 equal，则返回的将是 end1 和表示第二个范围中元素 i 的迭代器。

A.2.3. Binary-Search Algorithms

A.2.3. 二分查找算法

Although these algorithms may be used with forward iterators, they offer specialized versions that are much faster when used with random-access iterators.

虽然可以与前向迭代器一起使用这些算法，它们还是提供了随机访问迭代器一起使用的特殊版本，它们的速度更快。

These algorithms perform a binary search, which means that the input sequence must be sorted. These algorithms behave similarly to the associative container members of the same name (Section 10.5.2, p. 377). The equal_range, lower_bound, and upper_bound algorithms return an iterator that refers to the positions in the container at which the given element could be inserted while still preserving the container's ordering. If the element is larger than any other in the container, then the iterator that is returned might be the off-the-end iterator.

这些算法执行二分查找，这意味着输入序列必须是已排列的。这些算法的表现类似于同名的关联容器成员（第 10.5.2 节）。equal_range、lower_bound 和 upper_bound 算法返回一个迭代器，该迭代器指向容器中的位置，可以将给定元素插入到这个位置而仍然保持容器的排序。如果元素比容器中任意其他元素都大，则返回的迭代器会是超出末端迭代器。

Each algorithm provides two versions: The first uses the element type's less-than operator (<) to test elements; the second uses the specified comparison.

每个算法提供两个版本：第一个使用元素类型的小于操作符（<）测试元素，第二个使用指定的比较关系。

Returns an iterator to the first position in which val can be inserted while preserving the ordering.

返回第一个这种位置的迭代器：可以将 val 插入到该位置而仍然保持顺序。

Returns an iterator to the last position in which val can be inserted while preserving the ordering.

返回最后一个这种位置的迭代器：可以将 val 插入到该位置而仍然保持顺序。

Returns an iterator pair indicating the subrange in which val could be inserted while preserving the ordering.

返回一个表示子范围的迭代器对，可以将 val 插入到该子范围而仍然保持顺序。

Returns a bool indicating whether the sequence contains an element that is equal to val. Two values x and y are considered equal if x < y and y <x both yield false.

返回一个 bool 值，表示序列是否包含与 val 相等的元素。如果 x < y 和 y <x 都获得假值，就认为两个值 x 和 y相等。

A.2.4. Algorithms that Write Container Elements

A.2.4. 写容器元素的算法

Many algorithms write container elements. These algorithms can be distinguished both by the kinds of iterators on which they operate and by whether they write elements in the input range or write to a specified destination.

许多算法写容器元素。可以根据所操作的迭代器种类，以及是写输入范围的元素还是写到特定目的地，来区分这些算法。

The simplest algorithms read elements in sequence, requiring only input iterators. Those that write back to the input sequence require forward iterators. Some read the sequence backward, thus requiring bidirectional iterators. Algorithms that write to a separate destination, as usual, assume the destination is large enough to hold the output.

最简单的算法读序列中的元素，只要求输入迭代器。那些写回输入序列的算法要求前向迭代器。一些算法反向读取序列，所以要求双向迭代器。写至单独目的地的算法，照常假定目的地足以保存输入。

Algorithms that Write but do Not Read Elements

只写元素不读元素的算法

These algorithms require an output iterator that denotes a destination. They take a second argument that specifies a count and write that number of elements to the destination.

这些算法要求表示目的地的输出迭代器。它们接受指定数量的第二个实参并将该数目的元素写到目的地。

Write cnt values to dest. The fill_n function writes cnt copies of the value val; generate_n evaluates the generator Gen() cnt times. A generator is a function (or function object (Section 14.8, p. 530)) that is expected to produce a different return value each time it is called.

将 cnt 个值写到 dest。fill_n 函数写 val 值的 cnt 个副本，generate_n 对发生器 Gen() 进行 cnt 次计算。发生器是一个函数（或函数对象（第 14.8 节）），每次调用它都期待产生一个不同的返回值。

Algorithms that Write Elements Using Input Iterators

使用输入迭代器写元素的算法

Each of these operations reads an input sequence and writes to an output sequence denoted by dest. They require dest to be an output iterator, and the iterators denoting the input range must be input iterators. The caller is responsible for ensuring that dest can hold as many elements as necessary given the input sequence. These algorithms return dest incremented to denote one past the last element written.

这些操作每一个读一个输入序列，并写到由 dest 表示的输出序列。它们要求 dest 是一个输出迭代器，而表示输入范围的迭代器必须是输入迭代器。调用者负责保证 dest 可以保存给定输入序列所需数量的元素。这些算法返回 dest，dest 增量至指向所写最后元素的下一位置。

Applies the specified operation to each element in the input range, writing the result to dest. The first version applies a unary operation to each element in the input range. The second applies a binary operation to pairs of elements. It takes the first argument to the binary operation from the sequence denoted by beg and end and takes the second argument from the sequence beginning at beg2. The programmer must ensure that the sequence beginning at beg2 has at least as many elements as are in the first sequence.

对输入范围中每个元素应用指定操作。将结果写到 dest。第一个版本对输入范围中每个元素应用一元操作。第二个版本对元素对应用二元操作，它从由 beg 和 end 表示的序列接受二元操作的第一个实参，从开始于 beg2 的第二个序列接受第二个实参。程序员必须保证开始于 beg2 的序列具有至少与第一个序列一样多的元素。

Copies each element to dest, replacing specified elements by the new_val. The first version replaces those elements that are == to old_val. The second version replaces those elements for which unaryPred is true.

将每个元素复制到 dest，用 new_val 代替指定元素。第一个版本代替那些 ==old_val 的元素，第二个版本代替那些使 unaryPred 为真的元素。

Both input sequences must be sorted. Writes a merged sequence to dest. The first version compares elements using the < operator; the second version uses the given comparison.

两个输入序列都必须是已排序的。将合并后的序列写至 dest。第一个版本 < 操作符比较元素，第二个版本使用给定的比较关系。

Algorithms that Write Elements Using Forward Iterators

使用前向迭代器写元素的算法

These algorithms require forward iterators because they write elements in their input sequence.

这些算法要求前向迭代器，因为它们修改输入序列中的元素。

Parameters to these functions are references, so the arguments must be writable. Swaps the specified element or elements denoted by the given iterators.

这些函数的形参是引用，所以实参必须是可写的。交换指定元素或由给定迭代器表示的元素。

Swaps the elements in the input range with those in the second sequence beginning at beg2. The ranges must not overlap. The programmer must ensure that the sequence starting at beg2 is at least as large as the input sequence. Returns beg2 incremented to denote the element just after the last one swapped.

用开始于 beg2 的第二个序列中的元素交换输入范围中的元素。范围必须不重叠。程序员必须保证开始于 beg2 的序列至少与输入序列一样大。返回 beg2，beg2 增量到指向被交换的最后一个元素之后的元素。

Assigns a new value to each element in the input sequence. fill assigns the value val; generate executes Gen() to create new values.

将新值赋给输入序列中的每个元素。fill 赋 val 值，generate 执行 Gen() 来创建新值。

Replace each matching element by new_val. The first version uses == to compare elements with old_val; the second version executes unaryPred on each element, replacing those for which unaryPred is true.

用 new_val 代替每个匹配元素。第一个版本使用 == 将元素和 old_val 比较，第二个版本对每个元素执行 unaryPred，代替使 unaryPred 为真的那些元素。

Algorithms that Write Elements Using Bidirectional Iterators

使用双向迭代器写元素的算法

These algorithms require the ability to go backward in the sequence, and so they require bidirectional iterators.

这些算法要求在序列中往回走的能力，所以它们要求双向迭代器。

Copies elements in reverse order to the output iterator dest. Returns dest incremented to denote one past the last element copied.

按逆序将元素复制到输出迭代器 dest。返回 dest，dest 增量至指向被复制的最后一个元素的下一位置。

Merges two adjacent subsequences from the same sequence into a single, ordered sequence: The subsequences from beg to mid and from mid to end are merged into beg to end. First version uses < to compare elements; second version uses a specified comparison. Returns void.

将同一序列中的两个相邻子序列合并为一个有序序列：将从 beg 到 mid 和从 mid 到 end 的子序列合并为从 beg 到 end 的序列。第一个版本使用 < 比较元素，第二个版本使用指定的比较关系。返回 void。

A.2.5. Partitioning and Sorting Algorithms

A.2.5. 划分与排序算法

The sorting and partitioning algorithms provide various strategies for ordering the elements of a container.

A partition divides elements in the input range into two groups. The first group consists of those elements that satisfy the specified predicate; the second, those that do not. For example, we can partition elements in a container based on whether the elements are odd, or on whether a word begins with a capital letter, and so forth.

partition 将输入范围中的元素划分为两组，第一组由满足给定谓词的元素构成，第二组由不满足谓词的元素构成。例如，可以根据元素是否为奇数划分容器中的元素，或者，根据单词是否以大写字母开头，诸如此类。

Each of the sorting and partitioning algorithms provides stable and unstable versions. A stable algorithm maintains the relative order of equal elements. For example, given the sequence

每个排序和划分算法都提供稳定和不稳定版本，稳定算法维持相等元素的相对次序。例如，给定序列

a stable partition based on whether a word begins with a capital letter generates the sequence in which the relative order of the two word categories is maintained:

基于单词是否以大写字母开头的稳定算法，产生维持两个单词类的相对次序的序列：

The stable algorithms do more work and so may run more slowly and use more memory than the unstable counterparts.

稳定算法完成更多工作，因此相比于不稳定算法，可能运行慢且使用更多内存。

Partitioning Algorithms

划分算法

Uses unaryPred to partition the input sequence. Elements for which unaryPred is true are put at the beginning of the sequence; those for which the predicate is false are at the end. Returns an iterator just past the last element for which unaryPred is true.

使用 unaryPred 划分输入序列。使 unaryPred 为真的元素放在序列开头，使 unaryPred 为假的元素放在序列末尾。返回一个迭代器，该迭代器指向使 unaryPred 为真的最后元素的下一位置。

Sorting Algorithms

排序算法

These algorithms require random-access iterators. Each of the sorting algorithms provides two overloaded versions. One version uses element operator < to compare elements; the other takes an extra parameter that specifies the comparison. These algorithms require random-access iterators. With one exception, these algorithms return void; partial_sort_copy returns an itertor into the destination.

这些算法要求随机访问迭代器。每个排序算法都提供两个重载版本，一个版本使用元素操作符 < 比较元素，另一个版本接受一个指定比较关系的额外形参。这些算法返回 void，除了一个例外，partial_sort_copy 返回目的地迭代器。

The partial_sort and nth_element algorithms do only part of the job of sorting the sequence. They are often used to solve problems that might otherwise be handled by sorting the entire sequence. Because these operations do less work, they typically are faster than sorting the entire input range.

partial_sort 和 nth_element 算法只完成序列排序的部分工作，经常用它们解决通过对整个序列排序来处理的问题。因为这些操作做的工作较少，所以它们一般比排序整个输入范围要快一些。

Sorts a number of elements equal to mid beg. That is, if mid beg is equal to 42, then this function puts the lowest-valued elements in sorted order in the first 42 positions in the sequence. After partial_sort completes, the elements in the range from beg up to but not including mid are sorted. No element in the sorted range is larger than any element in the range after mid. The order among the unsorted elements is unspecified.

对 mid beg 个元素进行排序，也就是说，如果 mid beg 等于 42，则该函数将有序次序中的最小值元素放在序列中前 42 个位置。partial_sort 完成之后，从 beg 到 mid（但不包括 mid）范围内的元素是有序的。已排序范围内没有元素大于 mid 之后的元素。未排序元素之间的次序是未指定的。

As an example, we might have a collection of race scores and want to know what the first-, second- and third-place scores are but don't care about the order of the other times. We might sort such a sequence as follows:

例如，有一个赛跑成绩的集合，我们想要知道前三名的成绩但并不关心其他名次的次序，可以这样对这个序列进行排序：

Sorts elements from the input range and puts as much of the sorted sequence as fits into the sequence denoted by the iterators destBeg and destEnd. If the destination range is the same size or has more elements than the input range, then the entire input range is sorted and stored starting at destBeg. If the destination size is smaller, then only as many sorted elements as will fit are copied.

对输入序列中的元素进行排序，将已排序序列中适当数目的元素放入由迭代器 destBeg 和 destEnd 表示的序列。如果目的地范围与输入范围一样大，或者比输入范围大，则将整个输入范围排序且有序序列从 destBeg 开始。如果目的地较小，则只复制适当数目的有序元素。

Returns an iterator into the destination that refers just after the last element that was sorted. The returned iterator will be destEnd if that destination sequence is smaller or equal in size to the input range.

返回目的地中的迭代器，指向已排序的最后一个元素之后。如果目的地序列比输入范围小或者与输入范围大小相等，返回的迭代器将是 destEnd。

The argument nth must be an iterator positioned on an element in the input sequence. After nth_element, the element denoted by that iterator has the value that would be there if the entire sequence were sorted. The elements in the container are also partitioned around nth: Those before nth are all smaller than or equal to the value denoted by nth, and the ones after it are greater than or equal to it. We might use nth_element to find the value closest to the median:

实参 nth 必须是一个迭代器，定位输入序列中的一个元素。运行 nth_element 之后，该迭代器表示的元素的值就是：如果整个序列是已排序的，这个位置上应放置的值。容器中的元素也围绕 nth 划分：nth 之前的元素都小于或等于 nth 所表示的值，nth 之后的元素都大于或等于它。可以使用 nth_element 查找与中值最接近的值：

A.2.6. General Reordering Operations

A.2.6. 通用重新排序操作

Several algorithms reorder the elements in a specified way. The first two, remove and unique, reorder the container so that the elements in the first part of the sequence meet some criteria. They return an iterator marking the end of this subsequence. Others, such as reverse, rotate, and random_shuffle rearrange the entire sequence.

有几个算法用指定方法对元素进行重新排序。最前面的两个 remove 和 unique 对容器重新排序，以便序列中的第一部分满足一些标准，它们返回标志这个子序列的末尾的迭代器。其他算法，如 reverse、rotate 和 random_shuffle，重新安排整个序列。

These algorithms operate "in place;" they rearrange the elements in the input sequence itself. Three of the reordering algorithms offer "copying" versions. These algorithms, remove_copy, rotate_copy, and unique_copy, write the reordered sequence to a destination rather than rearranging elements directly.

这些算法“就地”操作，它们在输入序列本身中重新安排元素。三个重新排序算法提供“复制”版本。算法 remove_copy、rotate_copy 和 unique_copy，将重新排序之后的序列写至目的地，而不是直接重新安排元素。

Reordering Algorithms Using Forward Iterators

使用前向迭代器的重新排序算法

These algorithms reorder the input sequence. They require that the iterators be at least forward iterators.

这些算法对输入序列进行重新排序。它们要求迭代器至少是前向迭代器。

"Removes" elements from the sequence by overwriting them with elements that are to be kept. The removed elements are those that are == to val or for which unaryPred is true. Returns an iterator just past the last element that was not removed.

通过用要保存的元素覆盖元素而从序列中“移去”元素。被移支的元素是 ==val 或使 unaryPred 为真的那些元素。返回一个迭代器，该迭代器指向未移去的最后一个元素的下一位置。

For example, if the input sequence is hello world and val is o, then a call to remove will overwrite the two elements that are the letter 'o' by shifting the sequence to the left twice. The new sequence will be hell wrldld. The returned iterator will denote the element after the first d.

例如，如果输入序列是 hello world 而 val 是 o，则 remove 调用将序列左移两次覆盖两个元素，即字母 'o'。新序列将是 hell wrldld，返回的迭代器将指向第一个 d 之后的元素。

"Removes" all but the first of each consecutive group of matching elements. Returns an iterator just past the last unique element. First version uses == to determine whether two elements are the same; second version uses the predicate to test adjacent elements.

“移去”匹配元素的每个连续组，除了第一个之外。返回一个迭代器，该迭代器指向最后一个单一元素的下一位置。第一个版本使用 == 确定两个元素是否相同，第二个版本使用谓词测试相邻元素。

For example, if the input sequence is boohiss, then after the call to unique, the first sequence will contain bohisss. The iterator returned will point to the element after the first s. The value of the remaining two elements in the sequence is unspecified.

例如，如果输入序列是 boohiss，则调用 unique 之后，第一个序列将包含 bohisss。返回的迭代器指向第一个 s 之后的元素，序列中剩余的两个元素的值是未指定的。

Rotates the elements around the element denoted by mid. The element at mid becomes the first element; those from mid + 1 through end come next, followed by the range from beg to mid. Returns void.

围绕由 mid 表示的元素旋转元素。mid 处的元素成为第一个元素，从 mid + 1 到 end 的元素其次，后面是从 beg 到 mid 的范围。返回 void。

For example, given the input sequence hissboo, if mid denotes the character b, then rotate would reorder the sequence as boohiss.

例如，给定输入序列 hissboo，如果 mid 表示字符 b，则旋转将序列重新排序为 boohiss。

Reordering Algorithms Using Bidirectional Iterators

使用双向迭代器的重新排序算法

Because these algorithms process the input sequence backward, they requre bidirectional iterators.

因为这些算法向后处理输入序列，所以它们要求双向迭代器。

Reverses the elements in the sequence. reverse operates in place; it writes the rearranged elements back into the input sequence. reverse_copy copies the elements in reverse order to the output iterator dest. As usual, the programmer must ensure that dest can be used safely. reverse returns void; reverse_copy returns an iterator just past the last element copied into the destination.

颠倒序列中的元素。reverse 就地操作，它将重新安排的元素写回输入序列。reverse_copy 将元素按逆序复制到输出迭代器 dest。照常，程序员必须保证可以安全块使用 dest。reverse 返回 void，reverse_copy 返回一个迭代器，该迭代器指向复制到目的地的最后一个元素的下一位置。

Reordering Algorithms Writing to Output Iterators

写至输出迭代器的重新排序算法

These algorithms require forward iterators for the input sequence and an output iterator for the destination.

这些算法要求输入序列的前向迭代器以及目的地的输出迭代器。

Each of the preceding general reordering algorithms has an _copy version. These _copy versions perform the same reordering but write the reordered elements to a specified destination sequence rather than changing the input sequence. Except for rotate_copy, which requires forward iterators, the input range is specified by input iterators. The dest iterator must be an output iterator and, as usual, the programmer must guarantee that the destination can be written safely. The algorithms return the dest iterator incremented to denote one past the last element copied.

前面的每个通用重新排序算法都有一个 _copy 版本，这些 _copy 版本执行相同的重新排序，但是将重新排序之后的元素写至指定目的地序列，而不是改变输入序列。除 rotate_copy（它要求前向迭代器）之外，其他的都由迭代器指定输入范围。dest 迭代器必须是输出迭代器，而且，程序员也必须保证可以安全地写目的地。这些算法返回 dest 迭代器，dest 迭代器增量至指向被复制的最后元素的下一位置。

Copies elements except those matching val or for which unaryPred return true into dest.

除了与 val 匹配或使 unaryPred 返回真的元素之外，其他元素都复制到 dest。

Like rotate except that it leaves its input sequence unchanged and writes the rotated sequence to dest. Returns void.

除了保持输入序列不变并将旋转后的序列写至 dest 之外，与 rotated 很像。返回 void。

Reordering Algorithms Using Random-Access Iterators

使用随机访问迭代器的重新排序算法

Because these algorithms rearrange the elements in a random order, they require random-access iterators.

因为这些算法按随机次序重新安排元素，所以它们要求随机访问迭代器。

Shuffles the elements in the input sequence. The second version takes a random-number generator. That function must take and return a value of the iterator's difference_type. Both versions return void.

打乱输入序列中的元素。第二个版本接受随机数发生器，该函数必须接受并返回迭代器的 difference_type 值。两个版本都返回 void。

A.2.7. Permutation Algorithms

A.2.7. 排列算法

Consider the following sequence of three characters: abc. There are six possible permutations on this sequence: abc, acb, bac, bca, cab, and cba. These permutations are listed in lexicographical order based on the less-than operator. That is, abc is the first permutation because its first element is less than or equal to the first element in every other permutation, and its second element is smaller than any permutation sharing the same first element. Similarly, acb is the next permutation because it begins with a, which is smaller than the first element in any remaining permutation. Those permutations that begin with b come before those that begin with c.

考虑下面的三个字符的序列：abc。这个序列有 6 种可能的排列：abc, acb, bac, bca, cab 和 cba。基于小于操作符按字典序列出这些排列，即，abc 是第一排列，因为它的第一个元素小于或等于其他每个排列中的首元素，而且，它的第二个元素小于首元素的任意排列中的第二个元素。类似地，acb 是下一个排列，因为它以 a 开头，a 小于其余任意排列中的首元素。以 b 开关的那些排列出现在以 c 开头的那些之前。

For any given permutation, we can say which permutation comes before it and which after it. Given the permutation bca, we can say that its previous permutation is bac and that its next permutation is cab. There is no previous permutation of the sequence abc, nor is there a next permutation of cba.

对于任意给定排列而言，可以指出哪个排列出现在它之前以及哪个出现在它之后。给定排列 bca，可以指出它的前一排列是 bac，它的下一排列是 cab。序列 abc 之前没有排列，cba 之后也没有下一排列。

The library provides two permutation algorithms that generate the permutations of a sequence in lexicographical order. These algorithms reorder the sequence to hold the (lexicographically) next or previous permutation of the given sequence. They return a bool that indicates whether there was a next or previous permutation.

标准库提供两个排列算法，按字典序产生序列的排列。这些算法重新排列序列，以便（按字典序）保存给定序列的下一个或前一个排列。它们返回指出是否存在下一个或前一个排列的 bool 值。

The algorithms each have two versions: One uses the element type < operator, and the other takes an extra argument that specifies a comparison to use to compare the elements. These algorithms assume that the elements in the sequence are unique. That is, the algorithms assume that no two elements in the sequence have the same value.

每个算法有两个版本：一个使用元素类型的 < 操作符，另一个接受指定用于比较元素的比较关系的实参。这些算法假定序列中的元素是唯一的，也就是说，算法假定序列中没有两个元素具有相同值。

Permutation Algorithms Require Bidirectional Iterators

要求双向迭代器的排列算法

To produce the permutation, the sequence must be processed both forward and backward, thus requiring bidirectional iterators.

为了产生排列，必须对序列进行前向和后向处理，因此要求双向迭代器。

If the sequence is already in the last permutation, then next_permutation reorders the sequence to be the lowest permutation and returns false. Otherwise, it transforms the input sequence into the next permutation, which is the lexicographically next ordered sequence and returns true. The first version uses the element < operator to compare elements; the second version uses specified comparison.

如果序列已经是在最后一个排列中，则 next_permutation 将序列重新排列为最低排列并返回 false；否则，它将输入序列变换为下一个排列，即字典序的下一个排列，并返回 true。第一个版本使用元素的 < 操作符比较元素，第二个版本使用指定的比较关系。

Like next_permutation, but transforms the sequence to form the previous permutation. If this is the smallest permutation, then it reorders the sequence to be the largest permutation and returns false.

与 next_permutation 很像，但变换序列以形成前一个排列。如果这是最小的排列，则它将序列重新排列为最大排列，并返回 false。

A.2.8. Set Algorithms for Sorted Sequences

A.2.8. 有序序列的集合算法

The set algorithms implement general set operations on a sequence that is in sorted order.

These algorithms are distinct from the library set container and should not be confused with operations on sets. Instead, these algorithms provide setlike behavior on an ordinary sequential container (vector, list, etc.) or other sequence, such as an input stream.

这些算法不同于标准库中的 set 容器，不应该与 set 的操作相混淆，相反，这些算法提供普通顺序容器（vector、list，等等）或其他序列（如输入流）上的集合式行为。

With the exception of includes, they also take an output iterator. As usual, the programmer must ensure that the destination is large enough to hold the generated sequence. These algorithms return their dest iterator incremented to denote the element just after the last one that was written to dest.

除了 include 之外，它们也接受输出迭代器。程序员照常必须保证目的地足以保存生成的序列。这些算法返回它们的 dest 迭代器，dest 迭代器增量至指向紧接在写至 dest 的最后一个元素之后的元素。

Each algorithm provides two forms: The first uses the < operator for the element type to compare elements in the two input sequences. The second takes a comparison, which is used to compare the elements.

每个算法都提供两种形式：第一种形式使用元素类型的 < 操作符比较两个输入序列中的元素，第二种形式接受一个用于比较元素的比较关系。

Set Algorithms Require Input Iterators

要求输入迭代器集合算法

Returns true if every element in the second sequence is contained in the input sequence. Returns false otherwise.

如果输入序列包含第二个序列中的每个元素，就返回 true；否则，返回 false。

Creates a sorted sequence of the elements that are in either sequence. Elements that are in both sequences occur in the output sequence only once. Stores the sequence in dest.

创建在任一序列中存在的元素的有序序列。两个序列中都存在的元素在输出序列中只出现一次。将序列存储在 dest 中。

Creates a sorted sequence of elements present in both sequences. Stores the sequence in dest.

创建在两个序列中都存在的元素的有序序列。将序列存储在 dest 中。

Creates a sorted sequence of elements present in the first container but not in the second.

创建在第一个容器中但不在第二个容器中的元素的有序序列。

Creates a sorted sequence of elements present in either container but not in both.

创建在任一容器中存在但不在两个容器中同时存在的元素的有序序列。

A.2.9. Minimum and Maximum Values

A.2.9. 最大值和最小值

The first group of these algorithms are unique in the library in that they operate on values rather than sequences. The second set takes a sequence that is denoted by input iterators.

这些算法的第一组在标准库中是独特的，它们操作值而不是序列。第二组接受一个由输入迭代器表示的序列。

Returns the minimum/maximum of val1 and val2. The arguments must have exactly the same type as each other. Uses either < operator for the element type or the specified comparison. Arguments and the return type are both const references, meaning that objects are not copied.

返回 val1 和 val2 的最大值／最小值。实参必须是完全相同的类型。使用元素类型的 < 操作符或指定的比较关系。实参和返回类型都是 const 引用，表示对象不是复制的。

Returns an iterator referring to the smallest/largest element in the input sequence. Uses either < operator for the element type or the specified comparison.

返回指向输入序列中最小／最大元素的迭代器。使用元素类型的 < 操作符或指定的比较关系。

Lexicographical Comparison

字典序比较关系

Lexicographical comparison examines corresponding elements in two sequences and determines the comparison based on the first unequal pair of elements. Because the algorithms process elements sequentially, they require input iterators. If one sequence is shorter than the other and all its elements match the corresponding elements in the longer sequence, then the shorter sequence is lexicographically smaller. If the sequences are the same size and the corresponding elements match, then neither is lexicographically less than the other.

字典序比较关系检查两个序列中的对应元素，并基于第一个不相等的元素对确定比较关系。因为算法顺序地处理元素，所以它们要求输入迭代器。如果一个序列比另一个短，并且它的元素与较长序列中对应元素相匹配，则较短的序列在字典序上较小。如果序列长短相同且对应元素匹配，则在字典序上两者都不小于另一个。

Does an element by element comparison of the elements in the two sequences. Returns true if the first sequence is lexicographically less than the second sequence. Otherwise, returns false. Uses either < operator for the element type or the specified comparison.

对两个序列中的元素进行逐个比较。如果第一个序列在字典序上小于第二个序列，就返回 true；否则，返回 false。使用元素类型的 < 操作符或指定的比较关系。

A.2.10. Numeric Algorithms

A.2.10. 算术算法

Numeric algorithms require input iterators; if the algorithm writes output, it uses an output iterator for the destination

算术算法要求输入迭代器，如果算法修改输出，它就使用目的地输出迭代器。

These functions perform simple arithmetic manipulations of their input sequence. To use the numeric algorithms, the numeric header must be included.

这些算法执行它们的输入序列的简单算术操纵。要使用算术算法必须包含头文件 numeric。

Returns the sum of all the values in the input range. The summation starts with the initial value specified by init. The return type is the same type as the type of init.

返回输入范围中所有值的总和。求和从指定的初始值 init 开始。返回类型是与 init 相同的类型。

Given the sequence 1,1,2,3,5,8 and an initial value of 0, the result is 20. The first version applies the + operator for the element type; second version applies the specified binary operation.

给定序列 1,1,2,3,5,8 以及初始值 0，结果是 20。ø第一个版本应用元素类型的 + 操作符，第二个版本应用指定的二元操作符。

Returns the sum of the elements generated as the product of two sequences. The two sequences are examined in step, and the elements from each sequence are multiplied. The product of that multiplication is summed. The initial value of the sum is specified by init. The second sequence beginning at beg2 is assumed to have at least as many elements as are in the first sequence; any elements in the second sequence beyond the size of the first sequence are ignored. The type of init determines the return type.

返回作为两个序列乘积而生成的元素的总和。步调一致地检查两个序列，将来自两个序列的元素相乘，将相乘的结果求和。由 init 指定和的初值。假定从 beg2 开始的第二个序列具有至少与第一个序列一样多的元素，忽略第二个序列中超出第一个序列长度的任何元素。init 的类型决定返回类型。

The first version uses the element's multiplication (*) and addition (+) operators: Given the two sequences 2,3,5,8 and 1,2,3,4,5,6,7, the result is the sum of the initial value plus the following product pairs:

第一个版本使用元素的乘操作符（*）和加操作符（+）：给定两个序列 2,3,5,8 和 1,2,3,4,5,6,7，结果是初值加上下面的乘积对：

The second version applies the specified binary operations, using the first operation in place of addition and the second in place of multiplication. As an example, we might use inner_product to produce a list of parenthesized namevalue pairs of elements, where the name is taken from the first input sequence and the corresponding value is in the second:

第二个版本应用指定的二元操作，使用第一个操作代替加而第二个操作代替乘。作为例子，可以使用 inner_product 来产生以括号括住的元素的名－值对的列表，这里从第一个输入序列获得名字，从第二个序列中获得对应的值：

If the first sequence contains if, string, and sort, and the second contains keyword, library type, and algorithm, then the output would be

如果第一个序列包含 if、string 和 sort，且第二个序列包含 keyword、library type 和 algorithm，则输出将是

Writes a new sequence to dest in which the value of each new element represents the sum of all the previous elements up to and including its position within the input range. The first version uses the + operator for the element type; the second version applies the specified binary operation. The programmer must ensure that dest is at least as large as the input sequence. Returns the dest iterator incremented to refer just after the last element written.

将新序列写至 dest，其中每个新元素的值表示输入范围中在它的位置之前（不包括它的位置）的所有元素的总和。第一个版本使用元素类型 + 操作符，第二个版本应用指定的二元操作符。程序员必须保证 dest 至少与输入序列一样大。返回 dest，dest 增量到指向被写入的最后元素的下一位置。

Given the input sequence 0,1,1,2,3,5,8, the destination sequence will be 0,1,2,4,7,12,20. The fourth element, for example, is the partial sum of the three previous values (0,1,1) plus its own( 2), yielding a value of 4.

给定输入序列 0,1,1,2,3,5,8，目的序列将是 0,1,2,4,7,12,20。例如，第四个元素是前三值（0,1,1）的部分和加上它自己的值（2），获得值 4。

Writes a new sequence to dest in which the value of each new element other than the first represents the difference of the current and previous element. The first version uses the element type's - operation; the second version applies the specified binary operation. The programmer must ensure that dest is at least as large as the input sequence.

将新序列写至 dest，其中除了第一个元素之外每个新元素表示当前元素和前一元素的差。第一个版本使用元素类型的 - 操作符，第二个版本应用指定的二元操作。程序员必须保证 dest 至少与输入序列一样大。

Given the sequence 0,1,1,2,3,5,8, the first element of the new sequence is a copy of the first element of the original sequence: 0. The second element is the difference between the first two elements: 1. The third element is the difference between the second and third element, which is 0, and so on. The new sequence is 0,1,0,1,1,2,3.

给定序列 0,1,1,2,3,5,8，新序列的第一个元素是原序列第一个元素的副本：0，第二个元素是前两个元素的差：1，第三个元素是原序列第三个元素和第二个元素的差，为 0，以此类推，新序列是 0,1,0,1,1,2,3。

A.2. A Brief Tour of the Algorithms

A.2. 算法简介