Patrón generador de C ++ equivalente a Python

Tengo un código de Python de ejemplo que necesito imitar en C ++. No necesito ninguna solución específica (como soluciones de rendimiento basadas en co-rutinas, aunque también serían respuestas aceptables), simplemente necesito reproducir la semántica de alguna manera.

Pitón

Este es un generador de secuencias básico, claramente demasiado grande para almacenar una versión materializada.

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

El objetivo es mantener dos instancias de la secuencia anterior e iterar sobre ellas en semicerrado, pero en partes. En el siguiente ejemplo, el first_passusa la secuencia de pares para inicializar el búfer, y second_passregenera la misma secuencia exacta y procesa el búfer nuevamente.

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

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

C ++

Lo único que puedo encontrar para una solución en C ++ es imitar yieldcon corrutinas de C ++, pero no he encontrado ninguna buena referencia sobre cómo hacer esto. También estoy interesado en soluciones alternativas (no generales) para este problema. No tengo suficiente presupuesto de memoria para guardar una copia de la secuencia entre pasadas.

Los generadores existen en C ++, con otro nombre: Iteradores de entrada . Por ejemplo, leer de std::cines similar a tener un generador de char.

Simplemente necesita comprender lo que hace un generador:

• hay una masa de datos: las variables locales definen un estado
• hay un método de inicio
• hay un método "siguiente"
• hay una manera de señalar la terminación

En su ejemplo trivial, es bastante fácil. Conceptualmente:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Por supuesto, envolvemos esto como una clase adecuada:

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

Así que hum, sí ... podría ser que C ++ es un poco más detallado :)

En C ++ hay iteradores, pero implementar un iterador no es sencillo: hay que consultar los conceptos del iterador y diseñar cuidadosamente la nueva clase de iterador para implementarlos. Afortunadamente, Boost tiene una plantilla iterator_facade que debería ayudar a implementar los iteradores y los generadores compatibles con iteradores.

A veces, se puede usar una corrutina sin pila para implementar un iterador .

PD: Consulte también este artículo que menciona un switchtruco de Christopher M. Kohlhoff y Boost.Coroutine de Oliver Kowalke. El trabajo de Oliver Kowalke es una continuación de Boost.Coroutine de Giovanni P. Deretta.

PD Creo que también puedes escribir una especie de generador con lambdas :

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;

O con un functor:

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;

PD Aquí hay un generador implementado con las corrutinas de 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;
}

Dado que Boost.Coroutine2 ahora lo admite muy bien (lo encontré porque quería resolver exactamente el mismo yieldproblema), estoy publicando el código C ++ que coincide con su intención original:

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

En este ejemplo, pair_sequenceno toma argumentos adicionales. Si es necesario, std::bindo se debe usar una lambda para generar un objeto de función que toma solo un argumento (de push_type), cuando se pasa al coro_t::pull_typeconstructor.

Todas las respuestas que implican escribir su propio iterador son completamente incorrectas. Tales respuestas pierden por completo el sentido de los generadores de Python (una de las características más grandes y únicas del lenguaje). Lo más importante sobre los generadores es que la ejecución se reanuda donde se detuvo. Esto no les sucede a los iteradores. En su lugar, debe almacenar manualmente la información de estado de modo que cuando se llame de nuevo al operador ++ o al operador *, la información correcta esté en su lugar al comienzo de la siguiente llamada a la función. Es por eso que escribir su propio iterador de C ++ es un dolor gigantesco; mientras que los generadores son elegantes y fáciles de leer + escribir.

No creo que haya un buen análogo para los generadores de Python en C ++ nativo, al menos no todavía (hay un rummor de que el rendimiento aterrizará en C ++ 17 ). Puede obtener algo similar recurriendo a un tercero (por ejemplo, la sugerencia de Boost de Yongwei) o lanzando el suyo.

Yo diría que lo más parecido en C ++ nativo son los hilos. Un subproceso puede mantener un conjunto suspendido de variables locales y puede continuar la ejecución donde se detuvo, de manera muy similar a los generadores, pero necesita un poco de infraestructura adicional para admitir la comunicación entre el objeto generador y su llamador. P.ej

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

Sin embargo, esta solución tiene varias desventajas:

