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

为了方便诠释, 下面的定义均使用通俗易懂的叙述, 可能与实际定义有所出入, 一切以C++中定义的concept结果为准

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

有命名空间的化简using std::views = std::ranges::views

1. std::ranges中的特征

下图是特征总览

1.1. std::ranges::range

struct Type {
	iterator begin();
	sentinel end();
}
1
2
3
4

要求

• 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>);
1
2
3
4
5

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

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

细化

设有std::ranges::range T, begin返回类型为iterator = std::ranges::iterator_t, end返回类型为sentinel = 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 == 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(); // 可选
}
1
2
3
4
5

要求

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

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

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

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

• std::ranges::disable_sized_range = true
• std::disable_sized_sentinel_for = 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] = subrange;
1

也可以用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++23), 重放
• 对象std::views::cartesian_product(C++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 = 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));
1
2

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

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));
1
2

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

其他语言的迭代器一般自带哨位, 对应到C++来实际上是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([=](auto&& it) {
        return std::forward<decltype(it)>(it) + n;
    });
};
1
2
3
4
5

然后就可有

range | plus(123);
1

3.5.1. 常用的变换实现参考

• with_index: 附加计数器

inline constexpr auto with_index(size_t start = 0) {
    return std::views::transform([index = start](auto&& it) mutable {
        return std::make_tuple(index++, std::forward<decltype(it)>(it));
    });
};
1
2
3
4
5

用法

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

• subtract: 差集

inline constexpr auto subtract(auto&& container) {
    return std::views::filter([cont = std::forward<decltype(container)>(container)](auto&& it) {
        return std::ranges::find(cont, it) == std::ranges::end(cont);
    });
}
1
2
3
4
5

用法

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

• to: 输出到容器 (标准库版本在C++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) };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

用法

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

• on_each_indexed: 附加计数的遍历

inline constexpr auto on_each_indexed(auto&& func, size_t start = 0) {
    return std::views::filter([index = start, func = std::forward<decltype(func)>(func)](auto& value) mutable {
        func(index++, value);
        return true;
    });
}
1
2
3
4
5
6

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

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

5. 迭代器特征

下面是特征关系总览

4.1. std::input_or_output_iterator

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

struct Iter {
    using difference_type = ptrdiff_t;
    MyIter& operator++() { return *this; }
    MyIter operator++(int) { return *this; }
    int operator*() const { return 0; }
};
1
2
3
4
5
6

4.2. std::forward_iterator

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

struct Iter {
    using difference_type = ptrdiff_t;
    using value_type = int;
    MyIter& operator++() { return *this; }
    MyIter operator++(int) { return *this; }
    int operator*() const { return 0; }
    bool operator==(MyIter const& other) const { return true; }
};
1
2
3
4
5
6
7
8

4.3. std::semiregular

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

struct Type {};
1