C++ 20 范围库概览

某天写算法题，习惯性地调用 std:sort 然后熟练地按下 Tab 键，如果不出意外，它应该会为我自动补全补全列表第一行的 begin..end；但是毫无征兆的黄色波浪线为这本来理所应当的日常染上了非日常的色彩…… 不是这你也能警告的？

一看提示，竟然是推荐我用一个叫做 ranges::sort 的 API，一看调用签名，好家伙不就是省去了 begin..end 吗？这部分还是 IDE 已经帮我写了；但是一看这是个 C++ 20 的新特性就有点绷不住了，所以去学了。

范围库有什么用？

就像编译器的提示一样，比起它是个什么东西，可能大火还是会更在意它会对我们的编程造成什么改变；假设我们现在要对包含了 1~n 的数组的每个元素进行乘加操作，然后再从中选出一部分感兴趣的元素，最后再打印前五个元素；那么在没有范围库的 C++ 早期版本中就得这么写：

auto my_func(const set<int> &interested, int n, int k, int b, int m = 5) {
    vector<int> a(n), a1;
    iota(a.begin(), a.end(), 1);
  	transform(a.begin(), a.end(), a.begin(), [=](int i) { return i * k + b; });
    copy_if(a.begin(), a.end(), back_inserter(a1), [&](int i)-> bool { return interested.count(i);});
    for (int i = 0; i < m && i < a1.size(); ++i) cout << a1[i] << endl; 
}

很麻烦！写了大量的 begin..end 且不说，甚至还要产生中间变量，实在是有够蠢的；有的人可能认为这是瞎几把用 STL 算法导致的，毕竟如无必要勿增实体；那么我们用最原始的 C++ 循环来进行这个过程：

auto my_func(const set<int> &interested, int n, int k, int b, int m = 5) {
    vector<int> a1;
  	for (int i = 1; i <= n; ++i) {
      	if (interested.count(i * k + b)) {
          	a1.push_back(i * k + b);
            if (m--) cout << i * k + b << endl;
        }
    }
}

看起来确实简洁了不少，但是如果初始数组不是硬编码的话，还是没有避免中间变量的产生；如果有很多这种操作呢？为每一个操作编写一个硬编码的函数吗？

但是现在我们有了范围库，所以它的全新版本是下面这样的：

auto my_func(const set<int> &interested, int n, int k, int b, int m = 5) {
    for (auto i : views::iota(1, n) 
         				| views::transform([=](int i) { return i * k + b; })
        				| views::filter([&](int i)-> bool { return interested.count(i);})
        				| views::take(5))
      	cout << i << endl;
}

看起来用的还是 C++ 算法库里的那些东西，但是给人的感觉完全不一样了！新的代码不仅是看起来更加简洁明了可读易懂，也完全避免了中间变量的产生；而且，都已经这么简洁的代码了，甚至还可以重用！如果我现在需要对一个数组先选出一部分元素，再进行上述操作的话，第一个老代码尚且还可以再增加一个中间变量，而第二个代码就完全不太能用了，得重新写一个新的硬编码函数了…… 但是在这里我们只需要：

auto my_operate = views::transform([=](int i) { return i * k + b; })
        				| views::filter([&](int i)-> bool { return interested.count(i);})
        				| views::take(5);
bool my_pred(int i);
for (auto i : views::iota(1)
    				| views::filter(my_pred)
     				| my_operate)
  	cout << i << endl;

上述代码几乎没有做什么伤筋动骨的修改，就又在不创建中间变量不损失可读性的情况下快速的实现了新版本。这就是范围库给我骄傲的资本！

动机

从上文的例子中我们可以看到，使用传统 C++ 基于迭代器的算法描述这一过程，不仅会产生不必要的中间变量，代码本身也难以阅读，更不具有什么迁移性；而硬编码则更是重量级；因此，为了更加优雅、清晰地描述算法，并尽量避免中间对象的生成，还要支持逻辑的重用，摆脱传统 C++ 的迭代器体系势在必行。

范围库里有什么？

范围库，也就是 <ranges> 头文件。仅就 C++ 20 引入版本的范围库而言，它包含以下的组成部分：

