4.md

四、算法

前一章讨论了标准库提供的存储数据的容器。除此之外，该库还提供了许多算法来处理这些数据或其他数据。算法独立于容器:它们只基于迭代器工作，因此只要提供合适的迭代器，就可以在任何范围的元素上执行。

这一章从输入/输出迭代器的简单定义开始，接着是按功能组织的所有可用算法的详细概述。本章最后讨论了迭代器适配器。

输入和输出迭代器

前一章简要解释了容器提供的不同种类的迭代器:正向、双向和随机访问。算法上下文中使用了另外两种迭代器类别，与其他三种相比，它们的要求更少。本质上:

• 输入迭代器:必须可取消引用才能读取元素。除此之外，只需要++、==和!=操作符。
• 输出迭代器:只需要++操作符，但是你必须能够在解引用后向它们写入元素。

对于这两者，它们提供单路访问也就足够了。也就是说，一旦增加，它们原则上可以使它们的所有先前副本无效。两个相应的迭代器标签，如在第 3 章中讨论的，也为这些类别提供:std::input_iterator_tag和output_iterator_tag。

标准容器返回的所有迭代器，以及指向 C 风格数组的指针，都是有效的输入迭代器。它们也是有效的输出迭代器，只要它们不指向const元素。

算法<algorithm>

本节概述了所有可用的算法，根据功能分为几个小节。除非另有说明，所有算法都在<algorithm>头文件中定义。

术语

以下术语和缩写用于算法定义中的类型:

• function:Callable——即 lambda 表达式、函数对象或函数指针。
• InIt、OutIt、FwIt、BidIt、RanIt:输入、输出、正向、双向或随机访问迭代器。
• UnaOp、BinOp:一元或二元运算，即接受一个 resp 的可调用操作。两个论点。
• UnaPred，BinPred:一元或二元谓词，谓词是返回布尔值的操作。
• Size:表示大小的类型，例如，元素的数量。
• DiffType:表示两个迭代器之间距离的类型。
• t:一个元素类型。
• Compare:用于比较元素的函数对象。如果未指定，则使用operator<。函数对象接受两个参数，如果第一个参数小于第二个参数，则返回true，否则返回false。强加的排序必须是严格的弱排序，就像默认的operator<一样。

算法通常接受一个可调用的参数:例如，一元或二元操作或谓词。这个可调用函数可以是 lambda 表达式、函数对象或函数指针。Lambda 表达式和函数对象将在第 2 章中讨论。

一般准则

首先，尽可能使用标准算法，而不是自己编写的循环，因为它们通常更有效，而且更不容易出错。此外，尤其是在引入 lambda 表达式之后，算法的使用通常会产生更短、可读性更强、不言自明的代码。

其次，对于一些算法，某些容器提供了等价的专用成员函数(见第 3 章)。这些算法效率更高，因此应该优先于一般算法。在接下来的算法描述中，我们总是列出这些备选方案。

最后，许多算法移动或交换元素。如果没有隐式或显式的移动和/或交换函数可用，这些算法会退回到复制元素。为了获得最佳性能，您应该始终考虑为重要的自定义数据类型实现专门的移动和/或交换函数。标准库提供的类型总是在适当的地方提供这些。关于移动语义和交换功能的更多信息，我们参考第 2 章。

对范围应用函数

• 为范围[first, last)中的每个元素调用给定函数，并返回std::move(function)。注意，当迭代整个容器或 C 风格数组时，基于范围的for循环更方便。

Function for_each(InIt first, InIt last, Function function)

• 转换范围[first1, last1)中的所有元素，并将结果存储在从target开始的范围中，该范围允许等于first1或first2以执行就地转换。对于第一个版本，对每个转换后的元素执行一元运算。对于第二种情况，对每个转换后的元素和第二个范围中的相应元素执行二元运算。设 length = (last1 - first1)，则对长度为 0 ≤ n <的对(*(first1 + n ), *(first2 + n ))执行二进制运算。返回目标范围的结束迭代器，所以(target +长度)。

OutIt transform(InIt first1, InIt last1, OutIt target, UnaOp operation)
OutIt transform(InIt1 first1, InIt1 last1, InIt2 first2,
                OutIt target, BinOp operation)

例子

下面的示例使用transform()通过 lambda 表达式将vector中的所有元素加倍，然后使用transform()通过标准函数对象对元素求反，最后使用for_each()将所有元素输出到控制台。这段代码还需要<functional>:

std::vector<int> vec{ 1,2,3,4,5,6 };

std::transform(cbegin(vec), cend(vec), begin(vec),
   [](auto& element) { return element * 2; });

std::transform(cbegin(vec), cend(vec), begin(vec), std::negate<>());

std::for_each(cbegin(vec), cend(vec),
   [](auto& element) { std::cout << element << " "; });

输出如下所示:

-2 -4 -6 -8 -10 -12

检查元素是否存在

• 如果范围[first, last)中的所有元素、无元素或至少有一个元素满足一元predicate，则返回true。如果范围为空，all_of()和none_of()返回true，而any_of()返回false。

bool all_of(InIt first, InIt last, UnaPred predicate)
bool none_of(InIt first, InIt last, UnaPred predicate)
bool any_of(InIt first, InIt last, UnaPred predicate)

• 返回[first, last)中等于给定value或满足一元predicate的元素数量。[替代:所有有序和无序的关联容器都有一个count()成员。]

DiffType count(InIt first, InIt last, const T& value)
DiffType count_if(InIt first, InIt last, UnaPred predicate)

例子

以下示例演示了如何使用all_of()来检查所有元素是否都是偶数:

查找元素

• 在范围[first, last)的所有元素中搜索第一个等于value、满足一元predicate或不满足predicate的元素。返回找到的元素的迭代器，如果没有找到，返回last。[替代:所有有序和无序的关联容器都有一个find()成员。]

InIt find(InIt first, InIt last, const T& value)
InIt find_if(InIt first, InIt last, UnaPred predicate)
InIt find_if_not(InIt first, InIt last, UnaPred predicate)

• 返回一个迭代器到[first1, last1)中的第一个元素，它等于[first2, last2)中的一个元素。如果没有找到这样的元素或者如果[first2, last2)为空，则返回last1。如果给出了一个二元谓词，它将用于判断两个范围之间的元素是否相等。

InIt find_first_of(InIt first1, InIt last1,
                   FwIt first2, FwIt last2[, BinPred predicate])

• 返回范围[first, last)中第一对相邻元素的第一个元素的迭代器，这些元素彼此相等或匹配一个二进制数predicate。如果没有找到合适的相邻元素，返回last。

FwIt adjacent_find(FwIt first, FwIt last[, BinPred predicate])

例子

以下代码片段使用find_if()算法在人员列表中查找一个名为 Waldo 的人:

auto people = { Person("Wally"), Person("Wilma"), Person("Wenda"),
                Person("Odlaw"), Person("Waldo"), Person("Woof") };
auto iter = std::find_if(begin(people), end(people),
   [](const Person& p) { return p.GetFirstName() == "Waldo"; });

二进位检索

以下所有算法都要求给定范围[ first，last]在value上排序或至少分区(分区稍后解释)。如果不满足这个前提条件，算法的行为是未定义的。

• 如果在范围[first, last)中有一个等于value的元素，则返回true。

bool binary_search(FwIt first, FwIt last, const T& value[, Compare comp])

• 将迭代器返回到[first, last)中第一个对lower_bound()的比较不小于value的元素，以及第一个对upper_bound()的比较大于value的元素。当在一个排序范围内插入时，如果插入发生在迭代器之前，这两个位置都适合插入value(就像顺序容器的insert()方法一样；参见下一个“示例”小节)。[替代:所有有序关联容器都有lower_bound()和upper_bound()成员。]

FwIt lower_bound(FwIt first, FwIt last, const T& value[, Compare comp])
FwIt upper_bound(FwIt first, FwIt last, const T& value[, Compare comp])

• 返回一个包含下限和上限的pair。[替代:所有有序和无序的关联容器都有一个equal_range()成员。]

pair<FwIt, FwIt> equal_range(FwIt first, FwIt last,
                             const T& value[, Compare comp])

例子

下面的代码片段演示了如何在vector的正确位置插入一个新值，以保持元素的排序:

下一个例子使用equal_range()找到等于 2 的值的范围。它返回一个迭代器的pair。第一个指向第一个等于 2 的元素，第二个指向最后一个 2:

后续搜索

所有的子序列搜索算法都接受一个可选的二元谓词，用于判断元素是否相等。

• For search() / find_end()，分别返回一个迭代器到[first1, last1)中第一个/最后一个子序列的开头，等于范围[first2, last2)。如果第二个范围为空，则返回first1 / last1，如果没有找到相等的子序列，则返回last1。

