Эквивалент C ++ шаблону генератора Python

У меня есть пример кода Python, который мне нужно воспроизвести на C ++. Мне не требуется какое-либо конкретное решение (например, решения yield на основе совместной подпрограммы, хотя они также могут быть приемлемыми ответами), мне просто нужно каким-то образом воспроизвести семантику.

питон

Это основной генератор последовательности, явно слишком большой для хранения материализованной версии.

def pair_sequence():
    for i in range(2**32):
        for j in range(2**32):
            yield (i, j)

Цель состоит в том, чтобы поддерживать два экземпляра указанной выше последовательности и выполнять итерацию по ним полусадочно, но по частям. В приведенном ниже примере first_passиспользуется последовательность пар для инициализации буфера, а second_passрегенерируется такая же точная последовательность и снова обрабатывается буфер.

def run():
    seq1 = pair_sequence()
    seq2 = pair_sequence()

    buffer = [0] * 1000
    first_pass(seq1, buffer)
    second_pass(seq2, buffer)
    ... repeat ...

C ++

Единственное, что я могу найти для решения на C ++, - это имитировать yield сопрограммы C ++, но я не нашел хороших справочников о том, как это сделать. Меня также интересуют альтернативные (не общие) решения этой проблемы. У меня недостаточно памяти для хранения копии последовательности между проходами.

Генераторы существуют в C ++ под другим именем: Итераторы ввода . Например, чтение из std::cinаналогично генераторуchar .

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

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

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

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;
};

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

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

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

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

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 Вот генератор, реализованный с сопрограммами Mordor :

#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;
}

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

#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или лямбда должна использоваться для генерации объекта функции, который принимает только один аргумент (из push_type), когда он передается в coro_t::pull_typeконструктор.

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

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

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

// 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();
}

Однако у этого решения есть несколько недостатков:

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

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

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

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

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

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

Примерно так очень похоже:

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;
}

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

Использование 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;
}

Что - то вроде этого :

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

using ull = unsigned long long;

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

    return 0;
}

Напечатает числа от 0 до 99

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

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

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

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;
};      

Этот ответ работает на C (и, следовательно, я думаю, что он работает и на C ++)

#include <stdio.h>

const uint64_t MAX = 1ll<<32;

typedef struct {
    uint64_t i, j;
} Pair;

Pair* generate_pairs()
{
    static uint64_t i = 0;
    static uint64_t j = 0;
    
    Pair p = {i,j};
    if(j++ < MAX)
    {
        return &p;
    }
        else if(++i < MAX)
    {
        p.i++;
        p.j = 0;
        j = 0;
        return &p;
    }
    else
    {
        return NULL;
    }
}

int main()
{
    while(1)
    {
        Pair *p = generate_pairs();
        if(p != NULL)
        {
            //printf("%d,%d\n",p->i,p->j);
        }
        else
        {
            //printf("end");
            break;
        }
    }
    return 0;
}

Это простой, не объектно-ориентированный способ имитации генератора. У меня это сработало, как и ожидалось.

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

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

В частности, поскольку C ++ не имеет естественной абстракции для очереди, вам необходимо использовать конструкции, которые реализуют очередь внутри. Итак, ответ, который дал пример с итераторами, - достойная реализация концепции.

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