范围的概念：范围表明了对象的可以被迭代的属性；范围以迭代器来指示开头，并以哨兵来指示结尾（哨兵的类型可能和迭代器不同）；STL 中可迭代的容器都是范围。
访问范围的函数：一组用来从符合范围约束的对象中获取迭代器/哨位，或者是范围大小的方法。
视图类：视图是轻量的范围；它的构造/复制/移动/销毁的时间是常数，而和范围大小无关；视图通常不拥有元素所有权，并且可以被视图工厂或者是范围适配器工厂创建；它们被定义为 ranges:: 下以 _view 结尾并实现了 view 的类。
范围相关类型的别名模版：一组用来获得范围中迭代器/哨位/大小的类型的别名模版。
范围适配器闭包工厂：范围适配器是修改范围来生成延迟计算的视图的闭包；除了可以和范围组合形成视图之外，范围适配器之间可以组合；产生这些闭包的函数被定义在 views:: 下，被称为范围适配器工厂；每个函数都对应了一种上述的视图类。
视图工厂函数：生成简单视图（而非闭包）的函数；它们和范围适配器工厂一样是被定义在 views:: 下的函数，并且存在对应的视图类；它们产生的视图通常也是延迟求值的。
范围上进行的受约束算法：一系列和 std:: 下迭代器算法几乎完全相同的算法；不同的是它们受到概念强制约束，接受迭代器-哨位对或者是范围作为处理对象。

整个范围库最核心的部分就是范围的概念，它告别了传统 C++ 迭代器描述的容器-算法的结构，转而在新的更加语义化的范围体系里进行讨论；视图是整个标准库中除了 STL 容器之外的另一大实现了范围的类，为这个结构提供了可以操作的对象；而范围适配器则定义了这个体系的操作，它比起基于迭代器的算法更加语义安全，更加符合实际应用且写起来更方便整洁。

文章开头的例子就是对着三大块的应用：在范围概念的约束下，创建视图并且用范围适配器修改它，再对得到的结果进行遍历。

范围是什么？

和传统 C++ 的迭代器区间类似，范围是使用一组迭代器-哨兵确定的左闭右开的可遍历的区间。在 C++ 20 中，范围是一个概念，也就是说可以说某个类或对象是一个范围，但是并不能直接实例化范围；实际上 STL 中可以迭代的容器都是范围。范围作为概念的语法定义如下所示：

template< class T >
concept range = requires( T& t ) {
  ranges::begin(t);
  ranges::end  (t);
};

也就是说，一个类如果实现了 begin/end 方法或者是对标准库的 begin/end 重载，那么它就是一个范围；这和之前就有的 range-based for-循环是一样的；但是对于概念而言，语法上的要求并不是全部；在语义层面上，范围还要求这两个方法是常数时间的。

范围的定义如此简单，可能会令人产生疑惑？那么之前 STL 容器里定义的这个那个迭代器又算是什么呢？实际上范围确实还要有迭代器类型，但是比起之前基于迭代器的容器需要反复定义各种 cvr 限定的版本，在范围库中，只要定义了 begin/end，其他的版本都可以推导出来；范围库定义了一组获得它们的各种限定版本的类型别名。这些类型别名只基于两个类型：begin 的返回值被看作是迭代器类型，end 的返回值被看作是哨兵类型。

你可能已经注意到了，比起 STL 容器中使用一对迭代器表示区间，范围明确的将区间的两侧分成了不同的类型；且不论迭代器，哨位到底是什么呢？简单地来说，它是一个实现了至少单侧的和迭代器的 operator== 的对象，当这个判等时，说明迭代器已经到达了范围的边界；C++ 20 将这种概念形式化地实现为 std::sentinel_for，所以可以说，对于迭代器 It 而言，它的哨兵 Se 应当满足了 sentinel_for<Se, It>。

举一个最典型的例子，对于 C 风格的字符串，我们可以将字符串末尾的 \0 看作是哨兵，所以可以实现对于 C 风格字符串的迭代器，也就是 C 指针的哨位：

struct c_string_npos {  
    constexpr bool operator==(const char *s) const {  
        return s == nullptr || *s == '\0';  
    }  
    // constexpr friend bool 
    // operator==(const char *s, const c_string_npos &p) { return p == s; }  
};

只要实现了两侧运算符的任意一个，sentinel_for<c_string_npos, char *> 就为 true。

