Реализация генератора в C ++ 0x

Question

Ключевое слово python yield было для меня большой концептуальной абстракцией, позволяющей перевести важные части алгоритма в понятную человеку форму. Ранее мы обсуждали:

Генераторы Python на разных языках

, где был дан ответ для библиотеки Windows только на C ++. Кроме того, я нашел еще один пример использования расширения макросов в вопросе:

Генераторы в C ++ - недопустимое использование нестатического члена данных

Крайность моих знаний в области информатики говорит мне, что функция yield имеет что-то связанное с сопрограммами и монадами, но я не совсем понимаю, как это вписывается в то, что C ++ или C ++ 0x можно выполнить.

Похоже, что в C ++ без использования макро-расширения или волокна (потока) только для Windows, yeild не может быть реализовано. Это правда? Меняется ли вопрос с дополнительными языковыми возможностями C ++ 0x?

Answer 1

Вы можете сопоставить yield механизм python с итераторами C ++.

См. Итератор ввода функции повышения и пример:

Функция Input Input Iterator позволяет создавать итераторы, которые инкапсулируют нулевой объект функции и объект состояния, который отслеживает число приращений итератора. Итератор ввода функции моделирует концепцию InputIterator и полезен для создания ограниченных итераторов ввода.

Как итератор генератора, итератор ввода функции принимает функцию, которая моделирует концепцию генератора (которая в основном является нулевым или объектным объектом с нулевой арностью). Каждое приращение функции Function Input Iterator вызывает функцию генератора и сохраняет значение в итераторе. При разыменовании итератора возвращается сохраненное значение.

Answer 2

yield - это, по сути, способ реализации ограниченной формы сопрограмм.

Если вы хотите достаточно сильно, вы можете (как в «людях») реализовать относительно полные сопрограммы в C, используя setjmp и longjmp.В C ++ вы можете , вероятно, сделать то же самое, хотя я не совсем уверен.Проблема с C ++ заключается в том, чтобы решить, какие dtors выполнять когда.Не случайно, я думаю, что ответ заключается в том, что использование сопрограмм не должно влиять на dtors, но я не особо задумывался об этом.Если предположить, что это правильно, то для C ++ должен работать примерно такой же код, как и для C.

C ++ 0x добавляет полную поддержку потоков и тому подобное.Хотя это может быть неуклюжим и / или увеличивать накладные расходы, почти все, что вы можете надеяться сделать с волокнами, вы также можете делать с потоками.Таким образом, он будет поддерживать идиому чуть более напрямую, поэтому реализация будет намного проще.

Answer 3

Хм Я никогда не использовал генераторы сам, но, насколько я понимаю, вам нужна какая-то функция, которая возвращает итератор, который реализует оператор приращения ++. Псевдокод:

int f(int x) {
    for(int i = 0; i < x; ++i) {
        yield(i);
    }
}

for(iterator it = make_generator(std::bind(f, 5));
    it != generator_end();
    ++it)
{
    do_something(*it);
}

// iterator specialized for the return type of f
template<typename T>
iterator<T> make_generator(Function<T (void)> f) {
    ...
}

Вам нужно будет построить итератор из указателя на функцию f, и вы можете передать любые аргументы в f, используя std::bind.

Теперь на каждой итерации вам нужно в какой-то момент эффективно вызывать f, и функция yield должна выполнить некоторые манипуляции со стеком, чтобы сохранить текущий стек, вернуть полученное значение и восстановить стек при повторном вызове функции. Вам нужно только сохранить стек до точки, где вызывается f (нет необходимости для всего стека), но это может быть сложно реализовать. Возможно, вам придется сохранить указатель стека перед вызовом f, а затем скопировать содержимое (указатель предыдущего стека .. текущий указатель стека) куда-либо.