跳转到内容
Professional C++（第 6 版）

精通标准库算法

正如第 18 章“标准库容器”所展示的那样，标准库提供了一套令人印象深刻的泛型数据结构。大多数库到这里也就结束了。然而，标准库还额外提供了一整套泛型算法。除少数例外外，这些算法都可以应用到任意容器中的元素上。借助这些算法，你可以在容器中查找、排序和处理元素，并完成大量其他操作。算法之美，在于它们不仅独立于底层元素的类型，也独立于所操作容器的类型。算法完成工作时只依赖 iterator 或 range 接口；这两者已经在第 17 章“理解迭代器与 Ranges 库”中讨论过。

标准库提供了一大批 不受约束算法（unconstrained algorithms），它们全部只依赖 iterator 来工作。这些算法并没有附加 concepts 形式的约束；相关内容见第 12 章“使用模板编写泛型代码”。除此之外，标准库还提供了一大批 受约束算法（constrained algorithms），有时也叫 基于 range 的算法。它们既能处理 iterator，也能处理 range，并且带有恰当的约束，因此当你错误地使用某个算法时，编译器能产生更易读的错误信息。本章会先聚焦不受约束算法，因为它们大量存在于现有代码和旧代码库中；因此，你必须知道它们是如何工作的。等你理解了这些之后，再来看受约束算法如何让事情变得更简单，就会觉得非常轻松。

第 16 章“C++ 标准库概览”已经从高层视角介绍了全部标准库算法，但没有涉及任何编码细节。结合第 19 章“函数指针、函数对象与 Lambda 表达式”的知识，现在正是时候真正看看这些算法如何在实践中使用，并发掘它们的真正威力了。

算法概览

Section titled “算法概览”

不受约束算法背后的“魔法”在于：它们不是直接操作容器本身，而是通过 iterator 中介来工作。正因为如此，它们不会绑死在某个具体容器实现上。所有标准库算法都实现为函数模板，其中模板类型参数通常是 iterator 类型。iterator 本身通过函数参数传入。函数模板通常能从函数参数中推导出模板类型，因此你一般可以像调用普通函数一样调用这些算法，而不是像调用模板那样显式指定类型。

大多数算法都需要一个源序列作为处理对象。对于不受约束算法，源序列由一对 iterator 来指定，也就是 begin iterator 与 end iterator，这被称为公共区间（common range）。正如第 17 章所解释的那样，对大多数容器来说，公共区间都是左闭右开的：它包含范围内的第一个元素，但不包含最后一个。end iterator 实际上只是一个“越过末尾”的标记。

算法会对传给它们的 iterator 提出某些要求。例如，copy_backward() 会把一个序列中的元素复制到另一个序列中，并且从最后一个元素开始复制；它就是一个需要双向迭代器的算法。类似地，stable_sort() 会在原地对元素排序，并保持重复元素的相对顺序；它则要求随机访问迭代器。这意味着，这类算法无法用于那些不提供所需 iterator 的容器。forward_list 就是一个只支持前向迭代器、不支持双向或随机访问迭代器的容器，因此 copy_backward() 和 stable_sort() 都不能用于 forward_list。

绝大多数算法定义在 <algorithm> 中，少量数值算法定义在 <numeric> 中。它们全都位于 std 命名空间。

大多数算法都是 constexpr 的，这意味着它们可以用于实现 constexpr 函数。具体哪些算法是 constexpr，请查阅标准库参考资料（见附录 B“注释书目”）。

理解算法的最佳方式，是先通过几个详细例子看看它们如何工作。一旦你掌握了其中几个，剩下的就很容易类推。本节将详细介绍 find()、find_if() 和 accumulate() 这几个算法。后续各节则会按算法类别分别讨论其中具有代表性的样本。

find 与 find_if 算法

Section titled “find 与 find_if 算法”

find() 用于在一个公共区间中查找某个特定元素。你可以把它用于任意容器类型中的元素。它会返回一个指向找到元素的 iterator；如果找不到，则返回该 range 的 end iterator。注意，调用 find() 时给定的 range 不必一定是容器的全部元素范围，它也可以只是一个子区间。

如果 find() 没有找到元素，它返回的是函数调用中所指定的那个 end iterator，而不是底层容器自身的 end iterator。

在看 find() 之前，先定义一个函数模板，用于用整数填充容器。本章会多次用到这个函数模板。它以容器类型为模板参数，并通过一个约束来保证给定容器类型支持 push_back(int)。

template <typename Container>
    requires requires(Container& c, int i) { c.push_back(i); }
void populateContainer(Container& cont)
{
    while (true) {
        print("Enter a number (0 to stop): ");
        int value;
        cin >> value;
        if (value == 0) { break; }
        cont.push_back(value);
    }
}

现在来看 std::find() 的使用方式。这个示例以及 populateContainer() 函数模板都假定用户足够配合，只会输入合法数字；它并没有对用户输入做错误检查。如何对 stream 输入做错误检查，会在第 13 章“揭开 C++ I/O 的面纱”中讨论。

vector<int> myVector;
populateContainer(myVector);


while (true) {
    print("Enter a number to lookup (0 to stop): ");
    int number;
    cin >> number;
    if (number == 0) { break; }
    auto endIt { cend(myVector) };
    auto it { find(cbegin(myVector), endIt, number) };
    if (it == endIt) {
        println("Could not find {}", number);
    } else {
        println("Found {}", *it);
    }
}

为了搜索 vector 中的全部元素，find() 通过 cbegin(myVector) 和 endIt 这两个 iterator 参数来调用，而 endIt 被定义为 cend(myVector)。如果你只想搜索某个子区间，只需要替换这两个 iterator 即可。

下面是一次示例运行：

Enter a number (0 to stop): 3
Enter a number (0 to stop): 4
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 0
Enter a number to lookup (0 to stop): 5
Found 5
Enter a number to lookup (0 to stop): 8
Could not find 8
Enter a number to lookup (0 to stop): 0

利用 if 语句中的 initializer，可以把 find() 调用和结果检查合并为一句：

if (auto it { find(cbegin(myVector), endIt, number) }; it == endIt) {
    println("Could not find {}", number);
} else {
    println("Found {}", *it);
}

某些容器，例如 map 和 set，会提供它们自己的 find() 成员函数；本书在第 18 章中讨论这些容器时已经给出过示例。

如果某个容器提供了与泛型算法功能相同的成员函数，你应当优先使用成员函数，因为它更快。例如，泛型 find() 算法即使作用于 map，也是线性时间；而 map 自己的 find() 成员函数则是对数时间。

find_if() 与 find() 很相似，只不过它接受的不是一个要匹配的具体元素，而是一个返回 true 或 false 的谓词回调函数。find_if() 会对 range 中的每个元素调用该谓词，直到谓词返回 true；此时，find_if() 返回一个指向该元素的 iterator。下面这个程序从用户那里读取考试分数，然后检查是否有任何一个分数是“满分”。这里把“满分”定义为 100 或更高。程序与前面的示例相似，这里只突出显示主要差异：

bool perfectScore(int num) { return num >= 100; }


int main()
{
    vector<int> myVector;
    populateContainer(myVector);


    auto endIt { cend(myVector) };
    auto it { find_if(cbegin(myVector), endIt, perfectScore) };
    if (it == endIt) {
        println("No perfect scores");
    } else {
        println("Found a \"perfect\" score of {}", *it);
    }
}

这个程序把 perfectScore() 函数的指针传给 find_if()，之后算法会对每个元素调用它，直到它返回 true。

除了向 find_if() 传递函数指针外，你也可以传递一个函数对象。第 15 章“重载 C++ 运算符”解释过：从 C++23 开始，如果一个函数对象的函数调用运算符不需要访问该类中任何非 static 数据成员或成员函数，那么这个调用运算符就可以被标记为 static。前面的 perfectScore() 函数就可以改写为一个带有 static 函数调用运算符的 PerfectScore 函数对象，如下所示：

class PerfectScore
{
    public:
        static bool operator()(int num) { return num >= 100; }
};

此时，对 find_if() 的调用需要改成：

auto it { find_if(cbegin(myVector), endIt, &PerfectScore::operator()) };

最后，除了 perfectScore() 函数或 PerfectScore 函数对象之外，你还可以使用在第 19 章中讨论过的 lambda 表达式：

auto it { find_if(cbegin(myVector), endIt, [](int i){ return i >= 100; }) };

accumulate 算法

Section titled “accumulate 算法”

我们经常需要计算容器中元素的和，或其他某种算术量。定义在 <numeric>（而非 <algorithm>）中的 accumulate() 函数，就是干这件事的。它最基本的形式，就是计算给定 range 中元素的总和。例如，下面这个函数会对以 span 给出的整数序列计算 arithmetic mean（算术平均值）。算术平均值就是所有元素之和除以元素个数：

double arithmeticMean(span<const int> values)
{
    double sum { accumulate(cbegin(values), cend(values), 0.0) };
    return sum / values.size();
}

accumulate() 的第三个参数是累加的初始值；在本例中，它应当是 0.0（加法的单位元），以便从一个全新的求和开始。

accumulate() 还有一个第二重载，允许调用方指定一个操作，用来代替默认的加法。这个操作以二元回调的形式给出。假设你想计算 geometric mean（几何平均值），也就是“序列中所有数字的乘积，再取其 1 / size 次方”。在这种情况下，你希望 accumulate() 计算的是乘积，而不是和。写法如下：

int product(int value1, int value2) { return value1 * value2; }


