C++20: Ranges、view 和 concepts C++20: Ranges、view 和 concepts C++20: Ranges、view 和 concepts

这是学习 A Tour of C++ by Bjarne Stroustrup Chapter 14 Ranges 的读书笔记

传统 STL 很早就有 range 的思想，即“任何能按顺序遍历元素的对象或表达式”。传统做法是用一对迭代器来表示一个 range，比如 v.begin() 和 v.end()。而 Ranges 是 C++ 20 引入的，把这种思想正式化、标准化后的库。

为什么需要 Ranges 库：

1. 提供 view 这种特殊的 range，并且提供了一系列创建 view 的工具（即 view adaptors）
2. 允许 Ranges 与 Concepts 结合，使得错误更早、更清晰
3. 传统 STL 算法以迭代器 pair 为核心，调用繁琐且容易把 begin/end 配错；Ranges 库允许直接对整个 range 使用算法

本篇笔记顺着上述三个理由展开：

1. 先讲 range 的定义与分类
2. 再着重讲 view 这一种 range
3. 再讲 range 与 concept 的关系
4. 最后讲 Ranges 库提供的算法

range 的定义与分类

range 不等于 container，因为：container 强调“拥有并存储 元素”，而 range 只强调“这组东西可以被遍历”。大致可以认为 range ≈ container + view，其中 view 就是可遍历但是不拥有元素的 range。

std::vector<int> v{1, 2, 3, 4};

这里的 v 既是 container 也是 range。但是：

auto r = v | std::views::filter([](int x) {
    return x % 2 == 0;
});

这里的 r 是 range，但是因为它不拥有这些元素而不是 container

range 的能力层级

range 可以按照多条线来分类，此处只讨论 遍历能力 和 是否拥有数据 两条线

1. range 拥有不同的遍历能力

• input_range：只能向前读取；
• forward_range：可以多次遍历；
• bidirectional_range：还能向后移动；
• random_access_range：可以跳跃访问；
• contiguous_range：元素在内存中连续。

2. range 是否拥有底层数据

• container: 自己拥有元素，并且负责元素的生命周期
• view：不拥有元素，只是通过迭代器、引用或其它方式访问外部数据

view、view adaptors 与 range factories

这里详细说一下 view，因为 view 是本章重要的内容：

1. view 不拥有

• view 很像数据库的视图，也有点像“带筛选规则的引用”
• view 通常只保存 “从哪里获取数据” 和 “按什么规则取”
• 底层 range 销毁后，view 仍然存在，但它指向的数据已经不存在了。之后遍历 view，就像悬空引用一样，是未定义行为

2. view 复制很便宜

• 由于 view 只是 “带筛选规则的引用”，因此 view 的复制很便宜，通常可以按值传递

3. view 的惰性求知

• 创建 view 时不会遍历所有元素。当迭代器递增或解引用的时候，view 才向底层 range 请求并计算需要的元素

4. 具体的 view

• 我们所讨论的 view，是一个统称。但是没有一种叫 “view” 的类型，只有更具体的 filter_view, take_view 等
• 这些具体的 view 要么通过 view adaptors 从 range 转化得来，要么通过 range factories 生成。

由于 std::ranges::view 相关的内容太重要了，标准库专门定义了一个命名空间别名：

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

使得以下两种表示等价，可以用更短的 std::views 来减少啰嗦

std::ranges::views
std::views

view adaptors

view adaptor 就是把一个 range 转换成另一个 view 的工具。

以下介绍 std::views::filter, std::views::take 和 std::views::transform 这三种 view adaptor，分别用来筛选、获取前几个元素和进行某种转换。

1. std::views::filter

把 range 转换成专门用来做筛选的 view。假设有：

vector<int> numbers {1, 2, 3, 4, 5};

然后想从中筛选出偶数，传统写法是写一个判断：

for (int x: numbers) {
    if (x % 2 == 0) 
        std::cout << x << ' ';
}

但是有了 views::filter 之后：

auto even_numbers = 
    numbers | std::views::filter([](int x) { return x % 2 == 0; });

在 ranges 的代码中，| 这个符号表示把左边的 range 交给右边的 view 来操作

• 这里的 even_numbers 会被推断为一个 filter_view 类型
• 这里 views::filter 需要一个 “筛选规则” 的 predicate，而 lambda 很适合临时写这种规则

