驯服 Filter View¶

标题：Taming the Filter View in C++ Programming

日期：2024/12/20

作者：Nicolai Josuttis

链接：https://www.youtube.com/watch?v=c1gfbbE2zts

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注：告诉你为什么 filter 需要缓存设计，然后各种爆炸就出现了。

我喜欢来这里。生活很大程度上在于找到你的同类（finding your people）。我花了很多时间试图弄清楚我的同类在哪里，而他们就在这里。

我是 Nico Josuttis，我们得谈谈。我们必须谈谈 C++ 的 filter view（过滤视图）。本次演讲的题目是“驯服 C++ Filter View”，这当然暗示了一个信息：这里面有问题，或者说有惊喜。你可能会说，这很符合 C++ 的传统。

首先，了解这些惊喜是什么以及我们在哪里需要小心是很有趣的。当然，另一个问题是“为什么会这样”。

基础介绍：Filter View¶

让我们先从 filter 谈起。假设我们有一个 print 函数，一个通用的打印函数，它接受一个 const T& 参数作为集合，并逐个打印元素，用空格分隔。我们可以传入一个 vector，也可以传入一个 set。

在 C++20 中有一些改进，以防你不了解：你可以使用 auto 来代替模板参数。你甚至可以用概念（Concept）来限定这个 auto。虽然它本质上仍然是一个函数模板，但我们可以这样约束它。

