Come funziona la categoria iteratore in C++?

Question

Ho cercato di capire implementazione iteratore, e mentre giocare con la fonte, ho visto questa dichiarazione:

typedef output_iterator_tag iterator_category; 

Non capisco come questo lavoro typedef all'interno della classe? Qual è l'effetto collaterale che fornisce? Qualcuno può camminarmi attraverso questo?

Answer 1

È necessario leggere la programmazione generica perché non è possibile ottenere questa risposta.

"Output Iterator" è un concetto che certi iteratori corrispondono. Ogni iteratore che è una realizzazione di questo concetto ha determinate funzionalità ad esso associate. È un po 'come l'ereditarietà, ma non lo è.

C++ non ha nulla di simile che rappresenti concetti (era una proposta aggiunta a C++ 0x ma non è riuscita a farlo). Stando così le cose, abbiamo bisogno di vari costrutti di template per permetterci di associare un "tag" con un tipo di iteratore. Associando il tipo output_iterator_tag con un iteratore stiamo affermando che il nostro tipo iteratore realizza il concetto OutputIterator.

Questo diventa molto importante quando si sta tentando di scrivere algoritmi il più possibile ottimizzati e anche generici. Ad esempio, eseguire un ordinamento con un iteratore che può essere incrementato o decrementato con un valore arbitrario (diverso da 1 in altre parole) è più efficiente di uno che non ha questa capacità. Inoltre, per ottenere un nuovo iteratore che sia la distanza X da un'altra può richiedere diverse operazioni a seconda delle capacità dell'iteratore. Per scrivere un tale algoritmo si usa "tag deploying". Per spiegarlo meglio, ecco un'implementazione (non testata) di std :: advance che funziona sia con gli iteratori che hanno un operatore + = che quelli che hanno solo un operatore ++ ed è il più veloce possibile con entrambe le versioni.

template < typename RandomAccessIterator > 
RandomAccessIterator advance(RandomAccessIterator it 
          , int amount 
          , random_access_iterator_tag) 
{ return it + amount; } 

template < typename ForwardIterator > 
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag) 
{ 
    for (;amount; --amount) ++it; 
    return it; 
} 

template < typename Iterator > 
Iterator advance(Iterator it, int amount) 
{ 
    typedef typename std::iterator_traits<Iterator>::iterator_tag tag; 
    advance(it, amount, tag()); 
} 

Ecco a memoria quindi è probabilmente pieno di bug (probabilmente hanno un sacco di tipi di sbagliato pari) ... ma questa è l'idea. I tag iteratore sono tipi che sono vuoti e che ereditano l'uno dall'altro esattamente nello stesso modo in cui i concetti si raffinano a vicenda. Ad esempio, un iteratore di accesso casuale è un iteratore diretto. Quindi random_access_iterator_tag è un derivato di forward_iterator_tag. A causa delle regole di risoluzione dell'overload delle funzioni, il passaggio di un random_access_iterator_tag alla funzione si risolve in tale versione della funzione anziché in forward_iterator_tag.

Ancora una volta, vai a leggere sulla programmazione generica. È essenziale utilizzare tutta la potenza del C++.

Oh, e infine ... Il typedef è presente nella definizione di classe dell'iteratore perché è un posto carino e conveniente in cui inserirlo. Un iterator_traits predefinito può cercarlo lì. Ti consigliamo di usare iterator_traits invece di quella definizione perché i puntatori raw sono anche iteratori e non possono avere typedef interni.

Answer 2

output_iterator_tag è una classe vuota. Il suo scopo è di consentire agli algoritmi di identificare classificazioni generiche di iteratori che seguono determinate regole e forniscono particolari operatori. Ciò consente agli algoritmi di fornire un'implementazione più specializzata di un determinato algoritmo in determinate condizioni.

Per esempio nell'intestazione di VS2010, "std :: distanza" 's algoritmo ha due implementazioni a seconda del 'iterator_category' typedef nelle iteratori passati in.

std :: distanza richiede solo un iteratore ingresso per calcolare la distanza tra due iteratori, ma potrebbe richiedere tempo lineare 'O (n)' per calcolare la risposta.

Se, tuttavia, il compilatore capisce che viene utilizzato un iteratore di accesso casuale e può quindi trarre vantaggio dall'operatore di sottrazione per calcolare la distanza nel tempo costante "O (1)".

Vorrei raccomandare di guardare Stephan T. Lavavej video dove va un po 'in caratteri tipografici e il loro uso nella libreria di modelli standard.