double geometricMean(span<const int> values)
{
    int mult { accumulate(cbegin(values), cend(values), 1, product) };
    return pow(mult, 1.0 / values.size());  // pow() 定义在 <cmath> 中
}

注意，这里把 product() 函数作为回调传给 accumulate()；而累加的初始值则是 1（乘法的单位元）。

你也可以不用单独的 product() 函数，而是改用 lambda 表达式：

double geometricMeanLambda(span<const int> values)
{
    int mult { accumulate(cbegin(values), cend(values), 1,
        [](int value1, int value2) { return value1 * value2; }) };
    return pow(mult, 1.0 / values.size());
}

你还可以使用第 19 章中提到的透明 multiplies<> 函数对象，来实现 geometricMean()：

double geometricMeanFunctor(span<const int> values)
{
    int mult { accumulate(cbegin(values), cend(values), 1, multiplies<>{}) };
    return pow(mult, 1.0 / values.size());
}

算法中的移动语义

Section titled “算法中的移动语义”

与标准库容器一样，标准库算法也会在合适的时候针对移动语义进行优化；也就是说，它们会移动对象，而不是执行潜在昂贵的复制操作。这能显著加速某些算法，例如本章稍后会详细讨论的 remove()。基于这一点，如果你想把自己定义的元素类存进容器中，就强烈建议你为这些类实现移动语义。任何类都可以通过实现移动构造函数和移动赋值运算符来获得移动语义。正如第 18 章所讨论的，这两个函数都应标记为 noexcept，否则标准库容器和算法将不会使用它们。关于如何为类添加移动语义，请参考第 9 章“精通类与对象”中的“实现移动语义”一节。

算法回调

Section titled “算法回调”

算法可以对传入的回调（例如函数对象与 lambda 表达式）生成多个副本，并对不同元素调用不同副本。

由于回调可能被复制多次，因此这类回调的副作用会受到严格限制。基本上，回调应当是无状态的。对函数对象来说，这意味着其函数调用运算符需要是 const；因此，你不能依赖函数对象内部状态在多次调用之间保持一致。对 lambda 表达式来说，同理，它们也不应该标记为 mutable。

当然也有例外。generate() 和 generate_n() 算法可以接受有状态回调，但即便如此，它们仍然会对回调做一次复制。而且，它们不会把这个副本返回给你，因此算法结束之后，你无法访问其中状态所发生的变化。唯一真正的例外是 for_each()。它会先把给定谓词复制一份到 for_each() 算法内部，并在结束时把这份副本返回给你。你可以通过这个返回值访问被改变后的状态。

为了防止回调被算法复制，你可以使用 std::ref() 辅助函数，把一个回调引用传给算法。这样可以确保算法始终使用同一个回调。例如，下面这段代码基于本章前面一个例子，不过这次使用的是一个存放在变量 isPerfectScore 中的 lambda 表达式。这个 lambda 表达式会统计自己被调用的次数，并把计数写到标准输出。isPerfectScore 会被传给 find_if() 算法，此时还没有使用 ref()。代码片段最后一条语句会额外显式调用 isPerfectScore 一次。

auto isPerfectScore { [tally = 0] (int i) mutable {
    println("{}", ++tally);  return i >= 100; } };


auto endIt { cend(myVector) };
auto it { find_if(cbegin(myVector), endIt, isPerfectScore) };
if (it != endIt) { println("Found a \"perfect\" score of {}", *it); }
println("---");
isPerfectScore(1);

输出可能如下：

Enter a number (0 to stop): 11
Enter a number (0 to stop): 22
Enter a number (0 to stop): 33
Enter a number (0 to stop): 0
1
2
3
---
1

从输出可以看到，find_if() 算法调用了 isPerfectScore 三次，因此输出了 1、2、3。而最后一行显示，对 isPerfectScore 的显式调用发生在另一个实例上，因为它又从 1 开始计数了。

现在，把对 find_if() 的调用改成下面这样：

auto it { find_if(cbegin(myVector), endIt, ref(isPerfectScore)) };

此时输出将会是 1、2、3、4，这就说明没有为 isPerfectScore 创建副本。

算法细节

Section titled “算法细节”

第 16 章按不同类别列出了所有可用的标准库算法。大多数算法定义在 <algorithm> 中，也有少数位于 <numeric> 中。它们都位于 std 命名空间。

本章的目标并不是以参考手册的方式，把所有可用算法逐条概览一遍。相反，我挑选了若干类别并为它们提供示例。只要掌握了这些算法的使用方式，你再去使用其他算法也不会有问题。关于 全部 算法的完整参考，请查阅标准库参考资料（见附录 B）。

不修改序列的算法

Section titled “不修改序列的算法”

不修改序列的算法，是指那些不会修改其所操作元素序列的算法。这类算法包括在一个 range 中搜索元素、比较两个 range，以及各种计数算法。

搜索算法

Section titled “搜索算法”

本章前面你已经看过两个搜索算法的例子：find() 和 find_if()。标准库还提供了若干其他变体，它们同样作用于元素序列。关于可用搜索算法及其复杂度，请参见第 16 章中的“搜索算法”一节。

所有这些算法默认都使用 operator== 或 < 作为比较运算符，但也都提供重载版本，允许你指定不同的比较回调。

下面是几个搜索算法的示例：

// 要搜索的元素序列。
vector myVector { 5, 6, 9, 8, 8, 3 };
auto beginIter { cbegin(myVector) };
auto endIter { cend(myVector) };


// 查找第一个不满足给定 lambda 表达式的元素。
auto it { find_if_not(beginIter, endIter, [](int i){ return i < 8; }) };
if (it != endIter) {
    println("First element not < 8 is {}", *it);
}


// 查找第一对相邻且相等的元素。
it = adjacent_find(beginIter, endIter);
if (it != endIter) {
    println("Found two consecutive equal elements with value {}", *it);
}


// 查找两个目标值中的第一个。
vector targets { 8, 9 };
it = find_first_of(beginIter, endIter, cbegin(targets), cend(targets));
if (it != endIter) {
    println("Found one of 8 or 9: {}", *it);
}


// 查找第一个子序列。
vector sub { 8, 3 };
it = search(beginIter, endIter, cbegin(sub), cend(sub));
if (it != endIter) {
    println("Found subsequence {{8,3}}");
} else {
    println("Unable to find subsequence {{8,3}}");
}


// 查找最后一个子序列（在这个例子里与第一个相同）。
auto it2 { find_end(beginIter, endIter, cbegin(sub), cend(sub)) };
if (it != it2) {
    println("Error: search and find_end found different subsequences "
         "even though there is only one match.");
}


// 查找第一段由两个连续 8 组成的子序列。
it = search_n(beginIter, endIter, 2, 8);
if (it != endIter) {
    println("Found two consecutive 8s");
} else {
    println("Unable to find two consecutive 8s");
}

输出如下：

First element not < 8 is 9
Found two consecutive equal elements with value 8
Found one of 8 or 9: 9
Found subsequence {8,3}
Found two consecutive 8s

专用搜索器

Section titled “专用搜索器”

search() 算法的一个可选参数允许你指定要使用的搜索算法。你有三个选择：default_searcher、boyer_moore_searcher 或 boyer_moore_horspool_searcher，它们都定义在 <functional> 中。后两者实现的是著名的 Boyer-Moore 和 Boyer-Moore-Horspool 搜索算法。它们比默认搜索器更高效，可用于在一段较大的文本中查找某个子串。Boyer-Moore 搜索器的复杂度如下（其中 N 是被搜索序列的大小，也就是 haystack；M 是要查找模式的大小，也就是 needle）：

  • 如果模式未找到，最坏情况复杂度为 O(N+M)。
  • 如果模式找到了，最坏情况复杂度为 O(N*M)。

以上是理论上的最坏复杂度。在实践中，这些专用搜索器往往是次线性的，优于 O(N)，也就是说，它们通常比默认版本快得多！之所以能做到次线性，是因为它们能够跳过字符，而不是检查 haystack 中的每一个字符。它们还有一个有趣特性：needle 越长，它们往往工作得越快，因为它们能在 haystack 中跳过更多字符。Boyer-Moore 和 Boyer-Moore-Horspool 的区别在于：后者在初始化和每次循环迭代中的常数开销更低；但它的最坏情况复杂度可能明显高于 Boyer-Moore。因此，具体该选哪一个，取决于你的具体使用场景。

下面是使用 Boyer-Moore 搜索器的一个示例：

string text { "This is the haystack to search a needle in." };
string toSearchFor { "needle" };
boyer_moore_searcher searcher { cbegin(toSearchFor), cend(toSearchFor) };
auto result { search(cbegin(text), cend(text), searcher) };
if (result != cend(text)) {
    println("Found the needle.");
} else {
    println("Needle not found.");
}

比较算法

Section titled “比较算法”

