Эквивалентная структура генератора Python для С++

Ответ 1

Генераторы существуют в С++, просто под другим именем: Input Iterators. Например, чтение из std::cin похоже на генератор char.

Вам просто нужно понять, что делает генератор:

• есть blob данных: локальные переменные определяют состояние
• существует метод init
• существует следующий метод
• существует способ передачи сигнала

В вашем тривиальном примере это достаточно просто. Концептуально:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Конечно, мы завершаем это как правильный класс:

class PairSequence:
    // (implicit aliases)
    public std::iterator<
        std::input_iterator_tag,
        std::pair<unsigned, unsigned>
    >
{
  // C++03
  typedef void (PairSequence::*BoolLike)();
  void non_comparable();
public:
  // C++11 (explicit aliases)
  using iterator_category = std::input_iterator_tag;
  using value_type = std::pair<unsigned, unsigned>;
  using reference = value_type const&;
  using pointer = value_type const*;
  using difference_type = ptrdiff_t;

  // C++03 (explicit aliases)
  typedef std::input_iterator_tag iterator_category;
  typedef std::pair<unsigned, unsigned> value_type;
  typedef value_type const& reference;
  typedef value_type const* pointer;
  typedef ptrdiff_t difference_type;

  PairSequence(): done(false) {}

  // C++11
  explicit operator bool() const { return !done; }

  // C++03
  // Safe Bool idiom
  operator BoolLike() const {
    return done ? 0 : &PairSequence::non_comparable;
  }

  reference operator*() const { return ij; }
  pointer operator->() const { return &ij; }

  PairSequence& operator++() {
    static unsigned const Max = std::numeric_limts<unsigned>::max();

    assert(!done);

    if (ij.second != Max) { ++ij.second; return *this; }
    if (ij.first != Max) { ij.second = 0; ++ij.first; return *this; }

    done = true;
    return *this;
  }

  PairSequence operator++(int) {
    PairSequence const tmp(*this);
    ++*this;
    return tmp;
  }

private:
  bool done;
  value_type ij;
};

Так что ж, да... может быть, что С++ немного более подробный:)

Ответ 2

В C++ есть итераторы, но реализация итератора не проста: нужно обратиться к концепциям итератора и тщательно спроектировать новый класс итератора для их реализации. К счастью, в Boost есть шаблон iterator_facade, который должен помочь в реализации итераторов и генераторов, совместимых с итераторами.

Иногда для реализации итератора можно использовать сопрограмму без стеков.

PS См. Также эту статью, в которой упоминаются как хакерский switch Кристофера М. Колхоффа, так и Boost.Coroutine Оливером Ковальке. Работа Оливера Ковальке является продолжением Boost.Coroutine Джованни П. Деретта.

PS Думаю, вы также можете написать некий генератор с лямбдами:

std::function<int()> generator = []{
  int i = 0;
  return [=]() mutable {
    return i < 10 ? i++ : -1;
  };
}();
int ret = 0; while ((ret = generator()) != -1) std::cout << "generator: " << ret << std::endl;

Или с функтором:

struct generator_t {
  int i = 0;
  int operator() () {
    return i < 10 ? i++ : -1;
  }
} generator;
int ret = 0; while ((ret = generator()) != -1) std::cout << "generator: " << ret << std::endl;

PS Здесь генератор реализован с сопрограммами Мордора:

#include <iostream>
using std::cout; using std::endl;
#include <mordor/coroutine.h>
using Mordor::Coroutine; using Mordor::Fiber;

void testMordor() {
  Coroutine<int> coro ([](Coroutine<int>& self) {
    int i = 0; while (i < 9) self.yield (i++);
  });
  for (int i = coro.call(); coro.state() != Fiber::TERM; i = coro.call()) cout << i << endl;
}

Ответ 3

Так как Boost.Coroutine2 теперь поддерживает его очень хорошо (я нашел его, потому что я хотел решить точно такую ​​же проблему yield), я отправляю код на С++ который соответствует вашему первоначальному намерению:

#include <stdint.h>
#include <iostream>
#include <memory>
#include <boost/coroutine2/all.hpp>

typedef boost::coroutines2::coroutine<std::pair<uint16_t, uint16_t>> coro_t;

void pair_sequence(coro_t::push_type& yield)
{
    uint16_t i = 0;
    uint16_t j = 0;
    for (;;) {
        for (;;) {
            yield(std::make_pair(i, j));
            if (++j == 0)
                break;
        }
        if (++i == 0)
            break;
    }
}

int main()
{
    coro_t::pull_type seq(boost::coroutines2::fixedsize_stack(),
                          pair_sequence);
    for (auto pair : seq) {
        print_pair(pair);
    }
    //while (seq) {
    //    print_pair(seq.get());
    //    seq();
    //}
}

В этом примере pair_sequence не принимает дополнительных аргументов. Если это необходимо, std::bind или lambda следует использовать для создания объекта функции, который принимает только один аргумент (из push_type), когда он передается конструктору coro_t::pull_type.

Ответ 4

