C++ 程序员广泛使用标准库中的容器。例如，很少找到没有引用std::vector或std::string的 C++ 代码库。然而，根据我的经验，标准库算法的使用频率要低得多，尽管它们提供了与容器相同的好处:
- 在解决复杂问题时，它们可以用作构建模块
- 它们被很好地记录下来(包括参考资料、书籍和视频)
- 许多 C++ 程序员已经熟悉它们了
- 它们的空间和运行时间成本是已知的(复杂性保证)
- 他们的实现是精心制作和高效的
如果这还不够，C++ 的特性，如 lambdas、执行策略、概念和范围，都使标准算法更加强大，同时也更易于使用。
在本章中，我们将了解如何使用算法库在 C++ 中编写高效的算法。您将了解到在应用中使用标准库算法作为构建模块的好处，包括性能和可读性。
在本章中，您将了解:
- C++ 标准库中的算法
- 迭代器和范围——容器和算法之间的粘合剂
- 如何实现可以在标准容器上运行的通用算法
- 使用 C++ 标准算法的最佳实践
让我们先来看看标准库算法，以及它们是如何变成今天这样的。
将标准的库算法集成到你的 C++ 词汇表中是很重要的。在这篇介绍中，我将介绍一组通过使用标准库算法可以有效解决的常见问题。
C++ 20 通过引入范围库和 C++ 概念的语言特性，对算法库进行了巨大的改变。因此，在我们开始之前，我们需要一个 C++ 标准库历史的简要背景。
你可能听过关于 STL 算法或者 STL 容器。希望你已经听说了 C++ 20 引入的新的范围库。C++ 20 中的标准库增加了很多内容。在继续之前，我需要弄清楚一些术语。我们将从 STL 开始。
STL ，或者标准模板库，最初是 20 世纪 90 年代添加到 C++ 标准库中的一个库的名称。它包含算法、容器、迭代器和函数对象。这个名字很有粘性，我们已经习惯于听到和谈论 STL 算法和容器。然而 C++ 标准并没有提到 STL 取而代之的是标准库及其单个组件，如迭代器库和算法库。我将尽量避免在本书中使用 STL 这个名字，而是在需要时谈论标准库或单个库。
现在进入范围库，我称之为约束算法。Ranges 库是 C++ 20 中添加到标准库中的一个库，它引入了一个名为<ranges>的全新头文件，我们将在下一章中详细介绍。但是 Ranges 库的加入也对<algorithm>头产生了很大的影响，因为它引入了所有以前存在的算法的重载版本。我将这些算法称为约束算法，因为它们是使用 C++ 概念进行约束的。因此，<algorithm>头现在包括了旧的基于迭代器的算法和新的算法，这些算法受 C++ 概念的约束，可以对范围进行操作。这意味着我们将在本章中讨论的算法有两种风格，如下例所示:
#include <algorithm>
#include <vector>
auto values = std::vector{9, 2, 5, 3, 4};
// Sort using the std algorithms
std::sort(values.begin(), values.end());
// Sort using the constrained algorithms under std::ranges
std::ranges::sort(values);
std::ranges::sort(values.begin(), values.end()); 请注意，sort()的两个版本都位于<algorithm>头中，但是它们通过不同的名称空间和签名来区分。本章将使用这两种风格，但总的来说，我建议尽可能使用新的约束算法。阅读本章后，好处将会变得显而易见。
现在，您已经准备好开始学习如何使用现成的算法来解决常见问题。
我将在这里列出一些常见场景和有用的算法，只是为了让您体验一下标准库中可用的算法。库中有许多算法，我将在本节中只介绍几个。关于标准库算法的快速而完整的概述，我推荐乔纳森·博卡拉在https://sched.co/FnJh的演讲 CppCon 2018，105 不到一小时的 STL 算法。
有一个可以打印序列元素的短助手功能是很有用的。下面的通用函数适用于任何保存元素的容器，这些元素可以使用operator<<()打印到输出流中:
void print(auto&& r) {
std::ranges::for_each(r, [](auto&& i) { std::cout << i << ' '; });
} print()功能使用的是for_each()，是从<algorithm>表头导入的算法。for_each()为范围内的每个元素调用我们提供的函数一次。我们提供的函数的返回值被忽略，并且对我们传递给for_each()的序列没有影响。我们可以使用for_each()来处理副作用，例如打印到stdout(我们在本例中就是这样做的)。
一个类似的，非常通用的算法是transform()。它还为序列中的每个元素调用一个函数，但是它没有忽略返回值，而是将函数的返回值存储在输出序列中，如下所示:
auto in = std::vector{1, 2, 3, 4};
auto out = std::vector<int>(in.size());
auto lambda = [](auto&& i) { return i * i; };
std::ranges::transform(in, out.begin(), lambda);
print(out);
// Prints: "1 4 9 16" 这段代码还演示了我们如何使用前面定义的print()函数。transform()算法将为输入范围内的每个元素调用一次我们的λ。为了指定输出的存储位置，我们为transform()提供了一个输出迭代器out.begin()。我们将在本章后面更多地讨论迭代器。
有了我们的print()函数和一些最通用算法的演示，我们将继续研究一些生成元素的算法。
有时我们需要给一个元素序列分配一些初始值或者重置整个序列。以下示例用值-1 填充向量:
auto v = std::vector<int>(4);
std::ranges::fill(v, -1);
print(v);
// Prints "-1 -1 -1 -1 " 下一个算法generate()为每个元素调用一个函数，并将返回值存储在当前元素中:
auto v = std::vector<int>(4);
std::ranges::generate(v, std::rand);
print(v);
// Possible output: "1804289383 846930886 1681692777 1714636915 " 在前面的例子中，对每个元素调用一次std::rand()函数。
我要提到的最后一个生成算法是来自<numeric>头的std::iota()。它以递增的顺序生成值。必须将起始值指定为第二个参数。下面是一个生成 0 到 5 之间的值的简短示例:
auto v = std::vector<int>(6);
std::iota(v.begin(), v.end(), 0);
print(v); // Prints: "0 1 2 3 4 5 " 这个序列已经被排序了，但是它更常见的情况是，你有一个需要排序的无序元素集合，我们接下来会看到它。
对元素进行排序是非常常见的操作。有一些排序算法的选择是很好了解的，但是在这个介绍中，我将只展示最常规的版本，简单命名为sort():
auto v = std::vector{4, 3, 2, 3, 6};
std::ranges::sort(v);
print(v); // Prints: "2 3 3 4 6 " 如上所述，这不是唯一的排序方式，有时我们可以使用部分排序算法来获得性能。我们将在本章后面讨论更多的异常排序。
另一个非常常见的任务是找出某个特定值是否在集合中。也许我们想知道一个集合中有多少特定值的实例。如果我们知道集合已经排序，这些搜索值的算法可以更有效地实现。您在第 3 章、分析和测量性能中看到了这一点，我们将线性搜索与二分搜索法进行了比较。
这里我们从find()算法开始，它不需要排序的集合:
auto col = std::list{2, 4, 3, 2, 3, 1};
auto it = std::ranges::find(col, 2);
if (it != col.end()) {
std::cout << *it << '\n';
} 如果找不到我们要找的元素，find()返回集合的end()迭代器。在最坏的情况下，find()需要检查序列中的所有元素，因此在 O(n) 时间运行。
如果我们知道集合已经排序，我们可以使用二分搜索法算法之一:binary_search()、equal_range()、upper_bound()或lower_bound()。如果我们将这些函数与提供对其元素的随机访问的容器一起使用，它们都保证在 O(log n) 时间内运行。当我们在本章后面讨论迭代器和范围时，您将更好地理解算法如何提供复杂性保证，即使它们在不同的容器上运行(有趣的是，接下来有一个部分被命名为迭代器和范围)。
在以下示例中，我们将使用带有以下元素的排序后的std::vector:
图 5.1:一个包含七个元素的分类标准::向量
binary_search()函数返回true或false，具体取决于是否能找到我们搜索的值:
auto v = std::vector{2, 2, 3, 3, 3, 4, 5}; // Sorted!
bool found = std::ranges::binary_search(v, 3);
std::cout << std::boolalpha << found << '\n'; // Output: true 在调用binary_search()之前，你要绝对确定集合已经排序。我们可以很容易地在代码中使用is_sorted()断言这一点，如下所示:
assert(std::ranges::is_sorted(v)); 该检查将在 O(n) 中运行，但仅在断言被激活时调用，因此不会影响最终程序的性能。
我们正在处理的排序集合包含多个 3。如果我们想知道集合中前 3 位或后 3 位的位置会怎样？在这种情况下，我们可以使用lower_bound()来查找前 3 个，或者使用upper_bound()来查找后 3 个之后的元素:
auto v = std::vector{2, 2, 3, 3, 3, 4, 5};
auto it = std::ranges::lower_bound(v, 3);
if (it != v.end()) {
auto index = std::distance(v.begin(), it);
std::cout << index << '\n'; // Output: 2
} 该代码将输出2，因为这是前 3 的索引。要从迭代器中获取元素的索引，我们使用<iterator>头中的std::distance()。
以同样的方式，我们可以使用upper_bound()获得元素的迭代器，经过最后 3:
const auto v = std::vector{2, 2, 3, 3, 3, 4, 5};
auto it = std::ranges::upper_bound(v, 3);
if (it != v.end()) {
auto index = std::distance(v.begin(), it);
std::cout << index << '\n'; // Output: 5
} 如果同时需要上限和下限，可以改为使用equal_range()，它返回包含 3s 的集合的子范围:
const auto v = std::vector{2, 2, 3, 3, 3, 4, 5};
auto subrange = std::ranges::equal_range(v, 3);
if (subrange.begin() != subrange.end()) {
auto pos1 = std::distance(v.begin(), subrange.begin());
auto pos2 = std::distance(v.begin(), subrange.end());
std::cout << pos1 << " " << pos2 << '\n';
} // Output: "2 5" 现在让我们探索一些其他有用的算法来检查一个集合。
有三种非常方便的算法叫做all_of()、any_of()和none_of()。它们都接受一个范围、一元谓词(接受一个参数并返回true或false的函数)和一个可选的投影函数。
假设我们有一个数字列表和一个决定数字是否为负数的小λ:
const auto v = std::vector{3, 2, 2, 1, 0, 2, 1};
const auto is_negative = [](int i) { return i < 0; }; 我们可以使用none_of()来检查这些数字是否都不是负数:
if (std::ranges::none_of(v, is_negative)) {
std::cout << "Contains only natural numbers\n";
} 进一步，我们可以使用all_of()来询问列表中的所有元素是否都是负数:
if (std::ranges::all_of(v, is_negative)) {
std::cout << "Contains only negative numbers\n";
} 最后，使用any_of()，我们可以看到列表中是否至少包含一个负数:
if (std::ranges::any_of(v, is_negative)) {
std::cout << "Contains at least one negative number\n";
} 很容易忘记这些位于标准库中的小而方便的构建块。但是一旦你养成了使用它们的习惯，你就再也不会回头，开始手写这些了。
计算等于某个值的元素数量最明显的方法是调用count():
const auto numbers = std::list{3, 3, 2, 1, 3, 1, 3};
int n = std::ranges::count(numbers, 3);
std::cout << n; // Prints: 4 count()算法以线性时间运行。然而，如果我们知道序列是排序的，并且我们使用的是向量或其他随机存取数据结构，我们可以使用equal_range()，它将在*0(log n)*时间运行。以下是一个例子:
const auto v = std::vector{0, 2, 2, 3, 3, 4, 5};
assert(std::ranges::is_sorted(v)); // O(n), but not called in release
auto r = std::ranges::equal_range(v, 3);
int n = std::ranges::size(r);
std::cout << n; // Prints: 2 equal_range()函数找到包含我们想要计数的值的所有元素的子范围。一旦找到子范围，我们可以使用<ranges>头中的size()来检索子范围的长度。
我想提一套小但极其有用的算法，这对一个经验丰富的 C++ 程序员来说是必不可少的知识。函数std::min()、std::max()和std::clamp()有时会被遗忘，取而代之的是我们经常发现自己像这样写代码:
const auto y_max = 100;
auto y = some_func();
if (y > y_max) {
y = y_max;
} 代码保证y的值在一定的限度内。这段代码可以工作，但是我们可以通过使用std::min()来避免可变变量和if语句，如下所示:
const auto y = std::min(some_func(), y_max); 通过使用std::min()，混淆我们代码的可变变量和if语句都被消除了。我们可以将std::max()用于类似的场景。如果我们想将一个值限制在最小值和最大值之内，我们可以这样做:
const auto y = std::max(std::min(some_func(), y_max), y_min); 但是，从 C++ 17 开始，我们现在有了std::clamp()在一个函数中为我们完成这个任务。因此，我们可以如下使用clamp():
const auto y = std::clamp(some_func(), y_min, y_max); 有时我们需要在一个未排序的元素集合中找到极值。为此，我们可以使用minmax()，它(不出所料)返回序列的最小值和最大值。结合结构化绑定，我们可以按如下方式打印极值:
const auto v = std::vector{4, 2, 1, 7, 3, 1, 5};
const auto [min, max] = std::ranges::minmax(v);
std::cout << min << " " << max; // Prints: "1 7" 我们也可以使用min_element()或max_element()找到最小或最大元素的位置。它不是返回值，而是返回一个指向我们正在寻找的元素的迭代器。在下面的例子中，我们找到了最小元素:
const auto v = std::vector{4, 2, 7, 1, 1, 3};
const auto it = std::ranges::min_element(v);
std::cout << std::distance(v.begin(), it); // Output: 3 这段代码打印出3，这是找到的第一个最小值的索引。
这是对标准库中一些最常见算法的简单介绍。算法的运行时成本是在 C++ 标准中规定的，所有的库实现都需要遵守这些标准，尽管不同平台之间的具体实现可能会有所不同。为了理解如何为处理多种不同类型容器的通用算法保留复杂性保证，我们需要仔细研究迭代器和范围。
正如在前面的例子中看到的，标准库算法对迭代器和范围而不是容器类型进行操作。本节将重点介绍迭代器和 C++ 20 中引入的新的范围概念。一旦掌握了迭代器和范围，正确使用容器和算法就变得容易了。
迭代器构成了标准库算法和范围的基础。迭代器是数据结构和算法之间的粘合剂。正如您已经看到的，C++ 容器以非常不同的方式存储它们的元素。迭代器提供了一种通用的方法来浏览序列中的元素。通过让算法对迭代器而不是容器类型进行操作，算法变得更加通用和灵活，因为它们不依赖于容器的类型和容器在内存中排列元素的方式。
迭代器的核心是一个对象，它代表序列中的一个位置。它有两个主要职责:
- 在序列中导航
- 在当前位置读写值
迭代器抽象根本不是 C++ 独有的概念，而是存在于大多数编程语言中。迭代器概念的 C++ 实现与其他编程语言的区别在于，C++ 模仿原始内存指针的语法。
基本上，迭代器可以被认为是具有与原始指针相同属性的对象；它可以步进到下一个元素并取消引用(如果指向有效的地址)。算法只使用指针允许的一些操作，尽管迭代器在内部可能是一个穿越树状结构的重对象。
直接在std命名空间下找到的大多数算法只对迭代器进行操作，而不是对容器(即std::vector、std::map等)进行操作。许多算法返回迭代器而不是值。
为了能够在序列中导航而不越界，我们需要一种通用的方法来判断迭代器何时到达序列的末尾。这就是我们的哨兵价值观。
一个标记值(或者简单地说是一个标记)是一个特殊的值，表示一个序列的结束。哨兵值使得迭代一个值序列成为可能，而无需事先知道序列的大小。哨兵值的一个示例用法是以空终止的 C 风格字符串(在本例中，哨兵是'\0'字符)。指向字符串开头的指针和结尾的标记足以定义一个字符序列，而不是跟踪空终止字符串的长度。
受约束的算法使用迭代器来定义序列中的第一个元素，并使用标记来指示序列的结束。哨兵的唯一要求是它可以与迭代器进行比较，这实际上意味着operator==()和operator!=()应该被定义为接受哨兵和迭代器的组合:
bool operator=!(sentinel s, iterator i) {
// ...
} 既然你知道了哨点是什么，我们如何创建一个哨点来指示一个序列的结束？这里的诀窍是使用一个叫做的过去式 迭代器作为哨兵。它只是一个迭代器，指向我们定义的序列中最后一个元素(或过去)之后的元素*。看看下面的代码片段和图表:*
|auto vec = std::vector {
'a','b','c','d'
};
auto first = vec.begin();
auto last = vec.end(); |
|
如上图所示，last迭代器现在指向'd'之后的一个想象元素。这使得通过使用循环来迭代序列中的所有元素成为可能:
for (; first != last; ++ first) {
char value = *first; // Dereference iterator
// ... 我们可以使用过去结束标记与我们的迭代器it进行比较，但是我们不能取消标记，因为它没有指向范围的元素。过去式迭代器的概念由来已久，甚至适用于内置的 C 数组:
char arr[] = {'a', 'b', 'c', 'd'};
char* end = arr + sizeof(arr);
for (char* it = arr; it != end; ++ it) { // Stop at end
std::cout << *it << ' ';}
// Output: a b c d 再次注意end实际上指出了边界，所以我们不允许取消引用它，但是我们被允许读取指针值并将其与我们的it变量进行比较。
范围是对我们在引用元素序列时使用的迭代器-哨兵对的替换。<range>标题包含多个定义不同种类范围需求的概念，例如input_range、random_access_range等。这些都是对最基本的概念range的提炼，定义如下:
template<class T>
concept range = requires(T& t) {
ranges::begin(t);
ranges::end(t);
}; 这意味着任何公开begin()和end()函数的类型都被认为是一个范围(假设这些函数返回迭代器)。
对于 C++ 标准容器，begin()和end()函数将返回相同类型的迭代器，而对于 C++ 20 范围，这通常是不正确的。具有相同迭代器和哨兵类型的范围实现了std::ranges::common_range的概念。新的 C++ 20 视图(将在下一章中介绍)返回可以是不同类型的迭代器-哨兵对。但是，可以使用std::views::common将它们转换为与迭代器和哨兵具有相同类型的视图。
在std::ranges命名空间中找到的约束算法可以对范围而不是迭代器对进行操作。由于所有标准容器(vector、map、list等)都满足范围概念，我们可以将范围直接传递给约束算法，如下所示:
auto vec = std::vector{1, 1, 0, 1, 1, 0, 0, 1};
std::cout << std::ranges::count(vec, 0); // Prints 3 范围是可迭代的东西(可以循环的东西)的抽象，在某种程度上，它们隐藏了 C++ 迭代器的直接使用。然而，迭代器仍然是 C++ 标准库的主要部分，并且在 Ranges 库中也广泛使用。
接下来你需要了解的是存在的不同类型的迭代器。
既然您已经更好地理解了范围是如何定义的，以及我们如何知道何时到达序列的末尾，现在是时候更仔细地研究迭代器可以支持的操作，以便导航、读取和写入值了。
序列中的迭代器导航可以通过以下操作完成:
- 向前一步:
std::next(it)或++ it - 后退:
std::prev(it)或--it - 跳到任意位置:
std::advance(it, n)或it += n
在迭代器所代表的位置读写一个值是通过取消对迭代器的引用来完成的。以下是它的外观:
- 读作:
auto value = *it - 写:
*it = value
这些是容器公开的迭代器最常见的操作。但是除此之外，迭代器可能对数据源进行操作，其中写或读意味着前进一步。这种数据源的例子可以是用户输入、网络连接或文件。这些数据源需要以下操作:
- 只读和向前一步:
auto value = *it; ++ it; - 只写和向前一步:
*it = value; ++ it;
这些操作只能用两个后续表达式来表示。第一个表达式的后置条件是第二个表达式必须有效。这也意味着我们只能对一个位置读取或写入一次值。如果我们想读取或写入一个新值，我们必须首先将迭代器推进到下一个位置。
并非所有迭代器都支持前面列表中的所有操作。例如，一些迭代器只能读取值和向前一步，而其他迭代器既可以读取、写入，又可以跳转到任意位置。
现在，如果我们考虑一些基本的算法，很明显，不同的算法对迭代器的要求是不同的:
- 如果一个算法计算一个值的出现次数，它需要读取和向前一步操作
- 如果一个算法用一个值填充一个容器，它需要写和向前一步操作
- 排序集合上的二分搜索法算法需要读取和跳转操作
根据迭代器支持的操作，一些算法可以更有效地实现。就像容器一样，标准库中的所有算法都有复杂性保证(使用大 O 符号)。一个算法要满足一定的复杂度保证，就要对它所操作的迭代器提出要求。这些需求被分成六个基本迭代器类别，如下图所示:
图 5.2:六个迭代器类别及其相互关系
箭头表示迭代器类别也具有它所指向的类别的所有功能。例如，如果一个算法需要一个前向迭代器，我们也可以给它传递一个双向迭代器，因为双向迭代器具有前向迭代器的所有功能。
这六项要求由以下概念正式规定:
std::input_iterator:支持只读，向前一步(一次)。std::count()等单程算法可以使用输入迭代器。std::istream_iterator是一个输入迭代器的例子。std::output_iterator:支持只写，向前一步(一次)。注意，输出迭代器只能写，不能读。std::ostream_iterator是输出迭代器的一个例子。std::forward_iterator:支持读写向前一步。当前位置的值可以多次读取或写入。像std::forward_list这样的单链表公开了前向迭代器。std::bidirectional_iterator:支持*读、写、*前进、后退。双向链接std::list公开双向迭代器。std::random_access_iterator:支持读、写、向前一步、向后一步、在恒定时间内跳转到任意位置。std::deque内部的元素可以用随机访问迭代器访问。std::contiguous_iterator:与随机访问迭代器相同，但也保证了底层数据是一个连续的内存块，比如std::string、std::vector、std::array、std::span、std::valarray(很少使用)。
迭代器类别对于理解算法的时间复杂度要求非常重要。对底层数据结构有很好的理解使得知道迭代器通常属于哪个容器变得相当容易。
我们现在准备深入挖掘大多数标准库算法使用的常见模式。
为了更好地理解标准算法，最好了解一下<algorithm>标题中所有算法使用的特性和常见模式。如前所述，std和std::ranges名称空间下的算法有很多共同点。我们将从适用于std算法和std::range约束算法的一般原则开始。然后，在下一节，我们将继续讨论std::ranges下的约束算法特有的特性。
从<algorithm>开始的函数只能修改指定范围内的元素；从不在基础容器中添加或删除元素。因此，这些函数永远不会改变它们所操作的容器的大小。
例如，std::remove()或std::unique()实际上并没有从容器中移除元素(不管它们的名称如何)。相反，它将应该保留的元素移动到容器的前面，然后返回一个标记，该标记定义了元素有效范围的新结束:
// Example with std::remove()
auto v = std::vector{1,1,2,2,3,3};
auto new_end = std::remove(
v.begin(), v.end(), 2);
v.erase(new_end, v.end()); |
| |
// Example with std::unique()
auto v = std::vector{1,1,2,2,3,3};
auto new_end = std::unique(
v.begin(), v.end());
v.erase(new_end, v.end()); |
|
C++ 20 在<vector>头中添加了新版本的std::erase()和std::erase_if()函数，这将立即从向量中删除值，而无需首先调用remove()然后调用erase()。
事实上，标准库算法从不改变容器的大小，这意味着当调用产生输出的算法时，我们需要自己分配数据。
将数据写入输出迭代器的算法，如std::copy()或std::transform()，需要为输出保留已分配的数据。由于算法只使用迭代器作为参数，它们不能自己分配数据。为了扩大算法操作的容器，它们依赖迭代器能够扩大它所迭代的容器。
如果将一个空容器的迭代器传递给算法进行输出，程序很可能会崩溃。下面的例子squared为空，说明了这个问题:
const auto square_func = [](int x) { return x * x; };
const auto v = std::vector{1, 2, 3, 4};
auto squared = std::vector<int>{};
std::ranges::transform(v, squared.begin(), square_func); 相反，您必须执行以下任一操作:
- 为生成的容器预先分配所需的大小，或者
- 使用插入迭代器，在迭代时将元素插入容器
下面的代码片段显示了如何使用预分配的空间:
const auto square_func = [](int x) { return x * x; };
const auto v = std::vector{1, 2, 3, 4};
auto squared = std::vector<int>{};
squared.resize(v.size());
std::ranges::transform(v, squared.begin(), square_func); 下面的代码片段显示了如何使用std::back_inserter()和std::inserter()将值插入到未预分配的容器中:
const auto square_func = [](int x) { return x * x; };
const auto v = std::vector{1, 2, 3, 4};
// Insert into back of vector using std::back_inserter
auto squared_vec = std::vector<int>{};
auto dst_vec = std::back_inserter(squared_vec);
std::ranges::transform(v, dst_vec, square_func);
// Insert into a std::set using std::inserter
auto squared_set = std::set<int>{};
auto dst_set = std::inserter(squared_set, squared_set.end());
std::ranges::transform(v, dst_set, square_func); 如果您在std::vector上操作，并且知道结果容器的预期大小，您可以在执行算法之前使用reserve()成员函数，以避免不必要的分配。否则，向量可能会在算法期间多次重新分配新的内存块。
相比之下，算法依赖于基本的==和<运算符，就像整数一样。为了能够使用自己的类和算法，operator==() 和operator<()必须由类提供或者作为算法的参数。
通过使用三向比较运算符operator<=>()，我们可以拥有编译器生成的必要运算符。下面的例子展示了一个简单的Flower类，其中operator==()被std::find()利用，operator<()被std::max_element()利用:
struct Flower {
auto operator<=>(const Flower& f) const = default;
bool operator==(const Flower&) const = default;
int height_{};
};
auto garden = std::vector<Flower>{{67}, {28}, {14}};
// std::max_element() uses operator<()
auto tallest = std::max_element(garden.begin(), garden.end());
// std::find() uses operator==()
auto perfect = *std::find(garden.begin(), garden.end(), Flower{28}); 除了使用当前类型的默认比较函数之外，也可以使用自定义比较函数，我们接下来将对此进行探讨。
有时我们需要在不使用默认比较运算符的情况下比较对象，例如，按长度排序或查找字符串时。在这些情况下，可以提供自定义函数作为附加参数。而原算法使用的是一个值(例如std::find())，带有特定运算符的版本名称与末尾附加的_if(std::find_if()、std::count_if()等)相同:
auto names = std::vector<std::string> {
"Ralph", "Lisa", "Homer", "Maggie", "Apu", "Bart"
};
std::sort(names.begin(), names.end(),
[](const std::string& a,const std::string& b) {
return a.size() < b.size(); });
// names is now "Apu", "Lisa", "Bart", "Ralph", "Homer", "Maggie"
// Find names with length 3
auto x = std::find_if(names.begin(), names.end(),
[](const auto& v) { return v.size() == 3; });
// x points to "Apu" std::ranges下受约束的算法为我们提供了一个称为投影的便利特性，它减少了编写自定义比较函数的需要。上一节中的前一个示例可以使用标准谓词std::less结合自定义投影进行重写:
auto names = std::vector<std::string>{
"Ralph", "Lisa", "Homer", "Maggie", "Apu", "Bart"
};
std::ranges::sort(names, std::less<>{}, &std::string::size);
// names is now "Apu", "Lisa", "Bart", "Ralph", "Homer", "Maggie"
// Find names with length 3
auto x = std::ranges::find(names, 3, &std::string::size);
// x points to "Apu" 还可以将 lambda 作为投影参数传递，当您想要在投影中组合多个属性时，这将非常方便:
struct Player {
std::string name_{};
int level_{};
float health_{};
// ...
};
auto players = std::vector<Player>{
{"Aki", 1, 9.f},
{"Nao", 2, 7.f},
{"Rei", 2, 3.f}};
auto level_and_health = [](const Player& p) {
return std::tie(p.level_, p.health_);
};
// Order players by level, then health
std::ranges::sort(players, std::greater<>{}, level_and_health); 将投影对象传递给标准算法的可能性是一个非常受欢迎的特性，并且确实简化了自定义比较的使用。
当移动元素时，所有算法都使用std::swap()和std::move()，但前提是移动构造函数和移动赋值被标记为noexcept。因此，在使用算法时，为重物实现这些是很重要的。如果它们不可用且无异常，则这些元素将被复制。
请注意，如果您在类中实现了移动构造函数和移动赋值运算符，std::swap()将使用它们，因此不需要指定的std::swap()重载。
标准库中每个算法的复杂度用大 O 符号指定。算法是在考虑性能的情况下创建的。因此，它们不分配内存，也没有比 O(n log n) 更高的时间复杂度。不符合这些标准的算法不包括在内，即使它们是相当常见的操作。
注意stable_sort()、inplace_merge()和stable_partition()的例外情况。许多实现倾向于在这些操作期间临时分配内存。
例如，让我们考虑一个测试非排序范围是否包含重复的算法。一种选择是通过遍历该范围并搜索该范围的其余部分来实现它。这将产生具有0(n2*)*复杂度的算法:
template <typename Iterator>
auto contains_duplicates(Iterator first, Iterator last) {
for (auto it = first; it != last; ++ it)
if (std::find(std::next(it), last, *it) != last)
return true;
return false;
} 另一种选择是复制整个范围，对其进行排序，并寻找相邻的相等元素。这将导致 O(n log n) 的时间复杂度，std::sort()的复杂度。然而，由于它需要复制完整的范围，它仍然不符合构建块算法的条件。分配意味着我们不能相信它不会抛出:
template <typename Iterator>
auto contains_duplicates(Iterator first, Iterator last) {
// As (*first) returns a reference, we have to get
// the base type using std::decay_t
using ValueType = std::decay_t<decltype(*first)>;
auto c = std::vector<ValueType>(first, last);
std::sort(c.begin(), c.end());
return std::adjacent_find(c.begin(),c.end()) != c.end();
} 复杂性保证从一开始就是 C++ 标准库的一部分，也是其巨大成功背后的主要原因之一。C++ 标准库中的算法是在考虑性能的情况下设计和实现的。
标准 C 库附带了许多低级算法，包括memcpy()、memmove()、memcmp()和memset()。根据我的经验，有时人们使用这些函数，而不是标准算法库中的等价函数。原因是人们倾向于相信 C 库函数更快，因此接受类型安全的权衡。
对于现代标准库的实现来说，情况并非如此；等效的算法std::copy()、std::equal()和std::fill()在看似合理的地方求助于这些低级的 C 函数；因此，它们提供了性能和类型安全。
当然，也有例外，C++ 编译器无法检测到使用低级 C 函数是安全的。例如，如果一个类型不容易复制，std::copy()就不能使用memcpy()。但这是有充分理由的；希望一个不容易复制的类的作者有充分的理由用这种方式设计这个类，我们(或者编译器)不应该通过不调用适当的构造函数来忽略这一点。
有时，来自 C++ 算法库的函数甚至比它们的 C 库同类函数更好。最突出的例子是 C 库中的std::sort()对qsort()。std::sort()和qsort()的一个很大的区别就是qsort()是功能std::sort()是功能模板。当qsort()调用作为函数指针提供的比较函数时，一般比调用一个普通的比较函数要慢很多，这个比较函数在使用std::sort()时可能会被编译器内联。
在使用标准算法和实现定制算法时，我们将在本章的剩余部分介绍一些最佳实践。
算法库包含通用算法。为了让这里的事情尽可能具体，我将展示一个如何实现通用算法的例子。这将为您提供一些如何使用标准算法的见解，同时证明实现通用算法并没有那么难。我将有意避免在这里解释示例代码的所有细节，因为我们将在本书的后面花费大量时间在泛型编程上。
在下面的例子中，我们将把一个简单的非通用算法转换成一个成熟的通用算法。
一个通用的算法是算法，它可以用于各种范围的元素，而不仅仅是一个特定的类型，比如std::vector。以下算法是仅适用于std::vector<int>的非通用算法的示例:
auto contains(const std::vector<int>& arr, int v) {
for (int i = 0; i < arr.size(); ++ i) {
if (arr[i] == v) { return true; }
}
return false;
} 为了找到我们要找的元素，我们依赖于std::vector的接口，它为我们提供了size()函数和下标运算符(operator[]())。然而，并不是所有的容器都为我们提供了这些功能，无论如何，我不建议您像这样编写原始循环。相反，我们需要创建一个对迭代器进行操作的函数模板。
通过用两个迭代器替换std::vector，用一个模板参数替换int，我们可以将算法转换为通用版本。以下版本的contains()可用于任何容器:
template <typename Iterator, typename T>
auto contains(Iterator begin, Iterator end, const T& v) {
for (auto it = begin; it != end; ++ it) {
if (*it == v) { return true; }
}
return false;
} 例如，要将其与std::vector一起使用，您必须通过begin()和end()迭代器:
auto v = std::vector{3, 4, 2, 4};
if (contains(v.begin(), v.end(), 3)) {
// Found the value...
} 我们可以通过提供一个接受范围的版本来改进这个算法，而不是两个独立的迭代器参数:
auto contains(const auto& r, const auto& x) {
auto it = std::begin(r);
auto sentinel = std::end(r);
return contains(it, sentinel, x);
} 这个算法不会强制客户端提供begin()和end()迭代器，因为我们已经将它们移到了函数内部。我们使用的是 C++ 20 中的缩写函数模板语法，以避免明确说明这是一个函数模板。作为最后一步，我们可以向参数类型添加约束:
auto contains(const std::ranges::range auto& r, const auto& x) {
auto it = std::begin(r);
auto sentinel = std::end(r);
return contains(it, sentinel, x);
} 如您所见，创建一个健壮的通用算法确实不需要那么多代码。我们传递给算法的数据结构的唯一要求是它可以公开begin()和end()迭代器。您将在第 8 章、编译时编程中了解更多约束和概念。
这让我们认识到我们创建的新的定制数据结构可以被标准的通用算法使用，只要它们公开begin()和end()迭代器或一个范围。举个简单的例子，我们可以实现一个二维的Grid结构，其中行作为一对迭代器公开，如下所示:
struct Grid {
Grid(std::size_t w, std::size_t h) : w_{w}, h_{h} { data_.resize(w * h);
}
auto get_row(std::size_t y); // Returns iterators or a range
std::vector<int> data_{};
std::size_t w_{};
std::size_t h_{};
}; 下图说明了带有迭代器对的Grid结构的布局:
图 5.3:基于一维向量的二维网格
get_row()的一个可能的实现将返回一个保存迭代器的std::pair，该迭代器代表行的开头和结尾:
auto Grid::get_row(std::size_t y) {
auto left = data_.begin() + w_ * y;
auto right = left + w_;
return std::make_pair(left, right);
} 代表一行的迭代器对可以被标准库算法使用。在下面的例子中，我们使用std::generate()和std::count():
auto grid = Grid{10, 10};
auto y = 3;
auto row = grid.get_row(y);
std::generate(row.first, row.second, std::rand);
auto num_fives = std::count(row.first, row.second, 5); 虽然这是可行的，但是使用std::pair有点笨拙，还需要客户端知道如何处理迭代器对。没有任何内容明确表示first和second成员实际上表示半开范围。如果它可以公开一个强类型的范围，那不是很好吗？幸运的是，我们将在下一章探索的 Ranges 库为我们提供了一个名为std::ranges::subrange的视图类型。现在，get_row()功能可以这样实现:
auto Grid::get_row(std::size_t y) {
auto first = data_.begin() + w_ * y;
auto sentinel = first + w_;
return std::ranges::subrange{first, sentinel};
} 我们甚至可以更懒一些，使用为这个场景量身定制的便捷视图std::views::counted()
auto Grid::get_row(std::size_t y) {
auto first = data_.begin() + w_ * y;
return std::views::counted(first, w_);
} 从Grid类返回的行现在可以与任何接受范围而不是迭代器对的约束算法一起使用:
auto row = grid.get_row(y);
std::ranges::generate(row, std::rand);
auto num_fives = std::ranges::count(row, 5); 这就完成了我们编写和使用支持迭代器对和范围的通用算法的示例。希望这给了你一些关于如何以通用的方式编写数据结构和算法的见解，以避免如果我们必须为所有类型的数据结构编写专门的算法时会出现的组合爆炸。
让我们考虑一下在使用我们一直在讨论的算法时会对您有所帮助的实践。我将首先强调实际利用标准算法的重要性。
C++ 20 引入的std::ranges下的约束算法比std下的基于迭代器的算法提供了一些好处。受约束的算法执行以下操作:
- 支持投影，这简化了元素的自定义比较。
- 支持范围而不是迭代器对。不需要将
begin()和end()迭代器作为单独的参数传递。 - 易于正确使用，并且由于受到 C++ 概念的约束，在编译期间会提供描述性错误消息。
我建议开始使用约束算法，而不是基于迭代器的算法。
你可能已经注意到这本书在很多地方使用了基于迭代器的算法。其原因是，在撰写本书时，并非所有的标准库实现都支持约束算法。
算法库包含三种基本的排序算法:sort()、partial_sort()和nth_element()。此外，它还包含一些变体，包括stable_sort()，但我们将重点关注这三个，因为根据我的经验，很容易忘记，在许多情况下，可以通过使用nth_element()或partial_sort()来避免完整的排序。
当sort()对整个范围进行排序时， partial_sort()和nth_element()可以被认为是检查该排序范围的部分的算法。在许多情况下，您只对排序范围的特定部分感兴趣，例如:
- 如果要计算某个范围的中值，则需要排序范围中间的值。
- 如果要创建一个人体扫描仪，该扫描仪可以使用 80%的平均身高，则需要排序范围内的两个值:距离最高的人 10%的值和距离最短的人 10%的值。
下图说明了与完全排序的范围相比，std::nth_element和std::partial_sort如何处理一个范围:
auto v = std::vector{6, 3, 2, 7,
4, 1, 5};
auto it = v.begin() + v.size()/2; |
| |
std::ranges::sort(v); |
**| |
std::nth_element(v.begin(), it,
v.end()); |
**| |
std::partial_sort(v.begin(), it,
v.end()); |
**|
图 5.1:使用不同算法的排序和非排序元素
下表显示了它们的算法复杂度；注意 m 表示正在完全排序的子范围:
| 算法 | 复杂性 | | `std::sort()` | *O(n 对数 n)* | | `std::partial_sort()` | *0(n log m)* | | `std::nth_element()` | *O(n)* |表 5.2:算法复杂性
现在你已经对std:nth_element()和std::partial_sort()有了深入的了解，让我们看看如何将它们结合起来检查一个范围的部分，就像整个范围被排序一样:
auto v = std::vector{6, 3, 2, 7,
4, 1, 5};
auto it = v.begin() + v.size()/2; |
| |
auto left = it - 1;
auto right = it + 2;
std::nth_element(v.begin(),
left, v.end());
std::partial_sort(left, right,
v.end()); |
**| |
std::nth_element(v.begin(), it,
v.end());
std::sort(it, v.end()); |
**| |
auto left = it - 1;
auto right = it + 2;
std::nth_element(v.begin(),
right, v.end());
std::partial_sort(v.begin(),
left, right);
std::sort(right, v.end()); |
**|
图 5.3:组合算法和相应的部分排序结果
如您所见，通过使用std::sort()、std::nth_element()和std::partial_sort()的组合，有很多方法可以避免在不绝对需要时对整个范围进行排序。这是获得性能的有效方法。
让我们看看std::nth_element()和std::partial_sort()如何与std::sort()相抗衡。我们已经用一个包含 1000 万个随机int元素的std::vector对此进行了测量:
std::sort(r.begin(), r.end()); | 760 毫秒(1.0 倍) | | 找到中位数 |
auto it = r.begin() + r.size() / 2;
std::nth_element(r.begin(), it, r.end()); | 83 毫秒(9.2 倍) | | 排序范围的前十分之一 |
auto it = r.begin() + r.size() / 10;
std::partial_sort(r.begin(), it, r.end()); | 378 毫秒(2.0 倍) |
表 5.3:部分排序算法的基准测试结果
很容易忘记复杂的算法可以通过组合标准库中的算法来实现。也许是因为一个旧习惯，即试图用手解决问题，并立即开始手工for-循环，并使用命令式方法解决问题。如果这听起来对你来说很熟悉，我的建议是充分了解标准算法，以便你开始考虑将它们作为首选。
我提倡在原始for循环上使用标准库算法，原因有很多:
- 标准算法提供性能。即使标准库中的一些算法看起来微不足道，但它们通常是以乍一看并不明显的方式进行优化设计的。
- 标准算法提供安全性。甚至更简单的算法也可能有容易被忽视的角落案例。
- 标准算法是经得起未来考验的；如果你想利用 SIMD 扩展、并行性，甚至是后期的 GPU，一个给定的算法可以被一个更合适的算法取代(见第 14 章、并行算法)。
- 标准算法被完整地记录下来。
此外，通过使用算法而不是for-循环，每个操作的意图都由算法的名称明确指示。代码的读者不需要检查原始for循环中的细节来确定如果您使用标准算法作为构建块，您的代码会做什么。
一旦你养成了用算法思考的习惯，你就会意识到很多for循环往往是一些简单算法的变体，比如std::transform()、std::any_of()、std::copy_if()和std::find()。
使用算法也将使代码更加清晰。您通常可以在没有嵌套代码块的情况下实现函数，同时避免可变变量。这将在下面的示例中演示。
我们的第一个例子来自真实世界的代码库，尽管变量名已经被伪装了。因为它只是一个切口，所以您不必理解代码的逻辑。这里的例子只是为了向您展示，与嵌套的for循环相比，使用算法时复杂性是如何降低的。
最初的版本是这样的:
// Original version using a for-loop
auto conflicting = false;
for (const auto& info : infos) {
if (info.params() == output.params()) {
if (varies(info.flags())) {
conflicting = true;
break;
}
}
else {
conflicting = true;
break;
}
} 在for -loop 版本中，很难理解conflicting设置为true的时间或原因，而在下面的算法版本中，你可以本能地看到如果info满足一个谓词，就会发生这种情况。此外，标准算法版本不使用可变变量，可以使用短λ和any_of()的组合来编写。以下是它的外观:
// Version using standard algorithms
const auto in_conflict = [&](const auto& info) {
return info.params() != output.params() || varies(info.flags());
};
const auto conflicting = std::ranges::any_of(infos, in_conflict); 尽管这可能夸大了这一点，但想象一下，如果我们跟踪一个 bug 或将其并行化，使用λ和any_of()的标准算法版本将更容易理解和推理。
为了进一步说明使用算法而不是“T0”循环的重要性，我想展示一些不太明显的问题，当你使用手工“T1”循环而不是标准算法时，你可能会遇到这些问题。
假设我们需要一个函数，将第一个 n 个元素从容器的前面移到后面，如下所示:
图 5.4:将前三个元素移到范围的后面
一种天真的方法是将第一个 n 元素复制到后面，同时迭代它们，然后擦除第一个 n 元素:
图 5.5:为了将元素移到范围的后面而进行的分配和解除分配
下面是相应的实现:
template <typename Container>
auto move_n_elements_to_back(Container& c, std::size_t n) {
// Copy the first n elements to the end of the container
for (auto it = c.begin(); it != std::next(c.begin(), n); ++ it) {
c.emplace_back(std::move(*it));
}
// Erase the copied elements from front of container
c.erase(c.begin(), std::next(c.begin(), n));
} 乍一看，它看起来似乎是合理的，但是检查它揭示了一个严重的问题——如果容器在迭代期间由于emplace_back()而重新分配，迭代器it将不再有效。当算法试图访问无效的迭代器时，算法将进入未定义的行为，在最好的情况下，会崩溃。
由于未定义的行为是一个明显的问题，我们将不得不重写算法。我们仍然使用手工制作的for循环，但是我们将使用索引而不是迭代器:
template <typename Container>
auto move_n_elements_to_back(Container& c, std::size_t n) {
for (size_t i = 0; i < n; ++ i) {
auto value = *std::next(c.begin(), i);
c.emplace_back(std::move(value));
}
c.erase(c.begin(), std::next(c.begin(), n));
} 解决方案奏效了；它不再崩溃了。但是现在，它有一个微妙的性能问题。std::list上的算法明显慢于std::vector上的算法。原因是和std::list::iterator一起使用的std::next(it, n)是 O(n) ，a std::vector::iterator上的 O(1) 。由于std::next(it, n)在for循环的每一步都被调用，该算法在std::list等容器上的时间复杂度为O(n2)。除了这个性能限制之外，前面的代码还有以下限制:
- 由于
emplace_back()，它不适用于静态大小的容器，如std::array - 它可能会抛出一个异常，因为
emplace_back()可能会分配内存并失败(不过这可能很少见)
当我们到达这个阶段时，我们应该浏览标准库，看看它是否包含合适的算法来用作构建块。方便的是，<algorithm>头提供了一个名为std::rotate()的算法，它在避免前面提到的所有缺点的同时，准确地完成了我们正在寻找的东西。这是我们使用std::rotate()算法的最终版本:
template <typename Container>
auto move_n_elements_to_back(Container& c, std::size_t n) {
auto new_begin = std::next(c.begin(), n);
std::rotate(c.begin(), new_begin, c.end());
} 我们来看看使用std::rotate()的优势:
- 算法不会抛出异常，因为它不会分配内存(尽管包含的对象可能会抛出异常)
- 它适用于尺寸无法改变的容器，如
std::array - 性能是 O(n) 不管它在哪个容器上运行
- 考虑到特定的硬件，该实现很可能得到优化
也许你会觉得for循环和标准算法之间的这个比较不公平，因为这个问题还有其他既优雅又高效的解决方案。然而，在现实世界中，当标准库中有算法在等待解决你的问题时，看到像你刚刚看到的实现是很常见的。
最后一个例子强调了这样一个事实，即使看起来非常简单的算法也可能包含您不会考虑的优化。我们来看看std::find()吧，比如。一眼看去，明显的实现再优化不过了。以下是std::find()算法的可能实现:
template <typename It, typename Value>
auto find_slow(It first, It last, const Value& value) {
for (auto it = first; it != last; ++ it)
if (*it == value)
return it;
return last;
} 然而，纵观 GNU libstdc++ 实现，当与random_access_iterator(换句话说，std::vector、std::string、std::deque和std::array一起使用时，libc++ 实现者已经一次将主循环展开成四个循环的块，导致比较(it != last)被执行四分之一次。
以下是取自 libstdc++ 库的std::find()优化版本:
template <typename It, typename Value>
auto find_fast(It first, It last, const Value& value) {
// Main loop unrolled into chunks of four
auto num_trips = (last - first) / 4;
for (auto trip_count = num_trips; trip_count > 0; --trip_count) {
if (*first == value) {return first;} ++ first;
if (*first == value) {return first;} ++ first;
if (*first == value) {return first;} ++ first;
if (*first == value) {return first;} ++ first;
}
// Handle the remaining elements
switch (last - first) {
case 3: if (*first == value) {return first;} ++ first;
case 2: if (*first == value) {return first;} ++ first;
case 1: if (*first == value) {return first;} ++ first;
case 0:
default: return last;
}
} 请注意，实际上是std::find_if()而不是std::find()利用了这种循环展开优化。但是std::find()是用std::find_if()实现的。
除了std::find()之外，libstdc++ 中的大量算法都是使用std::find_if()来实现的，例如any_of()、all_of()、none_of()、find_if_not()、search()、is_partitioned()、remove_if()和is_permutation()，这意味着所有这些都比手工for循环稍快一些。
我所说的轻微，实际上是指轻微；加速约为 1.07 倍，如下表所示:
| 在 10，000，000 个元素的`std::vector`中找到一个整数 | | 算法 | 时间 | 加速 | | `find_slow()` | 3.06 毫秒 | 1.00 倍 | | `find_fast()` | 3.26 毫秒 | 1.07x |表 5.5: find_fast()使用 libstdc++ 中的优化。基准测试显示，find_fast()比 find_slow()稍快。
然而，即使好处几乎可以忽略不计，使用标准算法，你可以免费得到它。
除了循环展开，一个非常微妙的优化是trip_count向后迭代，以便与零而不是值进行比较。在一些 CPU 上，与零比较比任何其他值稍快，因为它使用另一个汇编指令(在 x86 平台上，它使用test而不是cmp)。
下表显示了使用 gcc 9.2 时组件输出的差异:
| 行动 | C++ | 组装 x86 | | 与零比较 |auto cmp_zero(size_t val) {
return val > 0;
} |
test edi, edi
setne al
ret | | 与其他值进行比较 |
auto cmp_val(size_t val) {
return val > 42;
} |
cmp edi, 42
setba al
ret |
Table 5.6: The difference in assembly output即使在标准库实现中鼓励这种优化，也不要为了从这种优化中获益而重新排列手工循环，除非这是一个(非常)热点。这样做会严重降低代码的可读性；让算法来处理这类优化。
这是我关于使用算法而不是for循环的建议的结尾。如果你还没有使用标准算法，我希望我已经给了你一些论据来说服你试一试。现在我们将继续讨论我关于有效使用算法的最后一个建议。
我们将通过突出一个在试图组合来自算法库的多个算法时的常见问题来结束这一章:很难避免底层容器的不必要的副本。
举个例子可以澄清我在这里的意思。假设我们有某种类型的Student类来代表特定年份和特定考试分数的学生，如下所示:
struct Student {
int year_{};
int score_{};
std::string name_{};
// ...
}; 如果我们想在一大群学生中找到第二年分数最高的学生，我们可能会在score_上使用max_element()，但是由于我们只想考虑第二年的学生，这就变得棘手了。本质上，我们想从copy_if()和max_element()的组合中合成一个新算法，但是使用算法库合成算法是不可能的。相反，我们必须将第二年的所有学生复制到一个新容器中，然后迭代新容器以找到最高分数:
auto get_max_score(const std::vector<Student>& students, int year) {
auto by_year = [=](const auto& s) { return s.year_ == year; };
// The student list needs to be copied in
// order to filter on the year
auto v = std::vector<Student>{};
std::ranges::copy_if(students, std::back_inserter(v), by_year);
auto it = std::ranges::max_element(v, std::less{}, &Student::score_);
return it != v.end() ? it->score_ : 0;
} 这是其中一个的地方，很容易从零开始编写自定义算法，而不利用标准算法。但是，正如您将在下一章中看到的，没有必要为这样的任务放弃标准库。编写算法的能力是使用 Ranges 库的主要动机之一，我们将在下一篇文章中介绍。
在本章中，您学习了如何使用算法库中的基本概念，将它们用作构建块而不是手写for-循环的优势，以及为什么使用标准算法库有利于在后期优化您的代码。我们还讨论了标准算法的保证和权衡，这意味着从现在开始，您可以放心地使用它们。
通过使用算法而不是手动for循环的优势，您的代码库已经为并行化技术做好了充分的准备，这些技术将在本书的后续章节中讨论。标准算法缺少的一个关键特性是组合算法的可能性，当我们试图避免不必要的容器副本时，这一点得到了强调。在下一章中，您将学习如何使用 C++ Ranges 库中的视图来克服标准算法的这一限制。