C++20: Ranges
6/27/2021
Author's Profile Avatar
程序中常需要一次性传递多个同质对象。我们一般通过传递两个迭代器的方式来传递多个对象,这两个迭代器按约定一般称为首迭代器和尾迭代器。首迭代器指向被引用的多个对象中的第一个对象,尾迭代器指向被引用的多个对象中的最后一个对象的下一个虚拟位置。下图形象地说明了首迭代器和尾迭代器的关系。(图片引用自 cppreference)
notion image
迭代器有效地分离了对象的存储和对象的访问。提供迭代器的容器(数组、std::vector、用户自定义数据结构等)不需要关心上层算法的具体实现,使用迭代器的算法(std::sort 等)也不需要关心底层对象的存储和组织方式。因此,迭代器机制被广泛地应用在 generic 编程中。
迭代器机制有一个明显的不足,即需要使用两个迭代器来表示一组对象。其他支持迭代器抽象的编程语言通常只需要一个迭代器便可以完整地迭代出所有引用的对象。C++迭代器的这个不足导致了两个问题:一是使得代码更加复杂,代码复杂的直接后果便是出错率增加;二是许多通用的集合操作无法以一种相对优雅的方式依赖于 C++ 迭代器实现。例如,给定一组字符串,我们希望从中筛选出那些以 c++ 开头的字符串,并将这些筛选出的字符串转换为大写表示。我们希望传入的迭代器是通用的,不受特定的容器所限制。在 Rust 等语言中,实现会非常简洁:
fn foo<I: Iterator<Item=String>>(iter: I) -> impl Iterator<Item=String> {
    iter.filter(|s| s.starts_with("c++"))
    	.map(|s| s.to_uppercase())
}
在 C++ 中想要达到上面的效果,则需要不少 dirty work。STL 中没有提供与 filter 相关的通用算法,我们先看看 STL 中提供的与 map 相关的通用算法的设计,即 std::transform,其模板函数声明如下:
template <typename InputIt, typename OutputIt, typename UnaryOp>
OutputIt transform(InputIt first, InputIt last, OutputIt output, UnaryOp transformer);
可以看到,std::transform 的设计非常复杂。它通过前两个迭代器参数输入需要被 transform 的对象,通过第三个输出迭代器参数将 transform 后的对象输出,最后第四个参数为 transform 函数。我们可以模仿这一风格,写出 filter 模板函数声明:
template <typename InputIt, typename OutputIt, typename Predicate>
OutputIt filter(InputIt first, InputIt last, OutputIt output, Predicate predicate);
利用 filtertransform 函数可以完成前面提到的功能:
template <typename InputIt, typename OutputIt, typename Predicate, typename UnaryOp>
OutputIt foo(InputIt first, InputIt last, OutputIt output, Predicate predicate, UnaryOp transformer) {
    using T = typename std::iterator_traits<InputIt>::value_type;
    using std::transform;
    std::vector<T> temp;
    filter(first, last, std::back_inserter(temp), std::move(predicate));
    return transform(temp.begin(), temp.end(), output, std::move(transformer));
}
与前面的 Rust 代码相比,孰优孰劣一目了然。
为解决迭代器机制的不足,C++20 引入了 range 库。Range 库引入了一个核心的 concept,用于抽象一组对象(a range of objects)。在这一核心 concept 之上,range 库定义了一些非常实用的集合算法(例如 filter 和 map 等),使得在 C++ 中也能写出优雅度媲美 Rust 的集合算法。

Range

