C++20——ranges

2025-03-30

ranges简介

ranges 是一个比较抽象的概念。广义上说，任何可以按一定规则遍历的变量集合都是范围。
C++中的容器、容器的一部分可以被视为范围；被“容器工厂”函数产出的一些可迭代对象也可以被视为范围；数组、“指针+长度”的组合也可以视为范围。
更进一步地，上述范围按一定规则筛选出的子范围也可以被视为范围，比如任取一个range，取其最初的5个元素也可以组成一个range，将该range“隔三取一”的元素集合也可以组成一个range。
将其中元素按一定规则组合也可以“转化”为新的range：如创建一个滑动视窗，每次访问ranges中连续的三个元素。

为什么长篇大论介绍抽象的C++哲学？ranges 作为C++中的“高难”板块，对语法的掌握只决定应用的下限，而对其深入理解决定了应用的上限。

STL：C++标准库的中流砥柱

任何一种语言中对于 ranges 的处理都是亟待解决的问题之一。
面对之，C++98中即引入了STL(Standard Template Library，标准模板库)，其核心元素为 Containers、 Algorithms 和 Iterators ：

Containers：容器，通过特定方式封装底层存储空间，并提供对之操作接口的类模板。如std::vector提供动态连续存储空间，std::array实现了对数组的封装，std::list表征双向链表，std::map是基于红黑树的映射集、std::unordered_set基于哈希表的集合，等等。标准库中除了直接处理底层存储空间的容器，还有一类被称为 Container Adaptor（容器适配器）的类模板，其“帮助”我们进一步封装了既有的这些初始容器（以提供较为便捷的数据结构操作），如std::priority_queue（优先权队列）封装了std::vector，std::queue（单向队列）封装了std::deque~~虽然我也不知道为什么不封装std::forward_list~~。
Algorithms：算法，本质上是函数模板，通过分别传入begin和end的“迭代器”来确定操作范围。常见的包括std::sort、std::transform、std::reverse等等。
Iterators：迭代器，多为 nested class （嵌套类，又名“类中类”），专属于某个容器实例化后的模板类。

这三者其实都可以看作是在C样式的容器、算法组件上的进阶：

C中由于并没有类与对象的概念，因此“标准”的 Containers 只有数组Ty[]（包括指针+长度的组合，本质上表征的都是连续的存储空间），链表等特殊数据结构则需用户自行实现。C++的标准库则极大丰富了 Containers 家族；

C++设计哲学：功能相同或相近的前提下，组件应用优先级：标准库 > 三方库 > 手搓(hand-crafting)。其理由主要有二：标准库内容多经过极大量调试，相较三方库和手写代码而言bug率极低，事实上多数时候标准库组件调用出问题时都不应先行质疑标准库；同时标准库的可迁移性最强，在不同代码间的复用性佳。

C中“指针”即为迭代器，C++中面对指针可能存在的诸多问题~~包括但不限于野指针、空指针、解引用方式错误、边界检查、const约束弱、指针比较语义约束弱、只能访问连续存储空间等~~提出了 Iterators 家族，其在不改变指针使用习惯（通过重载operator++()/operator++(int)、operator*()等）的基础上将之封装，以实现对不同容器的相同语义适配（比如链表的operator++()重载为需要前进到下一个指针）和越界检查等。
C的<stdlib.h>提供了少量的算法函数（不知有多少学过C的人听闻过qsort和bsearch~~C语言里快乐快排/二分糊作业~~？广义上的算法函数可能多些，如strcmp、memcpy、strcat等等都算）。而C++依靠模板函数的优势，提供了极大量较为安全的、适配大量容器的算法函数，多分布于<algorithm>和<numeric>中。

现代C++提倡尽量避免“手搓”算法函数，若存在既有的库函数则应优先使用之。实际上<algorithm>（尤其是C++20后得到ranges加持的版本）配合~~到处乱飞的~~lambda可以应对绝大多数程序设计中遇到的轻量算法需求，如排序、查找、全排列、计数、折叠(fold)等等。

ranges：扶摇直上

上述介绍了传统C++中STL的三大组件。在现代C++的诸版本中，它们也都有所迭代提升，如C++11中大量新容器、新算法的加入（包括unordered_set等哈希容器、<algorithm>中any_of和is_heap等等）使之被称为“STL的第二春”。

