boost — реализовать ленивый генератор как forward_iterator в переполнении стека

MyGenerator представляет (возможно) конечную последовательность целых чисел, которая является дорогой для вычисления. Поэтому я не хочу генерировать их все заранее и поместить в контейнер.

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

Чтобы напечатать их все:

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

Как реализовать аналогичный генератор, который следует протоколу forward_iterator?

повышение :: function_input_iterator подходит близко, но я не знаю количество элементов заранее.

4

Решение

Прежде всего, посмотрите на реализацию 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(),
3

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector