C++
iteratori

C Iterators (Puntatori)

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

Questo codice produrrebbe i numeri da 1 a 5, uno su ogni riga come questa:

1
2
3
4
5

Breaking It Down

const int array[] = { 1, 2, 3, 4, 5 };

Questa linea crea un nuovo array intero con 5 valori. Gli array C sono solo indicatori della memoria in cui ogni valore è memorizzato insieme in un blocco contiguo.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

Queste linee creano due puntatori. Il primo puntatore riceve il valore del puntatore dell'array, che è l'indirizzo del primo elemento dell'array. L'operatore sizeof quando usato su un array C restituisce la dimensione dell'array in byte. Diviso per la dimensione di un elemento, questo dà il numero di elementi nella matrice. Possiamo usarlo per trovare l'indirizzo del blocco dopo l'array.

for (const int* i = first; i < afterLast; ++i) {

Qui creiamo un puntatore che utilizzeremo come un iteratore. E 'inizializzato con l'indirizzo del primo elemento che vogliamo iterare, e noi continueremo a iterare finché i è minore afterLast , il che significa che il tempo che i sta puntando a un indirizzo all'interno array .

    std::cout << *i << std::endl;

Infine, all'interno del loop possiamo accedere al valore che il nostro iteratore i sta indicando attraverso il dereferenziamento. Qui l'operatore dereferenzia * restituisce il valore all'indirizzo in i .

Panoramica

Gli iteratori sono posizioni

Gli iteratori sono un mezzo per navigare e operare su una sequenza di elementi e sono un'estensione generalizzata dei puntatori. Concettualmente è importante ricordare che gli iteratori sono posizioni, non elementi. Ad esempio, prendi la seguente sequenza:

A B C

La sequenza contiene tre elementi e quattro posizioni

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

Gli elementi sono cose all'interno di una sequenza. Le posizioni sono luoghi in cui operazioni significative possono accadere alla sequenza. Ad esempio, uno si inserisce in una posizione, prima o dopo l' elemento A, non in un elemento. Anche la cancellazione di un elemento ( erase(A) ) viene effettuata individuando innanzitutto la sua posizione, quindi eliminandola.

Da Iterators ai valori

Per convertire da una posizione a un valore, un iteratore è dereferenziato :

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

Si può pensare a un iteratore come al dereferenziamento del valore a cui si riferisce nella sequenza. Ciò è particolarmente utile per capire perché non si dovrebbe mai dereferenziare l'iteratore di end() in una sequenza:

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

In tutte le sequenze e i contenitori trovati nella libreria standard C ++, begin() restituirà un iteratore alla prima posizione e end() restituirà un iteratore a una passata l'ultima posizione ( non l'ultima posizione!). Di conseguenza, i nomi di questi iteratori negli algoritmi sono spesso etichettati first e last :

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

È anche possibile ottenere un iteratore per qualsiasi sequenza , perché anche una sequenza vuota contiene almeno una posizione:

+---+
|   |
+---+

In una sequenza vuota, begin() e end() saranno la stessa posizione, e nessuno dei due può essere dereferenziato:

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

La visualizzazione alternativa degli iteratori è che essi segnano le posizioni tra gli elementi:

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

e la dereferenziazione di un iteratore restituisce un riferimento all'elemento che viene dopo l'iteratore. Alcune situazioni in cui questa visualizzazione è particolarmente utile sono:

• insert operazioni inserirà elementi nella posizione indicata dall'iteratore,
• erase operazioni restituirà un iteratore corrispondente alla stessa posizione di quello passato,
• un iteratore e il suo iteratore inverso corrispondente si trovano nella stessa posizione tra gli elementi

Iteratori non validi

