Ranges 实战进阶
Ranges 实战进阶
🚀 Ranges 实战进阶：滑动窗口、zip_view、协程结合与性能分析
🧊 1. 实战：用 ranges 实现滑动窗口最大值（Monotonic Queue）
滑动窗口问题是算法题常客，比如 LeetCode 239：
给定数组 nums 和窗口大小 k，返回每个窗口内的最大值。
我们可以使用 ranges + 自定义 view 实现一个惰性滑动窗口视图。
✨ 目标接口：
1auto r = sliding_window(v, 3);
🧩 自定义 sliding_window view：
1template <std::ranges::view V>
2requires std::ranges::forward_range<V>
3class sliding_window_view : public std::ranges::view_interface<sliding_window_view<V>> {
4 V base_;
5 size_t k_;
6
7public:
8 sliding_window_view(V base, size_t k) : base_(std::move(base)), k_(k) {}
9
10 struct iterator {
11 std::ranges::iterator_t<V> first, last, end;
12 size_t k;
13
14 bool operator!=(const iterator& other) const {
15 return first != other.first;
16 }
17
18 auto operator*() const {
19 return std::ranges::subrange(first, last);
20 }
21
22 iterator& operator++() {
23 ++first;
24 ++last;
25 return *this;
26 }
27 };
28
29 auto begin() {
30 auto first = std::ranges::begin(base_);
31 auto last = first;
32 std::ranges::advance(last, std::min(k_, std::ranges::distance(first, std::ranges::end(base_))));
33 return iterator{first, last, std::ranges::end(base_), k_};
34 }
35
36 auto end() {
37 auto e = std::ranges::end(base_);
38 return iterator{e, e, e, k_};
39 }
40};
41
42template <std::ranges::viewable_range R>
43auto sliding_window(R&& r, size_t k) {
44 return sliding_window_view<std::ranges::views::all_t<R>>(std::views::all(std::forward<R>(r)), k);
45}
✅ 用法：
1std::vector<int> v{1, 3, -1, -3, 5, 3, 6, 7};
2
3for (auto w : sliding_window(v, 3)) {
4 int max = *std::ranges::max_element(w);
5 std::cout << max << " ";
6}
7// 输出: 3 3 5 5 6 7
🔗 2. 实现一个简版 zip_view
标准库暂未实现 views::zip，我们可以用结构绑定自定义一个。
💡 核心思想：
并行遍历两个或多个范围，组合成一个 tuple 或 pair。
🚧 简化 zip_view（仅支持两个 range）
1template <std::ranges::input_range R1, std::ranges::input_range R2>
2class zip_view {
3 R1 r1_;
4 R2 r2_;
5
6public:
7 zip_view(R1 r1, R2 r2) : r1_(std::move(r1)), r2_(std::move(r2)) {}
8
9 struct iterator {
10 std::ranges::iterator_t<R1> it1;
11 std::ranges::iterator_t<R2> it2;
12
13 auto operator*() const {
14 return std::pair(*it1, *it2);
15 }
16
17 iterator& operator++() {
18 ++it1;
19 ++it2;
20 return *this;
21 }
22
23 bool operator!=(const iterator& other) const {
24 return it1 != other.it1 && it2 != other.it2;
25 }
26 };
27
28 iterator begin() {
29 return {std::ranges::begin(r1_), std::ranges::begin(r2_)};
30 }
31
32 iterator end() {
33 return {std::ranges::end(r1_), std::ranges::end(r2_)};
34 }
35};
36
37template <std::ranges::viewable_range R1, std::ranges::viewable_range R2>
38auto zip(R1&& r1, R2&& r2) {
39 return zip_view<std::ranges::views::all_t<R1>, std::ranges::views::all_t<R2>>(
40 std::views::all(std::forward<R1>(r1)), std::views::all(std::forward<R2>(r2)));
41}
✅ 用法：
1std::vector<int> a{1, 2, 3};
2std::vector<std::string> b{"one", "two", "three"};
3
4for (auto [x, y] : zip(a, b)) {
5 std::cout << x << ": " << y << "\n";
6}
🌈 3. 与协程结合的展望（C++20）
C++20 的协程与 ranges 是天然搭档。例如你可以编写 generator<T>：
1generator<int> iota(int start, int end) {
2 for (int i = start; i < end; ++i)
3 co_yield i;
4}
然后包装为一个 view，实现懒惰无限序列、异步生成等。
目前标准库并未集成 coroutine-ranges，但 cppcoro, generator 等库已经实现了类似功能，未来 C++26 将会加强这种支持。
📊 4. 性能与对比分析
| 项目 | 传统 STL | ranges 写法 |
|---|---|---|
| 可读性 | 中 | 高（更像自然语言） |
| 组合性 | 低 | 高（管道链式） |
| 惰性计算 | 无 | ✅ 默认惰性 |
| 性能 | 稍快 | 与 STL 相近（懒惰 + inline） |
| Debug 类型 | 简单 | ❗可能复杂（需配合 decltype(auto)） |
| 拓展能力 | 需手写 | ✅ 可组合 views、自定义 view |
✅ 推荐实践：在性能要求不极端的情况下，优先使用
ranges，写法更现代、语义更清晰。
📘 最终总结（完整版）
| 分类 | 内容 |
|---|---|
| ranges 算法 | ranges::sort, ranges::find, ranges::copy 等 |
| views | filter, transform, take, drop, iota, reverse |
| 链式组合 | `r |
| 自定义 view | 可扩展行为（如滑窗、分组等） |
| zip_view / sliding_window | 实现复合逻辑 |
| range concepts | 用于模板约束或接口泛化 |
| 协程结合 | 可构建惰性数据流（未来趋势） |
| 容器转换 | to<vector>() 或 vector(r.begin(), r.end()) |
| 性能建议 | 惰性默认行为，适合大数据惰性处理场景 |
最后修改于 2025-07-08 18:57