C++ push_back vs Insert vs emplace

Question

Attualmente sto facendo un'applicazione utilizzando i vettori con C++.

So come la pre-ottimizzazione è la radice di tutto il male.

Ma davvero non posso fare a meno di essere curioso.

Sto aggiungendo parti di altri vettori in un altro vettore.
diremo il vettore avrà una dimensione che non cambia mai di 300.

Dal momento che ho sempre aggiungere alla fine del vettore

E 'veloce da fare:
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

o sarebbe più veloce per scorrere il vettore che voglio aggiungere e aggiungere ogni elemento singolarmente (pur prenotando in anticipo) con push_back o emplace. (incerto quale è più veloce)

Chiunque può aiutarmi su questo?

Answer 1

Ecco un principio generale: quando una libreria fornisce sia do_x_once e do_x_in_batch, quest'ultimo dovrebbe essere almeno veloce come chiamare do_x_once in un ciclo semplice. In caso contrario, la libreria è implementata molto male poiché un ciclo semplice è sufficiente per ottenere una versione più veloce. Spesso, tali funzioni/metodi batch possono eseguire ulteriori ottimizzazioni perché hanno una conoscenza degli interni della struttura dati.

Quindi, insert deve essere almeno altrettanto veloce come push_back in un ciclo. In questo caso particolare, un'implementazione intelligente di insert può eseguire un singolo reserve per tutti gli elementi che si desidera inserire. push_back dovrebbe verificare la capacità del vettore ogni volta. Non cercare di superare in astuzia la libreria :)

Answer 2

Come dice larsman, più si fa in una singola chiamata di libreria, il è più probabile che sia più efficiente. Nel caso di insert in un vettore, la libreria eseguirà normalmente al massimo una singola ripartizione e per copiare ogni elemento spostato al massimo una volta. Se si utilizza un loop e push_back, è possibile riallocare più volte , che potrebbe essere notevolmente più lento (come un ordine di grandezza ).

A seconda del tipo, tuttavia, può anche essere più veloce di fare qualcosa di simile:

a.resize(300); 
std::copy(b.begin(), b.end(), a.end() - 300); 

ho trovato questo per essere più veloce per semplici tipi scalari (come int) usando g ++ su un Macchina Intel

Answer 3

Suppongo che dipenda davvero dal compilatore (implementazione della libreria), dalla compilazione di opzioni e architettura. Fare un punto di riferimento rapido in VS2005 senza ottimizzazione (/ od) su processori Intel Xeon:

std::vector<int> a; 
std::vector<int> b; 

// fill 'a' with random values for giggles 

timer.start() 
// copy values from 'a' to 'b' 
timer.stop() 

ottengo questi risultati per 10 000 000 voci utilizzando questi diversi metodi di "valori di copia ...":

1. Riserva spazio per 'b', poi per-loop utilizzando b.push_back(a[i]);: 0.808 sec
2. Resize 'b', poi per-loop utilizzando indici assegnazione b[i] = a[i];: 0,264 sec
3. Nessun ridimensionamento 'b', proprio b.insert(b.end(), a.begin(), a.end());: 0,021 sec (nessuna differenza significativa con riserva prima)
4. std::copy(a.begin(), a.end(), std::back_inserter(b));: 0,944 sec (0.871 con riserva prima)
5. Resize 'b', poi memcopy sui puntatori di base memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));: 0.061 sec
012.

Con le ottimizzazioni attivate (/ Ox), tuttavia, è una storia diversa. Ho dovuto aumentare le dimensioni di 100 000 000 per ottenere una maggiore differenziazione:

ciclo
1. push_back: 0.659 sec
2. ciclo indice: 0,482 sec
3. inserto: 0,210 sec (nessuna differenza significativa con riserva prima)
4. std :: copia: 0.422 sec con riserva prima. Ho un cattivo_alloc senza di esso.
5. memcpy: 0,329 sec

Nei interessante notare è che con o senza ottimizzazioni, il metodo di inserimento scalato linearmente. Altri metodi erano chiaramente inefficienti senza ottimizzazioni, ma non riuscivano ancora ad ottenere altrettanto velocemente con loro. Come ha notato James Kanze, è diverso su g ++. Esegui un test con la tua piattaforma per convalidare.