c++ - 如何编写与 std::ranges 兼容的无限序列？

Question

我想编写一个结构，它将以与 std::ranges 和范围适配器兼容的方式生成无限的斐波那契数列。

所以如果我想要前 5 个偶数斐波那契数，我会这样写:

#include <iostream>
#include <ranges>

using namespace std;

int main() {
  auto is_even = [](auto a) { return a % 2 == 0; };
  for (auto v :
       something | ranges::views::filter(is_even) | ranges::views::take(5))
    std::cout << v << std::endl;

  return 0;
}

需要什么“东西”？

在我看来，它必须是一个带有前向迭代器的类，但我找不到任何示例。

Answer 1

编辑:正如康桐蔚在评论中所指出的那样，在 Cppcon，link 上提出了一个更好、更简洁的解决方案。 , 特里斯坦·布林德尔 (Tristan Brindle)。

我认为这可以作为制作自定义基于迭代器的生成器的快速引用。

根据您的要求，something必须是 std::ranges::view ，这意味着它必须是可移动的 std::ranges::range 源自 std::ranges::view_interface<something> .

我们可以通过以下方式解决所有这三个问题:

#include <ranges>

template<typename T>
class fib : public std::ranges::view_interface<fib<T>>{
public:
    struct iterator;


    auto begin() const { return iterator{}; }
    auto end() const { return std::unreachable_sentinel; }

};

公告 std::unreachable_sentinel 这使得创建没有尽头的序列变得非常简单。

我们仍然必须定义执行实际工作的迭代器。在你的情况下，我们想要 fib成为值的“来源”，所以我们的迭代器实际上应该是 std::input_iterator .为此需要一些样板代码，但它基本上只是一种可以递增和取消引用以产生其当前值的类型。

像这样的事情会做:

#include <iterator>

template<typename T>
struct fib<T>::iterator {
    using iterator_category = std::input_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T;

    constexpr iterator() noexcept = default;

    iterator& operator++() {
        auto old_next = next;
        next = next + current;
        current = old_next;

        return *this;
    }

    iterator operator++(int) {
        iterator current{*this};
        ++(*this);
        return current;
    }

    value_type operator*() const {
        return current;
    }

    bool operator==(const iterator& other) const { return current == other.current && next==other.next; }

private:
    T current= {};
    T next = T{} + 1; // Could perhaps be fancier.
};

增量运算符自己进行计算，这是一种简单的迭代算法。

就是这样，这是一个工作示例:

#include <cstdint>
#include <iostream>
int main() {
  auto is_even = [](auto a) { return a % 2 == 0; };
  for (auto v :
       fib<std::uint64_t>{} | std::ranges::views::filter(is_even) | std::ranges::views::take(10))
    std::cout << v << std::endl;

  return 0;
}

哪些输出:

0
2
8
34
144
610
2584
10946
46368
196418

当然，即使使用 std::uint64_t 也不会走得太远.但是T可以是任何足够的数字。

可以很容易地将迭代器泛化为包含有状态仿函数，可能是从范围本身传递的，在每次递增期间调用它并存储产生的值以供以后取消引用。这将是一种非常粗糙但简单的方式，至少可以模拟“基于 yield 的”生成器。