FwIt1 search(FwIt1 first1, FwIt1 last1,
             FwIt2 first2, FwIt2 last2[, BinPred predicate])
FwIt1 find_end(FwIt1 first1, FwIt1 last1,
               FwIt2 first2, FwIt2 last2[, BinPred predicate])

• 返回第一个子序列的迭代器，这个子序列由重复了count次的value组成。如果count为零，则返回first，如果没有找到合适的子序列，则返回last。

FwIt search_n(FwIt first, FwIt last, Size count,
              const T& value[, BinPred predicate])

最小/最大

• 返回对两个值中最小值或最大值的引用，如果两个值相等，则返回第一个值。

constexpr const T& min(const T& a, const T& b[, Compare comp])
constexpr const T& max(const T& a, const T& b[, Compare comp])

• 返回给定initializer_list中最小值或最大值的副本，或者如果有几个元素等于这个极值，则返回最左边元素的副本。

constexpr T min(initializer_list<T> t[, Compare comp])
constexpr T max(initializer_list<T> t[, Compare comp])

• 返回一个包含对两个值的最小值和最大值的引用的pair，按此顺序。如果两个值相等，则返回pair(a, b)。

constexpr pair<const T&, const T&> minmax(
        const T& a, const T& b[, Compare comp])

• 返回一个pair，包含一个initializer_list中的最小值和最大值的副本，按此顺序。如果几个元素都等于最小值，那么返回最左边一个的副本；如果几个元素等于最大值，则返回最右边的一个副本。

constexpr pair<T, T> minmax(initializer_list<T> t[, Compare comp])

• 返回一个最小值迭代器，一个最大值迭代器，或者分别返回一个包含范围[first, last)中最小和最大元素迭代器的pair。如果范围为空，则返回last或pair(first, first)。

FwIt min_element(FwIt first, FwIt last[, Compare comp])
FwIt max_element(FwIt first, FwIt last[, Compare comp])
pair<FwIt, FwIt> minmax_element(FwIt first, FwIt last[, Compare comp])

序列比较

所有的序列比较算法都接受一个可选的二元谓词，用于判断元素是否相等。

• 假设 n = (last1 - first1)，如果范围[first1, last1)和[first2, first2 + n )中的所有元素成对匹配，则返回true。第二个范围必须至少有 n 个元素。因此，后面讨论的四参数版本是避免越界访问的首选。

bool equal(InIt1 first1, InIt1 last1, InIt2 first2[, BinPred predicate])

• 设 n = (last1 - first1)，然后返回一个pair迭代器，指向范围[first1, last1)和[first2, first2 + n )中不匹配的第一个元素。第二个范围必须至少有 n 个元素。因此，为了避免越界访问，最好使用下面的四参数版本。

pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
                            InIt2 first2[, BinPred predicate])

• 早期三参数版本的安全版本，也知道第二个范围的长度。为了使equal()成为true，两个范围必须等长。对于mismatch()，如果在到达last1或last2之前没有发现不匹配对，则返回一对(first1 + m, first2 + m)和m = min(last1 - first1, last2 - first2)。

bool equal(InIt1 first1, InIt1 last1,
           InIt2 first2, InIt2 last2[, BinPred predicate])
pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1,
                            InIt2 first2, InIt2 last2[, BinPred predicate])

复制、移动、交换

• 将范围[first, last)中的所有元素(copy())或仅满足一元元素predicate ( copy_if())的元素复制到从targetFirst开始的范围。对于copy()，不允许targetFirst在[first, last)中:如果是这样的话，copy_backward()可能是一个选项。对于copy_if()，范围不允许重叠。对于这两种算法，目标范围必须足够大，以容纳复制的元素。返回结果范围的结束迭代器。

OutIt copy(InIt first, InIt last, OutIt targetFirst)
OutIt copy_if(InIt first, InIt last, OutIt targetFirst, UnaPred predicate)

• 将范围[first, last)中的所有元素复制到结束于targetLast的范围，该范围不在范围[first, last)中。目标范围必须足够大，以容纳复制的元素。复制是反向进行的，从复制元素(last-1)到(targetLast-1)开始，再回到first。返回一个迭代器到目标范围的开始，所以(targetLast - (last - first))。

BidIt2 copy_backward(BidIt1 first, BidIt1 last, BidIt2 targetLast)

