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

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

蟒蛇

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

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

目标是维护上面序列的两个实例,并以半锁步方式迭代它们,但是以块为单位。 在下面的示例中,yield使用对序列来初始化缓冲区,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 ++协同程序,但我没有找到任何关于如何做到这一点的好参考。 我也对这个问题的替代(非一般)解决方案感兴趣。 我没有足够的内存预算来保存传递之间序列的副本。

Noah Watkins asked 2019-09-08T19:00:12Z
11个解决方案
60 votes

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

Matthieu M. answered 2019-09-08T19:01:14Z
40 votes

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

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

附: 另见本文,其中提到了由Christopher M. Kohlhoff执导的switch和由Oliver Kowalke提出的Boost.Coroutine。 Oliver Kowalke的作品是Giovanni P. Deretta关于Boost.Coroutine的后续作品。

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

附: 这是一个用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;
}
ArtemGr answered 2019-09-08T19:02:10Z
19 votes

由于Boost.Coroutine2现在支持得很好(我发现它因为我想解决完全相同的pair_sequence问题),我发布的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)的函数对象,当它传递给coro_t::pull_type构造函数时。

Yongwei Wu answered 2019-09-08T19:02:43Z
3 votes

您应该在Visual Studio 2015中检查std :: experimental中的生成器,例如:[https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/]

我认为这正是你要找的。 整体生成器应该在C ++ 17中可用,因为这只是实验性的Microsoft VC功能。

Огњен Шобајић answered 2019-09-08T19:03:15Z
3 votes

所有涉及编写自己的迭代器的答案都是完全错误的。 这些答案完全忽略了Python生成器(语言最大和独特的功能之一)。 关于生成器最重要的事情是执行从它停止的地方开始。 迭代器不会发生这种情况。 相反,您必须手动存储状态信息,以便在重新调用operator ++或operator *时,在下一个函数调用的最开始就存在正确的信息。 这就是为什么编写自己的C ++迭代器是一个巨大的痛苦; 然而,发电机很优雅,易于阅读和书写。

我不认为在本机C ++中有一个很好的模拟Python生成器,至少现在还没有(有传言称收益率将落在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. OUT-> close()方法
    2. generator.join()
  3. 这不允许您停止发电机。 您可以进行一些修改以添加该功能,但它会增加代码的混乱。 它永远不会像Python的yield语句那样干净。
  4. 除了2之外,每次要“实例化”生成器对象时,还需要其他的样板文件:
    1. 频道*输出参数
    2. main中的其他变量:对,生成器
allyourcode answered 2019-09-08T19:04:52Z
2 votes

如果只需要为相对较少数量的特定生成器执行此操作,则可以将每个实现为一个类,其中成员数据等效于Python生成器函数的局部变量。 然后你有一个下一个函数,它返回生成器将产生的下一个东西,更新内部状态。

我相信这基本上类似于Python生成器的实现方式。 主要区别在于它们可以记住生成器函数的字节码中的偏移量,作为“内部状态”的一部分,这意味着生成器可以写为包含yield的循环。 您必须改为计算前一个的下一个值。 在您的pair_sequence的情况下,这是非常微不足道的。 它可能不适用于复杂的发电机。

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

Ben answered 2019-09-08T19:05:33Z
1 votes

这样的东西非常相似:

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

lip answered 2019-09-08T19:06:05Z
1 votes

使用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;
}
Engineerist answered 2019-09-08T19:06:31Z
0 votes

像这样的东西:

使用示例:

using ull = unsigned long long;

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

    return 0;
}

将打印从0到99的数字

smac89 answered 2019-09-08T19:07:00Z
0 votes

好吧,今天我也在寻找C ++ 11下的简单集合实现。 其实我很失望,因为我发现的一切都远离python生成器,或C#yield operator ...或太复杂。

目的是使收集只在需要时才发出其物品。

我希望它是这样的:

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

我发现这篇文章,恕我直言最佳答案是关于boost.oroutine2,由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;
};      
Stepan Dyatkovskiy answered 2019-09-08T19:08:10Z
-1 votes

正如函数模拟堆栈的概念一样,生成器模拟队列的概念。 其余的是语义。

作为旁注,您始终可以使用堆栈操作而不是数据来模拟具有堆栈的队列。 这实际上意味着您可以通过返回一对来实现类似队列的行为,第二个值要么具有要调用的下一个函数,要么指示我们没有值。 但这比收益率与收益率更为一般。 它允许模拟任何值的队列,而不是您期望从生成器获得的同类值,但不保留完整的内部队列。

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

这实际上意味着你可以实现具有简单队列功能的东西,如果你只是想要快速然后消耗队列的值,就像消耗从生成器产生的值一样。

Dmitry Rubanovich answered 2019-09-08T19:08:56Z
translate from https://stackoverflow.com:/questions/9059187/equivalent-c-to-python-generator-pattern