In quale scenario utilizzo un particolare contenitore STL?

Ho letto i contenitori STL nel mio libro su C ++, in particolare la sezione sull’STL e sui suoi contenitori. Ora capisco che ognuno di loro ha le sue proprietà specifiche, e sono vicino a memorizzare tutti loro … Ma quello che ancora non riesco a cogliere è in quale scenario viene usato ciascuno di essi.

Qual è la spiegazione? Il codice di esempio è molto preferito.

Questo cheat sheet fornisce un sumrio piuttosto buono dei diversi contenitori.

Vedere il diagramma di stream in basso come guida su cui utilizzare in diversi scenari di utilizzo:

http://linuxsoftware.co.nz/containerchoice.png

Creato da David Moore e concesso in licenza CC BY-SA 3.0

Ecco un diagramma di stream ispirato alla versione di David Moore (vedi sopra) che ho creato, che è aggiornato (principalmente) con il nuovo standard (C ++ 11). Questa è solo la mia opinione personale, non è indiscutibile, ma ho pensato che potrebbe essere utile a questa discussione:

inserisci la descrizione dell'immagine qui

Risposta semplice: usa il vettore <> per tutto, a meno che tu non abbia una vera ragione per fare diversamente.

Quando trovi un caso in cui stai pensando, “Gee, vector <> non funziona bene qui a causa di X”, vai sulla base di X.

Guarda l’efficace STL di Scott Meyers. È buono a spiegare come usare l’STL.

Se vuoi memorizzare un numero determinato / indeterminato di oggetti e non ne cancellerai mai uno, allora un vettore è quello che vuoi. È la sostituzione predefinita per un array C e funziona come uno, ma non ha un overflow. Puoi anche impostare le sue dimensioni in anticipo con reserve ().

Se vuoi memorizzare un numero indeterminato di oggetti, ma li aggiungerai e li eliminerai, probabilmente vorrai un elenco … perché puoi eliminare un elemento senza spostare alcun elemento successivo, diversamente dal vettore. Tuttavia, richiede più memoria di un vettore e non è ansible accedere sequenzialmente a un elemento.

Se vuoi prendere un mucchio di elementi e trovare solo i valori unici di questi elementi, leggerli tutti in un insieme lo faranno e li ordinerà anche per te.

Se hai molte coppie chiave-valore e vuoi ordinarle per chiave, allora una mappa è utile … ma conterrà solo un valore per chiave. Se hai bisogno di più di un valore per chiave, potresti avere un vettore / elenco come valore nella mappa, o usare una multimap.

Non è nell’STL, ma è nell’aggiornamento TR1 all’STL: se hai un sacco di coppie chiave-valore che stai cercando per chiave, e non ti interessa il loro ordine, potresti vuoi usare un hash – che è tr1 :: unordered_map. L’ho usato con Visual C ++ 7.1, dove era chiamato stdext :: hash_map. Ha una ricerca di O (1) invece di una ricerca di O (log n) per la mappa.

Dipende tutto da cosa vuoi memorizzare e cosa vuoi fare con il contenitore. Ecco alcuni esempi (molto non esaurienti) per le classi container che tendo ad usare maggiormente:

vector : layout compatto con sovraccarico di memoria ridotto o nullo per object contenuto. Efficiente per iterare finita. Aggiungere, inserire e cancellare può essere costoso, in particolare per oggetti complessi. Economici per trovare un object contenuto per indice, ad es. MyVector [10]. Usa dove avresti usato un array in C. Buono dove hai molti oggetti semplici (es. Int). Non dimenticare di usare reserve() prima di aggiungere molti oggetti al contenitore.

list : memoria di memoria ridotta per object contenuto. Efficiente per iterare finita. Aggiungere, inserire e cancellare sono economici. Usa dove avresti usato un elenco collegato in C.

set (e multiset ): sovraccarico significativo della memoria per object contenuto. Utilizzare dove è necessario scoprire rapidamente se quel contenitore contiene un determinato object o unire in modo efficiente i contenitori.

map (e multimap ): overhead di memoria significativo per object contenuto. Utilizzare dove si desidera memorizzare coppie chiave-valore e cercare rapidamente i valori per chiave.

Il diagramma di stream sul cheat sheet suggerito da zdan fornisce una guida più esauriente.

Un punto importante solo brevemente menzionato finora, è che se si richiede memoria contigua (come dà un array C), allora si può usare solo vector , array o string .

Usa array se la dimensione è nota al momento della compilazione.

Usa la string se hai solo bisogno di lavorare con i tipi di caratteri e hai bisogno di una stringa, non solo di un contenitore generico.

Usa il vector in tutti gli altri casi (il vector dovrebbe essere la scelta predefinita di contenitore nella maggior parte dei casi comunque).

Con tutti e tre di questi è ansible utilizzare la funzione membro data() per ottenere un puntatore al primo elemento del contenitore.

Una lezione che ho imparato è: prova ad avvolgerlo in una class, dal momento che cambiare il tipo di contenitore un bel giorno può dare grandi sorprese.

 class CollectionOfFoo { Collection foos; .. delegate methods specifically } 

Non costa molto in anticipo e consente di risparmiare tempo nel debug quando si desidera interrompere ogni volta che qualcuno esegue l’operazione x su questa struttura.

Venendo a selezionare la struttura dati perfetta per un lavoro:

Ogni struttura dati fornisce alcune operazioni, che possono variare la complessità temporale:

O (1), O (lg N), O (N), ecc.

In sostanza, è necessario fare una stima migliore, su quali operazioni verranno eseguite maggiormente e utilizzare una struttura dati che ha quell’operazione come O (1).

Semplice, non lo è (-:

Ho ampliato il fantastico diagramma di stream di Mikael Persson . Ho aggiunto alcune categorie di contenitori, il contenitore di array e alcune note. Se desideri la tua copia, ecco il disegno di Google. Grazie, Mikael per aver fatto il lavoro di base! Raccoglitore di contenitori C ++