你可以用多种方式比较整段元素 range：equal()、mismatch()、lexicographical_compare() 和 lexicographical_compare_three_way()。这些算法的好处在于：你可以比较来自不同容器的序列。例如，你可以比较一个 vector 的内容和一个 list 的内容。通常来说，这些算法最适合顺序容器。它们的工作方式，是按位置逐一比较两个集合中对应位置上的值。下面逐个说明：

  • equal()：若所有对应元素都相等，则返回 true。最初，equal() 接受三个 iterator：第一个 range 的 begin/end iterator，以及第二个 range 的 begin iterator。这个版本要求两个 range 具有相同数量的元素。从 C++14 开始，又新增了一个接受四个 iterator 的重载：第一个 range 的 begin/end iterator，加上第二个 range 的 begin/end iterator。这个版本可以处理大小不同的 range。强烈建议总是使用四个 iterator 的版本，因为它更安全！
  • mismatch()：返回两个 iterator（每个 range 各一个），指出两个 range 在何处出现了不匹配。与 equal() 一样，也有三 iterator 版本和四 iterator 版本。这里同样建议使用四 iterator 版本，以提高安全性！
  • lexicographical_compare()：按顺序比较两个 range 中同一位置上的元素。如果第一个 range 中第一个不相等元素小于第二个 range 中对应位置的元素，则返回 true；或者，如果第一个 range 的元素比第二个少，且第一个 range 的全部元素都等于第二个 range 的前缀部分中对应元素，也会返回 true。lexicographical_compare() 之所以叫这个名字，是因为它类似于字典中比较字符串大小的规则，但把这套规则推广到了任意类型对象。
  • lexicographical_compare_three_way()：与 lexicographical_compare() 类似，但执行三路比较，并返回一个比较类别类型（strong_ordering、weak_ordering 或 partial_ordering，详见第 1 章“C++ 与标准库速成”），而不是一个布尔值。

下面是这些算法的示例：

vector<int> myVector;
list<int> myList;


println("Populate the vector:");
populateContainer(myVector);
println("Populate the list:");
populateContainer(myList);


// 比较这两个容器
if (equal(cbegin(myVector), cend(myVector),
          cbegin(myList), cend(myList))) {
    println("The two containers have equal elements");
} else {
    // 如果容器不相等，就找出原因
    auto miss { mismatch(cbegin(myVector), cend(myVector),
                         cbegin(myList), cend(myList)) };
    println("The following initial elements are the same in "
        "the vector and the list:");
    for (auto iter { cbegin(myVector) }; iter != miss.first; ++iter) {
        print("{}\t", *iter);
    }
    println("");
}


// 现在比较它们的字典序。
if (lexicographical_compare(cbegin(myVector), cend(myVector),
                            cbegin(myList), cend(myList))) {
    println("The vector is lexicographically first.");
} else {
    println("The list is lexicographically first.");
}

下面是一段程序示例输出：

Populate the vector:
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 7
Enter a number (0 to stop): 0
Populate the list:
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 9
Enter a number (0 to stop): 8
Enter a number (0 to stop): 0
The following initial elements are the same in the vector and the list:
5      6
The vector is lexicographically first.

此外，还有几个作用于单个 range 的比较算法：all_of()、any_of() 和 none_of()。下面是一些例子：

// all_of() 示例
vector vec2 { 1, 1, 1, 1 };
if (all_of(cbegin(vec2), cend(vec2), [](int i){ return i == 1; })) {
    println("All elements are == 1");
} else {
    println("Not all elements are == 1");
}


// any_of() 示例
vector vec3 { 0, 0, 1, 0 };
if (any_of(cbegin(vec3), cend(vec3), [](int i){ return i == 1; })) {
    println("At least one element == 1");
} else {
    println("No elements are == 1");
}


// none_of() 示例
vector vec4 { 0, 0, 0, 0 };
if (none_of(cbegin(vec4), cend(vec4), [](int i){ return i == 1; })) {
    println("All elements are != 1");
} else {
    println("Some elements are == 1");
}

输出如下：

All elements are == 1
At least one element == 1
All elements are != 1

计数算法

Section titled “计数算法”

不修改序列的计数算法包括 count() 和 count_if()。下面这个例子使用 count_if() 统计 vector 中满足某个条件的元素数量。条件通过 lambda 表达式给出，它按值捕获其外围作用域中的 value 变量：

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int value { 3 };
auto tally { count_if(cbegin(values), cend(values),
    [value](int i){ return i > value; }) };
println("Found {} values > {}.", tally, value);

输出如下：

Found 6 values > 3.

这个例子还可以扩展，以演示按引用捕获变量。下面的 lambda 表达式通过递增外围作用域中按引用捕获的变量，来统计自己被调用了多少次：

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int value { 3 };
int callCounter { 0 };
auto tally { count_if(cbegin(values), cend(values),
    [value, &callCounter](int i){ ++callCounter; return i > value; }) };
println("The lambda expression was called {} times.", callCounter);
println("Found {} values > {}.", tally, value);

输出如下：

The lambda expression was called 9 times.
Found 6 values > 3

修改序列的算法

Section titled “修改序列的算法”

标准库提供了多种 修改序列算法，用于完成诸如“把元素从一个 range 复制到另一个 range”“删除元素”“反转一个 range 中元素顺序”等任务。

有些修改算法使用 源区间 和 目标区间 的概念：它们从源 range 中读取元素，并把修改结果写入目标 range。copy() 就是此类算法的代表。

还有一些算法是 in-place 进行工作的；也就是说，它们只需要一个 range，例如 generate()。

修改算法不能向目标容器中插入元素。它们只能覆盖/修改目标中原本就已经存在的元素。第 17 章解释了如何借助迭代器适配器，真正把元素插入目标中。

第 16 章中的“修改序列的算法”一节列出了所有可用的修改算法，并对每个算法给出描述。本节则为其中一部分算法提供示例代码。只要你理解了本节讲解的这些算法，就不会对其他未举例的同类算法有使用困难。

generate

Section titled “generate”

generate() 算法要求一个公共区间，并会用第三个参数给出的函数回调所返回的值，去替换该 range 中现有的值。下面这个例子将 generate() 与 lambda 表达式结合使用，把 2、4、8、16 …… 这些数字放进一个 vector 中：

vector<int> values(10); // 创建一个含 10 个元素的 vector。
int value { 1 };
generate(begin(values), end(values), [&value]{ value *= 2; return value; });
println("{:n}", values);

输出如下：

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024

transform

Section titled “transform”

transform() 算法有多个重载。其中一个重载会对某个 range 中的每个元素调用回调，并期望回调返回一个新元素，再将该新元素存入指定的目标 range。如果你希望 transform() 原地工作，那么源区间和目标区间可以是同一个。其参数分别是：源序列的 begin/end iterator、目标序列的 begin iterator，以及回调。例如，下面这段代码会给 vector 中的每个元素都加上 100。populateContainer() 与本章前面定义的是同一个函数。

vector<int> myVector;
populateContainer(myVector);


println("The vector contains: {:n}", myVector);
transform(begin(myVector), end(myVector), begin(myVector),
    [](int i){ return i + 100;});
println("The vector contains: {:n}", myVector);

一种可能的输出如下：

Enter a number (0 to stop): 1
Enter a number (0 to stop): 11
Enter a number (0 to stop): 0
The vector contains: 1, 11
The vector contains: 101, 111

transform() 的另一个重载会对两个 range 中对应位置的元素对调用一个二元函数。它要求：第一个 range 的 begin/end iterator、第二个 range 的 begin iterator，以及目标 range 的 begin iterator。下面这个例子创建两个 vector，然后使用 transform() 计算成对元素之和，并把结果存回第一个 vector：

vector<int> vec1, vec2;
println("Vector1:"); populateContainer(vec1);
println("Vector2:"); populateContainer(vec2);
if (vec2.size() < vec1.size())
{
    println("Vector2 should be at least the same size as vector1.");
    return 1;
}


println("Vector1: {:n}", vec1);
println("Vector2: {:n}", vec2);
transform(begin(vec1), end(vec1), begin(vec2), begin(vec1),
    [](int a, int b){ return a + b; });
println("Vector1: {:n}", vec1);
println("Vector2: {:n}", vec2);

输出可能如下：

Vector1:
Enter a number (0 to stop): 1
Enter a number (0 to stop): 2
Enter a number (0 to stop): 0
Vector2:
Enter a number (0 to stop): 11
Enter a number (0 to stop): 22
Enter a number (0 to stop): 33
Enter a number (0 to stop): 0
Vector1: 1, 2
Vector2: 11, 22, 33
Vector1: 12, 24
Vector2: 11, 22, 33

copy

Section titled “copy”

copy() 算法允许你把元素从一个 range 复制到另一个 range 中，复制顺序从第一个元素到最后一个元素。源区间和目标区间必须不同，但在某些限制下，它们可以重叠。限制规则是：对于 copy(b,e,d)，如果 d 在 b 之前，那么重叠没有问题；但如果 d 落在 [b,e) 区间内，则行为未定义。和所有修改算法一样，copy() 不能向目标区间中插入元素；它只会覆盖目标位置已有的元素。第 17 章解释了如何使用迭代器适配器，借助 copy() 向容器或 stream 中插入元素。

下面是一个简单的 copy() 示例，它调用 vector 的 resize() 成员函数，以确保目标容器中有足够空间。它会把 vec1 中的全部元素复制到 vec2 中。

vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(size(vec1));
copy(cbegin(vec1), cend(vec1), begin(vec2));
println("{:n}", vec2);

标准库还提供 copy_backward() 算法，它会从源区间向目标区间反向复制元素。换句话说，它会先从源区间的最后一个元素开始，把它放到目标区间的最后一个位置，然后每复制一个元素就向前移动。对 copy_backward() 来说，源区间和目标区间仍然必须是不同的 range，但同样允许在某些条件下发生重叠。此时的限制规则为：对 copy_backward(b,e,d)，如果 d 位于 e 之后，则重叠没有问题；但如果 d 落在 (b,e] 内，则行为未定义。前面的例子可以改写成用 copy_backward() 替代 copy()，如下所示。注意，第三个参数必须是 end(vec2)，而不是 begin(vec2)。输出与使用 copy() 的版本相同。

