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

Question

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

Предположим, у нас есть функция (или функциональный объект), которая отображает целое число на тип 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);

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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