limite algoritmi STL a N elementi

Question

(ispirato da un commento da nakiya)

Molti algoritmi STL prendono un intervallo come coppia di iteratori. Ad esempio, for_each(begin, end, &foo);. Ovviamente, se distance(begin, end) >= N e si inizia con un iteratore ad accesso casuale, allora for_each(begin, begin+N, &foo); si applica solo ai primi N elementi foo.

Ora c'è un'alternativa pulita e generica se una di queste due condizioni non viene soddisfatta?

Answer 1

Non esiste una soluzione completa generica senza modificare il tipo di iteratore.

Dimostrazione: supponiamo che il tipo iteratore è solo un InputIterator, così begin riferisce effettivamente (ad esempio) un flusso, e end è un marcatore iteratore speciale-caso, che confronterà pari all'iteratore "reale" una volta che il il vero iteratore ha letto EOF.

Poi qualsiasi uso di begin per cercare di elaborare un nuovo valore di end passare l'algoritmo, si "consuma" il valore originale di begin, dal momento che è così che il lavoro InputIterators.

Che cosa si potrebbe fare è scrivere una classe wrapper iteratore, in modo tale che i conteggi iteratore quante volte è stato incrementato, e mette a confronto pari ad un iteratore "fine" una volta che è stato incrementato N volte. N potrebbe essere un parametro template o un parametro costruttore per uno o più degli iteratori.

Qualcosa di simile. L'ho testato compila e lavora per me. Ancora da fare - Attualmente sto gestendo solo una delle tue due situazioni, "non un iteratore ad accesso casuale". Non gestisco anche l'altro, "distanza < 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; 
    } 
}; 

noti che il secondo costruttore richiede solo un iteratore perché il tipo sottostante potrebbe non essere costruibile predefinito (se è solo un'InputIterator). Nel caso in cui il chiamante stia creando un iteratore di "fine", non lo usa, perché non sarà valido una volta incrementata l'altra copia.

Se il tipo di iteratore sottostante è RandomAccess, questo wrapper non è necessario/voluto. Quindi fornisco una funzione template helper, che fa la deduzione del tipo allo stesso modo back_inserter per back_insert_iterator.Tuttavia, nel caso in cui il suo tipo di parametro è un iteratore di categoria ad accesso casuale, l'aiutante non dovrebbe tornare FiniteIterator<T>, ma proprio 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); 
} 

Esempio di utilizzo (e prova di minima):

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

Attenzione: finite_iterator(x, 1) == finite_iterator(++x, 0) è false, anche per un iteratore in avanti o migliore. Gli iteratori finiti sono paragonabili solo se vengono creati dallo stesso punto di partenza.

Inoltre, questo non è ancora completo. Ad esempio, std::reverse non funziona, perché ai fini dell'accesso al referente, finite_iterator(x, 1) sta "puntando a" x.

attualmente i seguenti succede a lavorare:

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

, quindi non sono molto lontano, ma non è una buona interfaccia. Avrei bisogno di pensare di più al caso degli iteratori bidirezionali.

Answer 2

Credo che si possa creare un tipo di iteratore wrapper simile a boost::counting_iterator che mantenga insieme sia un incremento che l'iteratore sottostante, e sarebbe uguale a un iteratore "finale" non appena l'incremento supera il valore massimo.

Answer 3

C'è già fill_n e generate_n, non c'è foreach_n (o for_n sarebbe probabilmente più appropriato) ma è abbastanza facile scriverne uno.

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

si potrebbe fare op (* inizio ++), ma anche se è meno digitando può generare più codice da copiare l'iteratore. size_type è numerico, quindi fare post-incremento non è meno efficiente e qui è un caso in cui è utile.