使用 Token Sequences 迭代 Ranges

Using Token Sequences to Iterate Ranges

Source | HN Comments

文章探讨了使用 Token Sequences 迭代 Ranges 的问题。作者指出，C++ Ranges 在使用 `filter`、`take_while` 和 `reverse` 等适配器时，由于循环结构的限制，可能导致不必要的迭代和性能损耗。文章对比了 Flux 库的内部迭代方案，展示了其避免性能问题的优势。最后，作者提出了一个基于 Token Sequences 的“疯狂”解决方案，通过代码注入的方式，允许自定义循环结构，从而实现更优化的迭代。

Barry's C++ Blog Just a blog about C++

Home 使用 Token Sequences 迭代 Ranges Post Cancel

使用 Token Sequences 迭代 Ranges

发表于 2025 年 4 月 3 日，更新于 2025 年 4 月 7 日作者：_Barry Revzin _ 1 次浏览 28 分钟 阅读使用 Token Sequences 迭代 Ranges 目录使用 Token Sequences 迭代 Ranges

最近在 StackOverflow 上有一个问题，促使我想写一篇关于 Ranges 的新文章。具体来说，我想写一些关于 Ranges 在某些情况下执行比表面上应该执行的更多工作的情况。然后我们可以做些什么来避免做那些额外的工作。我将提供一些解决方案——一个合理的解决方案，你今天就可以使用，以及一个相当疯狂的解决方案，它使用了一种我们仍在努力设计的语言特性，甚至可能不会出现在 C++29 中。

问题

为了本文的目的，我将只讨论一个非常简单的问题：

for (auto elem : r) {
  use(elem);
}

在 C++ 迭代器模型中，这会被转换为类似这样的代码：

auto __it = r.begin();
auto __end = r.end();
while (__it != __end) {
  use(*__it);
  ++__it;
}

我在这里故意使用 while 循环，因为它是一个更简单的结构，并且允许我最后写出前进步骤。现在，如果你想自定义 range 的行为，那么这些就是你的入口点。你可以更改初始化阶段 (begin() 和 end())，可以更改针对完整性的检查 (__it != __end)，可以更改读取操作 (*__it)，并且可以更改前进操作 (++__it)。就这样。你无法更改循环本身的结构。仅仅这一点就足以提供非常丰富的功能。这是一个非常强大的抽象。 Ranges 库有大量的 range 适配器，可以自定义此行为。其中一些非常巧妙地融入到这组自定义点中。 views::transform 只是改变了 *__it 的作用。 views::drop 只是改变了 r.begin() 的作用。这些适配器没有开销。现在，像 views::join 这样的适配器有一些开销，这可能并不令人惊讶。 views::join 真的想写两个嵌套循环，但它不能——它必须以某种方式展平迭代。或者 views::concat，它想写 N 个循环而不是一个，但它也做不到。但是有一些适配器似乎应该非常巧妙地融入到这个模型中。然而……

为什么总是 `views::filter`？

不知何故，无论主题是什么，views::filter 总是问题。在这种情况下，filter 似乎非常适合该模型。它需要自定义 begin() 和 ++__it，这两者都是现成的自定义点。检查和读取操作是直通的。那么问题是什么呢？好吧，让我们继续分解 filter(f) 对我们的循环所做的操作：

while (__it != __end) {     // (A)
  use(*__it);
  ++__it;
  // 现在我们必须做 find_if(f)
  while (__it != __end) {   // (B)
    if (f(*__it)) {
      break;       // (C)
    }
    ++__it;
  }
}

考虑一下这三行标记的行。当我们执行 find_if 来查找下一个元素时，我们必须确保我们不会超出 range 的末尾。这就是 (B) 中的检查。然后我们继续寻找一个满足我们谓词的元素。现在，内部循环将以两种方式之一终止：

我们到达了终点——(B) 中的检查失败。这意味着 (A) 中的检查当然也会失败，并且是多余的。
我们找到了一个元素——我们击中了 (C) 中的 break。这意味着 (A) 中的检查肯定会通过，并且是多余的。

理论上，我们只需要在 __it 和 __end 之间进行 N 次比较（原始 range 中的每个元素一次）。最佳循环应该是这样的：

while (__it != __end) {
  if (f(*__it)) {
    use(*__it);
  }
  ++__it;
}

