等效于 Python 生成器模式的 C + +

我有一些需要在 C + + 中模仿的 Python 代码示例。我不需要任何特定的解决方案(例如基于协同例程的产生式解决方案，尽管它们也是可接受的答案) ，我只需要以某种方式重现语义。

巨蟒

这是一个基本的序列生成器，显然太大，无法存储物化版本。

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 + + 中的解决方案，我唯一能找到的就是使用 C + + 协程模拟 yield，但是我还没有找到任何关于如何做到这一点的好的参考资料。我还对这个问题的替代(非一般)解决方案感兴趣。我没有足够的内存预算，以保持一个副本的顺序之间的通行证。

70579 次浏览
小开

如果只需要为数量相对较少的特定生成器执行此操作，则可以将每个生成器实现为一个类，其中成员数据等效于 Python 生成器函数的本地变量。然后您有一个下一个函数，该函数返回生成器将产生的下一个内容，并在此过程中更新内部状态。

我相信，这基本上类似于 Python 生成器的实现方式。主要区别在于，它们可以将生成器函数的字节码中的偏移量作为“内部状态”的一部分，这意味着生成器可以写成包含产量的循环。相反，您必须从前一个。对于 pair_sequence来说，这是相当微不足道的。可能不适用于复杂的发电机。

您还需要一些指示终止的方法。如果您返回的是“类指针”，并且 NULL 不应该是一个有效的可收益值，那么您可以使用 NULL 指针作为终止指示符。否则你需要一个带外信号。

小开
最佳答案

C + + 中存在生成器，只不过使用了另一个名称: 输入迭代器。例如，从 std::cin读取类似于拥有 char的生成器。

您只需了解生成器的作用:

  • 有一个数据块: 局部变量定义一个 国家
  • 有一个 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;
};

所以，嗯，是的... ... 可能是 C + + 有点冗长:)

小开

在 C + + 中有迭代器，但是实现迭代器并不简单: 必须参考 迭代器概念并仔细设计新的迭代器类来实现它们。值得庆幸的是，Boost 有一个 迭代器 _ facade模板，它应该有助于实现迭代器和与迭代器兼容的生成器。

有时候是 可以使用无栈协同程序来实现迭代器。

另见 这篇文章，其中提到了 Christopher M. Kohlhoff 的 switch攻击和 Oliver Kowalke 的 加速，加速攻击。奥利弗 · 科瓦尔克在 加速，加速上的作品 是一个后续行动乔瓦尼 · P · 德雷塔。

另外，我认为你也可以写一种生成器 和 Lambda 一起:

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;

附注: 这是一个使用 魔多协同程序实现的生成器:

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

类似的东西非常相似:

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，例如。

小开

您可能应该检查 Visual Studio 2015中的 std: : 驗中的生成器，例如: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

我觉得这正是你想要的。整个生成器应该在 C + + 17中可用，因为这只是微软 VC 的实验性特性。

小开

由于 加速，可乐定2号现在非常支持它(我发现它是因为我想解决完全相同的 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或 lambda 生成一个函数对象，该函数对象在传递给 coro_t::pull_type构造函数时只有一个参数(push_type)。

小开

所有涉及编写自己的迭代器的答案都是完全错误的。这样的答案完全忽略了 Python 生成器的意义(Python 生成器是该语言最伟大和独特的特性之一)。关于生成器最重要的事情是执行从停止的地方继续。迭代器不会出现这种情况。相反，您必须手动存储状态信息，以便在重新调用操作符 + + 或操作符 * 时，正确的信息位于下一个函数调用的 在最开始的时候中。这就是为什么编写自己的 C + + 迭代器是一个巨大的痛苦; 然而，生成器是优雅的，并且易于读写。

我不认为在本地 C + + 中有很好的模拟 Python 生成器，至少现在还没有(有传言说 产量将在 C + + 17土地)。你可以求助于第三方(例如勇卫的 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. Out-> close ()
    2. Generator.join ()
  3. 这不允许您停止发电机。您可以做一些修改来添加这种能力，但是它会给代码增加混乱。它永远不会像 Python 的屈服声明那样干净。
  4. 除了2之外，每次您想“实例化”一个生成器对象时，还需要其他一些样板文件:
    1. 通道 * 输出参数
    2. 主要附加变量: 对，生成器
小开

正如函数模拟堆栈的概念一样，生成器模拟队列的概念。剩下的就是语义学了。

另外，您总是可以通过使用操作堆栈而不是数据来模拟带有堆栈的队列。这实际上意味着您可以通过返回一个对来实现类似队列的行为，第二个值要么有下一个要调用的函数，要么表示我们没有值了。但这比收益率与回报率的关系更为普遍。它允许模拟任意值的队列，而不是您期望从生成器获得的同质值，但是不需要保持完整的内部队列。

更具体地说，由于 C + + 对队列没有自然的抽象，因此需要使用在内部实现队列的构造。所以给出这个带有迭代器的例子的答案是这个概念的一个不错的实现。

这实际上意味着，如果您只想快速地实现某些功能，然后使用队列的值，就像使用生成器产生的值一样，那么您可以使用基本的队列功能实现某些功能。

小开

就像 这个:

示例使用:

using ull = unsigned long long;


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


return 0;
}

将打印从0到99的数字

小开

使用 距离 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;
}
小开