在C++20中，ranges 的加入则无疑是为C++ STL家族增添了极为得力的干将。ranges 更像是一个抽象的概念，笔者认为其可由以下几部分组成：

Ranges Algorithm，“范围函数”；
Views/Ranges factory/adaptors，“范围/视图工厂/适配器”。

Algorithms：可读性与可靠性的双提升

概论

Ranges Algorithms 在C++20中被引入<algorithm>库中，其主要提供的是既有STL Algorithm的ranges版本（即实现的算法与既有函数完全相同），亦有少量新函数。
其标志是置于命名空间std::ranges而非std中。

用法上的异同，从以下代码中即能略窥一二：

std::vector<int> vc{2,3,5,7,11,0};

std::sort(vc.begin(),vc.end()); 
std::ranges::sort(vc); //simple, isn't it?
std::ranges::sort(vc.begin(),vc.end()); //Also works

std::ranges::sort(vc,[](int x,int y){return x>y;});

struct
{
    constexpr bool operator==(int v) const {return v == 7;}
}Se;

std::ranges::sort(vc.begin(),Se); //Novel usage #1

迭代器-哨兵对：锚定范围更为自由

以std::ranges::sort为例，其operator()提供的两个重载如下：

1
2

std::ranges::borrowed_iterator_t<_Rng> operator()<_Rng, _Pr, _Pj>(_Rng &&_Range, _Pr _Pred = {}, _Pj _Proj = {});
_It operator()<_It, _Se, _Pr, _Pj>(_It _First, _Se _Last, _Pr _Pred = {}, _Pj _Proj = {});

从函数签名看，最直观的一点不同在于ranges algorithm作用的对象不再是迭代器对(iterator pair，形如vc.begin()-vc.end())，而是 iterator-sentinel pair （迭代器-哨兵对）。可以认为其是既有的迭代器对的升级版：只要迭代器和哨兵类型定义了返回bool的operator!=，那么它们就可以组成一个range。

同时其也提供了直接作用于既定“范围”(ranges)上的重载，支持单独将自身作为ranges直接传递的变量，主要就是各种带有.begin()和.end()方法的容器和内置数组。

上述特性使得对"ranges"的创建变得极为灵活，如确定范围终点时可以自定义一个类型/采用其它类型，可以极大地提高代码的可读性和维护性，同时避免了不必要的时间/空间开销。
上述代码中，新建的“哨兵”Se就是一个极为轻量化的对象（其不占任何空间，只负责检验是否遇到7并截止之），为编译器优化开拓了极大空间的同时，让程序变得极为简洁（如此功能在既有STL中实现极为繁琐）。

同时，由于C++ Concepts并不会进行语义上的约束，故亦存在非常有趣且实用的用法，比如所谓的std::unreachable_sentinel就是一个“不可达”的哨兵，可以用于开拓无限range供使用：

struct unreachable_sentinel_t
{
    template<class Ty>
    constexpr bool operator==(Ty&&) const noexcept
    {
        return false;
    }
};

static constexpr inline unreachable_sentinel_t unreachable_sentinel = {};

极精妙之剑法：“映射”-Projection

回顾ranges algorithm的形参，_Pr是我们熟悉的“比较函数”(predicate)，_Pj则是新元素-“映射”(projection)。
_Pj是一个非常精巧有趣的设计，从调用效果而言其会令所有元素均经过_Proj“处理”一次（即_Proj应为一个接受单个元素类型的可调用对象）。由于其调用时用到了std::invoke，因而其能接受多种方式完成这个语义转换，其中不乏非常简洁清晰的版本：

struct T
{
    int a;
    int b;
    std::string c;
};

std::vector<T> vc{};
//...
std::ranges::sort(vc,{},[](auto&& x){return x.a+x.c.length();})
//This might seems differ little from traditional predicate lambdas in trivial usages, yet consider this...
std::ranges::sort(vc,[](auto&& x){return x.a;}) //Conventional approach
std::ranges::sort(vc,{},&T::a); //Surprise!

函数对象而非函数：“遁形”于ADL

另外，细心者不难发现ranges algorithm并不是以函数形式存在，而是以重载了operator()的函数对象形式表现。
如此是为了避免ADL(Argument-Dependent Lookup)，规避了与既有命名空间std、或其它命名空间（含自定义）的同名算法等产生冲突。