但相反，我们执行 N + K + 1 次比较，其中 K 是满足谓词的元素的数量。如果底层迭代器真的只是一个指针之类的东西，那么这些额外的 K+1 次比较可能会被优化掉。但是这些额外比较的存在会干扰优化器。此外，f 没有内联到迭代器中，并且倾向于通过指向 filter_view 的后向指针来访问，这也没有帮助。 K + 1 个额外的指针比较听起来可能没什么大不了的。但是，如果我们的比较比这更昂贵呢？

`views::take_while` 让情况更糟

我之前提到的实际 StackOverflow 问题不仅使用了 filter，还使用了 take_while(f) | filter(g)。就像 views::filter 似乎只需要调整 ++__it 一样，views::take_while 似乎只需要调整 __it != __end。它……应该完全适应。然而，如果我们分解 r | take_while(f) | filter(g) 实际上所做的操作，我们会得到这个：

while (__it != __end and f(*__it)) {    // (A)
  use(*__it);

  ++__it;
  // 现在我们必须做 find_if(g)
  // 除非现在受到 take_while(f) 的限制
  while (__it != __end and f(*__it)) {  // (B)
    if (g(*__it)) {
      break;             // (C)
    }
    ++__it;
  }
}

现在让我们考虑一下当我们退出内部循环时会发生什么。有三种情况：

我们在 (B) 中到达了真正的终点。现在我们再次检查 __it != __end，这当然会失败，再次出现 1 个多余的迭代器比较。
我们遇到了一个打破我们 take_while 标准的元素——一个 f 返回 false 的元素。但是我们必须在 (A) 中再次进行检查，这需要在同一元素上再次调用 f！
我们遇到了一个满足我们的 filter g 的元素。我们已经验证了它满足 f，但是现在我们……再次必须在 (A) 中调用 f！

或者，换句话说。当 (B) 变为 false 时，我们没有元素了——但即使它必须再次为 false，我们也会重新检查 (A)。但是当我们在 (C) 中中断时，我们仍然必须再次重新检查 (A)，即使它必须为 true。这意味着这个程序：

auto lt5 = [](int i){ println("lt5({})", i); return i < 5; };
auto even = [](int i) { println("even({})", i); return i % 2 == 0; };
auto v = vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9};
auto r = v | views::take_while(lt5) | views::filter(even);
for (int i : r) {
  println("got {}", i);
}

将打印以下内容：

lt5(1)
even(1)
lt5(2)
even(2)
lt5(2)
* got 2
lt5(3)
even(3)
lt5(4)
even(4)
lt5(4)
* got 4
lt5(5)
lt5(5)

请注意，我们对这 5 个元素调用了 8 次 lt5。在这种情况下，该函数非常便宜（或者如果我们不打印的话会很便宜）。但是如果不是呢？

翻转它并 `views::reverse` 它

问题是：如果我们在 range 中抛出一个 views::reverse 会发生什么？初步看来，也许 views::reverse 应该做得很好——因为我们基本上只需要将 ++__it 更改为 --__it。对吗？事实证明，反转 range 是一种偷偷摸摸地复杂的算法，很多人在第一次尝试编写时都会出错几次。即使使用整数编写它也可能很棘手，因为无符号整数在 0 处环绕。但是对于迭代器，你就是_无法_迭代超过 begin()。所以你必须这样构建你的循环：

auto __it = r.begin();
auto __end = r.end();
while (__it != __end) {
  // 首先递减
  --__end;
  // 然后读取
  use(*__end);
}

你可能会认识到这与正向循环的循环结构非常不同——我们在读取后递增。所以仅仅将递增翻转为递减是不够的。相反，我们必须在我们唯一可以做到的地方——在读取操作中进行递减。所以我们的循环是：

while (__it != __end) {
  auto __tmp = __end;
  --__tmp;
  use(*__tmp);
  --__end;
}

很难错过这里的开销：我们在每次迭代中递减相同的迭代器两次。如果底层迭代器只是一个指针，那没什么大不了的。并且对于许多迭代器，递增和递减并不是那么昂贵。但是如果移动我们的迭代器必须进行线性搜索，就像 views::filter 一样？好吧，就是这样。这个程序：

auto v = vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9};
auto r = v | views::take_while(lt5) | views::filter(even) | views::reverse;
for (int i : r) {
  println("* got {}", i);
}

现在打印：

lt5(1)
even(1)
lt5(2)
even(2)
lt5(2)
lt5(3)
even(3)
lt5(4)
even(4)
lt5(4)
lt5(5)
lt5(5)
even(4)
* got 4
even(4)
even(3)
even(2)
* got 2
even(3)
even(2)

