C++ Panoramica


Esempio

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.