ADL(Argument-Dependent Lookup)也是和SFINAE、Rule-of-three/five-zero等并列的C++著名“几大缩写”之一。
简单来说，设命名空间N中存在类型N::T和函数N::f(T)，则当试图调用这个函数（隐式或显式皆然）时，这个函数会被自动引入当前的命名空间（即使最开始并没有引入之）。
最为简单常见的实例无疑是<iostream>的爱恨情仇：

#include<iostream>
int main()
{
    std::cout << "Hello C++23!";
}

这个程序是可以通过编译的，但需要注意的是，此处我们只使用了std::cout，并没有声明过using std::operator<<(std::ostream&,const char*);；相当于这个函数是被自动引入当前命名空间的。
如此做确实会带来很多便利之处，亦避开了潜在的链接等问题；但作为一把双刃剑，其带来的命名空间冲突问题也极为严重，考虑以下这个非常简单的~~炸编译器~~实例：

namespace N
{
    struct T{};
    void f(T& arg){}
}

void f(T& arg){}
int main()
{
    N::T var{};
    f(var); //Not compile: ambiguious -  N::f(T&) or ::f(T&)?
}

对于不求甚解于C++者来说，很难发现ADL的“鬼斧神工”。
而ADL并不适用于类的成员函数，因此通过operator()重载并创建一个类的实例作为函数名即可规避此问题。

注意，只有类的成员函数才具备不可见于ADL的性质；std::operator<<(std::ostream&,int)一类的输入/输出运算符虽然在类内声明，但friend关键字表示该运算符的命名空间依然在类外。事实上friend和static函数为数不多的区别之一就在访问方式到底是不是要加类名+域解析符C::。详见C++类与继承基础全解

namespace N
{
    struct T{};
    class _F
    {
    public:
        void operator()(T&) const {}
    };

    static constexpr inline _F f = {};
}

void f(T& arg){}
int main()
{
    N::T var{};
    f(var); //OK: invokes ::f(T&),does not use ADL to somehow seek N::f::operator()(T&)
}

Concepts：行于

随着另一“金刚” Concepts的引入，所有的Ranges Algorithm都有concepts约束之，极大地保证了调用语义的正确性。
在经典的C++中，这一约束以 Legacy Iterator Specification 的形式存在，如各位可能都看到过这样的函数签名：

1 2	void sort<_RanIt, _Pr>(const _RanIt _First, const _RanIt _Last, _Pr _Pred); _OutIt copy<_InIt, _OutIt>(_InIt _First, _InIt _Last, _OutIt _Dest);

这里的_RanIt就是 random access iterator - 随机迭代器的缩写。其表示，这个函数会“希望”你传入一个能够随机访问的迭代器，因而实际上下述的调用是UB（并不能通过编译）：

1 2	std::list<int> ls{6,5,5,3,7}; std::sort(ls.begin(),ls.end());

再比如，迭代器对对于传入的迭代器类型会有一定要求，如：

支持operator*()解引用；
迭代器间是可以比较异同的（至少支持operator!=和operator==其一）；
对于“输出迭代器”(output iterator，即上述std::copy的一个模板参数)，应当支持operator=(Ty&&)，其中Ty是该输入迭代器解引用后返回的类型；
...

但在没有concepts的时代，虽然有SFINAE寥寥草草地进行着一些语法约束，但其观感极差且难以表达很多复合约束，故并没有被应用到STL Algorithm中。这也直接导致了STL Algorithm中可能存在许多莫名其妙的调用：

1	std::sort(1,2);

而这段代码虽然不能通过编译，但大部分IDE并不能直接检测出其错误，而编译时报错信息的解析非常繁琐（以GCC 13.1 - C++23为例）：

In file included from /usr/local/include/c++/14.2.0/algorithm:61,
                 from main.cpp:1:

(省略200余行...)

/usr/local/include/c++/14.2.0/bits/stl_algo.h:4771:18:   required from 'constexpr void std::sort(_RAIter, _RAIter) [with _RAIter = int]'
 4771 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:5:14:   required from here
    5 |     std::sort(1,2);
      |     ~~~~~~~~~^~~~~
/usr/local/include/c++/14.2.0/bits/stl_algobase.h:185:12: error: invalid type argument of unary '*' (have 'int')
  185 |       swap(*__a, *__b);
      |            ^~~~
