C++20 Ranges

Posted on Edited on In

Ranges 是C++20 提供的一套对范围的统一抽象和操作库。ranges 指可迭代的序列，它可以包括任何能够提供迭代器的数据结构， 如 vector, list, etc. 引入 ranges 可以使迭代的处理更简洁直观灵活。

我们知道 STL algorithms 利用迭代器对数据进行操作。比如我们需要对一个 vector 进行排序, 需要将排序的范围的迭代器做为参数传递给 sort() 方法：

1
2
3
std::vector v = {1,6,4,2,8};
std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater());

这种写法很灵活。但更多的时候，我们是想对整个 vector 进行排序，传入迭代器反而是多余的操作了。引入 Ranges 即可简化这一操作。

1
2
std::ranges::sort(v);
std::ranges::sort(v,std::greater());

在 ranges 库中，默认是对整个范围进行操作。当然，也可以像原来一样，使用迭代器来指定范围：

1
std::ranges::sort(v.begin(), v.end());

这是一种简化操作的方式。但 ranges 更重要的优势在于，它允许你以函数式编程的方式来操作 STL algorithm 。

例如：
在引入 ranges 之前，如果我们需要对一个数组进行多项操作，我们可能需要一些变量来存储中间值。

1
2
3
4
std::vector<int> v = {1, 6, 4, 2, 8, 7, 9, 0};
std::vector<int> p1, result;
std::copy_if(v.begin(), v.end(), std::back_inserter(p1), [](int e){ return e % 2 == 0;});
std::transform(p1.begin(), p1.end(),std::back_inserter(result), [](int e){ return e*10;});

而引入 ranges 后，可以不再需要中间变量：

1
2
3
std::vector<int> v = {1, 6, 4, 2, 8, 7, 9, 0};
auto result = v | std::views::filter([](int e) { return e % 2 == 0; }) |
                std::views::transform([](int e) { return e * 10; });

ranges 将多个操作使用管道操作符 | 连接在一起，不仅省去了中间变量，还使得代码更简洁易读。

View

view 是一个轻量级的 range。view 的构建、复制与销毁都是在常量时间内完成的，与view 内的元素多寡无关。view 由 range adaptor 创建。 view 中 “显示” 的元素由 range adaptor 决定。在上面的例子中，view 显示的是 从数据 v 中过滤偶数元素，并将这些元素乘以 10 。

注意这里使用了 “显示” 而不是 “拥有” 。这是因为 view 是惰性求值(evaluated lazily)的 。即在上例中，filter 和 transform 并没有被调用，因为 result 没有被使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <ranges>
#include <vector>

int main() {
  std::vector<int> v = {1, 6, 4, 2, 8, 7, 9, 0};
  auto fun_filter = [](int e) {
    std::cout << "f_" <<e<<" ";
    return e % 2 == 0;
  };

  auto fun_transform = [](int e) {
    std::cout << "t_"<<e<<" ";
    return e * 10;
  };

  auto result =
      v | std::views::filter(fun_filter) | std::views::transform(fun_transform);

  std::cout << " - ";

  std::vector s(result.begin(), result.end());

  std::cout << std::endl;
  return 0;
}

这段代码中，在 ’ - ’ 被输出之前，没有任何其它输出，之后 ‘f_x’, ‘t_x’ 才开始被输出。当然，在这里也需要注意管道的运算，和不使用 ranges 不同，管道是按元素进行运算的， 即运算的顺序是：
filter(v0v_0)->null, filter(v1v_1)->transform(v1v_1)->result, filter(v2v_2)->transform(v2v_2)->result …
而非
(filter(v0v_0), filter(v1v_1), ......) -> (transform(v1v_1), …) -> result.
上例的输出为：

  • f_1 f_6 t_6 f_4 t_4 f_2 t_2 f_8 t_8 f_7 f_9 f_0 t_0

Adaptor

adaptor 为 ranges 生成一个随性求值的 view, 如前面所讲，adaptor 生成 view 时, ranges 中的元素不参与运算，只有在访问 view 时，才会对 view 中的元素求值。adaptor 可以串联起来，这是 ranges 的核心之所在，它解决了之前 STL algorithms 不易组合的问题。

使用 adaptor 创建 view 比直接创建 view 更高效，创建 view 的时间复杂度为 O(1)O(1) 。

Algorithm

前面用到的 std::rangs::sort(v) 是一个 range algorithm。range algorithm 与 std 命名空间中相应的迭代器的算法几乎完全相同。不同的是它们有 概念强制约束(concept-enforced constraints) , 可以同时接受 range 或 迭代器对来工作。

Function

//TODO

Concept

//TODO

参考