Вероятно, вы должны проверить генераторы в std:: experimental в Visual Studio 2015, например: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

Я думаю, это именно то, что вы ищете. Общие генераторы должны быть доступны на С++ 17, поскольку это только экспериментальная функция Microsoft VC.

Ответ 5

Все ответы, связанные с написанием собственного итератора, полностью ошибочны. Такие ответы полностью упускают суть генераторов Python (одна из самых больших и уникальных функций языка). Самое главное в генераторах - это то, что исполнение забирает место, где оно остановилось. Это не происходит с итераторами. Вместо этого вы должны вручную хранить информацию о состоянии, так что, когда оператор ++ или оператор * вызывается заново, правильная информация находится на месте в самом начале следующего вызова функции. Вот почему писать свой собственный итератор С++ - это гигантская боль; тогда как генераторы элегантны и легко читаются + пишут.

Я не думаю, что есть хороший аналог для генераторов Python в родном С++, по крайней мере, пока нет (есть рум, который yield приземлится C++ 17). Вы можете получить что-то подобное, обратившись к стороннему (например, предложение Yongwei Boost) или сворачивая свои собственные.

Я бы сказал, что самое близкое в родном С++ - это потоки. Поток может поддерживать приостановленный набор локальных переменных и может продолжать выполнение там, где он был остановлен, очень похожий на генераторы, но вам нужно отбросить немного дополнительной инфраструктуры для поддержки связи между объектом-генератором и его вызывающим. Например.

// Infrastructure

template <typename Element>
class Channel { ... };

// Application

using IntPair = std::pair<int, int>;

void yield_pairs(int end_i, int end_j, Channel<IntPair>* out) {
  for (int i = 0; i < end_i; ++i) {
    for (int j = 0; j < end_j; ++j) {
      out->send(IntPair{i, j});  // "yield"
    }
  }
  out->close();
}

void MyApp() {
  Channel<IntPair> pairs;
  std::thread generator(yield_pairs, 32, 32, &pairs);
  for (IntPair pair : pairs) {
    UsePair(pair);
  }
  generator.join();
}

Это решение имеет несколько недостатков:

• Темы "дорогие". Большинство людей считают это "экстравагантным" использованием потоков, особенно когда ваш генератор настолько прост.
• Есть несколько действий по очистке, которые вам нужно запомнить. Они могут быть автоматизированы, но вам понадобится еще больше инфраструктуры, которая снова, скорее всего, будет считаться "слишком экстравагантной". В любом случае, очистка, которая вам нужна:
  • для улицы > близко()
  • generator.join()
• Это не позволяет остановить генератор. Вы можете внести некоторые изменения, чтобы добавить эту способность, но она добавляет беспорядок в код. Он никогда не был бы таким же чистым, как утверждение yield Python.
• В дополнение к 2, есть другие бит шаблона, которые необходимы каждый раз, когда вы хотите "создать экземпляр" объекта генератора:
  • Параметр канала * out
  • Дополнительные переменные в главном: пары, генератор

Ответ 6

Если вам нужно сделать это только для относительно небольшого числа определенных генераторов, вы можете реализовать их как класс, где данные элемента эквивалентны локальным переменным функции генератора Python. Затем у вас есть следующая функция, которая возвращает следующую вещь, которую даст генератор, обновляя внутреннее состояние, когда оно это делает.

В основном это похоже на то, как реализованы генераторы Python. Основное различие заключается в том, что они могут помнить смещение в байт-код для функции генератора как часть "внутреннего состояния", что означает, что генераторы могут быть записаны как циклы, содержащие выходы. Вы должны были бы вычислить следующее значение из предыдущего. В случае вашего pair_sequence, это довольно тривиально. Это может быть не для сложных генераторов.

Вам также необходимо указать способ завершения. Если вы возвращаете "pointer-like", а NULL не должно быть допустимым допустимым значением, вы можете использовать указатель NULL в качестве индикатора завершения. В противном случае вам нужен сигнал вне диапазона.

Ответ 7

Что-то вроде этого очень похоже:

struct pair_sequence
{
    typedef pair<unsigned int, unsigned int> result_type;
    static const unsigned int limit = numeric_limits<unsigned int>::max()

    pair_sequence() : i(0), j(0) {}

    result_type operator()()
    {
        result_type r(i, j);
        if(j < limit) j++;
        else if(i < limit)
        {
          j = 0;
          i++;
        }
        else throw out_of_range("end of iteration");
    }

    private:
        unsigned int i;
        unsigned int j;
}

Использование оператора() - это только вопрос того, что вы хотите сделать с этим генератором, вы также можете создать его как поток и убедиться, что он адаптируется к istream_iterator, например.

Ответ 8

Используя range-v3:

#include <iostream>
#include <tuple>
#include <range/v3/all.hpp>

using namespace std;
using namespace ranges;

auto generator = [x = view::iota(0) | view::take(3)] {
    return view::cartesian_product(x, x);
};

