C++ Ranges(一):核心概念与算法
Ranges 是 C++20 对区间、迭代器与算法的一次系统扩展。它让算法直接接收 range,让惰性 view 可以组合处理步骤,也用 concepts 表达迭代能力等约束。C++23 又补入常用查询算法、fold 算法和容器物化接口。本文介绍核心模型、所有权与生命周期、算法投影,以及 C++23 常用算法;完整的 view adaptor 与管道组合见第二篇:管道与 View Adaptors。
两篇分工如下:
| 文章 | 内容 |
|---|---|
| 本篇:核心概念与算法 | range/view、所有权与生命周期、投影、C++23 查询与 fold、容器物化 |
| 第二篇:管道与 View Adaptors | 管道组合、C++20/23 工厂与 adaptor 逐项示例、滑动窗口实战 |
为什么需要 Ranges
传统 STL 算法通常显式传递迭代器对,并在需要多步处理时建立中间容器:
1 | |
Ranges 算法可以接收整个 range;view 则可以延迟执行筛选和变换:
1 | |
view 通常不在创建时遍历或生成结果;迭代时才按需求值。不过,“view 一定不拥有数据”并不成立:owning_view 可以拥有一个 range 对象,而 ref_view 等 view 只是借用它。Ranges 能表达部分生命周期约束,但不会自动防止所有悬空引用。
最小可运行示例
以下程序以 C++20 编译即可运行,不依赖 C++23 的 range 格式化支持:
1 | |
输出:
1 | |
此处 evens 是一个 view,但其底层数据仍由 nums 持有;nums 必须比 view 和其迭代过程活得更久。管道表达式从左到右描述处理步骤,完整 adaptor 列表和组合规则见第二篇。
术语:range、view、adaptor、algorithm 与 closure
| 名称 | 含义 |
|---|---|
| range | 能通过 ranges::begin/end 遍历的一段元素;容器、数组和 view 都可能是 range |
| view | 满足 view concept 的轻量 range 类型;可借用数据,也可拥有 range 对象 |
| view adaptor | 接收一个或多个 range 并产生 view 的操作,如 filter、take |
| range factory | 产生 range 的操作,如 views::iota、views::single |
| ranges algorithm | 接收迭代器对或 range 的算法,如 ranges::sort、ranges::find |
| adaptor closure | 等待 range 输入的可组合管道组件,如 views::filter(pred) |
这些名称有关联但不等同。std::views 是 std::ranges::views 的命名空间别名;std::ranges::view 是 concept;std::views::filter 是 adaptor 对象。std::views::filter(pred) 本身是 closure,不是 view;将它应用于 range 后才得到 view。不要把 view、范围适配器闭包和 lambda 的闭包对象混为一谈。
头文件、标准版本与库支持
Ranges 算法声明在 <algorithm>,核心 concepts、view 和 adaptor 声明在 <ranges>。容器和其他类型仍需各自的头文件:
1 | |
C++20 标准引入 ranges core、view、adaptor 和 ranges 算法;C++23 引入下文介绍的新算法及容器物化接口。语言标准版本不等于标准库已完整实现。可用特性宏检查编译器所配标准库:
| 宏 | 表示的设施 | 头文件 |
|---|---|---|
__cpp_lib_ranges | C++20 Ranges 库基础设施 | <version> 或相关头文件 |
__cpp_lib_ranges_contains | contains、contains_subrange | <algorithm> |
__cpp_lib_ranges_starts_ends_with | starts_with、ends_with | <algorithm> |
__cpp_lib_ranges_find_last | find_last 系列 | <algorithm> |
__cpp_lib_ranges_fold | 六种 fold 算法 | <algorithm> |
__cpp_lib_ranges_iota | ranges::iota 填充算法 | <numeric> |
__cpp_lib_shift | C++23 ranges 版 shift_left/right | <algorithm> |
__cpp_lib_ranges_to_container | ranges::to | <ranges> |
__cpp_lib_containers_ranges | from_range、insert_range、append_range 等 | 相应容器头文件 |
宏值会随标准缺陷修正和实现更新变化。需要针对具体工具链编译时,宜在对应头文件之后包含 <version> 并检查宏是否达到所需值,而不是仅依据 -std=c++23 判断库功能已实现。可查阅 C++ library feature-test macros。
Range 与 view 的所有权模型
view 不等于“永远不拥有数据”
std::ranges::view<R> 要求 R 是 range、可移动,并且满足 view 对象的语义要求;它不是“绝不持有数据”的同义词。常见的 ref_view 保存对外部 range 的借用;owning_view 则通过值持有一个 range 对象。许多 adaptor view 保存底层 view 和谓词、函数等状态。
views::all(r) 把可用 range 规范化为 view:如果 r 已是 view,通常直接转发;如果是左值非 view range,通常得到 ref_view;如果是符合条件的右值非 view range,通常得到 owning_view。后者拥有被移动进来的容器对象,但若容器本身只是外部内存的包装,仍不接管那块外部内存。
1 | |
通常无需手动写 views::all:标准 view adaptor 会按规则处理其输入。但理解它有助于判断 view 的复制、移动和生命周期。右值容器是否可接入具体 adaptor 还取决于 viewable_range 及该 adaptor 自身的约束。标准:views::all、viewable_range
viewable_range 与常见 range 包装
viewable_range<R> 判断的是表达式类型(包括左值/右值和 const 属性)能否安全用于 view 操作,不是“是否属于 view”。例如,容器左值可以包装为 ref_view;符合条件的移动型右值容器可以被 owning_view 持有。临时 initializer_list 不能以同样方式接入,因为移动其包装对象不会延长底层数组的生命周期。
std::span 和 std::string_view 是 view,也是 borrowed range,但它们仍不拥有底层字符或元素。std::ranges::subrange<I, S> 用迭代器和 sentinel 表示一段区间,可选存储大小;它适合把“迭代器对”显式包装成 range,但也不会自动拥有迭代器指向的数据。
1 | |
这里 part 和 first_two 都依赖 data 的存活。subrange 是一种 view;span 也是 view;它们的 view 身份不代表拥有底层数据。标准:subrange、span
borrowed_range、dangling 与算法返回值
borrowed_range 描述的是:range 对象销毁后,从它取得的迭代器是否仍可独立使用。它不是底层数据仍有效的证明。span 和 string_view 的迭代器不会依赖 view 对象本身,但只有在其外部数据仍存活时才可用;临时 vector 的迭代器则会在容器销毁后失效。
ranges 算法的 range 重载对可能悬空的迭代器结果使用 std::ranges::dangling。例如:
1 | |
dangling 让调用者无法误把临时容器的迭代器解引用,但不会检查 view 内部捕获的引用,也不会保护借用型 view 指向的外部数据。range 重载若返回的是非迭代器结果(例如计数、布尔值或算法结果结构),也不意味着整个算法无生命周期要求。标准:borrowed_range、dangling
迭代类别、元素引用与失效
Ranges 使用迭代器 concept 表达操作能力:input 可单次读取,forward 可多次遍历,bidirectional 可双向移动,random_access 可常数时间跳转,contiguous 还保证连续存储。不是每个 range 都有 size(),也不是每个 sentinel 都与迭代器同类型。算法和 adaptor 的约束可能要求不同迭代能力,例如排序要求随机访问,反向遍历要求双向迭代。
对容器的迭代器失效规则仍由容器决定。vector 扩容会使迭代器、指针和引用失效;经 filter_view 等 adaptor 间接访问并不会令这些规则消失。某些 view 的迭代器还依赖 view 对象内部缓存或状态;不要在 view 生命周期结束后继续使用从中取得的迭代器,除非具体类型明确满足相应的借用保证。
Lambda 捕获与代理引用
view 通常会保存传入的谓词或转换函数。若 lambda 按引用捕获局部变量,而 view 比该变量活得更久,遍历 view 时就会访问悬空引用。按值捕获适合保存独立状态;引用捕获则要求被引用对象至少活到 view 的最后一次使用。
1 | |
Ranges 元素引用也不总是普通 T&。std::vector<bool> 的解引用结果是代理对象;某些变换 view 可能返回值或代理。读取代码通常可用 const auto& 绑定元素(临时代理的生命周期会延长到该局部引用作用域),但不要假定其地址可取、可写成普通对象引用,或能跨越底层容器的失效边界。具体操作仍需满足算法对引用类型及可写性的约束。
Ranges 算法、投影与 identity
Ranges 算法大多可直接接收 range,不必手动传 begin 和 end:
1 | |
Ranges 版本通常通过 concepts 在编译期约束迭代器、比较器和可调用对象,并且许多(但并非全部)算法提供 projection 参数。每个算法的签名都应单独查阅;不能把 projection 描述为所有 Ranges 算法的通用参数。
Projection 与 std::identity
projection 在比较或匹配前把元素映射为要处理的值。它可避免为常见成员访问编写只做转发的 lambda:
1 | |
sort 的 projection 将每个 Person 映射到 age;{} 使用默认比较器。许多 ranges 算法的默认 projection 是 std::identity,它原样返回输入,因此省略时不改变元素。projection 对某些算法有用,但是否存在该参数取决于具体算法。标准:算法要求与签名
C++23 常用 Ranges 算法
以下算法位于 <algorithm>,均在 std::ranges 中。代码片段假定各自列出的对象已在同一作用域声明。标准库支持可能滞后于语言模式,参见前面的特性宏表。
contains 与 contains_subrange
std::ranges::contains(range, value) 判断是否有元素与值相等;contains_subrange 判断第一个 range 是否包含与第二个 range 相等的一段连续子区间。二者可接 projection;contains_subrange 的 needle 也可指定 projection。
1 | |
contains_subrange 要求输入满足其前向遍历约束;它不是在无序区间中查找元素集合。若只是判断单值是否出现,contains 比手写 find(...) != end(...) 更直接。contains、contains_subrange
starts_with 与 ends_with
这两个算法判断一个 range 是否以另一个 range 开头或结尾,并支持比较器和 projection。它们不修改输入;如果模式比被检查 range 更长,结果为 false。
1 | |
starts_with 自 C++20 起已存在于 basic_string 成员函数中;C++23 增加的是 ranges 算法版本。ends_with 也有对应的字符串成员函数。ranges 版本可用于满足约束的其他序列。starts_with、ends_with
find_last、find_last_if 与 find_last_if_not
这些算法从逻辑上返回最后一个满足条件的元素位置。相较于 find 从头返回首个匹配项,它们适合“最后一次出现”这一查询。find_last 按值匹配;另两个分别查找谓词为真和谓词为假的最后一个元素。它们返回 subrange,其 begin() 是匹配项迭代器,end() 是输入终点;未找到时返回空子区间。可用 projection。
1 | |
这些算法要求至少前向范围。示例中的范围非空且匹配项存在,因此可解引用 begin();真实代码应先判断返回子区间是否为空。find_last 系列自 C++23 起提供。find_last、find_last_if、find_last_if_not
C++23 Fold 算法
fold 把一段序列按指定次序归约成一个累积结果。C++23 把六个 fold 算法放在 <algorithm> 的 std::ranges 命名空间下。它们支持 range 重载,提供带初值和无初值形式,并允许累积结果类型不同于初值类型;但该结果类型在折叠过程中保持固定,不能每一步任意变化。
左折叠和右折叠
左折叠依次计算 f(f(init, x1), x2)...;右折叠从右侧开始,计算 f(x1, f(x2, ...))。若 f 非结合或非交换,二者结果可不同。减法就是简单例子:
1 | |
右折叠的二元函数参数顺序是“当前元素、右侧累积值”,与左折叠的“累积值、当前元素”相反。fold_left 只要求输入范围;fold_right 要求双向迭代,因为需要从右向左处理。标准:fold 算法
带初值与不带初值:fold_left、fold_left_first
fold_left(range, init, f) 将给定初值作为第一次调用的左参数;空 range 时返回初值。fold_left_first(range, f) 把首元素作为起始累积值;空 range 时返回空 optional。后者因此表达“序列至少有一个元素时才有结果”。
1 | |
六个算法一览
| 算法 | 初值 | 方向/迭代要求 | 空 range 结果 |
|---|---|---|---|
fold_left | 显式 init | 左至右,输入范围 | 转换为结果类型的 init |
fold_left_first | 首元素 | 左至右,输入范围 | 空 optional |
fold_right | 显式 init | 右至左,双向范围 | 转换为结果类型的 init |
fold_right_last | 最后元素 | 右至左,双向范围 | 空 optional |
fold_left_with_iter | 显式 init | 左至右,输入范围 | 结束迭代器与转换后的 init |
fold_left_first_with_iter | 首元素 | 左至右,输入范围 | 结束迭代器与空 optional |
fold_right_last 是右向版本的无显式初值折叠:最后一个元素作为初始累积值,从右往左继续应用函数;空 range 返回空 optional。C++23 没有 fold_right_with_iter 或 fold_right_last_with_iter。
1 | |
累加器类型与移动
对于 fold_left,设初值类型为 T,元素引用类型为 Ref,结果类型 U 是 f(T, Ref) 返回类型去掉 cv/ref 后的类型。T 必须可隐式转换为 U;后续 f(U, Ref) 的结果也必须能赋给 U。右折叠相应交换函数参数顺序。无初值版本以元素值类型作为起始类型。累加器按移动语义传入下一步,但 callable 本身仍须满足 fold 的可复制等约束。
例如,以整数 0 为初值,归约浮点数后得到 double;空范围也返回 double 类型的零:
1 | |
这与 std::accumulate(..., 0) 把累积值限制为 int 不同。不过,不能直接用整数初值得到 std::string 累加器,因为 int 不可隐式转换为 std::string。拼接文本应显式传入 std::string{}。fold 不提供 projection 参数;需要提取成员时可先接 views::transform。
返回迭代器的两个左折叠
fold_left_with_iter 除累积值外还返回处理结束位置;fold_left_first_with_iter 的累积值则是 optional。两者都有 range 和迭代器/sentinel 重载。它们会处理完整个给定范围,而非自动在某个条件处提前停止;若要分段消费单遍输入源,应先显式限定范围边界。
1 | |
in_value_result<I, T> 的成员名是 in 和 value。对应的 first 版本以 value 保存 optional 累积值。range 重载的 in 使用 borrowed_iterator_t<R>:对非 borrowed 的临时容器,该成员是 dangling,但累积值仍可读取。迭代器重载则由调用者保证底层数据生命周期。
与 accumulate 和 reduce 的区别
std::accumulate 位于 <numeric>,是基于显式初值的有序左折叠,通过迭代器对调用,累积结果类型固定为初值类型 T。C++23 ranges fold 提供 range 重载、无初值形式、带迭代器的结果形式,以及不同于初值类型的固定累积结果类型。
std::reduce 同样在 <numeric>,允许实现以不同顺序组合操作数,因此用于并行或重排时通常要求运算满足相应结合性等性质。它不等价于保持顺序的 fold_left;例如减法不能把 reduce 当作从左向右的减法链。
C++23 填充与移位算法
ranges::iota:写入递增值
views::iota 惰性生成序列;ranges::iota 则立即向已有可写范围填入递增值,位于 <numeric>。返回结构的 out 是结束迭代器,value 是下一个待写值。
1 | |
shift_left 与 shift_right:原地移动
C++20 已有传统算法版本;C++23 新增 <algorithm> 中的 ranges 版本。它们在已有范围内移动元素,不改变容器大小,并返回保留下来的有效元素子范围。移动距离必须非负;未包含在返回区间内的元素不应再假定保留原值。
1 | |
shift_left 至少要求前向迭代器,shift_right 的 ranges 版本要求双向迭代器;两者均要求元素可按算法约束移动。它们不同于 views::drop:后者只是改变访问区间,不移动源元素。ranges::iota、ranges::shift_left/right
View 到容器:ranges::to 与 C++23 容器接口
view 是惰性 range,若结果必须脱离源数据生命周期独立保存,就应显式物化。C++23 的 std::ranges::to<Container>(range) 可从 range 构造容器;它能够在适用时选择 range 构造或插入方式,并可递归地把嵌套 range 转成嵌套容器。目标容器可以显式指定,也可在类型可推导时使用 deduction guide:
1 | |
推导目标类型的形式为 std::ranges::to<std::vector>(range),但能否推导取决于容器是否有适用的 deduction guide;需要稳妥指定结果类型时使用 to<std::vector<int>>。ranges::to 在 <ranges>,特性宏为 __cpp_lib_ranges_to_container。相关规范见 P1206R7。
C++23 还提供从 range 构造及向已有容器批量插入的接口。std::from_range 用于采用 range 构造 tag 的容器构造函数;insert_range 是关联容器和序列容器等提供的成员接口;append_range 用于支持它的序列容器,将元素追加到末尾。它们的声明分别在对应容器头文件中,特性宏为 __cpp_lib_containers_ranges。
1 | |
std::from_range tag 的定义可通过 <ranges> 获得;容器成员仍需包含相应容器头文件。不同容器的插入位置语义并不一致,例如 vector::insert_range(pos, range) 需要位置,关联容器的接口不需要。物化会立即遍历输入并建立容器存储。C++23 还加入了 range 格式化,但具体 range 和元素类型仍须满足 formatter 约束,标准库也可能尚未实现;逐元素输出可避免依赖该支持。
Sliding window 实战导引
C++23 的 views::slide 和 fold 可以表达移动窗口统计:slide 产生窗口,fold 负责窗口内的有序归约,需要独立保存时再用 ranges::to 物化。完整示例见第二篇:滑动窗口实战。slide 应通过 __cpp_lib_ranges_slide 检查支持,不能仅依据 __cpp_lib_ranges 或语言模式判断。






