límite de STL algoritmos para N elementos

Question

(inspirado por un comentario de nakiya)

Muchos algoritmos STL toman una serie como un par de iteradores. Por ejemplo, for_each(begin, end, &foo);. Obviamente, si distance(begin, end) >= N, y comienza es un iterador de acceso aleatorio, entonces for_each(begin, begin+N, &foo); aplica foo solo a los primeros N elementos.

¿Existe una alternativa limpia y genérica si no se cumple alguna de estas dos condiciones?

Answer 1

No existe una solución genérica completa sin cambiar el tipo de iterador.

Prueba: supongamos que el tipo de iterador es solamente un InputIterator, por lo begin en realidad se refiere a (por ejemplo) una corriente, y end es un iterador marcador caso especial, que comparará igual al iterador "real" una vez que el el iterador real ha leído EOF.

Entonces, cualquier uso de begin a tratar de llegar a un nuevo valor de end para pasar al algoritmo, se "consume" el valor original de begin, ya que así es como InputIterators trabajo.

Lo que podría hacer es escribir una clase contenedora de iterador, de modo que el iterador cuente cuántas veces se ha incrementado y compare igual a un iterador "final" una vez que se haya incrementado N veces. N podría ser un parámetro de plantilla, o un parámetro de constructor para uno u otro de los iteradores.

Algo como esto. Lo he probado y compila y funciona para mí. Aún por hacer: actualmente solo estoy manejando una de sus dos situaciones, "no es un iterador de acceso aleatorio". Yo tampoco manejo el otro, "distancia < N".

#include <iterator> 

template <typename It> 
class FiniteIterator : public std::iterator< 
    typename std::iterator_traits<It>::iterator_category, 
    typename std::iterator_traits<It>::value_type> { 
    typedef typename std::iterator_traits<It>::difference_type diff_type; 
    typedef typename std::iterator_traits<It>::value_type val_type; 
    It it; 
    diff_type count; 
    public: 
    FiniteIterator(It it) : it(it), count(0) {} 
    FiniteIterator(diff_type count, It it = It()) : it(it), count(count) {} 
    FiniteIterator &operator++() { 
     ++it; 
     ++count; 
     return *this; 
    } 
    FiniteIterator &operator--() { 
     --it; 
     --count; 
     return *this; 
    } 
    val_type &operator*() const { 
     return *it; 
    } 
    It operator->() const { 
     return it; 
    } 
    bool operator==(const FiniteIterator &rhs) const { 
     return count == rhs.count; 
    } 
    bool operator!=(const FiniteIterator &rhs) const { 
     return !(*this == rhs); 
    } 
    FiniteIterator operator++(int) { 
     FiniteIterator cp = *this; 
     ++*this; 
     return cp; 
    } 
    FiniteIterator operator--(int) { 
     FiniteIterator cp = *this; 
     --*this; 
     return cp; 
    } 
}; 

Nota que el segundo constructor sólo toma un iterador debido a que el tipo subyacente podría no ser construible por defecto (si es sólo un InputIterator). En el caso en que la persona que llama está creando un iterador "final", no lo usa, porque no será válido una vez que la otra copia se incremente.

Si el tipo de iterador subyacente es RandomAccess, este envoltorio no es necesario/deseado. Así que proporciono una función de plantilla auxiliar, que hace la deducción de tipo de la misma manera que back_inserter para back_insert_iterator.Sin embargo, en el caso de que su tipo de parámetro es un iterador de categoría de acceso aleatorio, el ayudante no debe volver FiniteIterator<T>, pero sólo T:

template <typename Iterator, typename Category> 
struct finite_traits2 { 
    typedef FiniteIterator<Iterator> ret_type; 
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) { 
     return ret_type(d, it); 
    } 
}; 

template <typename Iterator> 
struct finite_traits2<Iterator, std::random_access_iterator_tag> { 
    typedef Iterator ret_type; 
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) { 
     return it + d; 
    } 
}; 

template <typename Iterator> 
struct finite_traits { 
    typedef typename std::iterator_traits<Iterator>::iterator_category itcat; 
    typedef typename finite_traits2<Iterator, itcat>::ret_type ret_type; 
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) { 
     return finite_traits2<Iterator, itcat>::plus(it, d); 
    } 
}; 

template <typename Iterator, typename Distance> 
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it, Distance d) { 
    return finite_traits<Iterator>::plus(it, d); 
} 

template <typename Iterator> 
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it) { 
    return finite_traits<Iterator>::plus(it, 0); 
} 

Ejemplo de uso (y prueba mínima):

#include <iostream> 
#include <typeinfo> 
#include <list> 

struct MyIterator : std::iterator<std::bidirectional_iterator_tag, int> { 
    difference_type count; 
}; 

int main() { 
    std::cout << typeid(MyIterator::iterator_category).name() << "\n"; 
    std::cout << typeid(FiniteIterator<MyIterator>::iterator_category).name() << "\n"; 
    std::cout << typeid(MyIterator::difference_type).name() << "\n"; 
    std::cout << typeid(FiniteIterator<MyIterator>::difference_type).name() << "\n"; 

    int a[] = {1, 2, 3, 4, 5}; 
    std::copy(finite_iterator(a), finite_iterator(a,4), std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 
    std::list<int> al(finite_iterator(a), finite_iterator(a,4)); 
    std::cout << al.size() << "\n"; 
    std::copy(finite_iterator(al.begin()), finite_iterator(al.begin(),3), std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 
} 

Precaución: finite_iterator(x, 1) == finite_iterator(++x, 0) es falso, incluso para un iterador directo o mejor. Los iteradores finitos solo son comparables si se crean desde el mismo punto de partida.

Además, esto aún no está completo. Por ejemplo, std::reverse no funciona, porque para acceder a la referencia, finite_iterator(x, 1) está "apuntando a" x.

Actualmente los siguientes casos a trabajar:

std::list<int>::iterator e = al.begin(); 
std::advance(e,3); 
std::reverse(finite_iterator(al.begin()), finite_iterator(e,3)); 

así que no estoy lejos, pero eso no es una buena interfaz. Tendría que pensar más sobre el caso de los iteradores bidireccionales.

Answer 2

Creo que podría crear un tipo de iterador envoltorio similar a boost::counting_iterator que mantendría juntos un incremento y el iterador subyacente, y se compararía igual a un iterador "final" tan pronto como el incremento exceda el valor máximo.

Answer 3

Ya hay fill_n y generate_n, no hay foreach_n (o for_n probablemente sería más apropiado) pero es bastante fácil escribir uno.

template< typename FwdIter, typename Op, typename SizeType > 
void for_n(FwdIter begin, SizeType n, Op op) 
{ 
    while(n--) 
    { 
     op(*begin); 
     ++begin; 
    } 
} 

que podría hacer op (* comenzar ++), pero aunque es menos escribiéndola puede generar más código para copiar el iterador. size_type es numérico, por lo que el incremento posterior no es menos eficiente y aquí hay un caso en el que es útil.