int main () {
    for (auto x : generator()) {
        cout << get<0>(x) << ", " << get<1>(x) << endl;
    }

    return 0;
}

Ответ 9

Что-то вроде this:

Пример использования:

using ull = unsigned long long;

auto main() -> int {
    for (ull val : range_t<ull>(100)) {
        std::cout << val << std::endl;
    }

    return 0;
}

Будут напечатаны цифры от 0 до 99

Ответ 10

Что ж, сегодня я также искал простую реализацию коллекции под С++ 11. На самом деле я был разочарован, потому что все, что я нашел, слишком далеко от таких вещей, как генераторы Python или оператор С# yield... или слишком сложно.

Цель состоит в том, чтобы сделать коллекцию, которая будет излучать свои предметы только тогда, когда это требуется.

Я хотел, чтобы это было так:

auto emitter = on_range<int>(a, b).yield(
    [](int i) {
         /* do something with i */
         return i * 2;
    });

Я нашел этот пост, ИМХО лучший ответ был о boost.coroutine2, автор Yongwei Wu. Так как это самое близкое к тому, что хотел автор.

Стоит учиться повышенным процедурам. А я, наверное, буду заниматься по выходным. Но пока я использую свою очень маленькую реализацию. Надеюсь, это поможет кому-то еще.

Ниже приведен пример использования, а затем реализация.

Example.cpp

#include <iostream>
#include "Generator.h"
int main() {
    typedef std::pair<int, int> res_t;

    auto emitter = Generator<res_t, int>::on_range(0, 3)
        .yield([](int i) {
            return std::make_pair(i, i * i);
        });

    for (auto kv : emitter) {
        std::cout << kv.first << "^2 = " << kv.second << std::endl;
    }

    return 0;
}

Generator.h

template<typename ResTy, typename IndexTy>
struct yield_function{
    typedef std::function<ResTy(IndexTy)> type;
};

template<typename ResTy, typename IndexTy>
class YieldConstIterator {
public:
    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;

    typedef YieldConstIterator<ResTy, IndexTy> mytype_t;
    typedef ResTy value_type;

    YieldConstIterator(index_t index, yield_function_t yieldFunction) :
            mIndex(index),
            mYieldFunction(yieldFunction) {}

    mytype_t &operator++() {
        ++mIndex;
        return *this;
    }

    const value_type operator*() const {
        return mYieldFunction(mIndex);
    }

    bool operator!=(const mytype_t &r) const {
        return mIndex != r.mIndex;
    }

protected:

    index_t mIndex;
    yield_function_t mYieldFunction;
};

template<typename ResTy, typename IndexTy>
class YieldIterator : public YieldConstIterator<ResTy, IndexTy> {
public:

    typedef YieldConstIterator<ResTy, IndexTy> parent_t;

    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;
    typedef ResTy value_type;

    YieldIterator(index_t index, yield_function_t yieldFunction) :
            parent_t(index, yieldFunction) {}

    value_type operator*() {
        return parent_t::mYieldFunction(parent_t::mIndex);
    }
};

template<typename IndexTy>
struct Range {
public:
    typedef IndexTy index_t;
    typedef Range<IndexTy> mytype_t;

    index_t begin;
    index_t end;
};

template<typename ResTy, typename IndexTy>
class GeneratorCollection {
public:

    typedef Range<IndexTy> range_t;

    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;
    typedef YieldIterator<ResTy, IndexTy> iterator;
    typedef YieldConstIterator<ResTy, IndexTy> const_iterator;

    GeneratorCollection(range_t range, const yield_function_t &yieldF) :
            mRange(range),
            mYieldFunction(yieldF) {}

    iterator begin() {
        return iterator(mRange.begin, mYieldFunction);
    }

    iterator end() {
        return iterator(mRange.end, mYieldFunction);
    }

    const_iterator begin() const {
        return const_iterator(mRange.begin, mYieldFunction);
    }

    const_iterator end() const {
        return const_iterator(mRange.end, mYieldFunction);
    }

private:
    range_t mRange;
    yield_function_t mYieldFunction;
};

template<typename ResTy, typename IndexTy>
class Generator {
public:
    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;

    typedef Generator<ResTy, IndexTy> mytype_t;
    typedef Range<IndexTy> parent_t;
    typedef GeneratorCollection<ResTy, IndexTy> finalized_emitter_t;
    typedef  Range<IndexTy> range_t;

protected:
    Generator(range_t range) : mRange(range) {}
public:
    static mytype_t on_range(index_t begin, index_t end) {
        return mytype_t({ begin, end });
    }

    finalized_emitter_t yield(yield_function_t f) {
        return finalized_emitter_t(mRange, f);
    }
protected:

    range_t mRange;
};      

Ответ 11

Так же, как функция имитирует концепцию стека, генераторы имитируют концепцию очереди. Остальное - семантика.

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

Более конкретно, поскольку С++ не имеет естественной абстракции для очереди, вам нужно использовать конструкции, которые реализуют очередь внутри. Таким образом, ответ, который привел пример с итераторами, является достойной реализацией концепции.

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