¿iterador de secuencia? ¿No hay uno en el impulso?

Question

De vez en cuando siento la necesidad de cierto tipo de iterador (para el cual no puedo inventar un buen nombre, excepto el que está prefijado al título de esta pregunta).

Supongamos que tenemos una función (u objeto de función) que asigna un entero al tipo T. Es decir, tenemos una definición de secuencia matemática, pero en realidad no la tenemos almacenada en la memoria. Quiero hacer un iterador fuera de esto. La clase de iterador sería algo como esto:

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

Tal vez estoy siendo ingenuo, pero yo personalmente creo que este iterador sería muy útil. Por ejemplo, supongamos que tengo una función que verifica si un número es primo o no. Y quiero contar el número de primos en el intervalo [a, b]. Yo haría esto;

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

Desde que he descubierto algo que sería útil (al menos en mi humilde opinión) Definitivamente soy positivo que existe en aumento o la biblioteca estándar. Simplemente no puedo encontrarlo. Entonces, ¿hay algo como esto en boost?. En el muy poco probable caso de que realmente no exista, entonces voy a escribir uno, y en este caso me gustaría saber su opinión sobre si debo o no hacer el iterator_categoryrandom_access_iterator_tag. Mi preocupación es que este no es un RAI real, porque operator* no devuelve una referencia.

Gracias de antemano por cualquier ayuda.

Answer 1

boost::counting_iterator y boost::transform_iterator debe hacer el truco:

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

Uso:

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

Answer 2

Llamaré a esto un iterador de mapeo entero, ya que mapea una función sobre una subsecuencia de los enteros. Y no, nunca me he encontrado con esto en Boost o en el STL. No estoy seguro de por qué, ya que su idea es muy similar al concepto de iteradores de flujo, que también generan elementos al invocar funciones.

Si lo desea, la iteración de acceso aleatorio depende de usted. Intentaré construir primero un iterador directo o bidireccional, ya que (por ejemplo) las búsquedas binarias repetidas sobre una secuencia de enteros pueden ser más rápidas si se generan y almacenan de una vez.

Answer 3

¿El boost::transform_iterator satisface sus necesidades? hay varios adaptadores de iterador útiles en boost, el doc es here.

Answer 4

Creo que boost::counting_iterator es lo que está buscando, o al menos es lo más parecido. ¿Hay algo que estás buscando que no proporciona? Uno podría hacer, por ejemplo:

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

En resumen, es un iterador sobre una secuencia perezosa de valores consecutivos.

Answer 5

Boost.Utility contiene una generator iterator adaptor. Un ejemplo de la documentación:

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