copy_backward(cbegin(vec1), cend(vec1), end(vec2));

copy_if() 的工作方式是：输入 range 由两个 iterator 指定，输出目标由一个 iterator 指定，再配合一个谓词（例如函数或 lambda 表达式）。算法会把所有满足谓词的元素复制到目标区间中。请记住，copy 不会创建或扩展容器；它只会替换已有元素，因此目标区间必须足够大，以容纳所有要复制的元素。当然，在复制完成后，目标区间中“最后一个被复制元素之后”的那部分空间，通常也应该删除。为此，copy_if() 会返回一个 iterator，指向目标区间中“最后一个被复制元素之后”的位置。你可以用它来确定应该从目标容器中删除多少元素。下面这个例子就演示了这一点，它只把偶数复制到 vec2：

vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(size(vec1));
auto endIterator { copy_if(cbegin(vec1), cend(vec1),
         begin(vec2), [](int i){ return i % 2 == 0; }) };
vec2.erase(endIterator, end(vec2));
println("{:n}", vec2);

copy_n() 会把源区间中的 n 个元素复制到目标区间中。copy_n() 的第一个参数是起始 iterator，第二个参数是要复制元素个数的整数，第三个参数是目标 iterator。copy_n() 并不会做边界检查，因此你必须保证“起始 iterator + 要复制的元素个数”不会超过源集合的 end()，否则程序就会产生未定义行为。示例如下：

vector<int> vec1, vec2;
populateContainer(vec1);
size_t tally { 0 };
print("Enter number of elements you want to copy: ");
cin >> tally;
tally = min(tally, size(vec1));
vec2.resize(tally);
copy_n(cbegin(vec1), tally, begin(vec2));
println("{:n}", vec2);

move

Section titled “move”

与移动相关的算法有两个：move() 和 move_backward()。它们都使用移动语义（详见第 9 章）。如果你希望这些算法能作用在“元素类型为你自己定义类型”的容器上，就必须在你的元素类中提供 move assignment operator；下面这个例子就展示了这一点。main() 函数创建了一个包含三个 MyClass 对象的 vector，然后把这些元素从 vecSrc 移动到 vecDst。注意，代码中实际上出现了两种不同的 move()：单参数版本的 move() 定义在 <utility> 中，它的作用是把一个 lvalue 转成 rvalue；而三参数版本的 move() 则是标准库算法，用于在容器之间移动元素。关于如何实现 move assignment operator，以及如何使用单参数版 std::move()，请参考第 9 章。

class MyClass
{
    public:
        MyClass() = default;
        MyClass(const MyClass& src) = default;
        explicit MyClass(string str) : m_str { move(str) } {}
        virtual ~MyClass() = default;


        // 移动赋值运算符
        MyClass& operator=(MyClass&& rhs) noexcept {
            if (this == &rhs) { return *this; }
            m_str = move(rhs.m_str);
            println("Move operator= (m_str={})", m_str);
            return *this;
        }


        void setString(string str) { m_str = move(str); }
        const string& getString() const { return m_str; }
    private:
        string m_str;
};


int main()
{
    vector<MyClass> vecSrc { MyClass { "a" }, MyClass { "b" }, MyClass { "c" } };
    vector<MyClass> vecDst(vecSrc.size());
    move(begin(vecSrc), end(vecSrc), begin(vecDst));
    for (const auto& c : vecDst) { print("{} ", c.getString()); }
}

输出如下：

Move operator= (m_str=a)
Move operator= (m_str=b)
Move operator= (m_str=c)
a b c

move_backward() 使用与 move() 相同的移动机制，只不过它从最后一个元素向第一个元素移动。对 move() 和 move_backward() 来说，源区间和目标区间允许重叠，其限制规则与 copy() 和 copy_backward() 相同。

replace

Section titled “replace”

replace() 与 replace_if() 算法会把某个 range 中与给定值匹配、或满足给定谓词的元素，替换成一个新值。以 replace_if() 为例：它的第一和第二个参数指定要处理的元素范围；第三个参数是一个返回 true 或 false 的回调；如果它返回 true，容器中的值就会被第四个参数给出的新值所替换；如果返回 false，则保持原值不变。

例如，你可能希望把容器中的所有奇数都替换为 0：

vector<int> values;
populateContainer(values);
replace_if(begin(values), end(values), [](int i){ return i % 2 != 0; }, 0);
println("{:n}", values);

replace() 和 replace_if() 还有另外几个变体：replace_copy() 和 replace_copy_if()。它们会把结果复制到另一个目标区间中。它们与 copy() 类似，因此目标区间必须已经足够大，能够容纳复制后的元素。

erase

Section titled “erase”

正如第 18 章所介绍的，std::erase() 与 std::erase_if() 支持几乎所有标准库容器。官方上，这类操作被称为 统一容器擦除。erase() 会从容器中删除所有与给定值匹配的元素，而 erase_if() 会删除所有满足给定谓词的元素。这两个算法要求传入的是一个容器引用，而不是公共区间；它们也是从容器中移除元素的首选方式。

例如，下面这段代码会从一个 vector<string> 中删掉所有空字符串，并且让 erase_if() 完成全部工作：

vector<string> values {"", "one", "", "two", "three", "four"};
println("{:n}", values);
erase_if(values, [](const string& str){ return str.empty(); });
println("{:n}", values);

输出如下：

"", "one", "", "two", "three", "four"
"one", "two", "three", "four"

remove

Section titled “remove”

前一节介绍的 erase() 与 erase_if() 从 C++20 才开始可用。不过，了解 C++20 之前的做法依然很有必要，因为你会在旧代码中频繁见到。一种你也许会首先想到的办法，是查看容器文档，确认它是否提供 erase() 成员函数，然后遍历所有元素，对每个满足条件的元素调用 erase()。vector 就是一个拥有 erase() 成员函数的容器。但如果把这种做法应用在 vector 上，会非常低效：因为为了保持 vector 在内存中的连续性，它会引发大量内存移动操作，从而带来二次复杂度。而且，这种写法也更容易出错，因为每次调用 erase() 之后，你都必须非常小心地维护 iterator 的有效性。举个例子，下面这个函数会在不使用算法的前提下，从一个 vector<string> 中移除空字符串。注意 for 循环内部对 iter 的小心处理方式：

void removeEmptyStringsWithoutAlgorithms(vector<string>& strings)
{
    for (auto iter { begin(strings) }; iter != end(strings); ) {
        if (iter->empty()) {
            iter = strings.erase(iter);
        } else {
            ++iter;
        }
    }
}

这种写法低效且不推荐。对此问题更好的解决方案，是接下来要讲的 remove-erase-idiom，它具有线性时间复杂度。

remove 家族算法只能访问 iterator 抽象，而不能直接访问容器本身。因此，它们实际上无法真正从底层容器中删除元素。相反，它们会把“与给定值或谓词匹配的元素”用“后面第一个不匹配的元素”来覆盖。这个过程通过 move assignment 完成。结果就是：所有应该保留的元素都会被移动到 range 的前部。这样一来，整个 range 就会被分成两部分：需要保留的元素，以及需要删除的元素。算法返回一个 iterator，指向“应被删除那段元素范围”的第一个元素。你必须注意不要再使用那段范围中的任何元素，因为它们很可能已经被移动过。对于这个返回的 iterator，你唯一要做的，就是再调用一次容器的 erase()，把从该 iterator 到 range 末尾的所有元素真正删除。因此，流程就是：先调用 remove() 或 remove_if()，然后再调用容器的 erase()，删除从返回 iterator 到末尾的全部元素。这个过程就叫做 remove-erase-idiom。下面是一个使用这种习惯用法实现 removeEmptyStrings() 的示例：

void removeEmptyStrings(vector<string>& strings)
{
    auto it { remove_if(begin(strings), end(strings),
        [](const string& str){ return str.empty(); }) };
    // 擦除被“移走”的元素。
    strings.erase(it, end(strings));
}

使用 remove-erase-idiom 时，一定不要忘记传给 erase() 的第二个参数！如果忘了这个第二参数，那么 erase() 只会删除容器中的单个元素，也就是第一个参数所指向的那个元素。

remove_copy() 和 remove_copy_if() 是 remove() 与 remove_if() 的变体。它们不会修改源区间，而是把所有被保留下来的元素复制到另一个目标区间中。它们与 copy() 类似，因此目标区间必须已经足够大，以容纳这些新元素。

unique

Section titled “unique”

unique() 算法可以看作 remove() 的一个特例，它会删除所有相邻重复元素。list 容器提供了自己的 unique() 成员函数，其语义与此相同。通常来说，你应当在已排序序列上使用 unique()；当然，在未排序序列上运行它也并不会被禁止。

unique() 的工作方式与 remove() 类似：它会把应该保留的元素移动到 range 的前部，并返回一个 iterator，指向“待删除元素范围”的第一个元素。和 remove-erase-idiom 一样，调用 unique() 之后，必须紧接着调用 erase()。

unique() 的基本形式是在原地工作；此外，还存在一个名为 unique_copy() 的算法变体，它会把结果复制到新的目标区间中。

第 18 章已经给出过 list::unique() 的示例，因此这里不再重复一般形式的例子。

shuffle

Section titled “shuffle”

shuffle() 会以线性复杂度把一个 range 中的元素随机打乱顺序。它非常适合实现像“洗牌”这样的任务。shuffle() 需要三个参数：待打乱 range 的 begin/end iterator，以及一个 uniform random number generator 对象，用来指定随机数如何生成。示例如下（关于随机数引擎的使用以及如何“seed”，请参见第 23 章“随机数设施”）：

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };


random_device seeder;
default_random_engine generator { seeder() };


for (int i { 0 }; i < 6; ++i) {
    shuffle(begin(values), end(values), generator);
    println("{:n}", values);
}

一种可能的输出如下：

8, 6, 7, 5, 4, 1, 2, 9, 3
4, 1, 6, 2, 3, 7, 5, 9, 8
1, 4, 2, 5, 6, 8, 7, 3, 9
8, 4, 2, 7, 5, 9, 1, 6, 3
8, 9, 1, 7, 4, 5, 2, 6, 3
1, 7, 8, 5, 4, 3, 9, 6, 2

sample

Section titled “sample”

sample() 算法会从给定源区间中随机选出 n 个元素，并把它们存入目标区间。它需要五个参数：

  • 采样源区间的 begin/end iterator
  • 存放随机选中元素的目标区间 begin iterator
  • 要选取的元素数量
  • 一个随机数引擎

示例如下（关于随机数引擎与 seed 的细节，请参见第 23 章）：

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const size_t numberOfSamples { 5 };
vector<int> samples(numberOfSamples);


random_device seeder;
default_random_engine generator { seeder() };


for (int i { 0 }; i < 6; ++i) {
    sample(cbegin(values), cend(values), begin(samples),
        numberOfSamples, generator);
    println("{:n}", samples);
}

一种可能的输出如下：

1, 4, 7, 8, 9
1, 3, 4, 7, 9
2, 3, 4, 5, 7
3, 5, 6, 7, 9
1, 2, 3, 6, 7
1, 2, 4, 5, 8

reverse

Section titled “reverse”

reverse() 算法会反转一个 range 中元素的顺序：第一个元素与最后一个交换，第二个与倒数第二个交换，以此类推。

reverse() 的基本形式是原地工作，需要两个参数：待处理 range 的 begin/end iterator。它还有一个算法变体 reverse_copy()，会把结果复制到新的目标区间中，需要三个参数：源区间的 begin/end iterator，以及目标区间的 begin iterator。目标区间必须已经足够大，以容纳新元素。

下面是使用 reverse() 的一个例子：

vector<int> values;
populateContainer(values);
reverse(begin(values), end(values));
println("{:n}", values);

移位元素

Section titled “移位元素”

shift_left() 和 shift_right() 算法会通过移动元素到新位置，来实现对给定 range 中元素的左移和右移。shift_left() 返回一个指向新 range 末尾的 iterator，而 shift_right() 返回一个指向新 range 开始的 iterator。调用任一算法后，你都必须将这个返回 iterator 传给 erase()，以删除“从某一端移出去”的那些元素。示例如下：

vector values { 11, 22, 33, 44, 55 };
println("{:n}", values);


// 向左移动 2 个位置。
auto newEnd { shift_left(begin(values), end(values), 2) };
// 将 vector 调整为正确大小。
values.erase(newEnd, end(values));
println("{:n}", values);


// 向右移动 2 个位置。
auto newBegin { shift_right(begin(values), end(values), 2) };
// 将 vector 调整为正确大小。
values.erase(begin(values), newBegin);
println("{:n}", values);

输出如下：

11, 22, 33, 44, 55
33, 44, 55
33

操作型算法

Section titled “操作型算法”

这一类里只有两个算法：for_each() 和 for_each_n()。它们会对一个 range 中的每个元素（for_each()）或前 n 个元素（for_each_n()）执行一个回调。如果给定的 iterator 类型不是 const，那么回调也可以修改该 range 中的元素。这里提到这两个算法，是为了让你知道它们存在；不过在很多时候，直接使用简单的基于 range 的 for 循环，反而更容易读，也更直观。

for_each

Section titled “for_each”

下面是一个使用泛型 lambda 表达式打印 map 中元素的示例：

map<int, int> myMap { { 4, 40 }, { 5, 50 }, { 6, 60 } };
for_each(cbegin(myMap), cend(myMap), [](const auto& p)
    { println("{} -> {}", p.first, p.second); });

其中 p 的类型是 const pair<const int, int>&。输出如下：

4 -> 40
5 -> 50
6 -> 60

下面这个例子展示了如何结合 for_each() 和 lambda 表达式，同时计算一个元素 range 的和与积。这个 lambda 表达式显式只捕获它所需要的变量，并且按引用捕获；否则，在 lambda 表达式内对 sum 和 product 所做的修改，就不会在 lambda 外部可见。

vector<int> myVector;
populateContainer(myVector);


int sum { 0 };
int product { 1 };
for_each(cbegin(myVector), cend(myVector),
    [&sum, &product](int i){
        sum += i;
        product *= i;
});
println("The sum is {}", sum);
println("The product is {}", product);

这个例子也可以改写成函数对象的形式，把你想在 for_each() 处理完整个 range 之后取得的信息累积到函数对象内部。比如，你可以编写一个 SumAndProduct 函数对象，在一次遍历中同时追踪总和与总积：

class SumAndProduct
{
    public:
        void operator()(int value)
        {
            m_sum += value;
            m_product *= value;
        }


        int getSum() const { return m_sum; }
        int getProduct() const { return m_product; }
    private:
        int m_sum { 0 };
        int m_product { 1 };
};


int main()
{
    vector<int> myVector;
    populateContainer(myVector);


    SumAndProduct calculator;
    calculator = for_each(cbegin(myVector), cend(myVector), calculator);
    println("The sum is {}", calculator.getSum());
    println("The product is {}", calculator.getProduct());
}

你也许会想忽略 for_each() 的返回值，然后在算法结束后直接从 calculator 中读取信息。但那样并不行，因为 for_each() 会复制这个函数对象，并在结束时返回那份副本。为了确保行为正确，你必须接住这个返回值。

另一种做法，是像本章前面讲过的那样，使用 std::ref() 按引用传入 calculator：

for_each(cbegin(myVector), cend(myVector), ref(calculator));

关于 for_each() 还有最后一点（同样适用于下一节将讨论的 for_each_n()）：其回调允许接受一个“reference-to-non-const”参数，并对其进行修改。这会直接改变实际 range 中的值。示例如下：

vector values { 11, 22, 33, 44 };
// 将 values vector 中的每个元素都乘以 2。
for_each(begin(values), end(values), [](auto& value) { value *= 2; });
println("{:n}", values);

for_each_n

Section titled “for_each_n”

for_each_n() 需要一个 range 的 begin iterator、要遍历的元素个数 n，以及一个回调。它返回一个等于 begin + n 的 iterator。与往常一样，它不执行边界检查。下面这个例子只遍历 map 的前两个元素：

map<int, int> myMap { { 4, 40 }, { 5, 50 }, { 6, 60 } };
for_each_n(cbegin(myMap), 2, [](const auto& p)
    { println("{} -> {}", p.first, p.second); });

Partition 算法

Section titled “Partition 算法”

partition_copy() 会把源区间中的元素复制到两个不同的目标区间中。每个元素进入哪个目标区间，由一个谓词的结果（true 或 false）决定。partition_copy() 返回的是一对 iterator：分别指向第一个和第二个目标区间中“最后一个复制元素之后”的位置。与前面 copy_if() 的例子一样，这两个返回的 iterator 可以配合 erase() 使用，以从两个目标区间中删去多余元素。下面的代码片段要求用户输入若干整数，然后把它们划分到两个目标 vector 中：一个保存偶数，另一个保存奇数。

vector<int> values, vecOdd, vecEven;
populateContainer(values);
vecOdd.resize(size(values));
vecEven.resize(size(values));


auto pairIters { partition_copy(cbegin(values), cend(values),
    begin(vecEven), begin(vecOdd),
    [](int i){ return i % 2 == 0; }) };


vecEven.erase(pairIters.first, end(vecEven));
vecOdd.erase(pairIters.second, end(vecOdd));


println("Even numbers: {:n}", vecEven);
println("Odd numbers: {:n}", vecOdd);

输出可能如下：

Enter a number (0 to stop): 11
Enter a number (0 to stop): 22
Enter a number (0 to stop): 33
Enter a number (0 to stop): 44
Enter a number (0 to stop): 0
Even numbers: 22, 44
Odd numbers: 11, 33

partition() 算法会重新排列一个序列，使得所有令谓词返回 true 的元素都排在所有令其返回 false 的元素之前，但不会保持每个分区内部元素的原始顺序。下面这个例子演示了如何把一个 vector 划分成“所有偶数在前，所有奇数在后”：

vector<int> values;
populateContainer(values);
partition(begin(values), end(values), [](int i){ return i % 2 == 0; });
println("Partitioned result: {:n}", values);

输出可能如下：

Enter a number (0 to stop): 55
Enter a number (0 to stop): 44
Enter a number (0 to stop): 33
Enter a number (0 to stop): 22
Enter a number (0 to stop): 11
Enter a number (0 to stop): 0
Partitioned result: 22, 44, 33, 55, 11

另外还有一些 partition 算法可用。完整列表请参见第 16 章。

排序算法

Section titled “排序算法”

标准库提供了多种排序算法。排序算法会重新排列容器内容，使得集合中顺序相邻的元素之间保持某种有序关系。因此，它只适用于顺序容器。对于有序关联容器而言，排序没有意义，因为它们本来就保持元素有序；而对无序关联容器而言，排序同样没有意义，因为它们根本没有顺序概念。有些容器（例如 list 和 forward_list）提供了自己的排序成员函数，因为这些成员函数的实现可以比泛型排序机制更高效。因此，泛型排序算法最适合 vector、deque、array 和 C 风格数组。