• 将从start开始的count元素复制到从target开始的范围。目标范围必须足够大，以容纳这些元素。返回目标结束迭代器，所以(target + count)。

OutIt copy_n(InIt start, Size count, OutIt target)

• 类似于copy()和copy_backward()，但是移动元素而不是复制它们。

OutIt move(InIt first, InIt last, OutIt targetFirst)
BidIt2 move_backward(BidIt1 first, BidIt1 last, BidIt2 targetLast)

• 将范围[first1, last1)中的元素与范围[first2, first2 + (last1 - first1))中的元素交换。两个范围不允许重叠，第二个范围必须至少与第一个范围一样大。返回一个迭代器，从第二个范围中最后一个交换的元素开始。

FwIt2 swap_ranges(FwIt1 first1, FwIt1 last1, FwIt2 first2)

• 将由x指向的元素与由y指向的元素交换，所以swap(*x, *y)。

void iter_swap(FwIt1 x, FwIt2 y)

生成序列

• 将value分配给范围[first, last)或[first, first + count)中的所有元素。如果count为负，则不会发生任何事情。fill_n()的范围必须足够大，以容纳count元素。fill_n()返回(first + count)，如果count为负，则返回first。【替代品:array::fill()。]

void fill(FwIt first, FwIt last, const T& value)
OutIt fill_n(OutIt first, Size count, const T& value)

• 生成器是一个没有任何返回值的参数的函数。调用它来计算范围[first, last)或[first, first + count)中每个元素的值。如果count是负的，什么都不会发生。generate_n()的范围必须足够大，以容纳count元素。generate_n()返回(first + count)，如果count为负，则返回first。

void generate(FwIt first, FwIt last, Generator gen)
OutIt generate_n(OutIt first, Size count, Generator gen)

• 该算法在<numeric>标题中定义。范围[first, last)中的每个元素被设置为value，之后value递增，因此:

void iota(FwIt first, FwIt last, T value)

   *first = value++
   *(first + 1) = value++
   *(first + 2) = value++
   ...

例子

以下示例演示了generate()和iota():

拆卸和更换

• 将范围[first, last)中不等于value或不满足一元predicate的所有元素向范围的开头移动，之后[first, result)包含要保留的所有元素。返回result迭代器，指向传递了最后一个要保留的元素的迭代器。算法是稳定的，这意味着保留的元素保持它们的相对顺序。不应该使用[result, last)中的元素，因为它们可能因移动而处于未指定的状态。通常这些算法后面是对erase()的调用。这被称为删除-擦除习惯用法，在第 3 章中讨论。

FwIt remove(FwIt first, FwIt last, const T& value)
FwIt remove_if(FwIt first, FwIt last, UnaPred predicate)

【备选:】和forward_list有remove()和remove_if()成员。]

• 从范围[first, last)中的连续相等元素中删除除一个元素之外的所有元素。如果给定一个二元谓词，它将用于判断元素是否相等。否则等同于remove()，包括它后面通常应该跟一个erase()的事实。下一个“示例”小节显示了unique()的典型用法。【替代品:】、forward_list::unique()。]

FwIt unique(FwIt first, FwIt last[, BinPred predicate])

• 用newVal替换范围[first, last)中等于oldVal或满足一元predicate的所有元素。

void replace(FwIt first, FwIt last, const T& oldVal, const T& newVal)
void replace_if(FwIt first, FwIt last, UnaPred predicate, const T& newVal)

• 类似于前面的算法，但是将结果复制到从target开始的范围。目标范围必须足够大，以容纳复制的元素。输入和目标范围不允许重叠。返回目标范围的结束迭代器。

OutIt remove_copy(InIt first, InIt last, OutIt target, const T& value)
OutIt remove_copy_if(InIt first, InIt last, OutIt target, UnaPred predicate)
OutIt unique_copy(InIt first, InIt last, OutIt target [, BinPred predicate])
OutIt replace_copy(InIt first, InIt last, OutIt target,
                   const T& oldVal, const T& newVal)
OutIt replace_copy_if(InIt first, InIt last, OutIt target,
                      UnaPred predicate, const T& newVal)

例子

下面的例子演示了如何使用unique()和 remove-erase 习惯用法从vector中过滤出所有连续的相等元素:

反转和旋转

• 反转范围[first, last)中的元素。【替代品:list::reverse()，forward_list::reverse()。]

void reverse(BidIt first, BidIt last)

