Реализуйте ленивый генератор как forward_iterator в C++

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 по ссылке.
• Если вам не нужно оборачивать предыдущий MyGeneratorскорее вы просто хотите знать, как написать возможно бесконечный итератор, затем вы можете избавиться от параметра шаблона, сохранить любое иное состояние в итераторе и просто поместить код в состояние advance(),