第8.1章: ranges 与基于范围的算法

概述

range 是任何提供了起点与终点的对象。目前介绍过的所有容器—— ::fast_io::vector、 ::fast_io::string、 ::fast_io::array、 ::fast_io::span、 ::fast_io::string_view、 ::fast_io::cstring_view、 ::fast_io::index_span 以及 C 风格数组—— 都是连续范围。

基于范围的算法是一次作用于整个范围的操作。不必手工编写循环，你可以调用排序、查找、反转、复制或计数等函数。

在本章中，你将学到：

什么是 range
如何调用基于范围的算法
算法如何在不同容器上统一工作
如何用比较器定制算法

1. 什么是 range？

range 由两个迭代器定义：

一个起始迭代器
一个结束迭代器

你已经熟悉的 range 例子：


::fast_io::vector<int> v{1, 2, 3};
int a[3]{4, 5, 6};
::fast_io::span<int> s{a, 3};
::fast_io::string str{"abc"};
::fast_io::string_view sv{"hello"};

这些都是合法的 range。

2. 对 range 排序

最简单的例子就是排序：


::fast_io::vector<int> v{3, 1, 2};

::std::ranges::sort(v);   // ascending

要按逆序排序，请使用 ::std::ranges::greater：


::std::ranges::sort(v, ::std::ranges::greater{});

这对任何 range 都有效，包括 C 风格数组：


int a[5]{5, 1, 4, 3, 2};
::std::ranges::sort(a, ::std::ranges::greater{});

3. 带概念约束的比较器（<functional>）

C++20 在 <functional> 中提供了标准化的比较函数对象，它们与 range 算法天然配合：

std::ranges::equal_to —— x == y
std::ranges::not_equal_to —— x != y
std::ranges::less —— x < y
std::ranges::less_equal —— x <= y
std::ranges::greater —— x > y
std::ranges::greater_equal —— x >= y
std::compare_three_way —— x <=> y

它们经过概念检查、可复用，并且不会生成额外代码。

4. 用 lambda 作为比较器

你可以用 lambda 作为比较器：


::std::ranges::sort(v, [](int a, int b) noexcept {
    return a > b;
});

请始终把比较器 lambda 标记为 noexcept。如果比较器抛出异常，C++ 标准要求程序终止。

5. lambda 显然不是零开销

每个 lambda 表达式都是独有的类型，编译器会为每一个生成独立的代码，即便它们看起来完全相同：


::std::ranges::sort(v,  [](int a, int b) noexcept { return a > b; });
::std::ranges::sort(v1, [](int a, int b) noexcept { return a > b; });
::std::ranges::sort(v2, [](int a, int b) noexcept { return a > b; });

这三个 lambda 看起来一样，但会产生三个不同的比较器对象和三条独立的代码路径。这会增加：

二进制体积
指令缓存压力
冷启动时间
更新时间
网络传输体积（WASM/PWA）

当 lambda 出现在模板内部时（我们稍后会介绍），这种开销会变得 糟糕得多，因为模板会为每个不同的 lambda 类型分别实例化。

如果 ::std::ranges::greater{} 这类标准比较器可用，你应当始终优先使用它，而不是新写一个 lambda。

6. 在 range 中查找


int a[5]{10, 20, 30, 40, 50};

auto it = ::std::ranges::find(a, 30);

if (it != ::std::ranges::end(a)) {
    // found
}

7. 反转 range


::fast_io::string s{"hello"};

::std::ranges::reverse(s);   // "olleh"

8. 复制 range


int a[3]{1, 2, 3};
int b[3]{};

::std::ranges::copy(a, b);

9. 统计元素个数


::fast_io::vector<int> v{1, 2, 2, 3};

std::size_t n = ::std::ranges::count(v, 2);  // n = 2

10. 使用 ::std::ranges::begin 与 ::std::ranges::end

这些函数适用于所有 range，包括 C 风格数组：


int a[3]{10, 20, 30};

auto first = ::std::ranges::begin(a);
auto last  = ::std::ranges::end(a);

要点

range 由起点与终点定义。
所有 fast_io 容器与 C 风格数组都是连续 range。
基于范围的算法作用于整个 range。
算法不依赖容器类型。
<functional> 提供了可复用、经概念检查的比较器。
优先使用 std::ranges::greater，而不是自己写 lambda。
lambda 不是零开销，因为每一个都会生成新代码。
模板会让 lambda 膨胀严重恶化。
比较器 lambda 必须是 noexcept。
std::ranges::begin 与 std::ranges::end 适用于所有 range。