Итератор последовательности? Разве не в одном?

Время от времени я чувствую потребность в определенном виде итератора (для которого я не могу составить хорошее имя, кроме того, что префикс к названию этого вопроса).

Предположим, что у нас есть функция (или объект функции), которая отображает целое число типа T. То есть мы имеем определение математической последовательности, но на самом деле мы ее не храним в памяти. Я хочу сделать из него итератор. Класс итератора будет выглядеть примерно так:

template <class F, class T>
class sequence_iterator : public std::iterator<...>
{
    int i;
    F f;
    public:
    sequence_iterator (F f, int i = 0):f(f), i(i){}
    //operators ==, ++, +, -, etc. will compare, increment, etc. the value of i.
    T operator*() const
    {
        return f(i);
    }    
};

template <class T, class F>
sequence_iterator<F, T> make_sequence_iterator(F f, int i)
{
    return sequence_iterator<F, T>(f, i);
}

Возможно, я наивна, но лично я чувствую, что этот итератор будет очень полезным. Например, предположим, что у меня есть функция, которая проверяет, является ли число простым или нет. И я хочу подсчитать количество простых чисел в интервале [a, b]. Я бы это сделал,

int identity(int i)
{
   return i;
}
count_if(make_sequence_iterator<int>(identity, a), make_sequence_iterator<int>(identity, b), isPrime);

Так как я обнаружил что-то полезное (по крайней мере, IMHO), я определенно уверен, что он существует в boost или стандартной библиотеке. Я просто не могу его найти. Итак, есть что-то подобное в boost?. В очень маловероятном случае, что на самом деле нет, тогда я напишу один - и в этом случае я хотел бы узнать ваше мнение, следует ли мне сделать iterator_category random_access_iterator_tag. Меня беспокоит, что это не настоящий RAI, потому что operator* не возвращает ссылку.

Заранее благодарим за помощь.

Ответ 1

boost::counting_iterator и boost::transform_iterator должны сделать трюк:

template <typename I, typename F>
boost::transform_iterator<
    F,
    boost::counting_iterator<I>>
make_sequence_iterator(I i, F f)
{
    return boost::make_transform_iterator(
        boost::counting_iterator<I>(i), f);
}

Использование:

std::copy(make_sequence_iterator(0, f), make_sequence_iterator(n, f), out);

Ответ 2

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

Если вы хотите, чтобы итерация с произвольным доступом зависела от вас. Сначала я попытаюсь создать прямой или двунаправленный итератор, поскольку (например, повторные двоичные поиски по последовательности целых чисел могут быть быстрее, если они сгенерированы и сохранены за один раз.

Ответ 3

Соответствует ли boost::transform_iterator вашим потребностям? существует несколько полезных адаптеров итераторов в boost, doc здесь.

Ответ 4

Я думаю, boost:: counting_iterator - это то, что вы ищете, или, по крайней мере, ближе всего. Есть ли что-то, что вы ищете, это не предусмотрено? Можно сделать, например:

std::count_if(boost::counting_iterator<int>(0),
      boost::counting_iterator<int>(10),
      is_prime); // or whatever ...

Короче говоря, это итератор по ленивой последовательности последовательных значений.

Ответ 5

Boost.Utility содержит итератор-генератор. Пример из документации:

#include <iostream>
#include <boost/generator_iterator.hpp>

class my_generator
{
public:
    typedef int result_type;
    my_generator() : state(0) { }
    int operator()() { return ++state; }
private:
    int state;
};

int main()
{
    my_generator gen;
    boost::generator_iterator_generator<my_generator>::type it =
      boost::make_generator_iterator(gen);
    for (int i = 0; i < 10; ++i, ++it)
        std::cout << *it << std::endl;
}