Se si implementa una classe di array nel modo in cui viene comunemente implementata, le sue prestazioni sono più lente rispetto al suo equivalente STL come un vettore. Quindi cosa rende i contenitori/algoritmi STL veloci?Cosa rende veloce STL?
Gli algoritmi STL come for_each accettano oggetti funzione che possono essere facilmente inseriti. C, d'altra parte, utilizza i puntatori di funzione che sono molto più difficili da ottimizzare per il compilatore.
Questo fa una grande differenza in alcuni algoritmi come l'ordinamento in cui la funzione di confronto deve essere chiamata più volte.
Wikipedia ha some more information nel caso siate interessati.
EDIT:
Come per la classe di vettore del STL, non credo che sia necessariamente più veloce che quello che si potrebbe trovare, per esempio, glibc.
questo è probabilmente uno dei punti chiave: D –
interessante ... – toto
La libreria standard utilizza buoni algoritmi, come nel caso di un array (std :: vector) di solito raddoppia lo spazio di archiviazione ogni volta che si esaurisce lo spazio, mentre un'implementazione ingenua può incrementare lo storage di un elemento ogni volta. Poiché aumentare la quantità di memoria è molto lento (tutti i dati esistenti devono essere copiati dalla vecchia allocazione alla nuova allocazione), ciò può fare una grande differenza.
Analogamente, tutti gli altri algoritmi sono implementati in modi piuttosto ottimali. La libreria standard di solito non utilizza alcun tipo di srotolamento del loop o altre ottimizzazioni del genere a livello di codice sorgente. È semplicemente un codice buono e semplice (con nomi di variabili orribili e molti modelli) ottimizzato dal compilatore.
Quello che ho detto non è specificato dallo standard C++, ma è quello che sembra essere la pratica comune nelle implementazioni esistenti.
Doppio lo spazio di archiviazione può essere davvero pessimo dopo aver raggiunto un megabyte o così .... –
Hassan Syed: Non si spreca mai più del 50% della memoria allocata. Non lo chiamerei "abbastanza cattivo". –
Apparentemente std :: vector cresce di un fattore di 1,5: http://amitp.blogspot.com/2003_11_01_amitp_archive.html#106843046050898865 – Manuel
Gli algoritmi in STL sono stati studiati per anni da tutti i livelli di matematici e informatici, e in genere utilizzano gli algoritmi più efficienti in assoluto, che la vostra implementazione potrebbe non utilizzare. L'implementazione comune è quella che probabilmente non è la più veloce, ma è più facile da capire; l'STL sta probabilmente utilizzando un'implementazione più ottimizzata.
Quando tutti i tipi di persone altamente istruite hanno benedetto qualcosa (SE loro hanno) non pensate che non sia necessario pensarci. Sono abbastanza abili e qualificati a sbagliare. –
-1: Direi che non è proprio una dichiarazione vera. Gli "algoritmi" sono specifici per l'implementazione. Viene specificato solo il comportamento esposto degli algoritmi/contenitori STL, ecc. Ci sono molte molte implementazioni dell'STL e non tutte sono state scrutinate (anzi, direi che la maggior parte non l'hanno) a un livello vicino a un livello che tu rivendichi. Molte implementazioni sono migliori di quelle che il codificatore medio può scrivere, ma un buon programmatore può facilmente competere con loro ... –
La maggior parte delle classi di array delle persone aumenta le dimensioni di un incremento costante anziché di un fattore costante (come richiede la libreria standard). Ciò significa che l'inserimento di un elemento richiede un tempo approssimativamente lineare anziché il tempo costante ammortizzato per la libreria standard.
qualsiasi sviluppatore che lo faccia dovrebbe restituire il suo corso di informatica –
@DrJokepu: Stai assumendo che lo sviluppatore HA una laurea in informatica:) +1 –
il codice è scritto in modo compilatore, ad es. inlining, ecc.
naturalmente, gli algoritmi che usano sono stati-of-the-art.
Oltre agli algoritmi buoni e generali (come altri hanno notato), l'STL è anche abbastanza efficiente a causa del pesante utilizzo dei modelli.
Template metaprograms hanno la bella caratteristica che il compilatore li ottimizza in modo aggressivo. Alcuni compilatori sono molto bravi in questo e riducono i modelli al codice più piccolo, più efficiente e richiesto per un determinato compito. E in generale, ciò significa che le funzioni sono in linea quando possibile, e il codice per interagire con un particolare tipo è ridotto alla sua forma più semplice. La maggior parte delle implementazioni di STL (e la maggior parte di Boost), ovviamente, ne approfitta al massimo.
"Il modo in cui viene comunemente implementato" è una cosa molto vaga. Tutti lo implementano a modo suo.Tecnicamente, è comunemente * non implementato * ma riutilizzato. –
Specifica le operazioni a cui fai riferimento e come hai determinato che la libreria standard è più veloce. –
@ Mehrdad, Malte: Sì, sono d'accordo. Ma diciamo per una classe di array, inserendo un elemento nel mezzo spostando gli elementi una volta posizionati indietro per creare uno spazio vuoto per il nuovo elemento. Questa implementazione è molto più lenta di push_back() di un vettore. Lo determino ottenendo il tempo oi cicli di clock. – jasonline