1. Los hilos son "caros". La mayoría de la gente consideraría que esto es un uso "extravagante" de hilos, especialmente cuando su generador es tan simple.
2. Hay un par de acciones de limpieza que debe recordar. Estos podrían automatizarse, pero necesitaría aún más infraestructura, lo que, nuevamente, es probable que se considere "demasiado extravagante". De todos modos, las limpiezas que necesitas son:
   1. fuera-> cerrar ()
   2. generator.join ()
3. Esto no le permite detener el generador. Puede hacer algunas modificaciones para agregar esa capacidad, pero agrega desorden al código. Nunca sería tan limpio como la declaración de rendimiento de Python.
4. Además de 2, hay otros bits repetitivos que se necesitan cada vez que desee "instanciar" un objeto generador:
   1. Parámetro de canal * de salida
   2. Variables adicionales en principal: pares, generador

Probablemente debería verificar los generadores en std :: experimental en Visual Studio 2015, por ejemplo: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

Creo que es exactamente lo que estás buscando. Los generadores generales deberían estar disponibles en C ++ 17 ya que esta es solo una característica experimental de Microsoft VC.

Si solo necesita hacer esto para un número relativamente pequeño de generadores específicos, puede implementar cada uno como una clase, donde los datos de los miembros son equivalentes a las variables locales de la función del generador de Python. Luego, tiene una función siguiente que devuelve lo siguiente que produciría el generador, actualizando el estado interno a medida que lo hace.

Esto es básicamente similar a cómo se implementan los generadores de Python, creo. La principal diferencia es que pueden recordar un desplazamiento en el código de bytes para la función del generador como parte del "estado interno", lo que significa que los generadores se pueden escribir como bucles que contienen rendimientos. En su lugar, tendría que calcular el siguiente valor del anterior. En el caso de usted pair_sequence, eso es bastante trivial. Puede que no sea para generadores complejos.

También necesita alguna forma de indicar la terminación. Si lo que está devolviendo es "similar a un puntero", y NULL no debería ser un valor válido válido, puede usar un puntero NULL como indicador de terminación. De lo contrario, necesita una señal fuera de banda.

Algo como esto es muy similar:

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

Usar el operador () es solo una cuestión de lo que quiere hacer con este generador, también puede construirlo como un flujo y asegurarse de que se adapte a un istream_iterator, por ejemplo.

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

Algo como esto :

Ejemplo de uso:

using ull = unsigned long long;

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

    return 0;
}

Imprimirá los números del 0 al 99

Bueno, hoy también estaba buscando una implementación de colección fácil en C ++ 11. En realidad, me decepcionó, porque todo lo que encontré está demasiado lejos de cosas como los generadores de python o el operador de rendimiento de C # ... o demasiado complicado.

El propósito es realizar una colección que emitirá sus ítems solo cuando sea requerido.

Quería que fuera así:

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

Encontré esta publicación, en mi humilde opinión, la mejor respuesta fue sobre boost.coroutine2, de Yongwei Wu . Ya que es lo más cercano a lo que quería el autor.

Vale la pena aprender couroutines de impulso .. Y quizás lo haga los fines de semana. Pero hasta ahora estoy usando mi implementación muy pequeña. Espero que ayude a alguien más.

A continuación se muestra un ejemplo de uso y luego implementación.

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

Esta respuesta funciona en C (y, por lo tanto, creo que también funciona en 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;
}

Esta es una forma sencilla, no orientada a objetos, de imitar un generador. Esto funcionó como se esperaba para mí.

Así como una función simula el concepto de pila, los generadores simulan el concepto de cola. El resto es semántica.

Como nota al margen, siempre puede simular una cola con una pila utilizando una pila de operaciones en lugar de datos. Lo que eso significa en la práctica es que puede implementar un comportamiento similar a una cola devolviendo un par, cuyo segundo valor tiene la siguiente función a llamar o indica que no tenemos valores. Pero esto es más general que lo que hace el rendimiento frente al rendimiento. Permite simular una cola de cualquier valor en lugar de valores homogéneos que espera de un generador, pero sin mantener una cola interna completa.

Más específicamente, dado que C ++ no tiene una abstracción natural para una cola, debe utilizar construcciones que implementen una cola internamente. Entonces, la respuesta que dio el ejemplo con iteradores es una implementación decente del concepto.

Lo que esto significa en la práctica es que puede implementar algo con la funcionalidad de cola básica si solo desea algo rápido y luego consumir los valores de la cola de la misma manera que consumiría los valores generados por un generador.