2. std::views::take

用来限制一个 range 的元素，让你只看到 range 的前几个元素。假设有：

vector<int> v{10, 20, 30, 40, 50};

如果想获取前三个元素，传统做法是

int count = 0;
for (int x: v) {
    if (count >= 3) {
        break;
    }
    std::cout << x << ' ';
    count++;
}

而有了 views::take 之后：

for (int x: v | views::take(3)) {
    std::cout << x << ' ';
}

3. std::views::transform

把底层元素逐个传给变换函数之后产生一个 view

std::vector<int> numbers{1, 2, 3};

auto doubled = numbers | std::views::transform([](int x) { return x * 2; });

这里的 pipelining 操作：

指的就是前面的 | 操作，把多个 view 操作按顺序连起来，比如：

numbers | views::filter(is_even()) | views::take(3);

其实这样就很像机器学习里面的数据清洗流程，但是在 C++ 当中这都是通过 views 来完成的，因此没有复制原数据

range factories

range factories 是为了 “按需产生一个 range”

不需要先有一个 vector 装着元素再用来遍历

先学 4 种 views:

• empty_view：产生 0 个元素
• single_view{x}：产生 1 个元素，也就是 x
• iota_view{x, y}：按递增规则产生多个元素 产生 x 到 y - 1
• istream_view：从输入流逐个读取元素

1. views::empty

auto nothing = views::empty<int>;  // 根本没有元素的 view
for (int x: nothing) {
    std::cout << x; // 一次也不会执行
}

目的是，有时候某分支没有结果，仍可返回一个合法 range

2. views::single

auto one = views::single(10)

适用于算法需要接收 range，但是当前只有一个值的情况

3. views::iota

auto numbers = views::iota(3, 7);

产生 3, 4, 5, 6

其实就类似 Python 的 range(3, 7)

只给一个参数时也可产生无限序列（通常接 views::take()）

auto numbers = views::iota(3) | views::take(4);

4. views::istream

auto numbers = views::istream<int>(std::cin);

输入什么数字，就用什么数字生成 range

ranges 与 concept 的关系

concepts 就是用来帮助编译器判断当前这个对象是否适宜做某些操作的。可以类比数学中的集合概念：预先定义好了一些条件，满足这个条件的所有类型构成一个集合，这个集合就是 concept。

编译器在编译时要检查的就是：当前这个类型是否属于这个集合；若不属于，则存在非法操作。因此应当把 concept 看作 “类型谓词”。

通常来说，我们不需要自定义 concept，因为标准库已经实现了大部分我们会用到的 concepts 了。如果一定要自定义 concept，则使用 concept 关键词，语法类似这样：

template<class T>
concept HasSize = requires(T x) { x.size(); };

编译器在检查 HasSize concept 的时候，就会检查对应类型在调用 .size() 的时候是否会报错

有三类 concepts：

• 类型 concepts
  • 比如是不是整数，能否复制
• 迭代器 concepts
  • 能不能向前走，能不能向后走
• range concepts
  • 是不是 forward_range

用 concept 约束自定义算法

template<forward_range R>
requires sortable<iterator_t<R>>
voif my_sort(R& r) {
    // ...
}

这里有两个要求：

• R 必须是 forward_range
• R 的迭代器必须 sortable 这里使用的都是标准库定义好的 concept，没有自定义 concept，因此直接用就可以了

用 concepts 区分 range 的能力

range
sized_range
input_range
forward_range
bidirectional_range
random_access_range
contiguous_range

这些 concepts 让库可以根据 range 的能力选择或限制算法实现。

这里其实就是本笔记一开始说到的 “根据遍历能力划分 range”

用 concepts 描述 iterator 和操作对象

input_iterator    // 描述迭代器能做什么
forward_iterator  // 描述迭代器能做什么
sortable          // 描述元素是否能排序
predicate         // 描述函数能否充当谓词
sentinel_for      // 描述一个结束标记是否能和迭代器配合

Ranges 库提供的算法

这种遍历是旧式，有两个迭代器:

sort(v.begin(), v.end()); 

有可能出现 sort(v1.begin(), v2.end()) 这种起点和终点分属两个容器的情况

引入 Ranges 库的算法后的新式写法，可以确保起点和终点属于一个序列：

ranges::sort(v);