查看原文
其他

Ranges and Views in C++20

CPP开发者 2023-07-27

The following article is from CPP编程客 Author 里缪

本篇介绍下C++20的Ranges,补充下Modern C++主题中还未写过的重要内容。

什么是Ranges和Views?

Ranges主要涉及四个基本概念,如下表。
概念解释
range可迭代区间的抽象概念
range algo可接受Ranges的算法
view轻便、惰性的Ranges
range adaptor创建Views的适配器
第一,Ranges表示范围(区间),描述了一组可以迭代的元素,包含一个begin与end迭代器,STL中的容器就属此列。
既然表示范围,就具有几种不同的定义形式:
  • 一个begin迭代器,和一个end迭代器

  • 一个begin迭代器,和一个结束标识符(sentinel)

  • 一个begin迭代器,和元素数量

  • 数组元素

下面的示例演示了这四种不同定义形式的使用方式:
template <auto T>
struct end_with {
    bool operator==(auto pos) const {
        return *pos == T;
    }
};

int main() {
    std::vector vec { 7, 2, 15, 20, 9 };

    // 1. Ranges of begin and end iterator
    auto rng = std::ranges::subrange(vec);
    fmt::print("Ranges of begin and end iterator: {}\n", rng);

    // 2. Ranges of begin and a sentinel
    std::ranges::subrange rng_sentinel {vec.begin(), end_with<20>{}};
    fmt::print("Ranges of begin and a sentinel: {}\n", rng_sentinel);      

    // 3. Ranges of begin and a count
    auto pos = std::ranges::find(vec, 2);
    if (std::ranges::distance(pos, vec.end()) >= 3) {
        auto rng_count = std::views::counted(pos, 3);
        fmt::print("Ranges of begin and a count: {}\n", rng_count);
    }

    // 4. Ranges of an array
    int arr[] = { 7, 2, 15, 20, 9 };
    auto rng_arr = std::ranges::subrange(arr);
    fmt::print("Ranges of an array: {}", rng_arr);
}
输出如下:
Ranges of begin and end iterator: [7, 2, 15, 20, 9]
Ranges of begin and a sentinel: [7, 2, 15]
Ranges of begin and a count: [2, 15, 20]
Ranges of an array: [7, 2, 15, 20, 9]
该示例只为说明存在四种不同的定义形式,其中std::ranges::subrange表示一个子范围,因此可以通过不同形式来定义一个新的Range。
第二,Range algo表示支持Ranges的算法。以往的标准算法,都需要指定begin和end迭代器,多是不便。Ranges算法改善了这一现状,例如:
std::vector v1 { 7, 2, 15, 20, 9 };
auto v2(v1);

// sort with STL
std::sort(v1.begin(), v1.end());
fmt::print("sort with STL: {}\n", v1); 

// sort with ranges
std::ranges::sort(v2);
fmt::print("sort with ranges: {}", v2);

//////////
// Output:
sort with STL: [2, 7, 9, 15, 20]
sort with ranges: [2, 7, 9, 15, 20]
可以看到,Ranges算法比STL算法使用起来要更加方便。
第三,Views是一种更加轻便的Ranges,它不拥有任何数据,故其拷贝、移动或赋值都是常数复杂度。通过Views,可以对Ranges进行某些操作,比如在C++17已经引入的针对字符串的std::string_view
这里列举一些常见的Views:
  • std::ranges::take_view

  • std::ranges::filter_view

  • std::ranges::transform_view

  • std::ranges::drop_view

  • std::ranges::join_view

  • std::ranges::split_view

  • std::ranges::keys_view

  • std::ranges::values_view

  • std::ranges::iota_view

这些Views都可以对Ranges进行某种操作,比如filter_view可以过滤元素,transform_view可以对元素进行转换。
并且,它们可以组合使用,执行是惰性的。惰性俗语就是推一步走一步,不需要就不会执行。
最后,Range adaptor指的就是创建Views的简便方式,位于std::views命名空间之下。
如上述Views对应的Adaptors如下:
  • std::views::take

  • std::views::filter

  • std::views::transform

  • std::views::drop

  • std::views::join

  • std::views::split

  • std::views::keys

  • std::views::values