和迭代器定义的区间一样，范围也根据其迭代器类型的不同具有不同的类型。但是在这之外，还有一些场合除了对于迭代器的显式的语法要求，还有着更多的语义要求，就拓宽了范围的类型。因为这些额外的类型往往无法在语法层面上给出行之有效的定义，就需要程序员在符合语义的前提下，手动启用/关闭这些特性。

下面介绍一些在迭代器类型之外的不同类型的范围。

`std::ranges::sized_range`

除了所有范围都应当实现的常数时间的 begin/end 方法之外，还要实现常数时间的 size 方法，并且确保通过 begin/end 获得的迭代器和哨位之间可以作差。

如果类在语法层面上实现了 size 方法，但是该方法并不符合语义上的要求的场合（最经典的：比如 size 方法不是常数时间），程序员应当特化 disable_sized_range 来避免该类被识别为 sized_range；如果还要特别说明 begin/end 获得的迭代器-哨位之间不可作差，还要额外特化 disable_sized_sentinel_for。

`std::ranges::borrowed_range`

这个概念要求从范围实例的 begin/end 方法获取的迭代器的生存周期可以比范围实例本身更长；因此即使范围实例被销毁，使用它产生的迭代器也不应该遇到悬垂问题。在大多数时候，这种情况表明范围本身并不具有数据的所有权，因此范围本身的生命周期和迭代器的生命周期无关；但是这并不代表着使用来自 borrowed_range 的迭代器就可以不考虑这个问题，来自它的迭代器的安全仍然是程序员保证的。

在标准库中的 borrowed_range 并不多；在引入范围库之前，只有 string_view 和 span 满足它的约束 —— 这也是上文中说到的“大多数时候”；而考虑到范围库，subrange、一部分工厂函数生成的简单视图以及部分范围适配器产生的视图也被看作是 borrowed_range。

但是实际上，代码中的 borrowed_range 可能一点也不少。我们观察 borrowed_range 概念的语法实现：

template<class R>
concept borrowed_range =
    ranges::range<R> &&
    (std::is_lvalue_reference_v<R> ||
     ranges::enable_borrowed_range<std::remove_cvref_t<R>>);

可以看到有两层约束：首先 borrowed_range 显然必须得先是 range；然后第二个条件就很有意思，它要求的是当 R 是一个左值引用或者用户手动开启了 enable_borrowed_range；后者且不论，前者可能会一时让人有些诧异，但是仔细想想也确实是这么一回事 —— 左值引用并不具有实际对象的所有权，因此还是“大多数时候”！

为了在编译阶段避免将非借用范围传递给一个需要使用到 borrowed_range 性质的函数，标准库还提供了一个模版别名 borrowed_iterator_t；它实际上是一个条件类型：它接受一个范围作为模版形参，当模版实参是一个 borrowed_range 时这个类型被定义为该范围的迭代器，否则则是占位类型 dangling，对任意尝试解引用它的代码报编译错误。

视图是什么？

视图是范围的细化概念，它要求实现它的类型是如果支持复制/移动/创建/销毁操作，那么这些操作应当可以常数时间内完成；一般来说，视图不占有其包含元素的所有权；由于操作的时间复杂度和数据的所有权显然不是语法层面的特征，因此需要用户在满足语义时手动开启；它的声明如下：

1 2	template<class T> concept view = ranges::range<T> && std::movable<T> && ranges::enable_view<T>;

观察它的声明，可以再次确认视图是范围，并且在语法层面上支持移动操作；除此之外的语义部分，编译器无从感知，所以需要用户手动开启 enable_view 来保证语义的正确。

为方便实现，范围库还提供了空基类 view_base 和辅助声明的接口 view_interface；任何继承自它们的类都相当于手动开启了 enable_view。

`std::ranges::view_interface`

和空基类 view_base 不同，view_interface 不仅为派生类开启了 enable_view，还可以辅助派生类定义作为范围最基本的 begin/end 接口，并根据迭代器的类型，为派生类增加标准库风格的其他范围接口，并且这些接口无需程序员自行实现；因此它常常以 CRTP 的方式使用：

class my_view : public std::ranges::view_interface<my_view> {
public:
    auto begin() const { /*...*/ }
    auto end() const { /*...*/ }
};

根据迭代器类型的不同，view_interface 会提供不同的接口；具体的规则如下：

迭代器类别	对应范围	新提供的方法
	`range`	`begin`/`end`
