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

Question

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

蟒蛇

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

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++中找到解决方案的唯一方法就是模仿yieldC++协同程序,但我没有找到关于如何做到这一点的任何好的参考.我也对这个问题的替代(非一般)解决方案感兴趣.我没有足够的内存预算来保存传递之间序列的副本.

Answer 1

生成器存在于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++有点啰嗦:)

Answer 2

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

有时,无堆栈协程可用于实现迭代器.

PS另见本文提到switch克里斯托弗·科尔霍夫和奥利弗·科瓦尔克的Boost.Coroutine的黑客攻击.Oliver Kowalke的作品是 Giovanni P. Deretta 关于Boost.Coroutine 的后续作品.

PS我想你也可以用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;

或者使用仿函数:

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

Answer 3

由于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或者应该使用lambda生成一个只push_type传递一个参数(of )的函数对象,当它传递给coro_t::pull_type构造函数时.

Answer 4

所有涉及编写自己的迭代器的答案都是完全错误的。这样的答案完全忽略了 Python 生成器（该语言最伟大和独特的功能之一）的重点。关于生成器的最重要的事情是执行从它停止的地方开始。这不会发生在迭代器上。相反，您必须手动存储状态信息，以便在重新调用 operator++ 或 operator* 时，正确的信息会在下一次函数调用的最开始处就位。这就是为什么编写自己的 C++ 迭代器是一个巨大的痛苦；而生成器是优雅的，并且易于读写。

我认为原生 C++ 中的 Python 生成器没有很好的模拟，至少现在还没有（有传言说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. 这不允许您停止生成器。您可以进行一些修改以添加该功能，但这会增加代码的混乱程度。它永远不会像 Python 的 yield 语句那样干净。
4. 除了 2 之外，每次要“实例化”生成器对象时，还需要其他一些样板：
   1. 通道*输出参数
   2. main 中的附加变量：pairs，generator

Answer 5

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