In che modo end() è implementato nei contenitori STL?

Così, quando abbiamo bisogno di attraversare un contenitore dall'inizio alla fine abbiamo scrivere qualcosa di simileIn che modo end() è implementato nei contenitori STL?

for (i = v->begin(); i != v->end(); i++)

assumendo i è un iteratore per il contenitore v.

La mia domanda è "che cosa garantisce che la fine punta sempre a passare l'ultimo elemento nel contenitore?" In che modo STL garantisce questo comportamento e c'è qualche possibilità che questo caso non sia vero?

fonte

2010-09-28 user283403

L'STL non garantisce questo comportamento. STL ** implementa ** questo comportamento in base ai requisiti definiti dallo standard. Lo standard dice che questo è il modo in cui dovrebbe funzionare lo sviluppatore che implementa il STL dovrebbe quindi far funzionare correttamente l'STL. –

Non è la migliore pratica. Preferisco l'operatore di pre-incremento ++ i piuttosto che i ++ quando non si memorizza il valore. Per molti tipi è più veloce. –

@Jive Dadson: questa non è la mia preoccupazione principale -> ricalcolare 'v-> end()' ad ogni giro del ciclo è certamente meno efficiente ... 'for (auto it = v.begin(), end = v .end(); it! = end; ++ it) 'è la forma canonica, anche se in C++ 0x si potrebbe anche usare' for (auto val: v) 'o' std :: foreach' e un lambda funzione. –

La specifica di stl garantisce che la fine sarà uno dopo la fine See here. Questo sarà sempre il caso. Esattamente come ciò può dipendere dall'implementazione (a volte i valori sono solo impostati su null, ad esempio), ma ti assicuro che il tuo loop sarà OK fintanto che v è un puntatore valido.

fonte

2010-09-28 06:48:32 JoshD

"la fine punta sempre a uno dopo l'ultimo elemento nel contenitore" significa che se si incrementa l'iteratore che punta all'ultimo elemento sarà uguale al risultato di end(). L'implementazione può essere diversa. In Visual C++ std::vector::end() restituisce l'iteratore specifico dell'implementazione che contiene il puntatore zero.

fonte

2010-09-28 06:52:13

Ne dubito fortemente, poiché 'std :: vector :: iterator' è un iteratore ad accesso casuale. Se 'std :: vector :: end()' ha restituito '(T *) 0',' end() - begin() 'sarebbe illegale, ma deve restituire' std :: vector :: size() ' – MSalters

Per essere più corretti:' end' restituisce l'iteratore specifico di implementazione che contiene il puntatore zero. –

La parte di * con puntatore a zero * è, beh, non necessaria e imprecisa. Nell'implementazione del vettore gcc, 'vector <> :: end()' è definito come 'vector <> :: begin() + vector <> :: size()', ed è in realtà memorizzato nell'oggetto 'vector <>' (Il vettore GCC è implementato mediante tre puntatori: * begin *, * end * e * end_of_capacity *, dove 'begin == end' se il vettore è vuoto,' begin + size() == end' in ogni momento e 'end == end_of_capacity' if' size() == capacity() '. Non ci sono * puntatore zero * ovunque per essere visto. –

C++ 03 Sezione 23.1/7 dice

begin() restituisce un iteratore riferimento al primo elemento nel contenitore.

end() restituisce un iteratore che rappresenta il valore univoco per il contenitore.

Se il contenitore è vuoto, quindi begin() == end();

fonte

2010-09-28 06:53:17

È questa la ragione per cui slist non è ufficialmente STL? la fine() di slist è 0 – vrdhn

STL assicura il problema memorizzando sempre cose come questa:

vector

Alla fine (gioco di parole), non importa quanto end()è, purché sia sempre end() (e, ovviamente, non può essere confuso con nessun altro nodo).

fonte

2010-09-28 06:56:38

+13

Mate, ottieni +1 solo per la grafica funky: -) – paxdiablo

Paint FTW, direi :) –

La citazione riportata di seguito dallo standard C++ non invalida questa risposta? soprattutto la grafica. – yasouser

Stai chiedendo informazioni su tutti i contenitori STL ... non un accenno al vettore specifico dove end() potrebbe essere implementato come come ovviamente ti aspetti. Qual è la fine della std :: map <>? La "fine è un passato dell'ultimo nodo utilizzato", la cosa è solo un concetto logico, che esprime che è possibile incrementare in modo sicuro da quell'ultimo nodo utilizzato, differenziarlo/equivalerlo dal/al concetto astratto di "fine" e fare qualche nodo aritmetica dove end è considerato uno più lungo dell'ultimo nodo utilizzato. Non prenderlo troppo alla lettera.

fonte

2010-09-28 06:56:38

Come alcuni dei precedenti poster hanno dichiarato che end() è uno dopo l'elemento finale. Se è necessario accedere all'ultimo elemento tramite iteratori, utilizzare iter = container.end() - 1; Altrimenti, nel caso dei vettori, variable = someVector.back(); Se si presuppone che la variabile sia del tipo di dati someVector.

Riguardo a ciò che garantisce che punta alla fine, il contenitore stesso lo gestisce internamente.Devi solo trattarlo come una scatola nera come qualsiasi altro oggetto e fidarsi che lo faccia correttamente.

Ogni volta che il contenitore viene ridimensionato, verrà tracciato dove si trova la fine e sarà aggiornato prima di accedere nuovamente a end(). A seconda del contenitore, tuttavia, se si dispone di un iteratore e lo si altera in qualche modo, può invalidare l'iteratore e interrompere il processo di iterazione.

fonte

2013-04-15 23:24:06 steviesama

In che modo end() è implementato nei contenitori STL?

risposta

Problemi correlati