sort() 算法通常以 O(N log N) 的时间复杂度对一个 range 进行排序。对某个 range 调用 sort() 后，其中元素会按照 operator< 所定义的非递减顺序（从小到大）排列。如果你不喜欢这个顺序，可以指定不同的比较器，比如 greater。

sort() 的一个变体叫做 stable_sort()，它会保持相等元素之间的相对顺序，但效率低于 sort()。

下面是一个使用透明 greater<> 比较器的 sort() 示例：

vector<int> values;
populateContainer(values);
sort(begin(values), end(values), greater<>{});

此外还有 is_sorted()，用于判断某个 range 是否已排序；以及 is_sorted_until()，用于返回一个 iterator，使得在它之前的所有元素都是已排序的。

nth_element() 是一个非常强大的 选择算法。给定一个元素 range，以及一个指向该 range 中第 n 个元素位置的 iterator，该算法会重新排列 range 中的元素，使得“nth 所指向位置上的元素”，恰好就是“如果整个 range 已经排序，这个位置上会出现的元素”。此外，它还会进一步重排元素，使得 nth 元素之前的所有元素都小于它，而它之后的所有元素都大于它。这个算法的有趣之处在于：它能在线性时间 O(n) 内做到这一切。你当然也可以不用 nth_element()，而是先把整个 range 排序，再取出感兴趣的元素；但那样的复杂度会变成线性对数时间，也就是 O(n log n)。

这些描述听起来有点抽象，所以我们直接来看实际用法。第一个例子是：找出给定 range 中第三大的元素。该例假定用户至少输入三个值。

vector<int> values;
populateContainer(values);
// 找出第三大的值。
nth_element(begin(values), begin(values) + 2, end(values), greater<>{});
println("3rd largest value: {}", values[2]);

另一个例子，是从一个 range 中取得最大的五个元素，并让它们按有序方式排列。该例假定用户至少输入五个值。

vector<int> values;
populateContainer(values);
// 取得最大的 5 个元素，并按顺序排列。
nth_element(begin(values), begin(values) + 4, end(values), greater<>{});
// nth_element() 已经把元素做了分区，现在对前半部分排序。
sort(begin(values), begin(values) + 5);
// 最后输出这个已排序的子区间。
for_each_n(begin(values), 5, [](const auto& element) { print("{}  ", element); });

二分查找算法

Section titled “二分查找算法”

有几种搜索算法只能作用于“已经排序”或至少“针对待搜索元素已经完成分区”的序列。这些算法包括 binary_search()、lower_bound()、upper_bound() 和 equal_range()。注意，像 map 和 set 这样的关联容器都有等价成员函数，因此在这些容器上你应使用成员函数版本。如何使用这些成员函数，请参考第 18 章中的相关示例。

lower_bound() 算法会在一个已排序的 range 中，找到“第一个不小于（也就是大于或等于）给定值”的元素。它经常用于判断某个新值应插入到已排序 vector 的哪个位置，从而让 vector 仍保持有序。示例如下：

vector<int> values;
populateContainer(values);


// 对容器排序
sort(begin(values), end(values));
println("Sorted vector: {:n}", values);


while (true) {
    int number;
    print("Enter a number to insert (0 to stop): ");
    cin >> number;
    if (number == 0) { break; }


    auto iter { lower_bound(begin(values), end(values), number) };
    values.insert(iter, number);
    println("New vector: {:n}", values);
}

binary_search() 算法会在线性查找之外，以对数时间复杂度找到匹配元素。它需要：指定待查找 range 的 begin/end iterator、要查找的值，以及可选比较器回调。若找到该值，则返回 true；否则返回 false。二分查找要求 range 已排序。其工作方式是：先比较 range 中间位置的元素，然后根据该元素是大于还是小于待查找值，继续去左半段或右半段中间位置比较。这个过程会持续进行，直到找到目标元素。实质上，算法每次迭代都会把搜索范围减半，因此具有对数复杂度。下面是一个示例：

vector<int> values;
populateContainer(values);


// 对容器排序
sort(begin(values), end(values));


while (true) {
    print("Enter a number to find (0 to stop): ");
    int number;
    cin >> number;
    if (number == 0) { break; }
    if (binary_search(cbegin(values), cend(values), number)) {
        println("That number is in the vector.");
    } else {
        println("That number is not in the vector.");
    }
}

集合算法

Section titled “集合算法”

集合算法可用于任何已排序 range。includes() 算法实现的是标准的“子集判断”：检查一个已排序 range 中的所有元素，是否都包含在另一个已排序 range 中（顺序无关）。

set_union()、set_intersection()、set_difference() 和 set_symmetric_difference() 算法则分别实现这些集合运算的标准语义。在集合论中，union 的结果是“属于任意一个集合的所有元素”；intersection 的结果是“同时属于两个集合的所有元素”；difference 的结果是“属于第一个集合但不属于第二个集合的所有元素”；symmetric difference 的结果则是集合的“异或”，也就是“属于其中一个集合，但不同时属于两个集合”的所有元素。

一定要确保你的结果 range 足够大，能够容纳这些运算的结果。对 set_union() 与 set_symmetric_difference() 来说，结果最多是两个输入 range 大小之和；对 set_intersection() 来说，结果最多等于较小那个输入 range 的大小；对 set_difference() 来说，结果最多等于第一个 range 的大小。

你不能使用关联容器（包括 set）的公共区间来存储这些结果，因为它们不允许改变 key。

下面我们通过示例来看看这些集合算法的实际效果。首先，定义一个受约束的 DumpRange() 函数模板，用来把给定 range 的元素写到标准输出流；其实现如下。ranges::subrange() 会把由一对 iterator 表示的公共区间转成一个真正的 range，然后就可以把它传给 println()。

template <forward_iterator Iterator>
void DumpRange(string_view message, Iterator begin, Iterator end)
{
    println("{}{:n}", message, ranges::subrange(begin, end));
}

有了这个辅助函数之后，下面就是集合算法的使用示例：

vector<int> vec1, vec2, result;
println("Enter elements for set 1:");
populateContainer(vec1);
println("Enter elements for set 2:");
populateContainer(vec2);


// 集合算法要求输入 range 已排序
sort(begin(vec1), end(vec1));
sort(begin(vec2), end(vec2));


println("Set 1: {:n}", vec1);
println("Set 2: {:n}", vec2);


if (includes(cbegin(vec1), cend(vec1), cbegin(vec2), cend(vec2))) {
    println("The second set is a subset of the first.");
}
if (includes(cbegin(vec2), cend(vec2), cbegin(vec1), cend(vec1))) {
    println("The first set is a subset of the second");
}


result.resize(size(vec1) + size(vec2));
auto newEnd { set_union(cbegin(vec1), cend(vec1), cbegin(vec2),
    cend(vec2), begin(result)) };
DumpRange("The union is: ", begin(result), newEnd);


newEnd = set_intersection(cbegin(vec1), cend(vec1), cbegin(vec2),
    cend(vec2), begin(result));
DumpRange("The intersection is: ", begin(result), newEnd);


newEnd = set_difference(cbegin(vec1), cend(vec1), cbegin(vec2),
    cend(vec2), begin(result));
DumpRange("The difference between set 1 and 2 is: ", begin(result), newEnd);


newEnd = set_symmetric_difference(cbegin(vec1), cend(vec1),
    cbegin(vec2), cend(vec2), begin(result));
DumpRange("The symmetric difference is: ", begin(result), newEnd);

下面是一段程序示例输出：

Enter elements for set 1:
Enter a number (0 to stop): 5
Enter a number (0 to stop): 6
Enter a number (0 to stop): 7
Enter a number (0 to stop): 8
Enter a number (0 to stop): 0
Enter elements for set 2:
Enter a number (0 to stop): 8
Enter a number (0 to stop): 9
Enter a number (0 to stop): 10
Enter a number (0 to stop): 0
Set 1: 5, 6, 7, 8
Set 2: 8, 9, 10
The union is: 5, 6, 7, 8, 9, 10
The intersection is: 8
The difference between set 1 and set 2 is: 5, 6, 7
The symmetric difference is: 5, 6, 7, 9, 10

merge() 算法允许你把两个已排序 range 合并起来，同时保持排序顺序不变。结果仍是一个有序 range，其中包含来自两个源 range 的全部元素。它在线性时间内完成。所需参数如下：

  • 第一个源区间的 begin/end iterator
  • 第二个源区间的 begin/end iterator
  • 目标区间的 begin iterator
  • 可选比较器回调

即便不用 merge()，你也能通过“先拼接两个 range，再对结果应用 sort()”达到同样效果；但那样效率会更低，复杂度是 O(N log N)，而不是 merge() 的线性复杂度。

一定要确保你提供了足够大的目标区间来存放 merge 的结果！

下面这个例子演示了 merge()：

vector<int> vectorOne, vectorTwo, vectorMerged;
println("Enter values for first vector:");
populateContainer(vectorOne);
println("Enter values for second vector:");
populateContainer(vectorTwo);


// 对两个容器都先排序
sort(begin(vectorOne), end(vectorOne));
sort(begin(vectorTwo), end(vectorTwo));


// 确保目标 vector 足够大，可以容纳来自两个源 vector 的全部值。
vectorMerged.resize(size(vectorOne) + size(vectorTwo));


merge(cbegin(vectorOne), cend(vectorOne),
      cbegin(vectorTwo), cend(vectorTwo), begin(vectorMerged));


println("Merged vector: {:n}", vectorMerged);

