In quale scenario utilizzo un contenitore STL particolare?

Question

Ho letto sui contenitori STL nel mio libro su C ++, in particolare la sezione su STL e sui suoi contenitori. Ora capisco che ognuno di loro ha le proprie proprietà specifiche e sono vicino a memorizzarli tutti ... Ma ciò che non afferro ancora è in quale scenario viene utilizzato ciascuno di essi.

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

Answer 1

Questo cheat sheet fornisce un riassunto abbastanza buono dei diversi contenitori.

Vedi il diagramma di flusso in basso come guida su cui utilizzare in diversi scenari di utilizzo:

_{Creato da David Moore e licenza CC BY-SA 3.0}

Answer 2

Ecco un diagramma di flusso 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 potesse essere prezioso per questa discussione:

Answer 3

Risposta semplice: usa std :: vector per tutto, a meno che tu non abbia una vera ragione per fare diversamente.

Quando trovi un caso in cui stai pensando, " Accidenti, std :: vector non funziona bene qui a causa di X " ;, vai sulla base di X.

Answer 4

Guarda Effective STL di Scott Meyers. È bravo a spiegare come utilizzare l'STL.

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

Se vuoi memorizzare un numero indeterminato di oggetti, ma li aggiungerai e li cancellerai, probabilmente vorrai un elenco ... perché puoi eliminare un elemento senza spostare alcun elemento seguente, a differenza del vettore. Richiede più memoria di un vettore, tuttavia, e non è possibile accedere in sequenza a un elemento.

Se vuoi prendere un gruppo di elementi e trovare solo i valori univoci di quegli elementi, leggerli tutti in un set lo farà, 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 utilizzare una multimappa.

Non è nell'STL, ma è nell'aggiornamento TR1 dell'STL: se hai molte coppie chiave-valore che cercherai per chiave e non ti importa del loro ordine , potresti voler usare un hash, che è tr1 :: unordered_map. L'ho usato con Visual C ++ 7.1, dove si chiamava stdext :: hash_map. Ha una ricerca di O (1) invece di una ricerca di O (log n) per la mappa.

Answer 5

Ho riprogettato il diagramma di flusso per avere 3 proprietà:

1. Penso che i contenitori STL siano divisi in 2 classi principali. I contenitori di base e quelli sfruttano i contenitori di base per attuare una politica.
2. Inizialmente il diagramma di flusso dovrebbe dividere il processo decisionale per le principali situazioni su cui dovremmo decidere e quindi elaborare ogni caso.
3. Alcuni contenitori estesi hanno la possibilità di scegliere diversi contenitori base come loro contenitore interno. Il diagramma di flusso dovrebbe considerare le situazioni in cui è possibile utilizzare ciascuno dei contenitori di base.

Il diagramma di flusso:

Ulteriori informazioni in questo link .

Answer 6

Un punto importante menzionato solo brevemente finora è che se hai bisogno di memoria contigua (come un array C), puoi usare solo vector , array , o stringa .

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

Usa stringa se devi lavorare solo con tipi di caratteri e hai bisogno di una stringa, non solo di un contenitore per scopi generici.

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

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

Answer 7

Tutto dipende da cosa vuoi archiviare e cosa vuoi fare con il contenitore. Ecco alcuni esempi (molto non esaustivi) per le classi di container che tendo a usare di più:

vector : layout compatto con poco o nessun sovraccarico di memoria per oggetto contenuto. Efficiente da ripetere. Aggiungere, inserire e cancellare può essere costoso, in particolare per oggetti complessi. Economico per trovare un oggetto contenuto per indice, ad es. myVector [10]. Usa dove avresti usato un array in C. Buono dove hai molti oggetti semplici (ad esempio int). Non dimenticare di usare reserve () prima di aggiungere molti oggetti al contenitore.

list : sovraccarico di memoria per oggetto contenuto. Efficiente da ripetere. Aggiungi, inserisci e cancella sono economici. Usa dove avresti usato un elenco collegato in C.

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

map (e multimap ): sovraccarico di memoria significativo per oggetto contenuto. Utilizzare dove si desidera memorizzare coppie chiave-valore e cercare rapidamente i valori in base alla chiave.

Il diagramma di flusso sul cheat sheet suggerito da zdan fornisce una guida più esaustiva.

Answer 8

Una lezione che ho imparato è: provare a racchiuderlo in una classe, poiché cambiare il tipo di contenitore in una bella giornata può portare grandi sorprese.

class CollectionOfFoo {
    Collection<Foo*> 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 di dati fornisce alcune operazioni, che possono variare in base alla complessità temporale:

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

Devi essenzialmente fare un'ipotesi migliore, su quali operazioni verranno eseguite di più e utilizzare una struttura di dati che ha quell'operazione come O (1).

Semplice, no (-:

Answer 9

Ho ampliato il il fantastico diagramma di flusso di Mikael Persson . Ho aggiunto alcune categorie di contenitori, il contenitore di array e alcune note. Se desideri la tua copia, here è il disegno di Google . Grazie, Mikael per aver fatto le basi! Selettore contenitore C ++

Answer 10

Ho risposto a questa domanda in un'altra domanda che è contrassegnata come duplice di questa. Ma penso che sia bello fare riferimento ad alcuni buoni articoli riguardanti la decisione di scegliere un contenitore standard.

Come ha risposto @David Thornley, std :: vector è la strada da percorrere se non ci sono altre esigenze speciali. Questo è il consiglio dato dal creatore di C ++, Bjarne Stroustrup in un blog del 2014.

Ecco il link per l'articolo https://isocpp.org/blog/2014/06/stroustrup-lists

e cita da quello,

  

E, sì, la mia raccomandazione è di usare std :: vector di default.

Nei commenti, l'utente @NathanOliver fornisce anche un altro buon blog, che ha misurazioni più concrete. https://baptiste-wicht.com/ post / 2012/12 / cpp-benchmark-vector-list-deque.html .