`input_iterator`/`output_iterator`	`input_range`/`output_range`
`forward_iterator`	`forward_range`	`empty`/`bool`/`size`/`front`
`bidirectional_iterator`	`bidirectional_range`	`back`
`random_access_iterator`	`random_access_range`	`operator[]`
`contiguous_iterator`	`contiguous_range`	`data`

也就是说，通过 view_interface，你只需要定义最基础的 begin/end，其他的这一系列方法都会由编译器自动生成，并且符合 C++ 标准库要求，无需手动实现；比如下面实现了一个对于 C 风格整数数组的视图类：

struct my_view : public std::ranges::view_interface<my_view> {
    int *p, n;
    my_view(int *p, int n) : p(p), n(n) {}
    [[nodiscard]] constexpr int *begin() const { return p; }
    [[nodiscard]] constexpr int *end() const { return p + n; }
};

由于 C 指针是一个连续迭代器，指向一块连续的内存空间，因此上述表格中的所有方法都已经自动实现了。

`std::ranges::subrange`

最基本的范围只包含 range/end 方法，相应的最简单的视图也只包含一组迭代器-哨位。和 view_interface 一类似，它也会根据迭代器的类型来提供不同的访问方法；但是这在 size 方法上却有所不同，可以参考声明：

template<
    std::input_or_output_iterator I,
    std::sentinel_for<I> S = I,
    ranges::subrange_kind K = std::sized_sentinel_for<S, I> ? 
        ranges::subrange_kind::sized : ranges::subrange_kind::unsized
>
    requires (K == ranges::subrange_kind::sized || !std::sized_sentinel_for<S, I>)
class subrange : public ranges::view_interface<subrange<I, S, K>>;

subrange 接受了三个模版参数，分别是迭代器类型、模版类型和一个枚举；前两个没什么好说的，但是这个枚举则决定了子范围是否实现了 size：如果不能通过迭代器-哨位作差以常数时间地求出 size，但是却通过这个枚举强制要求支持 size，那么除了迭代器和哨兵之外，还会额外存储尺寸。

subrange 总是实现了 ranges::viewable_range；并且当支持 size 时，还实现了 ranges::sized_range，这也没什么问题，因为获得 size 确实只需要读出存储的尺寸就可以了，这当然是常数时间的；并且，总是可以将 subrange 看作一个 pair 来进行方便的解绑，获得其存储的迭代器和哨卫。

范围适配器是什么？

范围适配器代表着对于一个 range 内元素的操作，它往往也支持延迟求值，并且通常可以和其他的范围适配器进行组合；这种可以独立于具体的范围进行组合的特性使得它可以方便的重用逻辑，而延迟求值的特性则使得它不会产生中间变量，从而彻底解决了传统 STL 基于迭代器算法的问题 —— 也就是本文开头中的炫酷写法；甚至，之前因为众所周知的原因而没能实现的字符串 split 操作也因此有了加入标准库的曙光。

范围适配器闭包指的是接受 viewable_range 或者另一个范围适配器闭包的一元可调用物；接受前者时返回一个 view，接受后者时返回一个新的组合后的闭包；并且还重载了运算符 | 作为调用的语法糖，使得组合范围适配器的语法相当简洁。形式化地说，范围适配器闭包满足如下性质：

若有范围适配器闭包对象 C 且有 R 实现了 range 概念，则表达式 C(R) 和 R | C 等价
若有范围适配器闭包对象 C 和 D，并且有 E = C | D，那么 E 存储 C 和 D 的副本，并且对于任何实现了 range 概念的 R，满足结合律：R | E 和 R | C | D 和 D(C(R)) 等价

标准库中的每个范围适配器都对应了一个位于 ranges:: 下以 _view 结尾的视图类；将适配器应用到范围就可以得到对应适配器的视图，这些视图具有适配器对应的视图类；此外，这些类都实现了 view 和 viewable_range 以兼容下一次转换。

语法糖的实现

如果你翻阅 C++ 文档，你可能会发现在范围库中只能找到工厂函数以及对应的视图类的定义，但是完全找不到范围适配器闭包这个东西；甚至是广受好评的语法糖 |，相关的类也没有一个实现了这个的重载；那么这个语法糖究竟是怎么实现的呢？

