Generador de C ++ equivalente a Python

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

Pitón

Este es un generador de secuencia 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 objective es mantener dos instancias de la secuencia anterior e iterar sobre ellas en semi-lockstep, pero en trozos. En el siguiente ejemplo, first_pass usa la secuencia de pares para inicializar el búfer, y second_pass regenera 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 el yield con las coroutinas 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 pases.

Los generadores existen en C ++, justo bajo otro nombre: Iteradores de entrada . Por ejemplo, leer desde std::cin es similar a tener un generador de char .

Simplemente necesitas entender lo que hace un generador:

  • hay un blob de datos: las variables locales definen un estado
  • hay un metodo inic
  • hay un “siguiente” método
  • hay una manera de señalar la terminación

En tu 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 > { // 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; 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 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::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 la implementación de un iterador no es sencilla: uno tiene que consultar los conceptos del iterador y diseñar cuidadosamente la nueva clase de iteradores 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 coroutina sin stack para implementar un iterador .

PD: vea también este artículo que menciona un switch por Christopher M. Kohlhoff y Boost.Coroutine por Oliver Kowalke. El trabajo de Oliver Kowalke es un seguimiento en Boost.Coroutine por Giovanni P. Deretta.

PD: Creo que también puedes escribir un tipo de generador con lambdas :

 std::function 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; 

PS Aquí hay un generador implementado con las coroutines Mordor :

 #include  using std::cout; using std::endl; #include  using Mordor::Coroutine; using Mordor::Fiber; void testMordor() { Coroutine coro ([](Coroutine& 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 problema de yield ), estoy publicando el código C ++ que coincide con su intención original:

 #include  #include  #include  #include  typedef boost::coroutines2::coroutine> 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_sequence no toma argumentos adicionales. Si es necesario, se debe usar std::bind o lambda para generar un objeto de función que tome solo un argumento (de push_type ), cuando se pasa al constructor coro_t::pull_type .

Probablemente debería revisar los generadores en std :: experimental en Visual Studio 2015, por ejemplo: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumble-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 función experimental de Microsoft VC.

Todas las respuestas que implican escribir su propio iterador son completamente erróneas. Esas respuestas omiten por completo el punto de los generadores de Python (una de las características más grandes y únicas del lenguaje). Lo más importante de los generadores es que la ejecución comienza donde se detuvo. Esto no le sucede a los iteradores. En su lugar, debe almacenar manualmente la información de estado de manera que cuando se llame nuevamente al operador ++ u operator *, la información correcta esté en su lugar al comienzo de la siguiente llamada a la función. Es por esto que escribir tu 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 rumor de que el rendimiento caerá en C ++ 17 ). Puede obtener algo similar al recurrir a un tercero (por ejemplo, la sugerencia Boost de Yongwei), o hacer rodar la suya propia.

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

 // Infrastructure template  class Channel { ... }; // Application using IntPair = std::pair; void yield_pairs(int end_i, int end_j, Channel* 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 pairs; std::thread generator(yield_pairs, 32, 32, &pairs); for (IntPair pair : pairs) { UsePair(pair); } generator.join(); } 

Esta solución tiene varias desventajas, sin embargo:

  1. Los hilos son “caros”. La mayoría de la gente consideraría esto como un uso “extravagante” de los hilos, especialmente cuando su generador es tan simple.
  2. Hay un par de acciones de limpieza que debes recordar. Se podrían automatizar, pero se necesitaría incluso más infraestructura, lo que, de nuevo, probablemente 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. Podrías hacer algunas modificaciones para agregar esa habilidad, pero agrega desorden al código. Nunca sería tan limpio como la statement de rendimiento de Python.
  4. Además de 2, hay otros bits de repetitivo que se necesitan cada vez que desee “crear una instancia” de un objeto generador:
    1. Canal * parámetro de salida
    2. Variables adicionales en main: pares, generador.

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 generarí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. Tendrías que calcular el siguiente valor del anterior. En el caso de tu pair_sequence , la pair_sequence 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 “puntero”, y NULL no debería ser un valor de rendimiento válido, podría 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 result_type; static const unsigned int limit = numeric_limits::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 pregunta de lo que quiere hacer con este generador, también podría crearlo como una transmisión y asegurarse de que se adapte a un istream_iterator, por ejemplo.

Utilizando range-v3 :

 #include  #include  #include  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(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 recostackción sencilla en C ++ 11. En realidad, me decepcionó, porque todo lo que encontré está demasiado lejos de cosas como los generadores de pitones o el operador de rendimiento de C # … o demasiado complicado.

El propósito es hacer una colección que emita sus artículos solo cuando sea necesario.

Quería que fuera así:

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

Encontré este post, la mejor respuesta de IMHO fue sobre boost.coroutine2, por Yongwei Wu . Ya que es el más cercano a lo que quería el autor.

Vale la pena aprender a mejorar las cortesías. Y tal vez 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 la implementación.

Example.cpp

 #include  #include "Generator.h" int main() { typedef std::pair res_t; auto emitter = Generator::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; } 

Generador.h

 template struct yield_function{ typedef std::function type; }; template class YieldConstIterator { public: typedef IndexTy index_t; typedef ResTy res_t; typedef typename yield_function::type yield_function_t; typedef YieldConstIterator 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 class YieldIterator : public YieldConstIterator { public: typedef YieldConstIterator parent_t; typedef IndexTy index_t; typedef ResTy res_t; typedef typename yield_function::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 struct Range { public: typedef IndexTy index_t; typedef Range mytype_t; index_t begin; index_t end; }; template class GeneratorCollection { public: typedef Range range_t; typedef IndexTy index_t; typedef ResTy res_t; typedef typename yield_function::type yield_function_t; typedef YieldIterator iterator; typedef YieldConstIterator 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 class Generator { public: typedef IndexTy index_t; typedef ResTy res_t; typedef typename yield_function::type yield_function_t; typedef Generator mytype_t; typedef Range parent_t; typedef GeneratorCollection finalized_emitter_t; typedef Range 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; }; 

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

Como nota al margen, siempre puede simular una cola con una stack utilizando una stack de operaciones en lugar de datos. Lo que eso significa prácticamente es que puede implementar un comportamiento similar a una cola devolviendo un par, cuyo segundo valor tiene la siguiente función a la que llamar o indica que estamos fuera de los valores. Pero esto es más general de lo que hace el rendimiento frente al retorno. Permite simular una cola de cualquier valor en lugar de valores homogéneos que usted 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, necesita usar construcciones que implementan una cola internamente. Entonces, la respuesta que dio el ejemplo con los 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 quiere algo rápido y luego consumir los valores de la cola tal como lo haría con los valores generados por un generador.