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

Question

MyGenerator 表示（可能）有限的整数序列，计算成本很高。所以我不想预先生成它们并将它们放入容器中。

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

要打印全部：

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

如何实现一个遵循forward_iterator协议的类似生成器？

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参考。
• 如果您不需要包装 previous MyGenerator，而是只想知道如何编写可能无限的迭代器，那么您可以摆脱模板参数，在迭代器中存储您喜欢的任何状态，然后只需放置代码推动国家进步advance()。