跳转到内容

C++/ranges

添加链接
维基教科书，自由的教学读本
< C++

<ranges>是C++20引入的标准库。<ranges>中定义了std::ranges和std::views命名空间。

基本概念

[编辑]

“范围”（range）定义为：任何能够提供迭代器对 [begin, end) 的对象。即：能被begin/end遍历的一段东西。这包括标准容器：vector, list, array等；原生数组：int arr[10]；特殊的范围range：istream_view (从流读取)，iota_view (生成序列)。 

// Range 概念的基本要求
template<typename T>
concept Range = requires(T& t) {
    std::ranges::begin(t);  // 必须有 begin()
    std::ranges::end(t);    // 必须有 end()
};
#include <ranges>
#include <vector>
#include <string>
#include <array>

// 验证各种类型是否满足 Range 概念
static_assert(std::ranges::range<std::vector<int>>);     // true
static_assert(std::ranges::range<std::string>);          // true
static_assert(std::ranges::range<std::array<int, 5>>);   // true
static_assert(std::ranges::range<int[10]>);              // true

“视图”（view）：轻量级的范围range的包装器（零拷贝），是轻量级、非拥有的range，支持常数时间复制、移动和赋值。惰性组合、惰性求值（操作延迟到迭代时）、时间复杂度O(1)构造/析构、可组合性（通过 | 管道符连接）、通常不拥有数据(或特例拥有少量数据），仅引用底层范围range。从底层的范围range返回数据，但不拥有任何数据。本质上，迭代时view返回下一个符合过滤条件的元素。 

// View 概念的要求
template<typename T>
concept View = std::ranges::range<T> && 
               std::movable<T> && 
               std::ranges::view_base<T>;
#include <ranges>
#include <vector>

// 验证各种视图类型
static_assert(std::ranges::view<std::ranges::iota_view<int, int>>);  // true
static_assert(std::ranges::view<decltype(std::views::iota(0) | std::views::take(5))>);  // true

// 容器不是 View（因为复制成本高）
static_assert(!std::ranges::view<std::vector<int>>);  // false

范围工厂（Range factory）：从“无现成输入range”开始，制造一个 range/view。包括：

  • 对象std::views::empty, void -> view, 使用std::views::empty<T>即可直接获得对象
  • 对象std::views::single, any -> view, 单对象的std::ranges::view
  • 对象std::views::iota, iterator | (iterator, sentinel) -> view, 一般哨位边界的有限或无限递增序列 例如，itoa将生成一系列递增的值，如auto rnums =std::views::iota(1,10);
  • 对象std::views::counted, (iterator, count) -> view, 计数哨位边界的有限递增序列
  • 对象std::views::istream<T>, istream<T> -> view, 输入流转std::ranges::view
  • 类型std::ranges::subrange, (iterator, sentinel, [size]) | (borrowed_range, [size]) -> subvrange, 迭代器-哨位对
  • 类型std::ranges::ref_view, range -> viewable_range 借用
  • 类型std::ranges::owning_view, range -> viewable_range 占用
  • 对象std::views::repeat(C++23), 由重复产生相同值的生成序列组成的视图
  • 对象std::views::cartesian_product(C++23), 由n元笛卡尔积计算出的结果元组组成的视图

视图适配器（Range adaptor）是一个函数对象，属于命名空间std::views，可接受一个已有的range，返回一个range或者视图对象view。视图适配器可以使用|操作符连接到其他视图适配器。视图适配器从|操作符的左侧获得范围操作数。|操作符会从左到右求值。为什么叫 adaptor？因为它通常不拥有数据，而是对已有 range 做一层包装。包括： // 元素操作

  • transform(fn) // 映射元素
  • filter(pred) // 条件过滤

// 结构操作

  • take(n) // 取前n元素
  • drop(n) // 跳过前n元素
  • reverse // 逆序
  • keys/values // 键/值提取（针对pair-like）

// 生成操作

  • iota(start) // 无限序列生成
  • empty<T> // 空范围

一个简单例子： 

#include <ranges>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 适配器可以存储为对象
    auto filter_even = std::views::filter([](int n) { return n % 2 == 0; });
    auto take_three = std::views::take(3);
    auto square = std::views::transform([](int n) { return n * n; });
    
    // 组合使用
    auto result = numbers | filter_even | take_three | square;
    
    for (int n : result) {
        std::cout << n << " ";  // 输出: 4 16 36
    }
    
    return 0;
}

