[C++]std::ranges中的特征和自定义std::ranges::view变换

自C&＃43;&＃43;20起, 基于编译时多态的面向特征(trait)开始流行, 取代了面向对象. 如std::format也全面转向面向特征, 并获得了领先的运行效率和高度自由的扩展能力. 复杂的多继承转变为正交的特征组合, 是面向特征的一大特色

有命名空间的化简using std::views &＃61; std::ranges::views

1. std::ranges中的特征

下图是特征总览

1.1. std::ranges::range

struct Type {
iterator begin();
sentinel end();
}


要求

• std::input_or_output_iterator iterator
• std::semiregular sentinel
• iterator与sentinel可做相等性比较

例子

下面是一个符合要求的std::ranges::range

struct Type {
int* begin();
int* end();
};
static_assert(std::ranges::range<MyType>);


C&＃43;&＃43;20前一般要求begin和end都返回一个迭代器, 在范围库中放宽了限制, 对于end只要能返回一个可比较的对象即可, 不要求对象可做迭代器都可以做的&＃43;&＃43;运算. 因此不再称end返回的对象为迭代器(iterator), 而称之为哨位(sentinel)

可以用std::ranges::iterator_t和std::ranges::sentinel_t从类型T中获取迭代器类型和哨位类型.
如要迭代器类型成立, 只需实现begin
如要哨位类型成立, 除了需要实现end, 还要实现begin

细化

设有std::ranges::range T, begin返回类型为iterator &＃61; std::ranges::iterator_t, end返回类型为sentinel &＃61; std::ranges::sentinel_t

• 如果std::input_iterator iterator, 则有std::ranges::input_range T
• 如果std::output_iterator iterator, 则有std::ranges::output_range T
• 如果std::forward_iterator iterator, 则有std::ranges::forward_range T
• 如果std::bidirectional_iterator iterator, 则有std::ranges::bidirectional_range T
• 如果std::random_access_iterator iterator, 则有std::ranges::random_access_range T
• 如果std::contiguous_iterator iterator, 则有std::ranges::contiguous_range T
• 如果iterator &＃61;&＃61; sentinel, 则有std::ranges::common_range T
• 如果std::ranges::view T或std::ranges::borrowed_range T, 则有std::ranges::viewable_range T

1.2. std::ranges::sized_range

struct Type {
iterator begin();
sentinel begin();
size_t size(); // 可选
}


要求

• std::ranges::range Type
• 提供size函数
• 能常数时间获取范围的长度

如果未提供size函数, 那么还要求

• std::forward_iterator iterator
• iterator与sentinel(及iterator)可作差

如果size或者iterator的作差不能用常数时间实现, 那么可以用特化

• std::ranges::disable_sized_range &＃61; true
• std::disable_sized_sentinel_for &＃61; true

强制关闭std::ranges::sized_range和std::ranges::sized_sentinel_for的特征

1.3. std::ranges::borrowed_range

如果类型std::ranges::range T的值T t的t.begin()和t.end()获得的迭代器的生命周期与t无关, 那么可以认为是std::ranges::borrowed_range

由于语言层面无法自动识别生命周期的关系, 因此要特征能被识别, 还要手动特化std::ranges::enable_borrowed_range为true

但特别地, 类型T&自然满足std::ranges::borrowed_range

1.4. std::ranges::view

如果std::ranges::range的复制只需要常数的时间, 那么可以认为是std::ranges::view
由于语言层面无法自动识别复制所需的时间复杂度, 因此要特征能被识别, 还要手动开启特征

对于std::ranges::range T, 满足以下条件之一, 即认为实现std::ranges::view特征

• 实现std::movable且特化std::ranges::enable_view为true时
• 或继承std::ranges::view_base
• 或继承std::ranges::view_interface

另外如果std::ranges::range T继承std::ranges::view_interface, 那么在T满足一些条件时, 还能自动获得以下函数

• empty(), 要求std::ranges::forward_range T
• operator bool(), 要求std::ranges::forward_range T
• data(), 要求std::contiguous_range T
• size(), 要求std::ranges::forward_range T, 且iterator与sentinel(及iterator)可作差
• front(), 要求std::ranges::forward_range T
• back(), 要求std::ranges::bidirectional_range T且std::ranges::common_range T
• operator[](), 要求std::ranges::random_access_range T

2. std::ranges::subrange 迭代器-哨位对

2.1. 构造

将迭代器(Iterator i)和哨位(Sentinel s)结合为std::ranges::view std::ranges::subrange类型的对象, 满足std::ranges::viewable_ranges, 并且当

• i和s对象可作差
• 或手动指定类型为std::ranges::subrange
• 或显式传递大小参数时

类型还实现std::ranges::sized_range

2.2. 结构化解绑

可以使用结构化解绑获取迭代器和哨位

auto [i, s] &＃61; subrange;


也可以用std::get<0>和std::get<1>分别获取迭代器和哨位

2.3. 操作

以上操作只在迭代器增加/自增时有边界检查

3. std::views中的std::ranges::view变换

3.1. std::ranges::view工厂构造

• 对象std::views::empty, void -> view, 使用std::views::empty即可直接获得对象
• 对象std::views::single, any -> view, 单对象的std::ranges::view
• 对象std::views::iota, iterator | (iterator, sentinel) -> view, 一般哨位边界的有限或无限递增序列
• 对象std::views::counted, (iterator, count) -> view, 计数哨位边界的有限递增序列
• 对象std::views::istream, istream -> 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&＃43;&＃43;23), 重放
• 对象std::views::cartesian_product(C&＃43;&＃43;23), 笛卡尔积
• 等等