• 向左旋转范围[first, last)中的元素，使middle指向的元素成为范围中的第一个元素，而(middle - 1)指向的元素成为范围中的最后一个元素(参见下一个“示例”小节)。返回(first + (last - middle))。

FwIt rotate(FwIt first, FwIt middle, FwIt last)

• 类似于reverse()和rotate()，但是将结果复制到从target开始的范围。目标范围必须足够大，以容纳复制的元素。输入和目标范围不允许重叠。返回目标范围的结束迭代器。

OutIt reverse_copy(BidIt first, BidIt last, OutIt target)
OutIt rotate_copy(FwIt first, FwIt middle, FwIt last, OutIt target)

例子

下一个代码片段旋转了vector中的元素。结果是5,6,1,2,3,4:

std::vector<int> vec{ 1,2,3,4,5,6 };
std::rotate(begin(vec), begin(vec) + 4, end(vec));

分割

• 如果范围[first, last)中的元素被分区，使得满足一元谓词的所有元素都在不满足该谓词的所有元素之前，则返回true。如果范围为空，也返回true。

bool is_partitioned(InIt first, InIt last, UnaPred predicate)

• 对范围[first, last)进行分区，使得满足一元谓词的所有元素都在不满足谓词的所有元素之前。返回不满足谓词的第一个元素的迭代器。stable_partition()保持两个分区中元素的相对顺序。

FwIt partition(FwIt first, FwIt last, UnaPred predicate)
BidIt stable_partition(BidIt first, BidIt last, UnaPred predicate)

• 通过将满足或不满足一元谓词的所有元素复制到分别从outTrue或outFalse开始的输出范围来划分范围[first, last)。两个输出范围都必须足够大，以容纳复制的元素。输入和输出范围不允许重叠。返回一个包含两个输出范围的结束迭代器的pair。

pair<OutIt1, OutIt2> partition_copy(InIt first, InIt last,
    OutIt1 outTrue, OutIt2 outFalse, UnaPred predicate)

• 要求基于一元predicate对范围[first, last)进行分区。向第二个分区的第一个元素返回一个迭代器:即不满足谓词的第一个元素。

FwIt partition_point(FwIt first, FwIt last, UnaPred predicate)

整理

• 对范围[first, last)中的元素进行排序。稳定版本保持相等元素的顺序。【替代品:list::sort()，forward_list::sort()。]

void sort(RanIt first, RanIt last[, Compare comp])
void stable_sort(RanIt first, RanIt last[, Compare comp])

• The (middle - first)范围[first, last)中最小的元素被排序并移动到范围[first, middle)。未排序的元素以未指定的顺序移动到范围[middle, last)。

void partial_sort(RanIt first, RanIt middle, RanIt last[, Compare comp])

• min(last - first, targetLast - targetFirst)范围[first, last)中的元素被排序并复制到目标范围。返回min(targetLast, targetFirst + (last - first))。

RanIt partial_sort_copy(InIt first, InIt last,
        RanIt targetFirst, RanIt targetLast[, Compare comp])

• 范围[first, last)中的元素以这样的方式移动，即在重新排列后，给定的迭代器nth指向如果整个范围被排序时该位置的元素。但是，实际上并没有对整个范围进行排序。然而，它是在nth指向的元素上(非稳定)分区的。

void nth_element(RanIt first, RanIt nth, RanIt last[, Compare comp])

• 如果范围[first, last)是排序序列，则返回true。

bool is_sorted(FwIt first, FwIt last[, Compare comp])

• 返回最后一个迭代器iter，这样[first, iter)就是一个有序序列。

FwIt is_sorted_until(FwIt first, FwIt last[, Compare comp])

• 返回范围[first1, last1)中的元素是否比范围[first2, last2)中的元素少。

bool lexicographical_compare(InIt1 first1, InIt1 last1,
        InIt2 first2, InIt2 last2[, Compare comp])

例子

partial_sort()和partial_sort_copy()算法可用于找出 n 个最大、最小、最差、最佳，...序列中的元素。这比排序整个序列要快。例如:

std::vector<int> vec{ 9,2,4,7,3,6,1 };
std::vector<int> threeSmallestElements(3);
std::partial_sort_copy(begin(vec), end(vec),
   begin(threeSmallestElements), end(threeSmallestElements));

nth_element()是一种所谓的选择算法，用于寻找序列中第 n 个最小的数，平均具有线性复杂度。例如，它可用于计算具有奇数个元素的序列的中值:

