如何懒洋洋地生成一个完成的项目序列并迭代它

Question

我觉得这个问题肯定已被多次询问和解决,因为在我看来这是一个非常通用的场景,但我找不到任何指向解决方案的方法.

我正在尝试实现一个通用的可迭代Generator对象,该对象产生一个数字序列,直到满足某个终止条件,表明已经达到这样的条件以便停止迭代.

基本思想本质上是与Python的生成器类似,其中一个对象产生值,直到它不再产生为止,然后StopIteration引发异常以通知外部循环序列已完成.

根据我的理解,问题分为创建序列生成对象,然后在其上获取迭代器.

对于序列生成对象,我想我会定义一个基Generator类,然后扩展它以提供特定的行为(例如,从一组范围中获取值,或从固定值列表中获取等).所有GeneraorS中的每个呼叫产生一个新的值operator()或者抛出一个ValuesFinishedException如果发电机跑到序列的末端.我这样实现了这个(我以单范围子类为例,但我需要能够建模更多类型的序列):

struct ValuesFinishedException : public std::exception { };

template <typename T>
class Generator
{
public:
    Generator() { };
    ~Generator() { };
    virtual T operator()() = 0; // return the new number or raise a ValuesFinishedException
};

template <typename T>
class RangeGenerator : public Generator<T>
{
private:
    T m_start;
    T m_stop;
    T m_step;

    T m_next_val;

public:
    RangeGenerator(T start, T stop, T step) :
        m_start(start),
        m_stop(stop),
        m_step(step),
        m_next_val(start)
    { }

    T operator()() override
    {
        if (m_next_val >= m_stop)
            throw ValuesFinishedException();

        T retval = m_next_val;
        m_next_val += m_step;
        return retval;
    }

    void setStep(T step) { m_step = step; }
    T step() { return m_step; }
};

但是对于迭代器部分,我被卡住了.我已经研究过任何我能想到的"Iterator","Generator"和同义词的组合,但我发现只考虑了生成器函数具有无限数量值的情况(例如参见boost的generator_iterator).我想过自己编写一个Generator::iterator类,但我只找到了end很好定义的简单迭代器(链表,数组重新实现)的例子.我事先不知道何时会到达终点,我只知道如果我迭代的生成器引发异常,我需要将迭代器的当前值设置为"end()",但我不知道知道如何表达它.

编辑:添加预期的用例

这个类的原因是有一个灵活的序列对象,我可以循环:

RangeGenerator gen(0.25f, 95.3f, 1.2f);
for(auto v : gen)
{
    // do something with v
}

范围的例子只是最简单的一个.我将至少有三个实际用例:

• 简单范围(可变步长)
• 多个范围的连接
• 存储在向量中的常量值序列

对于其中的每一个,我都计划有一个Generator子类,并为抽象定义了迭代器Generator.

Answer 1

您应该使用 C++ 习惯用法：前向迭代器。这让您可以使用 C++ 语法糖并支持标准库。这是一个最小的例子：

template<int tstart, int tstop, int tstep = 1>
class Range {
public:
    class iterator {
        int start;
        int stop;
        int step;
        int current;
    public:
        iterator(int start, int stop, int step = 0, int current = tstart) : start(start), stop(stop), step(step == 0 ? (start < stop ? 1 : -1) : step), current(current) {}
        iterator& operator++() {current += step; return *this;}
        iterator operator++(int) {iterator retval = *this; ++(*this); return retval;}
        bool operator==(iterator other) const {return std::tie(current, step, stop) == std::tie(other.current, other.step, other.stop);}
        bool operator!=(iterator other) const {return !(*this == other);}
        long operator*() {return current;}
        // iterator traits
        using difference_type = int;
        using value_type = int;
        using pointer = const int*;
        using reference = const int&;
        using iterator_category = std::forward_iterator_tag;
    };
    iterator begin() {return iterator{tstart, tstop, tstep};}
    iterator end() {return iterator{tstart, tstop, tstep, tstop};}
};

它可以与C++98方式一起使用：

using range = Range<0, 10, 2>;
auto r = range{};
for (range::iterator it = r.begin() ; it != r.end() ; ++it) {
    std::cout << *it << '\n';
}

或者使用新的范围循环：

for (auto n : Range<0, 10, 2>{}) {
    std::cout << n << '\n';
}

与 stl 结合使用：

std::copy(std::begin(r), std::end(r), std::back_inserter(v));

演示：http://coliru.stacked-crooked.com/a/35ad4ce16428e65d

Answer 2

如果您想要最初要求的通用生成器（而不是后来添加的更简单的用例），可以设置如下内容：

template <typename T>
struct Generator {
    Generator() {}
    explicit Generator(std::function<std::optional<T>()> f_) : f(f_), v(f()) {}

    Generator(Generator<T> const &) = default;
    Generator(Generator<T> &&) = default;
    Generator<T>& operator=(Generator<T> const &) = default;
    Generator<T>& operator=(Generator<T> &&) = default;

    bool operator==(Generator<T> const &rhs) {
        return (!v) && (!rhs.v); // only compare equal if both at end
    }
    bool operator!=(Generator<T> const &rhs) { return !(*this == rhs); }

    Generator<T>& operator++() {
        v = f();
        return *this;
    }
    Generator<T> operator++(int) {
        auto tmp = *this;
        ++*this;
        return tmp;
    }

    // throw `std::bad_optional_access` if you try to dereference an end iterator
    T const& operator*() const {
        return v.value();
    }

private:
    std::function<std::optional<T>()> f;
    std::optional<T> v;
};

如果您有 C++17（如果没有，请使用 Boost 或仅手动跟踪有效性）。很好地使用它所需的开始/结束函数看起来像

template <typename T>
Generator<T> generate_begin(std::function<std::optional<T>()> f) { return Generator<T>(f); }
template <typename T>
Generator<T> generate_end(std::function<std::optional<T>()>) { return Generator<T>(); }

现在，对于合适的函数，foo您可以像普通输入运算符一样使用它：

auto sum = std::accumulate(generate_begin(foo), generate_end(foo), 0);

我省略了应该Generator在 YSC 的答案中定义的迭代器特征 - 它们应该类似于下面的内容（并且operator*应该返回reference，并且您应该添加operator->，等等）

    // iterator traits
    using difference_type = int;
    using value_type = T;
    using pointer = const T*;
    using reference = const T&;
    using iterator_category = std::input_iterator_tag;