3.2. std::views中的变换构造对象

• std::views::all, view -> ref_view | owning_view 借用或占用
• std::views::filter(invokable), input_range & view -> input_range & view 过滤
• std::views::transform(invokable), input_range & view -> input_range & view 映射
• std::views::take(int), view -> subrange 取前一部分
• std::views::join, input_range & view -> input_range & view 展平
• std::views::split(forward_range & view), forward_range & view -> subrange 序列中的指定子序列为分割点划分序列
• std::views::common, view -> common_range 同化iterator_t和sentinel_t的类型, 以兼容旧的库函数

更多可见3.4. 与其他语言的迭代器的变换操作比较

3.3. operator|()的流式变换

std::views中的对象多为二段可调, 部分不需要参数的为一段可调

• 二段可调
  如std::views::take, 一段调用auto c &＃61; std::views::take(10)获得变换c, 之后二段调用c(range)才真正施行变换
• 一段可调
  如std::views::join, 其自身就是变换, 一段调用std::views::join(range)即可施行变换

变换都实现有operator|运算, 可对运算左侧的对象实施变换, 如

range | std::views::all | std::views::common;
/* 等价于 */ std::views::common(std::views::all(range));


二段可调的对象一般不是变换, 需要赋予参数进行一段调用后才能得到变换

range | std::views::take(5) | std::views::filter([](auto const& it) { return true; });
/* 等价于 */ std::views::filter([](auto const& it) { return true; })(std::views::take(5)(range));


3.4. 与其他语言的迭代器的变换操作比较

其他语言的迭代器一般自带哨位, 对应到C&＃43;&＃43;来实际上是std::ranges::range的概念
以kotlin为例 Flow, Channel, Sequence, Iterable的接口对比

3.5. 自定义std::ranges::view变换

可以走以下步骤

• 写一个作为包装适配器的视图类, 至少实现std::ranges::range特征, 最好实现std::ranges::view特征
• 写一个内部的迭代器类, 至少实现std::input_iterator特征
• 如果视图类做变换不需要参数
  写一个可调用对象(函数也行), 接收参数转发给视图类
• 如果视图类做变换需要参数
  写一个二段可调的可调用对象, 首次调用时传入参数做绑定, 二次调用时接收被变换的std::ranges::range, 转发给视图类

通常情况下, 都可以借助std::views::transform等基本工具来创建自定义变换, 如

inline constexpr auto plus(int n) {
return std::views::transform([&＃61;](auto&& it) {
return std::forward<decltype(it)>(it) &＃43; n;
});
};


然后就可有

range | plus(123);


3.5.1. 常用的变换实现参考

• with_index: 附加计数器

inline constexpr auto with_index(size_t start &＃61; 0) {
return std::views::transform([index &＃61; start](auto&& it) mutable {
return std::make_tuple(index&＃43;&＃43;, std::forward<decltype(it)>(it));
});
};


用法

for (auto const& [index, value] : range | with_index()) {}


• subtract: 差集

inline constexpr auto subtract(auto&& container) {
return std::views::filter([cont &＃61; std::forward<decltype(container)>(container)](auto&& it) {
return std::ranges::find(cont, it) &＃61;&＃61; std::ranges::end(cont);
});
}


用法

range | subtract(std::array{ v1, v2, v3 });


• to: 输出到容器 (标准库版本在C&＃43;&＃43;23实现) (只处理右值, 未正确处理左值引用)

template<typename Cont>
struct ToFn {
auto operator()(std::ranges::range auto&& r) {
std::ranges::copy(std::forward<decltype(r)>(r), std::back_inserter(cont));
return std::move(cont);
}
Cont cont;
};
template<typename Cont>
auto operator|(std::ranges::range auto&& r, ToFn<Cont>&& toFn) {
return std::move(toFn)(std::forward<decltype(r)>(r));
}
inline constexpr auto to(auto&& container) {
return ToFn<decltype(container)>{ std::forward<decltype(container)>(container) };
}


用法

auto vec &＃61; std::array{1, 2, 3} | to(std::vector<int>{});


• on_each_indexed: 附加计数的遍历

inline constexpr auto on_each_indexed(auto&& func, size_t start &＃61; 0) {
return std::views::filter([index &＃61; start, func &＃61; std::forward<decltype(func)>(func)](auto& value) mutable {
func(index&＃43;&＃43;, value);
return true;
});
}


注: 变换一般为惰性的, 需要用for遍历激活流, 否则流的计算不会触发
用法

for (auto const& item : arr | on_each_indexed([](size_t index, auto& value) {
std::cout << index << ":" << value << ",";
})) {}


5. 迭代器特征

下面是特征关系总览

4.1. std::input_or_output_iterator

下面是一个符合要求的std::input_or_output_iterator

struct Iter {
using difference_type &＃61; ptrdiff_t;
MyIter& operator&＃43;&＃43;() { return *this; }
MyIter operator&＃43;&＃43;(int) { return *this; }
int operator*() const { return 0; }
};


4.2. std::forward_iterator

下面是一个符合要求的std::forward_iterator

struct Iter {
using difference_type &＃61; ptrdiff_t;
using value_type &＃61; int;
MyIter& operator&＃43;&＃43;() { return *this; }
MyIter operator&＃43;&＃43;(int) { return *this; }
int operator*() const { return 0; }
bool operator&＃61;&＃61;(MyIter const& other) const { return true; }
};


4.3. std::semiregular

下面是一个符合要求的std::semiregular类

struct Type {};