洗牌

• 使用由统一随机数生成器生成的随机性打乱范围[first, last)中的元素。随机数生成库在第 1 章中解释。

void shuffle(RanIt first, RanIt last, UniformRanGen generator)

• 不赞成使用shuffle()，但为了完整性而提及。它打乱了范围[first, last)中的元素。随机数生成器rng是一个仿函数，其函数调用操作符接受一个整数参数n，并返回一个在[0, n)范围内的整数随机数，其n >为 0。如果没有提供随机数生成器，实现可以自由决定如何生成随机数。

void random_shuffle(RanIt first, RanIt last[, RNG&& rng])

例子

下面的例子打乱了vector中的元素。参见第 1 章了解更多关于随机数生成库的信息。代码片段还需要<random>和<ctime>:

排序范围上的操作

以下所有操作都需要对输入范围进行排序。如果不满足这个前提条件，算法的行为是未定义的。

• 将排序范围[first1, last1)和[first2, last2)中的所有元素合并到一个从target开始的范围中，这样目标范围也被排序。目标范围必须足够大，以容纳所有元素。输入范围不允许与目标范围重叠。返回目标范围的结束迭代器。算法稳定；也就是说，相同元素的顺序保持不变。【替代品:list::merge()，forward_list::merge()。]

OutIt merge(InIt1 first1, InIt1 last1,
            InIt2 first2, InIt2 last2, OutIt target[, Compare comp])

• 将排序后的范围[first, middle)和[middle, last)合并成一个排序后的序列，存储在范围[first, last)中。该算法是稳定的，因此保持了相等元素的顺序。

void inplace_merge(BidIt first, BidIt middle, BidIt last[, Compare comp])

• 如果排序范围[first2, last2)中的所有元素都在排序范围[first1, last1)中，或者前者为空，则返回true，否则返回false。

bool includes(InIt1 first1, InIt1 last1,
              InIt2 first2, InIt2 last2[, Compare comp])

• 对两个排序范围[first1, last1)和[first2, last2)执行集合运算(见下表),并将结果存储在从target开始的范围内。对目标范围内的元素进行排序。目标范围必须足够大，以容纳集合运算的元素。输入和输出范围不允许重叠。返回构造的目标范围的结束迭代器。
  • 联合:两个输入范围的所有元素。如果一个元素在两个输入范围内，那么它在输出范围内只出现一次。
  • 交集:两个输入范围内的所有元素。
  • 差异:所有在[first1, last1)中的元素和不在[first2, last2)中的元素。
  • 对称差:所有在[first1, last1)和不在[first2, last2)的元素，以及所有在[first2, last2)和不在[first1, last1)的元素。