最小值/最大值算法

Section titled “最小值/最大值算法”

min() 和 max() 算法通过 operator< 或用户提供的二元谓词，比较任意类型的两个或多个元素，并分别返回对最小元素或最大元素的 const 引用。minmax() 算法则返回一个 pair，其中同时包含两个或多个元素中的最小值与最大值。这些算法不作用于公共区间或 range。

min_element() 和 max_element() 算法则作用于公共区间，并分别返回指向该 range 中最小元素或最大元素的 iterator。minmax_element() 也作用于公共区间，但返回的是一对 iterator，分别指向该 range 中最小元素和最大元素。

下面这个程序给出了一些示例：

int x { 4 }, y { 5 };
println("x is {} and y is {}", x, y);
println("Max is {}", max(x, y));
println("Min is {}", min(x, y));


// 在超过两个值上使用 max() 和 min()。
int x1 { 2 }, x2 { 9 }, x3 { 3 }, x4 { 12 };
println("Max of 4 elements is {}", max({ x1, x2, x3, x4 }));
println("Min of 4 elements is {}", min({ x1, x2, x3, x4 }));


// 使用 minmax()。
auto p2 { minmax({ x1, x2, x3, x4 }) }; // p2 的类型是 pair<int, int>。
println("Minmax of 4 elements is <{},{}>", p2.first, p2.second);


// 使用 minmax() + structured bindings。
auto [min1, max1] { minmax({ x1, x2, x3, x4 }) };
println("Minmax of 4 elements is <{},{}>", min1, max1);


// 使用 minmax_element() + structured bindings。
vector values { 11, 33, 22 };
auto [min2, max2] { minmax_element(cbegin(values), cend(values)) };
println("minmax_element() result: <{},{}>", *min2, *max2);

程序输出如下：

x is 4 and y is 5
Max is 5
Min is 4
Max of 4 elements is 12
Min of 4 elements is 2
Minmax of 4 elements is <2,12>
Minmax of 4 elements is <2,12>
minmax_element() result: <11,33>

std::clamp() 是定义在 <algorithm> 中的一个小型辅助函数，用来确保某个值（v）处于给定最小值（lo）和最大值（hi）之间。如果 v < lo，它返回对 lo 的引用；如果 v > hi，它返回对 hi 的引用；否则返回对 v 的引用。示例如下：

println("{}", clamp(-3, 1, 10));
println("{}", clamp(3, 1, 10));
println("{}", clamp(22, 1, 10));

输出如下：

1
3
10

并行算法

Section titled “并行算法”

C++ 支持让 60 多个基于 iterator 的标准库算法并行执行，以提升性能。示例包括 std::for_each()、all_of()、copy()、count_if()、find()、replace()、search()、sort()、transform() 等等。

支持并行执行的算法都会把 execution policy（执行策略）作为可选的第一个参数。执行策略可以让你指定：某个算法是否允许被向量化，以及/或者是否允许并行执行。当编译器对代码做向量化时，它会用一条 向量 CPU 指令 替换多条 CPU 指令。一条向量指令能在一次硬件指令中，对多份数据执行同一种操作。这也被称为 single instruction multiple data（SIMD，单指令多数据）指令。标准定义了四种执行策略类型，以及对应的全局实例；它们都定义在 <execution> 中的 std::execution 命名空间里：

Execution policy 类型全局实例说明
sequenced_policyseq算法不允许并行，也不允许向量化执行。
parallel_policypar算法允许并行执行，但不允许向量化。
parallel_unsequenced_policypar_unseq算法允许并行执行和向量化执行，并且可以在不同线程之间迁移其执行。
unsequenced_policyunseq算法允许向量化执行，但不允许并行执行。

标准库实现可以自由添加额外的执行策略。

下面我们看一个为算法指定执行策略的例子。以下代码会使用并行策略对 vector 内容进行排序：

sort(execution::par, begin(values), end(values));

传给并行算法的回调不允许抛出任何未捕获异常。否则将触发对 std::terminate() 的调用，从而直接终止应用。

对于使用 parallel_unsequenced_policy 或 unsequenced_policy 执行的算法，回调函数之间允许出现交错调用；也就是说，它们是 unsequenced 的。这有助于编译器对代码进行向量化。但这也意味着，对函数回调的行为会施加很多限制。例如，它不能分配/释放内存、不能获取 mutex、不能使用非无锁的 std::atomic（参见第 27 章“使用 C++ 进行多线程编程”），等等。对于其他标准策略，函数调用之间虽然仍然是按顺序执行的，但这个顺序是不确定的；这类策略则不会对函数回调能做什么施加额外限制。

并行算法不会替你防止 data race 与 deadlock，因此当你并行执行算法时，避免它们是你的责任。关于 data race 和 deadlock 的预防，会在第 27 章多线程编程上下文中详细讨论。

即便对应的非并行重载是 constexpr，算法的并行重载也不是 constexpr。

某些算法的并行重载，其返回类型可能与非并行重载略有不同。例如，for_each() 的非并行重载会返回传入的回调，而并行重载则不返回任何内容。关于全部算法的完整概览——包括它们在并行和非并行重载下的参数与返回类型——请查阅你喜欢的标准库参考资料。

不过也要记住，使用某个算法的并行重载，并不保证它一定会比非并行重载更快。例如，当处理的元素数量很少时，并行重载反而可能因为并行化本身带来的额外开销而更慢。再比如，当你的容器不支持随机访问迭代器时，也可能影响效果。要决定某个具体使用场景应该使用并行还是顺序重载，你必须分别对两者做性能分析，并选择性能更好的那个。第 29 章“编写高效 C++”会讨论 profiling（性能分析）。

数值处理算法

Section titled “数值处理算法”

你前面已经看过一个数值处理算法的例子：accumulate()。下面几节会继续给出更多数值算法的示例。

iota

Section titled “iota”

定义在 <numeric> 中的 iota() 算法，会在给定 range 中生成一系列值：从某个指定的起始值开始，并通过不断应用 operator++ 生成后继值。下面这个例子展示了如何将它用于一个 vector<int>，不过它也适用于任何实现了 operator++ 的元素类型：

vector<int> values(10);
iota(begin(values), end(values), 5);
println("{:n}", values);

输出如下：

5, 6, 7, 8, 9, 10, 11, 12, 13, 14

归约算法

Section titled “归约算法”

标准库有四个 归约算法：accumulate()、reduce()、inner_product() 和 transform_reduce()，它们都定义在 <numeric> 中。accumulate() 已在本章前面讨论过。所有归约算法都会反复对给定 range（或两个给定 range）中的两个元素应用某种运算符，直到最后只剩下一个值。这类算法有时也被称为 accumulate、aggregate、compress、inject 或 fold 算法。

reduce
Section titled “reduce”

std::accumulate() 是少数几个不支持并行执行的算法之一。如果你希望在可并行执行的前提下计算某种广义和，那么需要使用 std::reduce()。

例如，下面这段代码计算了同样的和两次：一次用 accumulate()，一次用 reduce()。后者运行的是并行且向量化的版本，因此在大输入 range 上可能会快很多。它们都需要：range 的 begin/end iterator，以及一个初始值（本例中是 0）。

vector values { 1, 3, 6, 4, 6, 9 };
int result1 { accumulate(cbegin(values), cend(values), 0) };
int result2 { reduce(execution::par_unseq, cbegin(values), cend(values), 0) };

一般来说，对于元素范围 [x0, xn)，给定初始值 Init 和二元运算符 Ѳ，accumulate() 与 reduce() 都会计算如下结果：

  • Init Ѳ x0 Ѳ x1 Ѳ … Ѳ xn−1

默认情况下，accumulate() 使用的二元运算符是 operator+，而 reduce() 使用的是 std::plus。

inner_product
Section titled “inner_product”

inner_product() 用于计算两个序列的内积。例如，下面这个例子中的内积是 (1*9)+(2*8)+(3*7)+(4*6)，也就是 70：

vector v1 { 1, 2, 3, 4 };
vector v2 { 9, 8, 7, 6 };
println("{}", inner_product(cbegin(v1), cend(v1), cbegin(v2), 0));

inner_product() 还可以再接受两个额外参数，也就是在计算中使用的两个二元运算符；默认情况下它们分别是 operator+ 与 operator*。

inner_product() 也是一个不支持并行执行的算法。如果你需要并行执行，请改用下一节要讲的 transform_reduce()。

transform_reduce
Section titled “transform_reduce”

transform_reduce() 支持并行执行，并且既可以作用于一个元素 range，也可以作用于两个 range。在其第一种形式中，对于元素范围 [x0, xn)，给定初始值 Init、一元函数 f，以及二元运算符 Ѳ（默认是 std::plus），它会计算：

  • Init Ѳ f(x0) Ѳ f(x1) Ѳ … Ѳ f(xn−1)

而在作用于两个 range 时，它的行为与 inner_product() 相同，只不过默认使用的两个二元运算符分别是 std::plus 和 std::multiplies，而不是 operator+ 与 operator*。

扫描算法

Section titled “扫描算法”

扫描算法也被称为 prefix sum、cumulative sum 或 partial sum 算法。把这类算法应用到一个 range 上后，得到的结果是另一个 range，其中包含源 range 元素的各种前缀和。

一共有五个扫描算法：exclusive_scan()、inclusive_scan()/partial_sum()、transform_exclusive_scan() 和 transform_inclusive_scan()，它们都定义在 <numeric> 中。