Range 库的核心 concept 即为 std::ranges::range 这一 concept,其定义如下:
template <typename R>
concept range = requires(R &r) {
    std::ranges::begin(r);
    std::ranges::end(r);
};
可以看到,一个类型 R 是一个 range,当且仅当这个类型的实例对象能够被传入 std::ranges::begin 函数以及 std::ranges::end 函数中。std::ranges::begin 模板函数返回一个 range 的首迭代器、std::ranges::end 模板函数返回一个 range 的尾迭代器。对于带有 beginend 成员函数的类型,std::ranges::begin 会通过调用 begin 成员函数获取实例对象的首迭代器、std::ranges::end 会通过调用 end 成员函数获取实例对象的尾迭代器。因此,STL 中定义的各种容器类型都满足 std::ranges::range 的要求;另外,用户自己编写的容器,只要提供了 begin 成员函数和 end 成员函数,那么也满足 std::ranges::range 的要求。
我们熟知 C++ 一共有六类迭代器:input iterator、output iterator、forward iterator、bidirectional iterator、random access iterator 以及 contiguous iterator。类似地,根据一个 range 的首迭代器的种类进行划分,也可以将 range 分为六类:input range、output range、forward range、bidirectional range、random access range 以及 contiguous range。Range 库中对每一类 range 都有其对应的 concept,具体可以参加 cppreference 上的相关文档

Range Factories and Range Adaptors

除所有的标准容器外,range 库还提供了一些基础的 range,包括空 range(即不包含任何元素的 range)、只包含一个给定元素的 range、从一个初始值开始不断产生递增的值的 range 以及从一个 input stream 中不断读取特定类型的值的 range。这些 range 统称为 range factories。它们的具体用法可以参见 cppreference 上的相关文档
Range 库最引人注目的特性应该当属 range adaptors。回到本文开始的例子上面来,现在我们有一个包含了若干字符串的 range,我们希望从中得到一个新的 range,这个 range 中包含的字符串是输入的 range 中的那些以 c++ 开头的字符串的大写形式。使用 range 库,我们可以这样编写代码:
template <std::ranges::range InputRange>
auto foo(InputRange r) {
    using std::ranges::views::filter;
    using std::ranges::views::transform;
    auto starts_with_cpp = [](const std::string &s) noexcept { return s.starts_with("c++"); }
    auto transformer = [](const std::string &s) noexcept { return to_uppercase(s); }
    return r | filter(starts_with_cpp) | transform(transformer);
}
注意 foo 函数的最后一行。Range 库对 operator | 进行了重载,使得集合运算可以以一种类似于 shell 管道的方式自由地组合起来,非常直观易懂。这里的 filtertransform 是 ranges 库中提供的两个 range adaptor object,是两个重载了 operator () 的全局 inline constexpr 对象。Ranges 库中还提供了许多其他类似于 filtertransform 的 range adaptor objects,具体可参见 cppreference 上的相关文档
filtertransform 以及其他的 range adaptor objects 不仅可以按照上述例子中所示调用,其返回值作为 operator | 的操作数;也可以按照如下方式调用:
template <std::ranges::range InputRange>
auto foo(InputRange r) {
    using std::ranges::view::filter;
    auto starts_with_cpp = [](const std::string &s) noexcept { return s.starts_with("c++"); }
    return filter(r, starts_with_cpp);
}
也就是此时 filter 接收了两个参数,其中第一个参数是输入的 range,第二个参数则与原来的参数相同、为执行筛选所需的 predicate。此时,filter 将直接返回一个 range 表示 filter 的结果。transform 也类似,事实上,range 库所提供的所有 range adaptor objects 都遵循这样的约定:当向其传入一个 range 以及额外参数时,range adaptor object 将返回一个 range 作为结果;当仅向其传入额外参数而不传入输入的 range 时,range adaptor object 将返回一个 range adaptor closure object,这个 object 重载了 operator |operator ()。可以使用 operator | 将多个 range adaptor closure object 给连接起来,达到与 shell 管道类似的效果;也可以直接使用 operator () 并向其传入输入的 range,此时 range adaptor closure object 将会从输入的 range 产生输出 range 并返回。总结为代码即为:
auto r = get_input_range();  // r is the input range
auto fn = get_filter_function();
// The following 3 forms are semantically equivalent:
// Form #1
auto fr = std::filter(r, fn);
// Form #2
auto fr = std::filter(fn)(r);
// Form #3
auto fr = r | std::filter(fn);

Sentinel Iterators

