STL C++: quale metodo di iterazione su un contenitore STL è migliore?

Question

Questo può sembrare strano per alcuni di voi, ma quale dei seguenti 2 metodi di iterazione su un container STL è migliore? Perché?

class Elem; 
typedef vector<Elem> ElemVec; 
ElemVec elemVec; 

// Method 0 
for (ElemVec::iterator i = elemVec.begin(); i != elemVec.end(); ++i) 
{ 
    Elem& e = *i; 
    // Do something 
} 

// Method 1 
for (int i = 0; i < elemVec.size(); ++i) 
{ 
    Elem& e = elemVec.at(i); 
    // Do something 
} 

Metodo 0 sembra STL detergente, ma Metodo 1 ottiene lo stesso con il codice minore. Semplice iterazione su un contenitore è ciò che appare all sul luogo in qualsiasi codice sorgente. Quindi, sono propenso a scegliere il Metodo 1 che sembra ridurre l'ingombro visivo e la dimensione del codice.

PS: So che gli iteratori possono fare molto più di un semplice indice. Ma ti preghiamo di mantenere la risposta/discussione incentrata sulla semplice iterazione su un contenitore come mostrato sopra.

Answer 1

La prima versione funziona con qualsiasi contenitore e quindi è più utile nelle funzioni di modello che prendono qualsiasi contenitore come parametro. È anche leggermente più efficiente, anche per i vettori.

La seconda versione funziona solo per vettori e altri contenitori con indice intero. Sarebbe un po 'più idiomatico per quei contenitori, sarà facilmente comprensibile dai nuovi arrivati ​​al C++, ed è utile se devi fare qualcos'altro con l'indice, il che non è raro.

Come al solito, non c'è una semplice risposta "questa è meglio", temo.

Answer 2

Altri vantaggi del metodo di 0:

• se ci si sposta da vettore a un altro contenitore del ciclo rimane la stessa,
• facile da spostare da iteratore al const_iterator se avete bisogno,
• quando C++ 0x arriverà, la scrittura automatica ridurrà parte del disordine del codice.

Lo svantaggio principale è che in molti casi si esegue la scansione di due contenitori, nel qual caso un indice è più pulito rispetto al mantenimento di due iteratori.

Answer 3

Se non ti dispiace un (molto?) Piccola perdita di efficienza, mi consiglia di utilizzare Boost.Foreach

BOOST_FOREACH(Elem& e, elemVec) 
{ 
    // Your code 
} 

Answer 4

Metodo 0 è più veloce e quindi consigliato.

Il metodo 1 utilizza size() che può essere O (1), a seconda del contenitore e dell'implementazione di stl.

Answer 5

Dipende dal tipo di contenitore. Per un vector, probabilmente non importa quale si utilizza. Il metodo 0 è diventato più idiomatico, ma la loro non è una grande differenza, come dicono tutti.

Se avete deciso di utilizzare un list, invece, il metodo 1 sarebbe, in linea di principio, essere O(N), ma in realtà non esiste un elenco at() metodo, quindi non si può nemmeno farlo in quel modo. (Quindi a un certo livello la tua domanda impila il mazzo.)

Ma questo di per sé è un altro argomento per il metodo 0: utilizza la stessa sintassi per diversi contenitori.

Answer 6

Per coincidenza ho eseguito di recente un test di velocità (riempiendo 10 * 1024 * 1024 pollici con rand()).
Questi sono 3 piste, volta in nano-secondi

vect[i] time  : 373611869 
vec.at(i) time : 473297793 
*it = time  : 446818590 
arr[i] time  : 390357294 
*ptr time   : 356895778 

UPDATE: aggiunto STL-algoritmo std :: generare, che sembra correre il più veloce, a causa della particolare iteratore-ottimizzazione (VC++ 2008). tempo in micro secondi.

vect[i] time  : 393951 
vec.at(i) time : 551387 
*it = time  : 596080 
generate = time : 346591 
arr[i] time  : 375432 
*ptr time   : 334612 

Conclusione: utilizzare algoritmi standard, potrebbero essere più veloci di un ciclo esplicito! (e anche buone pratiche)

Aggiornamento: i tempi di cui sopra erano in una situazione legata all'I/O, ho eseguito gli stessi test con un limite della CPU (iterazione su un vettore relativamente breve, che dovrebbe rientrare nella cache ripetutamente, moltiplicare ogni elemento per 2 e scrivere di nuovo al vettore)

//Visual Studio 2008 Express Edition 
vect[i] time  : 1356811 
vec.at(i) time : 7760148 
*it = time  : 4913112 
for_each = time : 455713 
arr[i] time  : 446280 
*ptr time   : 429595 

//GCC 
vect[i] time  : 431039 
vec.at(i) time : 2421283 
*it = time  : 381400 
for_each = time : 380972 
arr[i] time  : 363563 
*ptr time   : 365971 

interessante notare iteratori e l'operatore [] è notevolmente più lento in VC++ rispetto al for_each (che sembra degradare i iteratori a puntatori attraverso alcuni template-magia per le prestazioni).
In GCC i tempi di accesso sono solo peggiori per a(), che è normale, perché è l'unica funzione di verifica dei range.

Answer 7

Metodo 0, per diversi motivi.

• E 'meglio esprime il vostro intento, che aiuta le ottimizzazioni del compilatore, così come la leggibilità
• off-by-one errori sono meno probabili
• funziona anche se si sostituisce il vettore con una lista, che doesn' t avere operatore []

Naturalmente, la soluzione migliore sarà spesso la soluzione 2: uno degli algoritmi std. std :: for_each, std :: transform, std :: copy o qualsiasi altra cosa di cui hai bisogno. Questo ha alcuni ulteriori vantaggi:

• esprime il vostro intento ancora meglio, e permette alcune ottimizzazioni del compilatore significativi (MS sicuro SCL effettua il controllo dei limiti sui vostri metodi di 0 e 1, ma salterà su algoritmi std)
• È meno codice (almeno nel sito di chiamata. Ovviamente devi scrivere un funtore o qualcosa per rimpiazzare il corpo del loop, ma sul sito di utilizzo, il codice viene ripulito un po ', che probabilmente è dove conta di più

In generale, evitare la sovrastima del codice Specificare esattamente cosa si desidera eseguire e nient'altro. i goritmi sono di solito la strada da percorrere, ma anche senza di loro, se non hai bisogno dell'indice i, perché farlo? Utilizza invece gli iteratori, in quel caso.

Answer 8

Il seguente metodo di iterazione su un contenitore di libreria standard è il migliore.

Usa c++11 (e non solo) 's range-based for-loop con la auto specifier:

// Method 2 
for (auto& e: elemVec) 
{ 
    // Do something with e... 
} 

Questo è simile alla tua Method 0 ma richiede meno di battitura, meno la tenuta e funziona con qualsiasi contenitore compatibile con std::begin() e std::end(), compreso matrici semplici.

Answer 9

Una possibilità non è considerato in precedenza: a seconda dei dettagli di "fare qualcosa", si può avere il metodo e il metodo 0 1 simultaneamente, non è necessario scegliere:

for (auto i = elemVec.begin(), ii = 0; ii < elemVec.size(); ++i, ++ii) 
{ 
    // Do something with either the iterator i or the index ii 
} 

In questo modo, trovare il l'indice o l'accesso al membro corrispondente sono entrambi ottenuti con una complessità insignificante.