Un iteratore viene invalidato se (ad esempio nel corso di un'operazione) la sua posizione non fa più parte di una sequenza. Un iteratore non valido non può essere cancellato fino a quando non è stato riassegnato a una posizione valida. Per esempio:

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

I numerosi algoritmi e le funzioni dei membri della sequenza nella libreria standard C ++ hanno regole che governano quando gli iteratori sono invalidati. Ogni algoritmo è diverso nel modo in cui tratta (e invalida) gli iteratori.

Navigazione con Iterators

Come sappiamo, gli iteratori sono per le sequenze di navigazione. Per fare ciò, un iteratore deve migrare la sua posizione per tutta la sequenza. Gli iteratori possono avanzare nella sequenza e alcuni possono avanzare all'indietro:

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

Nota, il secondo argomento di std :: distance dovrebbe essere raggiungibile dal primo (o, in altre parole, first dovrebbe essere minore o uguale del second ).

Anche se è possibile eseguire operatori aritmetici con iteratori, non tutte le operazioni sono definite per tutti i tipi di iteratori. a = b + 3; funzionerebbe per Iterator di accesso casuale, ma non funzionerebbe per gli iteratori di andata o bidirezionali, che possono ancora essere fatti avanzare di 3 posizioni con qualcosa come b = a; ++b; ++b; ++b; . Pertanto, si consiglia di utilizzare funzioni speciali nel caso in cui non si è sicuri di quale sia il tipo di iteratore (ad esempio, in una funzione modello che accetta iteratore).

Iterator Concepts

Lo standard C ++ descrive diversi concetti di iteratore. Questi sono raggruppati in base a come si comportano nelle sequenze a cui si riferiscono. Se si conosce il concetto di un modello iteratore (si comporta come), si può essere certi del comportamento di tale iteratore indipendentemente dalla sequenza a cui appartiene . Sono spesso descritti in ordine dal più piccolo al meno restrittivo (perché il prossimo concetto di iteratore è un passo migliore del suo predecessore):

• Input Iterators: può essere dereferenziato solo una volta per posizione. Può solo avanzare e solo una posizione alla volta.
• Iteratori di inoltro: un iteratore di input che può essere dereferenziato qualsiasi numero di volte.
• Iteratori bidirezionali: un iteratore diretto che può anche avanzare all'indietro di una posizione alla volta.
• Iteratori di accesso casuale: un iteratore bidirezionale che può avanzare avanti o indietro di un numero qualsiasi di posizioni alla volta.
• Iteratori contigui (dal C ++ 17): un iteratore di accesso casuale che garantisce che i dati sottostanti siano contigui in memoria.

Gli algoritmi possono variare a seconda del concetto modellato dagli iteratori a cui sono assegnati. Ad esempio, sebbene random_shuffle possa essere implementato per gli iteratori di inoltro, potrebbe essere fornita una variante più efficiente che richiede iteratori di accesso casuale.

Tratti iteratori

I tratti iteratori forniscono un'interfaccia uniforme alle proprietà degli iteratori. Permettono di recuperare valore, differenza, puntatore, tipi di riferimento e anche categoria di iteratore:

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

La categoria di iteratore può essere utilizzata per specializzare gli algoritmi:

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

Le categorie di iteratori sono fondamentalmente concetti di iteratori, ad eccezione degli Iterator contigui che non hanno il proprio tag, poiché è stato trovato che interrompe il codice.

Iteratori inversi

Se vogliamo scorrere a ritroso attraverso un elenco o un vettore, possiamo usare un reverse_iterator . Un iteratore inverso è costituito da un iteratore bidirezionale o di accesso casuale che mantiene come membro a cui è possibile accedere tramite base() .

Per eseguire iterazioni all'indietro, utilizzare rbegin() e rend() come gli iteratori rispettivamente per la fine della raccolta e l'inizio della raccolta.

Ad esempio, per iterare all'indietro utilizzare:

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

Un iteratore inverso può essere convertito in un iteratore in avanti tramite la funzione membro di base() . La relazione è che l'iteratore inverso fa riferimento a un elemento dopo l'iteratore di base() :

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

Nella visualizzazione in cui gli iteratori segnano le posizioni tra gli elementi, la relazione è più semplice:

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

Iterator vettoriale

begin restituisce un iterator al primo elemento nel contenitore della sequenza.

end restituisce un iterator al primo elemento dopo la fine.

Se l'oggetto vettoriale è const , sia begin che end restituiscono un const_iterator . Se vuoi che venga restituito un const_iterator anche se il tuo vettore non è const , puoi usare cbegin e cend .

Esempio:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Produzione:

1 2 3 4 5

Mappa Iterator

Un iteratore del primo elemento nel contenitore.

Se un oggetto mappa è const-qualificato, la funzione restituisce un const_iterator . In caso contrario, restituisce un iterator .

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

Produzione:

a => 200
b => 100
c => 300

Stream Iterators

Gli iteratori di streaming sono utili quando è necessario leggere una sequenza o stampare dati formattati da un contenitore:

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

Il programma di esempio stamperà 1 -- 2 -- 3 -- 4 -- sullo standard output.

Scrivi il tuo iteratore supportato dal generatore

Un modello comune in altri linguaggi sta avendo una funzione che produce un "flusso" di oggetti, ed essendo in grado di usare il codice loop per passarci sopra.

Possiamo modellarlo in C ++ come

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

esempio dal vivo

Archiviamo l'elemento generato in anticipo in modo da poter rilevare più facilmente se siamo già alla fine.

Poiché la funzione di un iteratore del generatore finale non viene mai utilizzata, è possibile creare un intervallo di iteratori di generatore copiando solo la std::function una volta. Un iteratore generatore predefinito è paragonabile a se stesso ea tutti gli altri iteratori del generatore finale.