c++ - 在 C++ 中将惰性生成器实现为 forward_iterator

Question

MyGenerator 代表一个(可能)有限的整数序列，计算起来很昂贵。所以我不想预先生成它们并将它们放入容器中。

struct MyGenerator{
  bool HasNext();
  int Next();
}

全部打印:

MyGenerator generator;
while (generator.HasNext()) {
  std::cout << generator.Next() << std::endl;
}

如何实现类似的遵循 forward_iterator 协议(protocol)的生成器？

boost::function_input_iterator接近，但我不知道预先元素的数量。

Answer 1

首先，查看boost::function_input_iterator 的实现，因为您想要的是相同的，只是必须修改测试迭代器的相等性以应对您不知道的事实它是否是无限的，如果不是，有多少项目。一旦您习惯了这种风格，Boost 的作者将通过他们的代码为您提供比我更好的建议:-)

就是说，沿着这些思路(未经测试):

template <typename Generator>
struct generator_iterator : iterator<forward_iterator_tag, int> {
    generator_iterator(const Generator &gen, end = false) : count(0), gen(gen), last_val(0), is_end(end) {
        if (!end) advance();
    }
    void advance() {
        if (gen.HasNext()) {
            lastval = gen.Next();
        } else {
            is_end = True;
        }
        count += 1;
    }
    int operator *() {
        return lastval;
    }
    generator_iterator &operator++() {
        advance();
        return *this;
    }
    generator_iterator operator++(int) {
        generator_iterator result = *this;
        advance();
        return result;
    }
    bool operator==(const generator_iterator &rhs) {
        return (is_end && rhs.is_end) || (count == rhs.count);
    }
    bool operator!=(const generator_iterator &rhs) {
        return !(*this == rhs);
   }

    size_t count;
    Generator gen;
    int lastval;
    bool is_end; 
};

• 原则上，计数可以换行，尽管您只需要在使用较小的 size_t 的实现上担心这一点，因为 64 位在实践中永远不会换行。为了安全起见，您可以使用不同的类型来保持计数:uint64_t 或者如果所有其他类型都属于用户定义的大整数类型。不过，请参阅 std::iterator 文档，因为一旦迭代器运行时间超过 size_t，您就想给它一个非默认的 difference_type。
• 类型 Generator 必须是可复制的(并且拷贝必须与原始状态相同，并且之后两者必须独立前进)否则你没有机会实现 forward_iterator 除了存储来自生成器的潜在无限数量的输出。如果您只需要一个input_iterator，那么您可以通过引用来引用Generator。
• 如果您不需要包装之前的 MyGenerator，而只想知道如何编写一个可能无限的迭代器，那么您可以去掉模板参数，存储任何状态你喜欢在迭代器中，只需将代码放入 advance() 中即可。