4

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

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

全部打印：

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

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

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

4

1 回答 1

3

首先，看看 的实现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您想要给它一个 non-default 的时间difference_type。
  • 该类型Generator必须是可复制的（并且副本必须与原始具有相同的状态，并且之后两者必须独立前进）否则您将没有机会实现一个，forward_iterator除非存储来自生成器的潜在无限量的输出。如果您只需要 aninput_iterator那么您可以参考Generatorby reference。
  • 如果您不需要包装 previous MyGenerator，而只是想知道如何编写一个可能无限的迭代器，那么您可以摆脱模板参数，将您喜欢的任何状态存储在迭代器中，然后将代码推进国家advance()。
于 2014-12-22T14:24:56.217 回答