Как лениво генерировать готовую последовательность элементов и перебирать ее - PullRequest
Новая
       2

Как лениво генерировать готовую последовательность элементов и перебирать ее

0 голосов
/ 04 сентября 2018

Я чувствую, что этот вопрос, должно быть, задавался и решался много раз, потому что это кажется мне довольно общим сценарием, но я не мог найти ничего, что указывало бы мне в направлении решения.

Я пытаюсь реализовать универсальный итерируемый Generator объект, который производит последовательность чисел до тех пор, пока не будет выполнено определенное условие завершения, сигнализирующее, что такое условие было достигнуто для остановки итерации.

Основная идея, по сути, заключается в том, чтобы иметь нечто похожее на генераторы Python, где объект возвращает значения до тех пор, пока у него больше нет выхода, а затем возникает исключение StopIteration для информирования внешнего цикла о завершении последовательности.

Из того, что я понимаю, проблема распадается на создание объекта, генерирующего последовательность, а затем получение итератора над ним.

Для объекта, генерирующего последовательность, я подумал, что определю базовый класс Generator, который затем расширяется для обеспечения определенного поведения (например, для получения значений из набора диапазонов или из списка фиксированных значений и т. Д.). ). Все 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; }
};

Что касается итераторов, я застрял. Я исследовал любую комбинацию «Итератор», «Генератор» и синонимов, которую я только мог придумать, но все, что я нашел, рассматривает только случай, когда функция генератора имеет неограниченное количество значений (см., Например, generator_iterator boost ). Я думал о написании Generator::iterator класса сам, но я нашел только примеры тривиальных итераторов (связанные списки, переопределения массивов), где end четко определено. Я не знаю заранее, когда будет достигнут конец, я только знаю, что если генератор, который я перебираю, вызывает исключение, мне нужно установить текущее значение итератора в «end ()», но я не знать, как это представить.

Редактировать: добавление предполагаемого варианта использования

Причина этого класса в том, чтобы иметь гибкий объект последовательности, который я могу зациклить: 

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

Пример диапазона - самый простой. У меня будет как минимум три фактических варианта использования:

  • простой диапазон (с переменным шагом)
  • объединение нескольких диапазонов
  • последовательность постоянных значений, хранящихся в векторе

Для каждого из них я планирую иметь подкласс Generator, с итератором, определенным для аннотации Generator.

Ответы [ 4 ]

0 голосов
/ 04 сентября 2018

Если вам нужен универсальный генератор, который вы изначально запрашивали (а не более простые варианты использования, добавленные позже), то можно установить примерно так: 

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;
0 голосов
/ 04 сентября 2018

Цикл, основанный на цикле, полностью связан с итератором, реализующим функции begin (), end () и operator ++.

Так что генератор должен их реализовать. 

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))
{
}
0 голосов
/ 04 сентября 2018

Вариант использования, который вы описываете (объединение диапазонов и т. Д.), Может оправдать зависимость от библиотеки, поэтому вот решение, основанное на 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. Библиотека имеет только заголовок.

0 голосов
/ 04 сентября 2018

Вы должны использовать идиому 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';
}

В соединении со стандартом: 

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

Демонстрация: http://coliru.stacked -crooked.com / a / 35ad4ce16428e65d

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...