今天我也在寻找 C + + 11下的简单集合实现。实际上我很失望，因为我发现的所有东西都与 Python 生成器或 C # 产生运算符之类的东西相去甚远，或者太复杂了。

其目的是进行集合，该集合仅在需要时才发出其项。

我希望是这样的:

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

我发现这篇文章，恕我直言，最好的答案是关于 boost.coroutine2，由 吴提供。因为它是最接近作者想要的。

这是值得学习的提高例行公事。.我周末可能会去。但到目前为止，我使用的是非常小的实现。希望能帮到别人。

下面是使用的例子，然后实现。

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

发电机

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<stdint.h>
//#include<stdio.h>


#define MAX (1ll << 32) //2^32


typedef struct {
uint64_t i, j;
} Pair;


int generate_pairs(Pair* p)
{
static uint64_t i = 0;
static uint64_t j = 0;


p->i = i;
p->j = j;
    

if(++j == MAX)
{
j = 0;
if(++i == MAX)
{
return -1; // return -1 to indicate generator finished.
}
}
    

return 1; // return non -1 to indicate generator not finished.
}


int main()
{
while(1)
{
Pair p;
int fin = generate_pairs(&p);
        

//printf("%lld, %lld\n", p.i, p.j);
        

if(fin == -1)
{
//printf("end");
break;
}
}
return 0;
}

这是一种简单的、非面向对象的模拟生成器的方法。

编辑: 以前的代码是错误的，我已经更新了它。

注意: 对于给定的问题，这段代码可以改进为只使用 uint32 _ t 而不是 uint64 _ t。

小开

使用简单的 goto 语句可以得到屈服的举止，因为它很简单，所以我用 C 语言编写了它。

在生成器函数中你要做的就是:

  • 所有变量都声明为 static
  • 最后一个收益退出是用一个标签记住的
  • 变量在函数结束时重新初始化

例如:

#include <stdio.h>


typedef struct {
int i, j;
} Pair;


// the function generate_pairs  can generate values in successive calls.
// - all variables are declared as static
// - last yield exit is memorized with a label
// - variables are reinitialized at the end of function
Pair* generate_pairs(int imax, int jmax)
{
// all local variable are declared static. So they are declared at the beginning
static int i = 0;
static int j = 0;
static Pair p;
// the exit position is marked with a label
static enum {EBEGIN, EYIELD1} tag_goto = EBEGIN;
    

// I goto to the last exit position
if (tag_goto == EYIELD1)
goto TYIELD1;
    

    

for (i=0; i<imax; i++)   {
for (j=0; j<jmax; j++)   {
p.i = i;   p.j = -j;
            

// I manage the yield comportment
tag_goto = EYIELD1;
return &p;
TYIELD1 : ;
}
j = 0;
}
    

// reinitialization of variables
i = 0;   j = 0;   // in fact this reinitialization is not useful in this example
tag_goto = EBEGIN;
    

// NULL means ends of generator
return NULL;
}


int main()
{
for (Pair *p = generate_pairs(2,4); p != NULL; p = generate_pairs(2,4))
{
printf("%d,%d\n",p->i,p->j);
}
printf("end\n");
return 0;
}

提交答案