最直观的感受是的确减少了不少字母,表意更加清晰。但这只是其一,事实上,Range adaptors还会对某些Views进行一些优化。例如,若传入一个std::string_view,那么take()将会返回std::string_view,而非take_view
因此,要优先使用这些Adaptors。
总结一下,本节介绍了四个最基本,也是最重要的概念,只有明晰了这些概念,才能明白如何应用。
下面各节,会详细地讲解这些概念更多的内容。

Ranges算法

Ranges的基本组件定义在<ranges>中,而算法定义在<algorithm>中。
基本上常用的STL算法都具有Ranges形式的重载版本,这也导致到了C++20,包含<algorithm>之后的编译时间大大增加。
上节使用过的std::ranges::sort就是其中的算法之一,下面再介绍几个常用的算法。
第一组,std::ranges::all_ofstd::ranges::any_of
看一个简单的示例:
std::vector vec { 1, 2, -1, -2};
auto is_positive = [](int n) { return n > 0; };
auto res_all_of = std::ranges::all_of(vec, is_positive);
auto res_any_of = std::ranges::any_of(vec, is_positive);


fmt::print("vec中的所有元素皆大于0: {}\n", res_all_of);
fmt::print("vec中存在元素大于0:{}\n", res_any_of);

/////////
// Output:
vec中的所有元素皆大于0: false
vec中存在元素大于0:true
效果一目了解,不多作介绍。
第二组,std::ranges::count_ifstd::ranges::find_if
例子如下:
std::vector vec { "monster""monadic""buggy""cooper""resurrent""mono"};        

// std::ranges::count_if
auto res_count_if = std::ranges::count_if(vec, [](const std::string& item) {
    return item.starts_with("mon");
});
fmt::print("以mon开头的元素个数为: {}\n", res_count_if);

// std::ranges::find_if
const auto& res_find_if = std::ranges::find_if(vec, [](const std::string& item) {
    return item.ends_with("er");
});

if(res_find_if != std::end(vec)) {
    fmt::print("首个以er结尾的元素:{}\n", *res_find_if);
}

//////////
// Output:
以mon开头的元素个数为: 3
首个以er结尾的元素:monster
其中,count_if可以统计符合某种predicate的元素个数,find_if可以查找符合某种predicate的第一个元素。
第三个,std::ranges::mismatch
用法如下:
std::string s1 { "ABBCD" };
std::string s2 { "ABBEF" };
auto [n1, n2] = std::ranges::mismatch(s1, s2);
const auto pos = std::distance(std::begin(s1), n1);
fmt::print("s1和s2不匹配位置:{}", pos);

//////////
// Output:
s1和s2不匹配位置:3
该算法用于比较两个Ranges不匹配的位置,返回值为ranges::mismatch
通过返回值中的in1in2可以分别访问两个Ranges中不匹配位置的迭代器,然而通过structure bindings是一种更好的方式。
第四个,std::ranges::search
用法如下:
std::vector v1 { 1, 5, 2, 3, 4, 7, 8 };
std::vector v2 { 2, 3, 4 };

auto res = std::ranges::search(v1, v2);
if(!res.empty()) {
    const auto pos1 = std::distance(v1.begin(), res.begin());
    const auto pos2 = std::distance(v1.begin(), res.end());
    fmt::print("搜索的结果位于{}-{}\n", pos1, pos2);
}

//////////
// Output:
搜索的结果位于2-5
它的作用是在一个Ranges中找到另一个Ranges匹配的位置。
最后再来介绍一个,std::ranges::shuffle
与排序相反,该算法用于打乱元素。用法如下:
std::vector<int> v(10);
std::iota(v.begin(), v.end(), 1);

fmt::print("v: {}\n", v);

std::random_device rd;
std::mt19937 gen{rd()};

std::ranges::shuffle(v, gen);
fmt::print("shuffle v: {}\n", v);

//////////
// Output:
v: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
shuffle v: [4, 7, 8, 1, 6, 10, 2, 3, 9, 5]
其中,std::iota用于自增式生成值元素,指定从1开始。
更多的Ranges算法可以参考https://en.cppreference.com/w/cpp/algorithm。

