[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();
}

要求

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

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

细化

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

要求

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

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

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

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

• std::ranges::disable_sized_range<T> = true
• std::disable_sized_sentinel_for<iterator, iterator> = 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<T>为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<T>为true时
• 或继承std::ranges::view_base
• 或继承std::ranges::view_interface<T>

另外如果std::ranges::range T继承std::ranges::view_interface<T>, 那么在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<Iterator, Sentinel>类型的对象, 满足std::ranges::viewable_ranges, 并且当

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

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

2.2. 结构化解绑

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

auto [i, s] = subrange;

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

2.3. 操作

函数名	操作简介	返回值	要求
next	增加迭代器	新的std::ranges::subrange	std::ranges::forward_iterator Iterator
prev	减少迭代器	新的std::ranges::subrange	std::ranges::bidirectional_iterator Iterator
advance	自增/自减迭代器	自身	无

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

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

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

• 对象std::views::empty, void -> view, 使用std::views::empty<T>即可直接获得对象
• 对象std::views::single, any -> view, 单对象的std::ranges::view
• 对象std::views::iota, iterator | (iterator, sentinel) -> view, 一般哨位边界的有限或无限递增序列
• 对象std::views::counted, (iterator, count) -> view, 计数哨位边界的有限递增序列
• 对象std::views::istream<T>, istream<T> -> 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<input_range> & view -> input_range & view 展平
• std::views::split(forward_range & view), forward_range & view -> subrange<forward_range & view> 序列中的指定子序列为分割点划分序列
• 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));

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

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++来实际上是std::ranges::range的概念
以kotlin为例 Flow, Channel, Sequence, Iterable的接口对比

-	kotlin Iterator/Sequence	C++20
编号	withIndex	/
遍历	onEach forEach	/ std::ranges::for_each
取值	first last single	front back std::views::single(front())
查值	contains elementAt find findLast indexOf	contains (部分) operator[] std::ranges::find std::ranges::find_if std::ranges::find_end /
归约	fold reduce scan toXxx	std::accumulate / / std::views::to (C++23)
统计	count all any none average maxOf minOf sum	std::ranges::count std::ranges::count_if std::ranges::all_of std::ranges::any_of std::ranges::none_of / std::max_element std::min_element /
Map化	associate groupBy	/ /
拣选	Map.keys Map.values /	std::views::keys std::views::values std::views::element
局部	take takeWhile drop dropWhile windowed /	std::views::take std::views::take_while std::views::drop std::views::drop_while / std::views::stride (C++23)
过滤	filter	std::views::filter
映射	map / /	std::views::transform std::views::zip_transform (C++23) std::views::adjacent_transform (C++23)
组合	zip zipWithNext / /	std::views::zip (C++23) / std::views::slide (C++23) std::views::adjacent (C++23)
解配对	unzip	/
合并	plus	/
二分	partition	std::ranges::partition
平坦化	flatMap flatten joinTo	/ std::views::join std::views::join_with
拆分	String.split	std::views::split std::views::lazy_split
内组合	chunked /	std::views::chunk (C++23) std::views::chunk_by (C++23)
值去抖	distinct	/
集合运算	minus intersect subtract union	/ / / /
重排	shuffled sorted reverse	std::ranges::shuffle / std::views::reverse

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;
    });
};

然后就可有

range | plus(123);

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));
    });
};

用法

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

• 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);
    });
}

用法

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

• 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) };
}

用法

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

• 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;
    });
}

注: 变换一般为惰性的, 需要用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 = ptrdiff_t;
    MyIter& operator++() { return *this; }
    MyIter operator++(int) { return *this; }
    int operator*() const { return 0; }
};

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; }
};

4.3. std::semiregular

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

struct Type {};