Студент

Лотков Даниил

Задача

Генератор последовательностей

Состояние

Открыто

Дедлайн

Назначено

09.02.2015, 15:37

Реализовать шаблонный класс-генератор последовательностей. Аргументами шаблона являются тип значения и функтор инкремента.

Мотивация

В численных вычислениях часто приходится иметь дело с последовательностями значений. Например, «все числа от 1 до 100», «все нечётные числа от 1 и более», «все числа от 0 до 10 с шагом 0,025» и т.д. Традиционная работа с такими объектами в C++ предполагает устройство циклов:

for (double x = 0; x < 10; x += 0.025) { 
   // ....
}

// Кстати, x += dx не очень хороший вариант, ибо при малом dx 
// будут накапливаться ошибки округления. Лучше использовать
// формулу x = x0 + n*dx и итерировать целочисленное n.

Но если задуматься, объекты-последовательности вполне укладываются в треугольник «алгоритмы — итераторы — контейнеры». Можно представить, что последовательность попросту является виртуальным контейнером, что где-то лежит vector<double> с 400 значениями от 0 до 9,975. Но в действительности, поскольку мы можем вычислить любое значение такого контейнера за константное время, тратить память вовсе не обязательно. Вычисления могут производиться непосредственно при разыменовании итератора.

И тогда мы приходим к такой структуре:

// Генератор
template <typename T, typename IncOp>
class Range {
public:
    Range(const T &begin, const T &end, const IncOp &inc = IncOp());

    typedef ... iterator;

    iterator begin() const;
    iterator end() const;

    // ...
};

inline int plus_1(int x) { return x + 1; }

int main() {
    Range<int, plus_1> r(0, 10);

    for (int x: r)
        cout << x;  // 0 … 9
}

Задание

Необходимо реализовать нужные методы в Range и шаблонный класс итератора так, чтобы итерирование по объекту класса Range возвращало элементы последовательности.

Усложнение

Путь 1

Реализовать другую версию, где вместо IncOp передаётся функтор MemberFunc, который для своего аргумента int n возвращает значение последовательности. Продумать, какие в этом случае будут параметры шаблонов и аргументы конструктора у MemberFunc и у Range.

Путь 2

Реализовать возможность применения задаваемого функтора к элементам последовательность. Например, чтобы при передаче функтора, возводящего в квадрат, можно было вместо 0, 1, 2, 3 получить 0, 1, 4, 9.

Пример кода:

// Функтор, возвращающий свой аргумент (для любого типа). 
// ПРОСТО ВОЗЬМИТЕ ЭТО КАК ЕСТЬ
struct Identity {
    template<typename U>
    constexpr auto operator()(U&& v) const noexcept
    -> decltype(std::forward<U>(v))
    { return std::forward<U>(v); }
};

// Генератор
template <typename T, typename IncOp, typename ValueOp = Identity>
class Range {
public:
    Range(const T &begin, const T &end, const IncOp &inc = IncOp(),
          const ValueOp &valop = ValueOp());

    typedef ... iterator;

    iterator begin() const;
    iterator end() const;

    // ...
};

inline int plus_1(int x) { return x + 1; }

template <typename T>
inline T square(T x) { return x*x; }

int main() {
    Range<int, plus_1, square> rs(1, 5);

    for (int x: rs)
        cout << x;  // 1… 4… 9… 16
}