Views

Views的一大优势是可以组合使用,举个例子:
int main() {
    std::vector<int> v;
    auto is_odd = [](int i) { return i % 2 == 1; };

    for (int i : std::views::iota(1)
                 | std::views::take(20)
                 | std::views::filter(is_odd)) {
        v.push_back(i);
    }

    fmt::print("The answer is: {}", v);
}

// Output:
The answer is: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]    
这里调用了三个Range adaptors函数,它们会创建相应的Views。iota()用于递增地从1开始产生数值,take()截取产生的前20个数值,filter()对截取的数据进行过滤。
普通的函数,要组合这三个操作,只有嵌套调用,或是根据返回值再逐个调用,非常不利用组合使用。
而Views通过提供pipe (|) symbol来标准化函数的组合方式,这是个语法糖。对应如下:
// pipe symbol
A() | B() | C()

// nested syntax
C(B(A()))  
pipe symbol会按照从左往右的顺序执行这些组合的函数。
另一大优势是这些操作都是惰性的,同样举个例子:
std::vector<int> v;

auto filter = [](int i) {
    fmt::print("FILTER\n");
    return i % 2 == 0;
};
auto transform = [](int i) {
    fmt::print("TRANSFORM\n");
    return i * i;
};

auto lazy_range = std::views::iota(1, 10)
            | std::views::filter(filter)
            | std::views::transform(transform);


fmt::print("---lazy range print---\n");
for (auto i : lazy_range) {
    fmt::print("The element is {}\n", i);
}
此处使用了三个Views,iota()filter()在前面已经介绍过,transform()用于对元素进行一些转换操作。
普通的函数,执行到lazy_range这里,就已经计算出了结果。而Views却不一样,只有你需要使用结果的时候,它才会进行计算。
因此,上面的输出结果将为:
---lazy range print---
FILTER
FILTER
TRANSFORM
The element is 4
FILTER
FILTER
TRANSFORM
The element is 16
FILTER
FILTER
TRANSFORM
The element is 36
FILTER
FILTER
TRANSFORM
The element is 64
FILTER
大家可以仔细看看输出的流程。只有当需要获取Views的下一个值时,才会进行计算,这也是为何它支持可以产生无限元素的Views,比如std::views::iota
注意,有些Views定义为const时无法迭代,例如:
auto is_even = [](int i) { return i % 2 == 0; };
const auto view = std::views::iota(1, 10)
            | std::views::filter(is_even);

// ERROR
auto begin = std::ranges::begin(view);                                       
auto end   = std::ranges::end(view); 
可以应该通过auto&&来传递Views,此类Views还有:
  • std::ranges::filter_view

  • std::range::drop_while_view

  • std::ranges::split_view

  • std::ranges::drop_view

  • std::ranges::reverse_view

  • std::ranges::join_view

更多的Views基本用法可以参考https://en.cppreference.com/w/cpp/symbol_index/views。

C++20 Ranges的缺点与局限

C++20 Ranges并不完善,存在不少问题。
比如,尚不支持numeric算法,尚不支持并行算法,使用const修饰时有些Views无法迭代元素,常量约束有时会被打破等等。
许多问题都在即将到来的C++23中被解决,介绍时再来详细说说。

总结

Ranges算是C++20中细节最多的特性之一,本文侧重于介绍基本概念与用法,许多大坑暂未覆盖。
看过本篇,能够辨析Ranges的四个基本概念与掌握基本用法,就算是达到了目的。


- EOF -


加主页君微信,不仅C/C++技能+1

主页君日常还会在个人微信分享C/C++开发学习资源技术文章精选,不定期分享一些有意思的活动岗位内推以及如何用技术做业余项目

加个微信,打开一扇窗


推荐阅读  点击标题可跳转

1、如何更优雅地迭代 std::tuple ?

2、大规模 C++ 编译性能优化系统 OMAX 介绍

3、对 int 变量赋值的操作是原子的吗?为什么?


关注『CPP开发者』

看精选C/C++技术文章

点赞和在看就是最大的支持❤️

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存