也就是说，对于我们最初的五个元素，我们有相同的 8 次 lt5 调用——没有任何改变。但是之前我们实际上只有我们需要的那 4 次 even 调用。现在，我们有 10 个。这不是一个好的结果。

顺便说一句，我最近写了一篇关于通过 filter 进行变异的文章，其中提出了避免多通道变异的案例。由于这种双重递减逻辑，views::reverse _是_一种多通道算法。我稍后会回到这一点。我们发现自己所处的位置是 Ranges 代码与零开销相去甚远。如果不是这样就好了。为了避免这个问题，我们可以做些不同的事情吗？

合理的解决方案：Flux

我已经向你承诺了两种解决方案，并且你已经读到这里了，所以让我们开始吧。 Tristan Brindle 有一个名为 Flux 的库。他就此发表过许多会议演讲，其标题通常包含“Iteration Revisited”（例如，CppCon 2023 的这个演讲）。强烈建议查看演讲和库。 Flux 的高度简化版本是它实际上与 C++20 Ranges 非常相似。主要区别实际上在于 Flux 指针（而不是 C++ 迭代器）是哑的——它不知道如何前进自身或读取自身。因此，正如我之前介绍的 C++ 循环是：

auto __it = r.begin();
auto __end = r.end();
while (__it != __end) {
  use(*__it);
  ++__it;
}

Flux 循环是：

auto __cursor = flux::first(r);
while (not flux::is_last(r, __cursor)) {
  use(flux::read_at(r, __cursor));
  flux::inc(r, __cursor);
}

如果它看起来与你非常相似，那是因为它_确实_非常相似。实际上，Flux 和 C++ Ranges 是同构的。从一个映射到另一个非常容易。并且，实际上，如果你在 Flux 中做与我们在 C++ 中所做的相同的事情，我们会得到相同的行为：

auto v = vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9};
auto r = flux::ref(v).take_while(lt5).filter(even);
for (int i : r) {
  println("* got {}", i);
}

这有相同的 8 次 lt5 调用。

Flux 实际上不支持此列表上的 reverse()。为了让 Ranges 支持它，它必须急切地处理 take_while。 Flux 显然选择不这样做。此时你可能想知道为什么我可能将其描述为合理的解决方案，因为它具有相同的行为。 Tristan 有一个绝招。你可以改为这样做：

flux::ref(v)
  .take_while(lt5)
  .filter(even)
  .for_each([](int i){
    println("* got {}", i);
  });

表面上是相同的事情，只是我们正在使用 for_each 算法而不是 for 循环。现在，我们有了不同的结果：

lt5(1)
even(1)
lt5(2)
even(2)
* got 2
lt5(3)
even(3)
lt5(4)
even(4)
* got 4
lt5(5)

这只有 5 次 lt5 调用——正确的数量。这就是_内部迭代_的力量。在 Flux 中，for_each 不仅仅是围绕编写我之前展示的循环的包装器。它可以做得更好，因为它不受必须适应相同、刚性循环结构的限制。在内部，Flux 可以随意迭代——因为你无论如何都无法观察到它。除其他问题外，内部迭代还解决了众所周知的 transform(f) | filter(g) 问题，其中对于每个满足 g 的元素，f 都会被调用两次。

空间考量

现在，Flux 的另一个重要好处——不仅仅是内部迭代自定义点——是分层的发生方式。让我们以相同的 r | transform(f) | filter(g) 示例为例，并考虑它实际是什么样的。你最终会得到一个对象——视图——它将包含 r、f 和 g。这并不奇怪。但是迭代器是什么样的呢？它们将有一个指向 r 的迭代器，以及一个指向 transform_view 的指针（以获取 f——或者可能只是指向 F 的指针）和一个指向 filter_view 的指针（以获取 g 和 transform_view）。或者，以可视方式表示，如下所示：

struct the_view {
  R underlying; // 底层 range
  F f;     // transform 函数
  G g;     // filter 谓词
};

struct the_iterator {
  iterator_t<R> underlying;  // 底层迭代器
  F* f;            // 指向 transform 函数的指针
  the_view* parent;      // 指向视图的指针（用于 filter）
};

这里有一个非常明显的问题。为什么 the_iterator 需要 F* 和 the_view* 成员？鉴于你已经可以通过 parent->f 获取函数？ Ranges 并不是这样工作的。包装是增量发生的。我们无法尝试最终确定我们的管道以优化我们的空间使用。 transform_view 根本不知道下一个 filter_view。此外，由于 the_iterator 通过指针追逐获得大量信息，因此很可能会对优化产生负面影响。另一方面，在 Flux 中，我们的结构如下所示：