在 C++ 20 中，范围适配器闭包这一如此重要的概念只是被提出，而并没有被形式化的纳入标准中；也就是说和各种内部类型/内部对象一样，范围适配器闭包的实现因编译器而异；在简单地阅读了 Apple Clang、GCC 和 MSVC 的实现之后，这里将比较好懂的 Apple Clang 版本放在下面：

template <class _Tp>  
struct __range_adaptor_closure {  

    template <ranges::viewable_range _View, _RangeAdaptorClosure _Closure>  
        requires same_as<_Tp, remove_cvref_t<_Closure>> &&  
                 invocable<_Closure, _View>  
    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI  
    friend constexpr decltype(auto) operator|(_View&& __view, _Closure&& __closure)  
        noexcept(is_nothrow_invocable_v<_Closure, _View>)  
    { return std::invoke(std::forward<_Closure>(__closure), std::forward<_View>(__view)); }  
  
    template <_RangeAdaptorClosure _Closure, _RangeAdaptorClosure _OtherClosure> 
        requires same_as<_Tp, remove_cvref_t<_Closure>> &&  
                 constructible_from<decay_t<_Closure>, _Closure> &&  
                 constructible_from<decay_t<_OtherClosure>, _OtherClosure>  
    [[nodiscard]] _LIBCPP_HIDE_FROM_ABI  
    friend constexpr auto operator|(_Closure&& __c1, _OtherClosure&& __c2)  
        noexcept(is_nothrow_constructible_v<decay_t<_Closure>, _Closure> &&  
                 is_nothrow_constructible_v<decay_t<_OtherClosure>, _OtherClosure>)  
    { return __range_adaptor_closure_t(std::__compose(std::forward<_OtherClosure>(__c2), std::forward<_Closure>(__c1))); } 
};

可以清晰地看到，在上文形式化定义中的两种不同情况下的 operator | 的重载：在应用到范围上的时候，直接调用闭包并将范围作为参数传入；在组合两个闭包的时候，发生的并不是调用，而是将两个函数进行组合。组合的类型在 MSVC/GCC 中声明了新的内部类型，看起来就太麻烦了。

不过在 C++ 23 中，这一概念已经被纳入标准库：std::ranges::range_adaptor_closure

有哪些工厂函数？

这一小节的标题相比没有必要叫“工厂函数是什么？”吧？毕竟这算是一个很经典的 OOP 概念：工厂函数是用来产生对象的函数；C++ 范围库中包含了两种工厂函数，它们都位于 ranges::views:: 下，分别产生简单的视图对象和范围适配器闭包。

简单的视图对象指的是通过参数简单描述的，并且支持延迟求值的视图，最经典的就是自增视图 iota：只需要一个开始元素就可以声明一个无限长的自增序列 —— 当然自增并没有实际进行无限次，只有当需要访问视图的时候才会逐个自增计算每个元素。

范围适配器以及它的闭包的定义已经在上一小节讲过了。而有些常用的 C++ 序列算法在这里被实现为了范围适配器，比如 filter 啊 transform 这些；在别的高级语言里这些都理所应当的是数组的方法，但是在传统 C++ 中却为了迭代器将它们和容器分开 —— 现在它们又理所应当地结合在一起了！

和范围适配器一样，每个简单视图工厂函数都对应了一个位于 ranges:: 下以 _view 结尾的视图类，并且该类就是对应工厂函数的返回类型；当然，这些视图类都实现了 view 和 viewable_range （它们本来就是视图！）以兼容范围适配器的转换。

那范围算法呢？

范围算法又称为是受到范围概念约束的算法；本质上它是 C++ 算法库中的迭代器算法对于范围的实现，将范围这一整套概念融于其中来约束算法的行为，从而对它们的调用更容易得到语义上的正确。当然，从语法的角度来说也省去了 begin..end 的麻烦，毕竟不是所有人都在用 CLion（）

部分算法也有着不同的表现，就比如文章开头提到的 ranges::sort 函数：它的迭代器版本 std::sort 接受了为了支持并行计算的执行策略，而范围库里的版本则另外接受 Proj 参数，用于从元素中获得需要用于比较的部分（默认值为 std::identity，就是返回自身的一元函数），因此可以认为范围库中的版本实际上更加贴近实际使用，毕竟为了按照 ID 数字大小排序就写一个排序器还是有些繁琐了。

后记

为什么范围适配器的语法糖这么美丽？这就是函数式编程给你带来的自信吗！