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

问题描述 投票:10回答:4

我觉得这个问题必须多次被问及解决,因为在我看来这是一个非常通用的场景,但我找不到任何指向解决方案的方法。

我正在尝试实现一个通用的可迭代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; }
};

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

编辑:添加预期的用例

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

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

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

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

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

c++ iterator
4个回答
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;

4
投票

你应该使用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));

但是:ぁzxswい


2
投票

基于for循环的范围是关于实现begin(),end()和operator ++的迭代器。

所以发电机必须实施它们。

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

然后添加一个实例化生成器的函数,你就完成了

template<typename T>
struct generator {
    T first;
    T last;

    struct iterator {
        using iterator_category = std::input_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T *;
        using reference = T &;
        T value;

        iterator(T &value) : value(value) {}

        iterator &operator++() {
            ++value;
            return *this;
        }
        iterator operator++(int) = delete;

        bool operator==(const iterator &rhs) { return value == rhs.value; }
        bool operator!=(const iterator &rhs) { return !(*this == rhs); }
        const reference operator *() { return value; }
        const pointer operator->() const { return std::addressof(value); }
    };

    iterator begin() { return iterator(first); }
    iterator end() { return iterator(last); }
};

1
投票

您描述的用例(范围的串联等)可能证明对库的依赖性,因此这里是基于template<typename T> generator<T> range(T start, T end) { return generator<T>{ start, end }; } for (auto i : range(0, 10)) { } 的解决方案,它正在进入C ++ 20。您可以轻松地遍历整数值,此处从0到10,步长为2,

range-v3

或者用浮点值实现一个类似的循环(注意[from,to]这里是一个闭合范围,第三个参数表示步数)

#include <range/v3/all.hpp>

using namespace ranges;

for (auto i : view::ints(0, 11) | view::stride(2))
   std::cout << i << "\n";

当谈到连接时,图书馆开始闪耀:

for (auto f : view::linear_distribute(1.25f, 2.5f, 10))
   std::cout << f << "\n";

请注意,上面的代码片段使用const std::vector world{32, 119, 111, 114, 108, 100}; for (auto i : view::concat("hello", world)) std::cout << char(i); std::cout << "\n"; 进行编译。该库只是标题。

© www.soinside.com 2019 - 2024. All rights reserved.