/usr/local/include/c++/14.2.0/bits/stl_algobase.h:185:18: error: invalid type argument of unary '*' (have 'int')
  185 |       swap(*__a, *__b);
      |                  ^~~~

现在知道为什么C++20的Concepts那么受欢迎了吧(bushi)有关C++20 Concepts的更多可移步：C++20——Concepts

若试图将函数改为std::ranges::sort，则一方面IDE会直接报错（没有匹配的operator()重载）；另一方面，编译的报错信息也相对简短直观许多：

main.cpp: In function 'int main()':
main.cpp:5:22: error: no match for call to '(const std::ranges::__sort_fn) (int, int)'
    5 |     std::ranges::sort(1,2);
      |     ~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/local/include/c++/14.2.0/algorithm:63,
                 from main.cpp:1:
/usr/local/include/c++/14.2.0/bits/ranges_algo.h:1779:7: note: candidate: 'template<class _Iter, class _Sent, class _Comp, class _Proj>  requires (random_access_iterator<_Iter>) && (sentinel_for<_Sent, _Iter>) && (sortable<_Iter, _Comp, _Proj>) constexpr _Iter std::ranges::__sort_fn::operator()(_Iter, _Sent, _Comp, _Proj) const'
 1779 |       operator()(_Iter __first, _Sent __last,
      |       ^~~~~~~~

(依然省略40行)

/usr/local/include/c++/14.2.0/bits/ranges_base.h:501:22: note: the required expression 'std::ranges::_Cpo::begin(__t)' is invalid
  501 |         ranges::begin(__t);
      |         ~~~~~~~~~~~~~^~~~~
/usr/local/include/c++/14.2.0/bits/ranges_base.h:502:20: note: the required expression 'std::ranges::_Cpo::end(__t)' is invalid
  502 |         ranges::end(__t);
      |         ~~~~~~~~~~~^~~~~

其中也可以一窥ranges algorithm对于迭代器-哨兵对的约束：存在几个具名concepts，包括random_access_iterator、sentinel_for等。
以random_access_iterator为例，对于 Legacy random iterator，其只是在cppreference上以文本形式指明了语义要求：
C++_Itereator_requirements
而在ranges algorithm中，其则是直接了当地用concepts约束了迭代器类应当满足的语法要求：

template <class _It>
concept random_access_iterator = bidirectional_iterator<_It>
    && derived_from<_Iter_concept<_It>, random_access_iterator_tag> && totally_ordered<_It>
    && sized_sentinel_for<_It, _It> && requires(_It __i, const _It __j, const iter_difference_t<_It> __n) {
        { __i += __n } -> same_as<_It&>;
        { __j + __n } -> same_as<_It>;
        { __n + __j } -> same_as<_It>;
        { __i -= __n } -> same_as<_It&>;
        { __j - __n } -> same_as<_It>;
        { __j[__n] } -> same_as<iter_reference_t<_It>>;
    };

对concepts语法有一定了解就不难完整地解读上述约束：
在满足双向迭代器要求的基础上，满足sized_sentinel_for和totally_ordered，同时对于标定的iter_difference_t（迭代器差值类型）的一个实例，本迭代器与该实例进行operator+（含左右和加减的重载）、加/减复合赋值都会返回It&或It，并且支持下标运算后返回一个引用类型（详情参阅C++标准库）。

显然_It = int必定无法满足上述约束，而既有的随机访问迭代器（主要是std::vector和原始指针）都满足之。

Views：Ranges的灵魂

至此来说，ranges algorithm依然“只是”STL Algorithm加上了一些concepts约束和多了几层打包工作而已。Ranges迷人的灵魂所在，亦作为其中最复杂迷离的要素，还是在"Views"——视图之上。

语法向：`namespace views` 和 `operator|`

视图是一种特殊的函数对象，其被定义在<ranges>的namespace std::ranges::views中。但由于库中存在声明：

namespace std
{
    namespace views = ranges::views;
}

因此，调用视图对象时只需要使用std::views::XXX即可。

注释：所有的视图对象都是轻量级、且能被平凡地复制( trivially copyable )的。

在调用方式方面，大多数视图支持以下几种调用方式：

直接调用（即传统的operator()），如std::views::filter(vc,[](int v){return v>3;})。
串联调用，又名“管道操作符”-"pipeline operator"，即operator|，如此做会间接调用右侧视图对象的operator()，并将左操作数作为第一形参放入其中。

串联调用支持将多种views操作连接在一起的原因类似于流插入/输出运算符operator<</operator>>，利用了其从左向右的结合性，同时每次调用都会返回一个（类似）自身的对象。

因此，以下几种调用方法是等价的：

std::vector<int> vc{6,5,5,3,7};

auto fn = [](int v){return v>3;}
std::views::filter(vc,fn);
vc | std::views::filter(fn);

逻辑向：“随心所欲不逾矩”的组合

有了前面的operator|铺垫，现在也就不难理解views~~容易用上头~~的原因了：
Ranges Library提供的原子函数(atomic functions)颇为丰富，语法分类来看，这些函数一部分属于"Ranges factory" - 范围工厂，可根据给定参数产生一个新的Range；一部分属于"Ranges adaptor" - 容器适配器，可作用于既有Range上并产生一个操作过的Range；有少量函数二者皆然（取决于其形参）。
这些函数多处于std::views::中，亦有少量在std::ranges内。

严格地，由于Ranges的惰性计算机制，这里的“操作过的Range”事实上不太准确：任何Range在被“使用”前均都不会进行任何计算。详见下一节内容。

这些操作涵盖了编程实践中对于Ranges的大部分“需求”，如：

只读型：过滤(filter)、分隔(stride)、分块(chunk)、取舍(drop/count)等；
视图型：滑动(slide)、相邻(adjacent)等；
修改型：转化(transform)等；
工厂型：枚举(enumerate)、压缩(zip)、迭代(iota)、重复(repeat)等。

在C++20中只引入了16个views，C++23又向其中添加了16个，C++26依然会继续添加。

由此，C++20被称为继C++11后又一个划时代的C++版本也就不难理解了。C++11颠覆了许多传统C++的代码写法，而C++20的ranges亦然：

std::vector<int> vc{};

for(auto&& [x,y] : vc | std::views::filter([](int x){return x > 0;}) 
                  |std::views::take(10) | std::views::enumerate)
            //Sematics can't be more explicit and clear: filter scores above 0, take 10 and enumerate them
            //If one wishes to reverse the range, simply append std::views::reverse to the end
            {
                  std::println("No.#{}: score = {}",x+1,y);
            }

设计向：惰性视图，分秒必争

上述所有组合产生的ranges对象都是一个惰性的可迭代对象，类似于python的generator object。
惰性对象的含义在于，对ranges进行管道组合的时候并不会执行任何计算（或者让ranges factory开工什么的），计算发生的时机是调用之时。
可以理解为，ranges对象实际上是一份该如何进行ranges的产生与变换的“说明书”，进行管道组合等操作只是在改说明书（而非其中出现的目标range）。

std::vector<int> vc{1,2,3,4,5};
auto rng = vc | std::views::reverse | std::views::transform([](int x){return std::format("{}",x);});

//No invocation of the lambda function, visit of the vector or calling std::format until here: the view is lazy
//You can even further modify the view upon the beginning of iteration

for(auto x : rng | std::views::take(3))
{
      //The iteration starts, thus the ranges object gets working
      std::println("{}",x);
}

同时，为了保证语义的正确性，并非所有的Range都是等价的。典型地，如 contiguous range（连续范围）就是一类对底层要求较高的Range，可以用于其上的算法显然会多于能用于其它一般Range（比如单向Range）的算法。又如std::ranges::sort就要求目标range是一个可读写的、能够随机访问的Range；很多range（或经过部分操作的range）会不满足这一条件，如

std::list<int> ls{};
//std::ranges::sort(ls);  //Not Compile

std::vector<int> vc{};
std::ranges::sort(vc); //OK
std::ranges::sort(vc | std::views::reverse); //Still OK
//std::ranges::sort(vc | std::views::chunk(3)); //Not Compile

结语

Ranges作为STL继往开来的产物，结合Concepts约束、Views的灵活组合等特性开创了新时代C++算法的新纪元，同时也体现了C++新特性的几个特点：关联语法点多，通晓难度极大；但其接口亦易于上手调用，且开发上限极高。本篇仅讲解了Ranges的基本使用方法、部分设计哲学和底层原理等，关于 user-defined 的视图等在C++23中又有诸多更新与亮点。
关于视图的进阶用法等，以后可能可以咕一篇专题来讲.sage