Efficienza della funzione di copia STL

Question

Sto provando a creare un insieme di parole univoche da un elenco di voci, ognuna delle quali ha un vettore di stringhe.

Così ho fatto una funzione chiamata Inserisci, che viene chiamata per ciascuna delle voci come queste:

for(auto & e : _Entries) 
    _Dictionary.Insert(begin(e.getNameWords()), end(e.getNameWords())); 

Il _Dictionary classe ha al suo interno un set (il contenitore STL) e ho scritto la funzione di inserimento nel modo seguente :

template< typename InputIterator > 
void Insert(InputIterator first, InputIterator last) 
{ 
    for(auto it = first ; it != last ; ++it) 
     _AllWords.insert(*it); 
} 

Nel mio caso, chiamando inserimento per tutte le voci _Entries preso una media di 570 millisecondi.

poi ho pensato che avrei dovuto utilizzare le funzioni che lo STL ha già a fare la stessa cosa che il ciclo for in Inserire lo fa, così ho cambiato la funzione Inserire la seguente:

template< typename InputIterator > 
void Insert(InputIterator first, InputIterator last) 
{ 
    copy(first, last, inserter(_AllWords, begin(_AllWords))); 

} 

ero aspettandosi questo per

1. essere più corretto, e
2. essere almeno altrettanto veloce, se non di più

(guidato dalla filosofia di lasciare che STL faccia quanto più possibile per te). Tuttavia, sono stato sorpreso di notare che questa implementazione ha effettivamente richiesto più tempo; non molto di più, ma un costante di 200 millisecondi in più rispetto alla precedente implementazione basata sul ciclo.

So che questa è una differenza di velocità essenzialmente insignificante, ma sono ancora sorpreso.

Quindi la mia domanda è: perché la mia implementazione è più veloce?

Nota: lo sto compilando con la versione 3.5.2 di clang con la libreria standard libC++ e con il flag -O3, in Ubuntu 14.04.

Answer 1

Il problema è questo:

copy(first, last, inserter(_AllWords, begin(_AllWords))); 

finisce per chiamare questa versione di insert:

iterator insert(iterator hint, const value_type& value); 

con begin() come il suggerimento. Questo, in genere, non è dove vorrete inserire ogni valore. Di conseguenza, stai semplicemente facendo in modo che il contenitore lavori di più cercando di capire dove aggiungere i tuoi valori dal momento che il tuo hint è il il più cattivo possibile.

ma nota che c'è anche questo sovraccarico di insert:

template< class InputIt > 
void insert(InputIt first, InputIt last); 

che si dovrebbe semplicemente usare ^{& pugnale;}:

template< typename InputIterator > 
void Insert(InputIterator first, InputIterator last) 
{ 
    _AllWords.insert(first, last); 
} 

E side-nota, _AllWords è un identificatore riservato.

---

^{e pugnale;} Sebbene basa su questa note:

I sovraccarichi (5-6) sono spesso implementate come un ciclo che chiama il sovraccarico (3) con end() come suggerimento; sono ottimizzati per l'aggiunta di una sequenza ordinata (ad esempio un altro set) il cui elemento più piccolo è maggiore l'ultimo elemento *this

che sembra un obiettivo molto preciso per ottimizzare contro, che si può o non può soddisfare, quindi probabilmente non dovresti usare questo sovraccarico e il tuo ciclo iniziale va bene.