ranges库在std::views命名空间中包括一些变换函数：

  • take(int)选出view里的前N个元素。如果改编后的视图包含的元素少于N，则返回所有元素。
  • take_while()给定一个一元谓词 pred 和一个视图 r，它生成一个范围 [begin(r)， ranges::find_if_not(r, pred)) 的视图。
  • reverse()逆序双向视图里的所有元素
  • filter(invokable)视图使用一个谓词函数筛选出view里的特定元素，例如auto result = nums|std::views::filter([](int i){return 0==i%2;});
  • transform(invokable)视图使用了一个转换函数，对每个元素应用转换函数后，返回底层range的视图。例如auto result =nums|std::views::transform([](int i){return i*i;});
  • drop()排除view里的前N个元素，如果改编后的视图包含少于 N 个元素，则返回一个空范围。例如：rnums = std::views::drop(rnums,5);
  • drop_while()给定一个一元谓词 pred 和一个视图 r，它生成一个范围 [ranges::find_if_not(r, pred)， ranges::end(r)) 的视图。
  • keys()选出pair里的first成员。是elements_view<views::all_t<R>, 0> 的别名。
  • values()选出pair里的second成员。是elements_view<views::all_t<R>, 1>的别名。
  • all() 把一个 range 转成 view：如果输入本身就是 view，直接返回；如果是左值容器，可能返回 ref_view；如果是右值且满足条件，可能返回owning_view。
  • join()将二维/多维的范围视图平展为一维视图
  • split(forward_range & view)接受一个视图和一个分隔符，并将视图划分为分隔符上的子范围。分隔符可以是单个元素，也可以是元素的视图。
  • common()或common_range()获取一个迭代器和哨兵具有不同类型的视图，并将其转换为具有相同类型迭代器和哨兵的相同元素的视图。对于调用期望范围的迭代器和哨点类型相同的遗留算法很有用。
  • counted()计数视图显示了迭代器i和非负整数 n 的计数范围([iterator.requirements.general]) i+[0, n) 的元素的视图。
  • elements()接受一个类元组值和 size_t 的视图，并生成一个值类型为已改编视图值类型的第 n 个元素的视图。
  • zip(C++23) 由对已改编视图的相应元素的引用的元组组成的视图
  • zip_transform(C++23) 由转换函数应用到所适应视图的相应元素的结果元组组成的视图
  • adjacent(C++23) 由对已改编视图的相邻元素的引用元组组成的视图
  • adjacent_transform(C++23) 由转换函数应用于所适应视图的相邻元素的结果元组组成
  • join_with(C++23) 一种视图，由将范围视图平展得到的序列组成，元素之间有分隔符
  • slide(C++23) 第 M 个元素是另一个视图的第 M 个到 (M + N - 1) 个元素的视图
  • chunk(C++23) 一个由另一个视图的元素组成的n个大小的不重叠连续块的视图范围
  • chunk_by(C++23) 将视图拆分为给定谓词返回false的每对相邻元素之间的子范围
  • as_const(C++23) 将视图转换为常量范围
  • as_rvalue(C++23) 将每个元素强制转换为右值的序列视图
  • stride(C++23) 由另一个视图的元素组成的视图，一次向前移动N个元素

range是容器上的一个抽象概念，可以理解成指明首末位置的迭代器，即pair<begin,end>,这样range自身就包含能用于算法的足够信息，大多数算法只要用一个range参数就可以工作。基于range的概念，C++在名字空间std::ranges提供了与标准算法同名、但却使用range参数的算法，写法很简洁。从C++20开始，<algorithm>头文件中的大多数算法都会基于“范围”。这些版本在<algorithm>头文件中，但是在std::ranges命名空间中，这使它们与传统算法分离开。所以无需再调用两个迭代器的算法。例如std::sort(v.begin(),v.end());可以用范围来调用std::ranges::sort(v);使用试图适配器更为直观、易读：std::ranges::sort(v|std::ranges::view::reverse|std::ranges::views::drop(5));

range的分类

[编辑]
标题文本
Concept Description
std::ranges::input_range can be iterated from beginning to end at least once
std::ranges::forward_range can be iterated from beginning to end multiple times
std::ranges::bidirectional_range iterator can also move backwards with --
std::ranges::random_access_range can jump to elements in constant-time []
std::ranges::contiguous_range elements are always stored consecutively in memory
std::ranges::sized_range 范围的大小可由std::ranges::size()获得，提供size函数，能常数时间获取范围的长度；如果未提供size函数, 那么还要求

std::forward_iterator且iterator与sentinel(及iterator)可作差；如果size或者iterator的作差不能用常数时间实现, 那么可以用特化：std::ranges::disable_sized_range<T> = true且std::disable_sized_sentinel_for<iterator, iterator> = true， 强制关闭std::ranges::sized_range和std::ranges::sized_sentinel_for的特征

std::ranges::common_range 如果iterator == sentinel
std::ranges::viewable_range 如果std::ranges::view 或std::ranges::borrowed_range
std::ranges::borrowed_range 如果类型std::ranges::range T的值T t的t.begin()和t.end()获得的迭代器的生命周期与t无关, 那么可以认为是std::ranges::borrowed_range。由于语言层面无法自动识别生命周期的关系, 因此要特征能被识别, 还要手动特化std::ranges::enable_borrowed_range<T>为true

对照实现C#的LINQ的功能

[编辑]

std::ranges基本上可以一对一的实现C#的LINQ的功能：

C# LINQ 方法 C++20 std::ranges/views 组件 功能说明
Where std::views::filter 过滤满足条件的元素
Select std::views::transform 元素映射/转换
Take std::views::take 获取前 N 个元素
Skip std::views::drop 跳过前 N 个元素
TakeWhile std::views::take_while 一直取元素直到条件不成立
SkipWhile std::views::drop_while 一直跳过元素直到条件不成立
OrderBy std::ranges::sort 排序
Reverse std::views::reverse 反转序列
Any / All / Contains std::ranges::any_of / std::ranges::all_of 判断元素是否存在/全部满足
Zip std::views::zip 合并多个序列
Concat std::views::concat 连接两个序列
Range std::views::iota 生成连续数字序列

二者都是延迟执行（懒加载），不遍历就不真正计算，零拷贝、高性能。都能操作任何可枚举集合（数组、vector、string、list等等）。

例如，C#的LINQ程序： 

var result = numbers
    .Where(x => x % 2 == 0)
    .Select(x => x * 2)
    .Skip(2)
    .Take(5);

对应于C++程序： 

auto result = numbers
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * 2; })
    | std::views::drop(2)
    | std::views::take(5);
检索自“https://zh.wikibooks.org/w/index.php?title=C%2B%2B/ranges&oldid=185437”