struct the_sequence {
  R underlying; // 底层 range
  F f;     // transform 函数
  G g;     // filter 谓词
};
struct the_cursor {
  cursor_t<R> underlying; // 底层指针
};

在这里，the_sequence 看起来与我们用于 the_view 的内容相同。但是 the_cursor……等等，所有成员都去哪儿了？请记住，Flux 指针不知道如何前进或读取自身——你需要序列才能做到这些。但是 filter 和 transform 都不需要对指针做任何特殊的事情，它们甚至没有包装它。并且不需要任何指针——一切都纯粹是作为组合来完成的。较少的指针追逐对优化器更友好，这可能就是为什么其他等效的 Flux 管道优化得更好的原因。值得注意的是，由于 Flux 和 Ranges 是同构的，你可以从任何 Flux 序列中生成 C++ 迭代器。并且该迭代器是什么样的？它只是一对指针和一个指向序列的指针。实际上，获取 Flux 管道然后将其转换为 C++ 迭代器会执行那种最终化的空间操作。非常酷。

疯狂的解决方案：Token Sequences

你们中的一些人可能认为这很无聊。系好安全带，多萝西。堪萨斯州即将说再见。虽然 Reflection 正以全速前进到 C++26，但我们主要只会获得_内省_工具。没有太多的代码_生成_。即使只是内省也将是对该语言的巨大而具有变革意义的补充，并且我对此感到非常兴奋。添加更多是不可能的。时间只有这么多，即使是 P2996 也非常庞大。我们一直在研究的一种注入想法称为 Token Sequences。该推介的简短版本是，表示 C++ 代码的最佳方式是 C++ 代码，因此我们希望 C++ 代码注入看起来尽可能像 C++ 代码。在我们认为原始的、未检查的 token 序列是最佳方法。 Daveed Vandedoorde 在 EDG 中做了一个部分（偶尔有 bug）的实现，我将在此处进行演示。

另请查看他的 CppCon Reflection 主题演讲！这篇文章的目的不是真正解释设计或激发其具体细节。相反，它是为了演示你可以用它做什么样的恶作剧。也许这最终可以告诉我们指定 range 的内部迭代的正确方法是什么？谁知道。我在这篇博客文章中一直强调的关键问题是 C++ 中的循环结构是_固定的_。它_必须_看起来像这样：

auto __it = r.begin();
auto __end = r.end();
while (__it != __end) {
  use(*__it);
  ++__it;
}

如果你的算法想要一个稍微不同的结构——那么你就倒霉了。例如，take_while(f) 想要这样做：

auto __it = r.begin();
auto __end = r.end();
while (__it != __end) {
  if (not f(*__it)) {
    break;
  }
  use(*__it);
  ++__it;
}

并且 filter(g) 想要这样做：

auto __it = r.begin();
auto __end = r.end();
while (__it != __end) {
  if (g(*__it)) {
    use(*__it);
  }
  ++__it;
}

而 reverse 想要编写我之前展示的完全不同的循环，我们在其中递减然后读取。如果……我们可以编写我们想要的任何循环呢？我们不会直接编写最佳循环吗？让我们这样做！

签名

我们将复制基于 range 的 for 循环的结构——与其他每种语言也使用的相同结构。也就是说，我们将有一个包含三个部分的循环：

循环元素
range
主体

这些都只是 token 序列。我们将有一个函数，它接受这三个部分并注入适合它们的正确循环：

consteval auto for2(info init, info range, info body) -> void {
  // ...
}

我们将像这样调用它：

consteval {
  for2(
    ^^{ int i },
    ^^{
      v
      | views::take_while(lt5)
      | views::filter(even)
      | views::reverse
    }
    ^^{
      println("* got {}", i);
    });
}

在这里，我们有三个已经是非常不同的东西的 token 序列。第一个是声明，没有分号。第二个是表达式。第三个是语句序列。但是它们都共享相同的语法。 for2 必须做的是根据我们正在迭代的 range 确定要注入什么循环。但是我们没有 range 类型。我们有…… token 序列。我们如何从中获取类型？在我深入了解这些细节之前，让我们先退一步谈谈模型。

模型

最终，我们将做一些与 Tristan 在 Flux 中所做的事情非常相似的事情。在内部迭代 filter_view 意味着在内部迭代底层视图，并且仅有条件地执行主体。在内部迭代 transform_view 意味着在内部迭代底层视图，并在传递元素之前应用额外的操作。在内部迭代 take_while_view 意味着在内部迭代底层视图，并可能提前中断。一次进行一部分，我们想要为 v 发出的循环将如下所示：

auto&& __r0 = v;
auto __it = __r0.begin();
auto __end = __r0.end();
for (; __it != __end; ++it) {
  int i = *__it;
  println("* got {}", i);
}

我们想要为 v | views::take_while(lt5) 发出的循环将是这样的：

auto&& __r0 = v | views::take_while(lt5);
auto&& __r1 = __r0.base();  // 底层
auto&& __pred1 = __r0.pred(); // take-while 谓词 (lt5)
auto __it = __r1.begin();
auto __end = __r1.end();
for (; __it != __end; ++it) {
  auto&& __elem1 = *__it;
  if (not __pred1(__elem1)) {
    break;
  }
  int i = __elem1;
  println("* got {}", i);
}

我们想要为 v | views::take_while(lt5) | views::filter(even) 发出的循环将是这样的：

auto&& __r0 = v | views::take_while(lt5) | views::filter(even);
auto&& __r1 = __r0.base();
auto&& __pred1 = __r0.pred(); // filter 谓词 (even)
auto&& __r2 = __r1.base();  // 底层
auto&& __pred2 = __r1.pred(); // take-while 谓词 (lt5)
auto __it = __r2.begin();
auto __end = __r2.end();
for (; __it != __end; ++it) {
  auto&& __elem2 = *__it;
  if (not __pred2(__elem1)) {
    break;
  }
  auto&& __elem1 = __elem2;
  if (__pred1(__elem1)) {
    int i = __elem1;
    println("* got {}", i);
  }
}

我们必须做的是将 range 视为表达式模板，并慢慢地剥离层。从概念上讲，递归并不是那么复杂——而且与你编写直接模板代码以尝试以合理的方式实现的代码并没有完全不同。以这种形式实际看到它非常新颖——即使这是一个相当简单的手写循环（尽管可能具有更好的标识符，而不必相互别名）。但是，这对于只有 token 序列的 token 序列是什么样的呢，我们甚至根本没有类型？

彻底使用 Token Sequences

有时，当你只有一个 token-sequence-injection-shaped 锤子时，解决方案就是 token-sequence-injection-shaped 钉子。在这种情况下，我们可以通过注入来找到解决方案。具体来说，让我们填写 for2 上的详细信息。它看起来像这样：

consteval auto for2(info init, info range, info body) -> void
{
  inject_tokens(^^{
    {
      auto&& __r0 = \tokens(range);
      using __R0 = std::remove_cvref_t<decltype(__r0)>;
      inject_tokens_impl<__R0, 0>::apply(Direction::forward, \(init), \(body));
    }
  });
}

也就是说——我们首先注入我们的 range（作为 __r0）。现在这是一个普通变量，我们可以获取其类型（作为 __R0）。我们可以从那里实际递归地注入。是的，我们正在注入一个 token 序列，其评估将注入另一个 token 序列。

Token-sequence-ception。我有两个助手可以用来实现这一点。一个是简单的枚举类，用于指示我们正在迭代哪个方向：

enum class Direction { forward, reverse };
consteval auto operator!(Direction d) -> Direction {
  return d == Direction::forward ? Direction::reverse : Direction::forward;
}

另一个是用于实际 token 序列原始注入的包装器。

consteval auto inject_tokens(info tokens) -> void {
  // __report_tokens(tokens);
  queue_injection(tokens);
}

std::meta::queue_injection 实际注入了提供的 token 序列。但是 EDG 有一个很好的小实用程序，叫做 __report_tokens，可以将它们打印到控制台。这对于调试至关重要。好的，首先让我们从我们的基础层开始。如果我们没有以任何方式自定义对 range 的迭代，我们将直接发出我们需要的简单 for 循环：

template <class R, int I>
struct inject_tokens_impl {
  static consteval auto apply(Direction d, info init, info body) -> void {
    if (d == Direction::forward) {
      inject_tokens(^^{
        {
          auto __it = \id("__r"sv, I).begin();
          auto __end = \id("__r"sv, I).end();
          for (; __it !=

使用 Token Sequences 迭代 Ranges

使用 Token Sequences 迭代 Ranges

问题

为什么总是 views::filter？

views::take_while 让情况更糟

翻转它并 views::reverse 它

合理的解决方案：Flux

空间考量

疯狂的解决方案：Token Sequences

签名

模型

彻底使用 Token Sequences

为什么总是 `views::filter`？

`views::take_while` 让情况更糟

翻转它并 `views::reverse` 它