Come sono collegati gli iteratori e i puntatori?

Question

Il codice con gli iteratori è simile al codice con i puntatori. Gli iteratori sono di un tipo oscuro (ad esempio std::vector<int>::iterator).

Quello che non capisco è il modo in cui gli iteratori e il puntatore sono correlati tra loro - è un iteratore un involucro attorno a un puntatore con operazioni sovraccariche per passare ad elementi adiacenti o è qualcos'altro?

Answer 1

Gli iteratori sono una generalizzazione dei puntatori.

Un iteratore (a seconda delle varianti) devono implementare * e ++

Quindi un puntatore è un iteratore. Ma non necessariamente il contrario.

Se si desidera eseguire un'iterazione su una struttura complessa (un albero, un grafico ...), l'iteratore sarà molto più di un puntatore e non farà alcun riferimento ad alcun posto effettivo nella ram.

Answer 2

Concettualmente, sì, ma non devono essere indicatori. I loro interni e le loro funzionalità dipenderanno dalla struttura dei dati che "avvolgono".

Ecco perché ci sono diversi "classes" of iterators. Per esempio. Unidirezionale, Bidirezionale, RandomAccess, ecc.

Alcuni sono in grado di classi multiple.

E.g. se la struttura interna è un albero rosso-nero o una lista collegata, gli iteratori potrebbero essere bidirezionali, ma non RandomAccess. Se avvolgono un vettore (implementato come array), avrai RandomAccess e Bidirectional.

Answer 3

Gli iteratori sono oggetti che sovraccaricano determinati operatori, quindi l'utilizzo sembrerebbe essere dei puntatori. Questo rientra nelle capacità di una determinata categoria di iteratori. Gli iteratori di accesso casuale sembrano interamente puntatori, altri tipi di iteratori non forniscono alcune operazioni (ad esempio, list<X>::iterator che è bidirezionale non ha l'operatore += tra molti altri che richiederebbero l'accesso casuale).

Per quanto riguarda i "nomi oscuri", non è del tutto impensabile utilizzare un puntatore normale per un iteratore:

template <class T> 
class MyContainer 
{ 
    ... 
    typedef T* iterator; 
} 

MyContainer<int>::iterator it; //the type is really int* 

Answer 4

Un iteratore è solo un concetto che fornisce l'interfaccia necessaria per iteratori - questi sono diversi per i diversi tipi di iteratori e sono specificati nella sezione 24.1 dello standard C++ (Iterator Requirements).

Il modo in cui gli iteratori vengono implementati dipende da cosa iterano sopra - per i vettori essi sono comunemente un wrapper attorno a un singolo puntatore a un array (in build di rilascio comunque), per i contenitori più complessi hanno un'implementazione più complicata. Per le gamme aperte, esse contengono lo stato di qualsiasi algoritmo utilizzato per generare gli elementi.

Si noti che un puntatore a un elemento in un array soddisfa i requisiti di un iteratore di accesso casuale, quindi in una certa misura sono intercambiabili.