void print(const auto& coll) {
    for (const auto& elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';
}

现在这里有一个新特性，就是我们可以使用 Views（视图）。举个例子：让我们只打印第一个集合的前三个元素；或者打印第二个集合的前三个元素。正如你所见，我们仍然使用通用的 print 函数，它使用基于范围的 for 循环（Range-based for loop）来遍历元素。

有一种更有趣的语法，使用管道符号（|）。这意味着你可以将集合“管道传输”到这个视图中以获取前三个元素。借此，你可以创建管道（pipelines），比如：取前三个元素，将它们转换为字符串，加上 “s”，然后遍历并打印所有这些元素。

这就是巨大的力量。这是将微小的计算片段组合在一起，汇聚成处理集合的巨大魔力和能力。

再举几个例子：这是一个古典音乐作曲家的 map，包含姓名和出生年份。让我们遍历这些作曲家，但不是全部。让我们只取那些 1700 年以后出生的，然后只取前三个，然后再只取他们的 key（即名字）。这就是我们要传递给基于范围的 for 循环的 range。瞧，你得到了输出。（顺便说一句，如果 map 对元素进行了排序，不要感到惊讶）。

再看一个例子。我们有一个名为 iota 的源视图，它生成值 1, 2, 3 等等（这可以是无限的）。让我们过滤这些元素，只取 3 的倍数，丢弃前 3 个，取接下来的 8 个，将这些值转换为字符串，加上 “s”，然后在基于范围的 for 循环中使用它。

这就是输出。我们很高兴 C++11 标准化了 auto，因为如果你要写出这个类型……它不仅仅是因为涉及到了 lambda，还因为它的类型是：iota_view 的 filter_view 的 drop_view 的 take_view 的 transform_view。

你也可以使用这些管道来修改元素。比如创建一个视图，只过滤非空单词，并打印出来。你会看到实际上它是如何工作的。

它是如何工作的？（原理）¶

了解它的工作原理对于理解你必须如何处理它非常重要。

原则上很简单。C++ 最成功的功能是遍历元素的值。它使用了一个通用的 API，即 迭代器（Iterators）。你通过 begin 和 end 获取它们，通过调用 ++ 遍历值，与 end 进行比较，并使用 * 访问值。

基于范围的 for 循环如果被使用，它会调用一个低级循环，使用该迭代器从 begin 到 end 遍历元素。这就通过原始指针一样：调用 begin 获取第一个元素；只要我们没到 end，打印值，去下一个元素；只要没到 end，打印值，去下一个元素，以此类推。

现在假设我们使用一个视图。假设我们调用 print，我们将所有元素通过管道传输到一个 filter（只允许小于 20 的元素），然后 transform（转换）每个元素。

print(coll | std::views::filter([](auto i){ return i < 20; })
           | std::views::transform([](auto i){ return -i; }));

它的工作方式是，我们在一定程度上创建了一个 filter view，然后将这个 filter view 传递给一个 transform view。正如你所见，这两者都包装了现有的容器（例如 vector）。

当你创建 filter view 时，你并没有开始计算或处理任何元素。 你只是创建了一个数据结构，这个数据结构是底层 range（这里是 vector）的一个包装器。这个包装器提供了与底层 range 相同的 API：你可以用迭代器从 begin 到 end 遍历并用 * 访问值。

此时什么都没有发生。当你再用 transform view 包装它时，你包装了 filter view，再次提供了一个用迭代器从 begin 到 end 的 API。

目前为止没有任何事情启动。 这不像在 Unix 中，当我们有一个管道时，我们开始生成值，存储它们，然后下一个组件开始处理。这里的游戏是在我开始迭代时才开始的。

当我调用 begin 时：

我去问最外层的视图（transform view）。
该视图向 filter view 请求 begin。
filter view 向底层集合（vector）请求 begin。

现在关于 begin 我们还没完。集合返回第一个元素（比如 47）的位置。这个位置被传回给 filter。 Filter 说：“等一下，在我放行之前，我得看看它的值。” 所以 filter 在这里调用 *（解引用），查看 47 的值，并拒绝了它。

Filter 如何拒绝？它调用 ++，意思是去下一个元素。我们仍然在 filter 的 begin 调用内部。集合返回 11 的位置。Filter 看着它，接受了它。这个位置（注意，是位置，不是值）被作为第一个位置传递给 transform。 Transform 说：“耶，我把所有东西都放行。如果你只想要一个元素，当你问我要值的时候我才会起作用。”

所以我们返回了迭代器。现在我们可以进行双重检查，与 end 比较，然后用 * 访问值。这意味着我们沿着这个“迭代器到迭代器到迭代器”的链条回去。当我们通过 transform 迭代器请求值时，它会说：“等一下，让我把这个值取反。” 然后去下一个元素，意味着我们再次穿过整个队列，说“去下一个元素”。只要没到 end，取值，打印，如此往复。

Filter 只是确保我们不使用每一个元素。Transformation 说当你需要值的时候，我把它取反。这就是我们所说的 拉取模型（Pull Model）。下一个元素及其值是 按需（on demand） 处理的。这与 Unix 中的推送模型（Push Model）完全不同。

优化的副作用¶

如果你调换 filter 和 transform 的顺序，会有有趣的后果。如果是先 transform 然后 filter：

我们请求 filter 的 begin。
Filter 去问 Transform。Transform 去问集合（拿到 8）。
Transform 看着 8，取反，把结果传递给 Filter。
Filter 说“我需要这个值”。所以 Filter 回到 Transform，Transform 问集合要值，取反，给 Filter。
Filter 检查后决定是否接受。

有趣的是，如果 Filter 拒绝了，它会请求下一个（++）。Transform 请求下一个（15），取反，传给 Filter。Filter 这次接受了。 Filter 传递出元素（位置）。此时 begin 调用完成。

然后在基于范围的 for 循环中，我们说“我们要取值”。 Filter 之前已经看过这个值了，但那个时刻已经过去了。我们只拿到了位置。所以在 for 循环中，我们再次查看该值。这意味着我们第二次不得不转换该值。

这种架构的副作用是：如果你把 filter 放在像 transformation 这样的组件后面，transformation 可能会被执行两次。你在链中放入的 filter 越多，你可能需要做的转换就越多。

Filter 需要值来检查。
调用者需要值来处理。
我们不传递值，我们传递位置（迭代器）。

第一个结论：尽早使用 Filter。 避免在使用它们之前做昂贵的操作。

不过不要太紧张。编译器会做大量优化。如果只是简单的取反和检查，编译器可能会把所有调用都内联并优化掉。这就相当于一个带有 if 的循环。但如果 transformation 很重，且编译器没有优化，这就很重要了。

Filter 的性能问题¶

现在让我们谈谈过滤和 filter view 的性能。

当我们在 C++ 中引入数据结构以提供 begin 和 ++ 等 API 时，我们的想法是统一遍历元素的方式。无论你有 vector 还是 list，它们完全不同，但我们有一些共同的保证：

声明和默认初始化是廉价的。
begin 是廉价的（通常只是指向第一个元素的指针）。
end 是廉价的。
empty 是廉价的（begin == end）。
size 是廉价的（我们通常跟踪大小）。
- 除了 forward_list。它不跟踪大小，因为这就需要遍历所有元素，代价昂贵。
下标操作符 [] 是廉价的，或者不提供。

原则是：要么它是廉价的，要么我们不提供它。 如果某些操作很昂贵，我们会确保它们看起来很丑陋、很麻烦，需要花费时间和精力（比如 std::advance）。

现在我们看看 filter view 会发生什么。假设我们有一个 vector，我们在上面放一个 filter view 并调用 begin。这很简单，我们去 filter 的 begin。但这还不够，因为 filter 必须仔细检查这是否真的是第一个匹配的元素。所以我们必须遍历元素值，直到找到匹配的元素。

begin 不再是廉价的。 如果第一个匹配的是容器中的最后一个元素，这就是一个线性操作（Linear Operation）。如果有一百万个元素，你过滤并找到最后一个，就是一百万次调用 ++ 和 *。对于 list 也是一样。

因此，在 filter view 中：

begin 可能是昂贵的（线性复杂度）。
end 可能是昂贵的（我们得知道结束在哪里）。

或者，我们可以作弊。在 filter view 中，我们确实作弊了。 end 并不真的是最后一个匹配元素之后的位置。因为反正内存也不连续，我们直接使用底层容器的 end。这样，end 变廉价了。

但是：

empty 可能是昂贵的。empty 本质上是调用 begin 看看是否等于 end。
size 是昂贵的（需要遍历统计）。
下标操作符 [] 是昂贵的（需要遍历跳转）。

因为我们不喜欢糟糕的性能，所以我们在 API 中关闭了这些操作。 Filter 没有 size。 你得到了一个新的容器，它没有 size，而且你可能比使用 forward_list 更常用它。 Filter 没有下标操作符 []。 而且，Filter 提供的迭代器不能计算第 10 个元素在哪里，只能逐个遍历。所以 filter 的迭代器不是随机访问迭代器（Random Access Iterator），只能向前（或向后）逐个移动。

这对泛型代码有后果：

如果你想检查是否为空，请不要比较 size == 0（因为不支持），请使用 empty()。
你不能对 filter 后的元素进行排序（std::sort），因为没有随机访问迭代器。

迭代 Filter View 的代价¶

假设我们有一个底层容器，我们在寻找每第 7 个元素。你可以使用基于范围的 for 循环。它在内部调用一次 begin 和一次 end。虽然 begin 昂贵，但这只发生一次，还可以接受。

但还有其他迭代方式，比如手动迭代：

for (auto pos = view.begin(); pos != view.end(); ++pos) { ... }

以前我会说，多次调用 end 是没问题的。但现在我们有了问题。

如果我们天真地实现 filter： begin 找到第一个匹配元素。如果我们要支持反向迭代（reverse），情况会变得非常糟糕。

如果你反向迭代（reverse view），外部将 begin 映射到 end，end 映射到 begin。如果在手动循环中多次调用 end，这会多次调用底层的 begin。如果你每次都要重新计算 begin（这可能是一个线性操作），那么这就变成了 二次复杂度（Quadratic Complexity）。这是一场噩梦。

这是一个事实。如果你用天真的 filter 实现（不缓存），filter | reverse 会在手动迭代时慢一万倍。这是不可接受的。

为了解决这个问题，标准库采用了缓存（Caching）。技巧很简单：当你对 filter 调用 begin 时，它找到第一个匹配元素，并将这个位置缓存在视图对象中。下一次你调用 begin，它是廉价的，直接使用缓存。

对于 vector，如果底层内存发生变化（比如 push_back 导致重新分配），缓存的迭代器会失效。但这里有个技巧：如果底层是随机访问范围（如 vector），我们不缓存迭代器，而是缓存偏移量（Offset）。这样即使内存重新分配，begin 仍然有效。

这看起来我们对修改底层 range 有很好的支持。但要小心。

我们现在的状态：

filter view 的声明/初始化：廉价。
begin：第一次调用可能昂贵，之后是廉价的（摊销常量）。
end：廉价。

这导致标准中的措辞发生了变化。容器要求常量时间复杂度，而视图只要求摊销常量时间复杂度（Amortized constant time）。问题是，摊销只有在你多次调用 begin 时才有好处，但这并不像 push_back 那样常见。

缓存 `begin` 的后果（灾难开始了）¶

你看到了 filter 是如何实现的，你可能觉得：“太棒了，我们解决了性能问题。” 现在我们必须谈谈这样做的后果。

1. const 正确性问题¶

让我们回到那个 print 函数。

void print(const auto& coll) { ... }

我们传入 vector，工作正常。传入 transform view，工作正常。现在传入 filter view：

std::vector v{1, 2, 3, 4};
auto fv = v | std::views::filter(...);
print(fv); // 编译错误！

编译失败。 即使你直接迭代一个 const 的 filter view：

const auto fv = v | std::views::filter(...);
for (auto elem : fv) { ... } // 编译错误！

也会编译失败。

为什么？因为 filter view 在调用 begin 时会修改自身（写入缓存）。这意味着 begin() 不是 const 的。 你不能对一个 const 的 filter view 进行迭代。

这就解释了为什么传给 const auto& coll 的 print 函数会失败。它把 view 变成了 const 引用，然后试图调用非 const 的 begin。

后果： 在你写的所有泛型代码中，如果你想支持 view，你需要将 const T& 替换为 T&&（通用引用/转发引用）。

void print(auto&& coll) { ... }

这就通过了，因为我们没有将其设为 const。

2. 线程安全问题¶

但是等等。你现在不再通过 const 引用传递了。如果在多线程环境中：一个线程在迭代（调用 begin 修改缓存）。另一个线程在检查 empty（也可能触发 begin 逻辑并写入缓存）。这是对同一个对象的并发修改。 这是未定义行为（Undefined Behavior），是运行时错误。

迭代一个 view 不是线程安全的。 处理 vector 是线程安全的，处理 transform view 是线程安全的，但处理 filter view 不是。这是一种“并发读是未定义行为”的情况。我们在 C++20 中标准化了一个非常有趣的用例：并发读会导致崩溃。

3. 令人讨厌的变通方法¶

有一些变通方法。比如在启动线程之前调用一次 empty() 来预热缓存。或者在调用端使用 subrange，或者使用 std::views::all 来创建引用语义。但如果你通过值传递 view，要小心。

修改元素的陷阱¶

我们谈了读，现在谈谈写。原则上允许修改元素。

// 过滤偶数，然后加 2
auto fv = v | std::views::filter([](auto i){ return i % 2 == 0; });
for (auto& elem : fv) { elem += 2; }

1, 4, 7, 10 变成了 1, 6, 7, 12。这很棒。

但是，如果我们在循环中做 elem += 1 呢？第一次迭代：4 变成 5。没问题。第二次迭代：我们再次调用 begin。由于缓存了第一次调用的结果（原来的第二个元素位置），它直接从那里开始。虽然那个元素现在变成了 5（不再是偶数），但迭代器还是从那里开始了。

标准委员会知道这个问题。官方措辞是： “修改 filter view 迭代器指向的元素是允许的，但如果结果值不再满足 filter 的谓词，则会导致未定义行为。”

这就好比在电梯前贴个告示：“进入前请确保电梯在这一层。” 我们已经尽职了，剩下的就是你的问题了。这在行话里叫“免责声明（Put your ass on the wall paper/Cover Your Ass）”。

Patrice 给我发了个很好的例子：如果你有一堆怪物，有些死了，你想用 filter 找出死的怪物并复活它们（dead = false）。 这是未定义行为。 你不能用 filter view 来“治愈”损坏的元素（healing broken elements）。这是 view 最常用的用例之一，但它是未定义行为。

如何驯服它？

即时创建管道（Ad-hoc）：不要重用 view。
只迭代一次。
将谓词逻辑和修改逻辑分开。

在迭代之间修改底层容器¶

还有更糟的。假设我们有 vector 和 list。我们创建 filter view。然后在迭代之前，我们在底层容器开头插入新元素。

对于 List：因为它是节点式的，缓存的迭代器（指向原来的第一个匹配项）仍然指向那个节点。新插入的元素（即使符合条件）会被跳过。对于 Vector：如果我们缓存的是偏移量，它可能指向了新插入位置的元素。

根据底层是 vector 还是 list，你会得到完全不同的行为。而且，如果你为了调试加了一个 print 语句（调用了 empty 或 begin），你会改变缓存的状态，从而改变程序的行为。 观察改变了状态。 这就是我们要面对的。

可以“取消缓存”吗？ 可以通过复制（Copy） view。如果是迭代器缓存（如 list），复制会重置它。如果是偏移量缓存（如 vector），复制也救不了你。

总结：Filter View 的“八宗罪”¶

我们已经在 C++ 中建立了 20 年的 Range 基本惯用法，但 Filter View 打破了它们：

你可以迭代 const ranges？ 对 Filter 来说坏了。
读迭代不改变状态？ 对 Filter 来说坏了。
Empty 没有副作用？ 对 Filter 来说坏了。
并发读是安全的？ 对 Filter 来说坏了。
Range 的副本具有相同的状态？ 对 Filter 来说坏了。
迭代之间的修改是安全的？ 对 Filter 来说坏了。
通过迭代器修改是安全的？ 对 Filter 来说坏了。

如何驯服 Filter View（最佳实践）¶

尽早使用 Filter：把它放在管道的前面。
即时（Ad-hoc）应用 Filter：不要传递 Filter View，在最后一刻再组合它们。
- 你可以传递除了源 range 之外的管道部分。
不要在 Filter 中修改元素。
- 或者如果必须修改，绝不要破坏谓词（不要把符合条件的改成不符合的）。
- 即：不能用来“修复”元素。
只迭代一次（像 Input Iterator 那样）。
不要在应用 Filter 后修改底层 range。
不要在并发代码中使用 Filter。
首选 empty() 而不是 size() == 0。

为什么设计成这样？¶

我们目前的“Begin 缓存”设计是为了避免某些情况下的二次复杂度（主要是 reverse | filter），但这导致了严重的 const 问题、并发问题和状态问题。

替代方案：

不缓存：这会让 filter view 变回 O(N) 的 begin。但这会导致 reverse 组合变成二次复杂度。
不缓存，并将 Filter 迭代器降级为 Input Iterator：这意味着只能迭代一次。但这会禁用某些算法。
显式缓存：比如 cache_latest 视图。

目前，这（带缓存的设计）是标准。虽然有些公司因为这些风险考虑禁止使用 Views，但我认为我们必须修复它。

我将在 C++26 提出提案（可能叫“Healing the Filter View”），试图修复这个问题。 也许我们可以让不缓存成为默认，或者改变迭代器类别。

如果你们认为这种编程方式不合适，请支持我，或者告诉我我是错的。我们需要社区的声音。

谢谢大家。