如何写一个兼容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;
}

需要什么“东西”？

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

Answer 1

编辑：正如康桐蔚在评论中指出的那样，Tristan Brindle link 在 Cppcon 上提出了一个更好、更清晰的解决方案。

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

根据您的要求，something 必须是 std::ranges::view, meaning it must be a moveable std::ranges::range deriving from 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;
}

输出：

当然，即使std::uint64_t，你也走不了多远。但是 T 可以是任何数字。

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

如何写一个兼容std::ranges的无限序列？

How to write an infinite sequence compatible with std::ranges?

c++

c++20

std-ranges