Perché le gamme di iteratori standard ?

Perché lo standard definisce end() come uno dopo la fine, invece che alla fine effettiva?

La migliore argomentazione è facilmente quella di Dijkstra stesso :

  • Vuoi che la dimensione dell’intervallo sia una semplice differenza – inizia ;

  • incluso il limite inferiore è più “naturale” quando le sequenze degenerano a quelle vuote, e anche perché l’alternativa ( escludendo il limite inferiore) richiederebbe l’esistenza di un valore sentinella “one-before-the-beginning”.

Devi ancora giustificare il motivo per cui inizi a contare a zero anziché a uno, ma ciò non faceva parte della tua domanda.

La saggezza dietro la convenzione [inizio, fine] si ripaga di volta in volta quando si ha una sorta di algoritmo che si occupa di più chiamate nidificate o iterate a costruzioni basate su intervalli, che si intrecciano naturalmente. Al contrario, l’utilizzo di una gamma doppiamente chiusa comporterebbe un codice off-by-one ed estremamente sgradevole e rumoroso. Ad esempio, considera una partizione [ n 0 , n 1 ) [ n 1 , n 2 ) [ n 2 , n 3 ). Un altro esempio è il ciclo di iterazione standard for (it = begin; it != end; ++it) , che esegue end - begin times. Il codice corrispondente sarebbe molto meno leggibile se entrambe le estremità fossero inclusivi – e immagina come gestiresti intervalli vuoti.

Infine, possiamo anche fare un buon argomento perché il conteggio dovrebbe iniziare da zero: con la convenzione semiaperta per intervalli che abbiamo appena stabilito, se vi viene assegnato un intervallo di elementi N (diciamo per enumerare i membri di un array), quindi 0 è il naturale “inizio” in modo che tu possa scrivere l’intervallo come [0, N ), senza scomode correzioni o correzioni.

In poche parole: il fatto che non vediamo il numero 1 ovunque negli algoritmi basati sulla distanza è una diretta conseguenza e la motivazione per la convenzione [inizio, fine].

Perché lo standard definisce end() come uno dopo la fine, invece che alla fine effettiva?

Perché:

  1. Evita la gestione speciale per intervalli vuoti. Per intervalli vuoti, begin() è uguale a end() &
  2. Rende semplice il criterio di fine per cicli che iterano sugli elementi: i cicli continuano semplicemente finché non viene raggiunto end() .

In realtà, molte cose correlate all’iterator hanno improvvisamente molto più senso se si considerano gli iteratori che non puntano agli elementi della sequenza ma in mezzo , con il dereferenziamento che accede al prossimo elemento proprio ad esso. Quindi l’iteratore “one past end” ha improvvisamente un senso immediato:

  +---+---+---+---+ | A | B | C | D | +---+---+---+---+ ^ ^ | | begin end 

Ovviamente begin punti all’inizio della sequenza e i punti end alla fine della stessa sequenza. La dereferenziazione begin accedere all’elemento A , e la end dereferenziamento non ha senso perché non c’è alcun elemento giusto. Inoltre, aggiunge un iteratore i nel mezzo

  +---+---+---+---+ | A | B | C | D | +---+---+---+---+ ^ ^ ^ | | | begin i end 

e immediatamente si vede che l’intervallo di elementi da begin a i contiene gli elementi A e B mentre l’intervallo di elementi da i a end contiene gli elementi C e D Il dereferenziamento dà l’elemento giusto, cioè il primo elemento della seconda sequenza.

Persino il “fuori campo” per gli iteratori inversi diventa improvvisamente ovvio in questo modo: l’inversione di tale sequenza dà:

  +---+---+---+---+ | D | C | B | A | +---+---+---+---+ ^ ^ ^ | | | rbegin ri rend (end) (i) (begin) 

Ho scritto i corrispondenti iteratori non inversi (base) tra parentesi qui sotto. Vedete, l’iteratore inverso appartenente a i (che ho chiamato ri ) punta ancora tra gli elementi B e C Tuttavia, a causa dell’inversione della sequenza, ora l’elemento B è a destra.

Perché allora

 size() == end() - begin() // For iterators for whom subtraction is valid 

e non dovrai fare cose strane come

 // Never mind that this is INVALID for input iterators... bool empty() { return begin() == end() + 1; } 

e non accidentalmente scrivere codice errato come

 bool empty() { return begin() == end() - 1; } // a typo from the first version // of this post // (see, it really is confusing) bool empty() { return end() - begin() == -1; } // Signed/unsigned mismatch // Plus the fact that subtracting is also invalid for many iterators 

Inoltre: cosa troverebbe find() return if end() indicato un elemento valido?
Vuoi davvero un altro membro chiamato invalid() che restituisce un iteratore non valido ?!
Due iteratori sono già abbastanza dolorosi …

Oh, e vedi questo post correlato .


Anche:

Se la end era prima dell’ultimo elemento, come insert() alla fine vera ?!

L’idioma iteratore di intervalli semichiusi [begin(), end()) si basa in origine sull’aritmetica del puntatore per gli array semplici. In quella modalità di funzionamento, avresti funzioni che sono state passate una matrice e una dimensione.

 void func(int* array, size_t size) 

La conversione in intervalli semichiusi [begin, end) è molto semplice quando si dispone di tali informazioni:

 int* begin; int* end = array + size; for (int* it = begin; it < end; ++it) { ... } 

Per lavorare con intervalli completamente chiusi, è più difficile:

 int* begin; int* end = array + size - 1; for (int* it = begin; it <= end; ++it) { ... } 

Poiché i puntatori agli array sono iteratori in C ++ (e la syntax è stata progettata per consentire ciò), è molto più semplice chiamare std::find(array, array + size, some_value) piuttosto che chiamare std::find(array, array + size - 1, some_value) .


Inoltre, se lavori con intervalli semichiusi, puoi usare l'operatore != Per verificare la condizione finale, perché (se gli operatori sono definiti correttamente) < implica != .

 for (int* it = begin; it != end; ++ it) { ... } 

Tuttavia non esiste un modo semplice per farlo con intervalli completamente chiusi. Sei bloccato con <= .

L'unico tipo di iteratore che supporta le operazioni < e > in C ++ sono iteratori ad accesso casuale. Se dovessi scrivere un operatore <= per ogni class iteratore in C ++, dovresti rendere tutti i tuoi iteratori completamente confrontabili e faresti meno scelte per creare iteratori meno capaci (come gli iteratori bidirezionali su std::list , o gli iteratori di input che operano su iostreams ) se C ++ utilizza gamme completamente chiuse.

Con end() punta verso la fine, è facile iterare una collezione con un ciclo for:

 for (iterator it = collection.begin(); it != collection.end(); it++) { DoStuff(*it); } 

Con end() punta all’ultimo elemento, un ciclo sarebbe più complesso:

 iterator it = collection.begin(); while (!collection.empty()) { DoStuff(*it); if (it == collection.end()) break; it++; } 
  1. Se un contenitore è vuoto, begin() == end() .
  2. I programmatori C ++ tendono a usare != Invece di < (meno di) in condizioni di loop, quindi avere end() punta a una posizione off-the-end è conveniente.