OutIt set_union(InIt1 first1, InIt1 last1,
                InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
OutIt set_intersection(InIt1 first1, InIt1 last1,
                InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
OutIt set_difference(InIt1 first1, InIt1 last1,
                InIt2 first2, InIt2 last2, OutIt target[, Compare comp])
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1,
                InIt2 first2, InIt2 last2, OutIt target[, Compare comp])

排列

• 如果第二个范围是第一个范围的排列，则返回true。对于三参数版本，第二个范围被定义为[first2, first2 + (last1 - first1))，并且该范围必须至少与第一个范围一样大。因此，四参数版本更适合防止越界访问(如果范围长度不同，它们将返回false)。如果给定一个二进制数predicate，它将用于判断两个范围之间的元素是否相等。

bool is_permutation(FwIt1 first1, FwIt1 last1,
                    FwIt2 first2[, BinPred predicate])
bool is_permutation(FwIt1 first1, FwIt1 last1,
                    FwIt2 first2, FwIt2 last2[, BinPred predicate])

• 将范围[first, last)中的元素转换为按字典顺序排列的下一个/上一个排列。如果这样的下一个/前一个排列存在，则返回true，否则返回false，并按照可能的最小/最大排列转换元素。

bool next_permutation(BidIt first, BidIt last[, Compare comp])
bool prev_permutation(BidIt first, BidIt last[, Compare comp])

很

在这个上下文中，术语堆不是指 C++ 运行时的动态内存池。在计算机科学中，堆也是一组基本的基于树的数据结构(众所周知的变体包括二进制、二项式和斐波那契堆)。这些数据结构是有效实现各种图形和排序算法的关键构件(经典的例子包括 Prim 算法、Dijkstra 算法和 heapsort)。这也是优先级队列的一种常见实现策略:事实上，前一章讨论的 C++ priority_queue容器适配器是使用下面定义的堆算法实现的。

对于下面的 C++ 算法，堆的树被展平成以特定方式排序的连续元素序列。虽然确切的排序是特定于实现的，但它必须满足以下关键属性:没有元素大于它的第一个元素，并且移除这个最大的元素和添加任何新元素都可以在对数时间内完成。

• 将范围[first, last)变成一个堆(在线性时间内)。

void make_heap(RanIt first, RanIt last[, Compare comp])

• 范围[first, last)的最后一个元素被移动到正确的位置，从而成为一个堆。在调用push_heap()之前，范围[first, last - 1)需要是一个堆。

void push_heap(RanIt first, RanIt last[, Compare comp])

• 通过用*(last - 1)交换*first并确保新的范围[first, last - 1)仍然是堆，从堆[first, last)中移除最大的元素。

void pop_heap(RanIt first, RanIt last[, Compare comp])

• 对范围[first, last)中的所有元素进行排序。在调用sort_heap()之前，该范围需要是一个堆。

void sort_heap(RanIt first, RanIt last[, Compare comp])

• 如果范围[first, last)表示堆，则返回true。

bool is_heap(RanIt first, RanIt last[, Compare comp])

• 返回最后一个迭代器iter，这样[first, iter)表示一个堆。

RanIt is_heap_until(RanIt first, RanIt last[, Compare comp])

数字算法<numeric>

以下算法在<numeric>标题中定义:

• 返回result，从result等于startValue开始，然后对范围[first, last)内的每个element执行result += element或result = op(result, element)计算得到。

T accumulate(InIt first, InIt last, T startValue[, BinOp op])

• 返回result，从等于startValue的result开始计算，然后依次对范围[first1, last1)中的每个el1和范围[first2, first2 + (last1 - first1))中的每个el2执行result += (el1 * el2)或result = op1(result, op2(el1, el2))。第二个范围必须至少与第一个范围一样大。

T inner_product(InIt1 first1, InIt1 last1, InIt2 first2,
                T startValue[, BinOp1 op1, BinOp2 op2])

• 计算从[first, last)开始的递增子范围的部分和，并将结果写入从target开始的范围。使用默认运算符+，结果就好像是按如下方式计算的:

OutIt partial_sum(InIt first, InIt last, OutIt target[, BinOp op])

• 返回目标范围的结束迭代器，所以(target + (last - first))。目标范围必须足够大以容纳结果。通过指定target等于first，可以就地完成计算。

   *(target) = *first
   *(target + 1) = *first + *(first + 1)
*(target + 2) = *first + *(first + 1) + *(first + 2)
   ...

• 计算范围[first, last)中相邻元素的差值，并将结果写入从target开始的范围。对于默认运算符-，计算结果如下:

OutIt adjacent_difference(InIt first, InIt last, OutIt target[, BinOp op])

• 返回目标范围的结束迭代器，所以(target + (last - first))。目标范围必须足够大以容纳结果。通过指定target等于first，可以就地完成计算。

   *(target) = *first
   *(target + 1) = *(first + 1) - *first
   *(target + 2) = *(first + 2) - *(first + 1)
   ...

例子

以下代码片段使用accumulate()算法计算序列中所有元素的总和:

inner_product()算法可用于计算两个数学向量的所谓点积:

迭代器适配器<iterator>

标准库提供了以下迭代器适配器:

• reverse_iterator:反转正在修改的迭代器的顺序。用make_reverse_iterator(Iterator iter)造一个。
• move_iterator:解引用被修改为右值的迭代器。用make_move_iterator(Iterator iter)造一个。
• back_insert_iterator:使用push_back()在容器后面插入新元素的迭代器适配器。使用back_inserter(Container& cont)建造一个。
• front_insert_iterator:迭代器适配器，使用push_front()在容器前面插入新元素。使用front_inserter(Container& cont)建造一个。
• insert_iterator:使用insert()在容器中插入新元素的迭代器适配器。要构建一个，使用inserter(Container& cont, Iterator iter)，其中iter是插入位置。

下面的例子通过使用deque上的front_insert_iterator适配器，以相反的顺序将所有元素从vector复制到deque。接下来，它使用accumulate()连接vector中的所有string(其默认组合运算符+执行string的连接)。因为这里使用了move_iterator适配器，所以string是移动的，而不是从vector复制的: