代码之家 › 专栏 › 技术社区 › GPhilo satyendra

如何懒洋洋地生成已完成的项目序列并对其进行迭代

iterator c++

GPhilo satyendra · 技术社区 · 7 年前

我觉得这个问题一定被问过很多次,解决过很多次,因为在我看来,这是一个非常普遍的情况,但我找不到任何东西能为我指明解决的方向。

我正在尝试实现一个通用的iterable Generator 对象,它产生一个数字序列,直到满足某个终止条件为止,表示已达到该条件以停止迭代。

StopIteration 引发异常以通知外部循环序列已完成。

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

对于序列生成对象,我想我应该定义一个基 发电机 Generaor s在每次调用 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”和同义词的任何组合,但我所发现的只是考虑了Generator函数有无限个值的情况(参见示例) boost's generator_iterator ). 我想写封信 Generator::iterator end 定义明确。我事先不知道何时到达结束,我只知道如果我正在迭代的生成器引发异常,我需要将迭代器的当前值设置为“end()”,但我不知道如何表示它。

编辑:添加预期用例

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

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

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

简单范围(带可变步长)
多个范围的串联

对于每一个我都计划有一个 发电机 子类,具有为抽象定义的迭代器 发电机 .

4 回复 | 直到 5 年前

Useless 7 年前

如果您想要您最初要求的通用生成器(而不是稍后添加的更简单的用例),那么是可以这样设置:

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或只是跟踪有效性)。使用这个函数所需的begin/end函数

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;

YSC 7 年前

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

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

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

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

Serve Laurijssen 7 年前

所以生成器必须实现它们。

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

template<typename T>
generator<T> range(T start, T end) {
    return generator<T>{ start, end };
}

for (auto i : range(0, 10))
{
}

lubgr 7 年前

您描述的用例(范围的串联等)可能会证明对库的依赖性是合理的,因此这里有一个基于 range-v3 ,在它进入C++ 20的途中。你可以很容易地迭代积分值,从0到10,步长为2,

#include <range/v3/all.hpp>

using namespace ranges;

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

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

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

注意,上面的代码段是用 -std=c++17 . 库仅为标题。