下表展示了：对于元素范围 [x0, xn)，在给定初始值 Init（对 partial_sum() 来说是 0）和二元运算符 Ѳ 的前提下，exclusive_scan() 与 inclusive_scan()/partial_sum() 分别会计算出哪些和 [y0, yn)：

exclusive_scan()inclusive_scan() / partial_sum()
y0 = Init y1 = Init Ѳ x0 y2 = Init Ѳ x0 Ѳ x1 … yn-1 = Init Ѳ x0 Ѳ x1 Ѳ … Ѳ xn-2y0 = Init Ѳ x0 y1 = Init Ѳ x0 Ѳ x1 … yn-1 = Init Ѳ x0 Ѳ x1 Ѳ … Ѳ xn-1

transform_exclusive_scan() 与 transform_inclusive_scan() 都会先对元素应用一个一元函数，再去计算广义和。这与 transform_reduce() 在 reduce 前先应用一元函数的做法类似。

要注意的是，这些扫描算法中，除了 partial_sum() 之外，都可以接受可选执行策略来实现并行化。它们的求值顺序是不确定的；而 partial_sum() 与 accumulate() 则保证从左到右求值。这也是为什么 partial_sum() 与 accumulate() 都无法并行化。

受约束算法

Section titled “受约束算法”

大多数算法在 std::ranges 命名空间中都有对应的受约束版本。究竟哪些算法存在受约束变体，请查阅你喜欢的标准库参考资料。这些算法同样定义在 <algorithm> 与 <numeric> 中，但和 std 命名空间中的不受约束版本不同，受约束版本会使用 concepts（见第 12 章）来约束模板类型参数。这意味着，当你传入非法参数时，编译器会给出更好的错误信息。例如，sort() 算法要求随机访问迭代器。如果你把一对 std::list iterator 传给 std::sort()，编译器可能会吐出一大堆晦涩错误；而对受约束的 ranges::sort() 来说，编译器会明确告诉你：传入的 iterator 并不是随机访问迭代器。

这些受约束算法的另一个好处，是它们既可以作用于由 begin/end iterator 对 给出的元素序列，也可以直接作用于一个 range。此外，它们还能支持 projection。关于 range 和 projection，请参见第 17 章。

下面来看几个受约束算法的实际示例。

受约束的 find

Section titled “受约束的 find”

和所有受约束算法一样，std::ranges::find() 既可以用 iterator 对来调用，也可以直接传入一个 range。用 iterator 对调用时，与不受约束版本的 std::find() 没什么区别：

vector values {1, 2, 3};
auto result { ranges::find(cbegin(values), cend(values), 2) };
if (result != cend(values)) { println("{}", *result); }

不过，如果你想把某个算法应用到容器中的 全部元素 上——而这往往是最常见的情况——那么每次都显式指定一对 begin/end iterator 来定义序列，就会显得有些繁琐。有了 range 支持，你只需要传一个 range 参数即可。前面的 find() 调用就可以更可读、更不容易出错地写成：

auto result { ranges::find(values, 2) };

受约束的 generate

Section titled “受约束的 generate”

再看另一个例子，这次使用的是受约束版本的 std::ranges::generate() 算法。代码先创建一个 lambda 表达式，它每次调用时只会返回下一个数字。接着，代码创建一个包含 10 个整数的 vector，并利用 generate() 与 nextNumber lambda 表达式，用递增整数填充这个 vector。随后输出 vector 的内容，再额外调用 nextNumber lambda 表达式四次。

auto nextNumber { [counter = 0] () mutable { return ++counter; } };
vector<int> values(10);
ranges::generate(values, nextNumber);
println("Vector contains {:n}", values);
print("Four more next numbers: ");
for (unsigned i { 0 }; i < 4; ++i) { print("{}, ", nextNumber()); }

输出如下：

Vector contains 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Four more next numbers: 1, 2, 3, 4,

正如输出所展示的那样，generate() 会复制这份 lambda 表达式。要避免这一点，可以像本章前面解释过的那样，使用 std::ref() 传递 lambda 表达式的引用，而不是副本：

ranges::generate(values, ref(nextNumber));

此时输出变为：

Vector contains 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Four more next numbers: 11, 12, 13, 14,

受约束的 for_each

Section titled “受约束的 for_each”

下面这个例子演示了如何把 std::ranges::for_each() 用在通过 std::ranges::views::filter（定义在 <ranges> 中）创建的过滤视图上。这个视图只保留 vector 中的偶数值。随后，这个过滤视图被传给 for_each()，并把其中每个值乘以 10。通过输出 vector 的内容，可以确认只有 vector 中的偶数被乘了 10。

vector values { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
println("Before: {:n}", values);
ranges::for_each(values | views::filter([](int value) { return value % 2 == 0; }),
    [](int& value) { value *= 10; });
println("After:  {:n}", values);

输出如下：

Before: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
After:  1, 20, 3, 40, 5, 60, 7, 80, 9, 100

仅受约束版本提供的算法

Section titled “ 仅受约束版本提供的算法”

C++23 引入了一些只以受约束算法形式存在的新算法。它们全部定义在 std::ranges 命名空间中。这包括不修改序列的算法 contains()、contains_subrange()、starts_with()、ends_with()、find_last()、find_last_if() 和 find_last_if_not()，以及 fold 算法 fold_left()、fold_left_first()、fold_right()、fold_right_last()、fold_left_with_iter() 和 fold_left_first_with_iter()。

下面是其中一些不修改序列算法的示例：

vector values { 11, 22, 33, 44, 55 };
vector v { 11, 22 };
println("{} contains 33 = {}", values, ranges::contains(values, 33));
println("{} contains {} = {}", values, v, ranges::contains_subrange(values, v));
println("{} starts with {} = {}", values, v, ranges::starts_with(values, v));

输出如下：

[11, 22, 33, 44, 55] contains 33 = true
[11, 22, 33, 44, 55] contains [11, 22] = true
[11, 22, 33, 44, 55] starts with [11, 22] = true

下面再看两个折叠算法的示例。fold_left() 和 fold_right() 会显式接收一个初始值作为参数之一；而 fold_left_first() 则使用给定 range 的第一个元素作为起始值，fold_right_last() 则使用最后一个元素作为起始值。这个例子展示了左折叠与右折叠的差异。fold_left_first() 与 fold_right_last() 都返回一个 optional，因此这里使用 value_or() 来处理空结果。

vector values { 500.0, 10.0, 2.0 };
auto foldedLeft { ranges::fold_left_first(values, divides<>{}) };
auto foldedRight { ranges::fold_right_last(values, divides<>{}) };
println("foldedLeft = {}", foldedLeft.value_or(0.0));
println("foldedRight = {}", foldedRight.value_or(0.0));

输出如下：

foldedLeft = 25
foldedRight = 100

左折叠计算的是 ((500.0 / 10.0) / 2.0)，而右折叠计算的是 (500.0 / (10.0 / 2.0))。

关于这些受约束算法的更多细节，请查阅你喜欢的标准库参考资料。

总结

Section titled “总结”

本章通过一组标准库算法的编码示例，展示了它们的实际用法。你也看到了：将这些算法与 lambda 表达式结合起来，能够写出既优雅又易于理解的代码。结合前面几章的内容，我希望你已经真正体会到标准库容器与算法的价值与威力。

接下来的几章会继续讨论 C++ 标准库的其他功能。第 21 章讨论正则表达式。第 22 章解释日期与时间支持。第 23 章展示如何生成随机数。第 24 章介绍更多可供你使用的词汇类型。最后，第 25 章会让你初步领略一些更高级的特性，例如分配器，以及如何编写符合标准库规范的算法和容器。

练习

Section titled “练习”

通过完成下面这些练习，你可以动手巩固本章讨论过的内容。所有练习的参考解答都包含在本书网站 www.wiley.com/go/proc++6e 提供的代码下载包中。不过，如果你在某道题上卡住了，建议先重读本章相关部分，尽量自己找到答案，再去查看网站上的解法。

  1. 练习 20-1： 使用你喜欢的标准库参考资料，查出 ranges::fill() 算法的参数形式。让用户输入一个数字，然后用 fill() 把一个含有 10 个整数的 vector 填满为这个数字。把 vector 的内容输出到标准输出以便验证。再给出第二种解法，使用 std::fill() 算法实现。
  2. 练习 20-2： 回顾第 16 章中“排列算法”一节，然后使用标准库参考资料弄清这些算法的参数。编写一个程序，让用户输入若干数字，然后使用某个排列算法打印出这些数字的全部排列。请给出两种解法：一种只使用受约束算法，另一种使用传统的、不受约束的旧式算法。
  3. 练习 20-3： 编写一个名为 trim() 的函数，用来移除给定字符串开头和结尾处的所有空白字符，并返回结果。要求只使用受约束算法。提示：要判断字符 c 是否为空白字符，可以使用定义在 <cctype> 中的 std::isspace(c)。如果 c 是空白字符，它返回非零值；否则返回 0。在你的 main() 函数中使用多个字符串测试这一实现。
  4. 练习 20-4： 使用一个受约束算法，创建一个包含 1 到 20 的 vector。然后，再使用单个受约束算法调用，把所有偶数与奇数分别复制到 evens 和 odds 容器中，并且在此过程中不要对这两个容器做任何空间预留。同时，仍然只用这一次算法调用，确保偶数按升序排列，而奇数按降序排列。请仔细选择 evens 和 odds 容器的类型。提示：也许第 17 章中有某些内容可以帮助你。
  5. 练习 20-5： 练习 20-3 的解法只使用了受约束算法。你能否只用传统的、不受约束的算法实现同样的功能？