前文已经介绍,只要一个类型能够通过 std::ranges::beginstd::ranges::end 函数得到其实例对象的首尾迭代器,那么这个类型就是一个 range。一般来说,引用一组对象的首尾迭代器的类型是一致的;但 range 库放松了这个限制。一个 range 的首尾迭代器可以为不同的类型。因此,一个 range 的尾迭代器在 range 库中被称为 sentinel(哨兵)。
允许一个 range 的首尾迭代器属于不同的类型可以让 range 具有更强的灵活性。首先,这将允许我们以一种更优雅的方式写出那种“生成值”的 range(即 generator)。例如,range 库提供了一个名为 iota 的 range factory,当仅接收一个参数时,iota 返回一个 range,该 range 将“生成”从给定的参数开始不断递增产生的所有值:
for (int x : std::ranges::views::iota(5)) {
    // This is infinite loop.
    // The program prints all possible 32-bit signed integers starting from 5.
    std::cout << x << std::endl;
}
此时,iota 返回的 range 的尾迭代器便是一个特殊的 sentinel iterator。这个 iterator 的特点是,它与任何其他的 iterator 通过 operator == 进行比较时都将返回 false。因此,迭代器将源源不断地产生迭代出的值。当然,我们也能够将 iota 返回的 range 的首尾迭代器定义为同一个类型,但这样我们势必必须用一个特殊的值来标记这种情况下的尾迭代器,这会影响代码的可读性。
其次,在某些场景下,range 的首尾迭代器属于不同类型可以避免一些不必要的计算。例如,假设我们需要定义一个 range,其表示一个 C-style string 中的所有字符。如果这个 range 的首尾迭代器是同一类型,那么在计算出 range 前我们势必需要首先使用 strlen 或类似的函数计算出指向字符串末尾 0 字节的尾迭代器,然后才能构造出这个 range;但如果 range 允许其首尾迭代器是不同类型,那么我们将其首迭代器定义为一个 const char *,其尾迭代器定义为一个特殊的 sentinel iterator,这个 sentinel iterator 可以与 const char * 进行比较,并且当且仅当 const char * 指向一个值为 0 字节时才返回 true。因此,我们不需要任何的额外计算便可以构造出这个 range。

Ranges and Views

在 range 的 concept 之上,range 库额外提供了另一个名为 view 的 concept。可以将 view 视为一种轻量级的 range,与 range 相比,它“不拥有”它所包含的元素。一个不是 view 的 range 可以“拥有”其所包含的所有元素,例如 STL 中的所有容器都“拥有”放在容器中的所有元素。可以将 range 和 view 的区别看作 std::stringstd::string_view 的区别。
形式化地,一个类型 R 是 view,当且仅当它满足以下条件:
  • R 是一个 range;
  • R 可以被移动构造、可以被移动赋值、可以被 swap;
  • 下面的两个条件满足一项:
    • R 直接或间接继承自 std::ranges::view_base
    • R 直接继承自 std::ranges::view_interface<U> 且 R 没有其他任何基类,其中 U 为任意一个类型,但通常情况下 R 使用 CRTP 直接继承自 std::ranges::view_interface<R>
std::ranges::view_base 是一个空类,它唯一的作用是起到标记 view 的作用,将 view 和 range 区分开来。如果没有任何的标记来区分 view 和 range,那么按照定义,STL 中的所有容器也将满足 view 的条件,这与 view 的语义设计不符。
std::ranges::view_interface<R> 则不同。它会根据类型参数 R(一般即继承自 view_interface 的 view 子类)的种类(即前文提到的六种 range),提供不同的实用成员函数。例如,当 R 的种类是 forward range 时,view_interface<R> 会提供 empty 成员函数,这个成员函数检测 view 中是否不包含任何的元素;当 R 是一个 random access range 时,view_interface<R> 会提供 operator[] 来按照索引访问 range 中包含的任意一个元素。有关这些函数的完整列表请参见 cppreference 上的相关文档
在 range 库中,所有提供的 range 均包含在 std::ranges 命名空间下;所有提供的 view 均包含在 std::ranges::views 命名空间下。