Come posso selezionare in modo efficiente un contenitore di libreria standard in C ++ 11?

C’è un’immagine ben nota (cheat sheet) chiamata “C ++ Container choice”. È un diagramma di stream per scegliere il miglior contenitore per l’utilizzo desiderato.

Qualcuno sa se esiste già una versione di C ++ 11?

Questo è il precedente: Scelta del contenitore eC ++

Non che io sappia, comunque può essere fatto testualmente da testo. Inoltre, il grafico è leggermente fuori, perché la list non è un contenitore così buono in generale, e nemmeno forward_list . Entrambe le liste sono contenitori molto specializzati per applicazioni di nicchia.

Per build un grafico del genere, hai solo bisogno di due semplici linee guida:

  • Scegli prima la semantica
  • Quando sono disponibili diverse scelte, vai per il più semplice

All’inizio, preoccuparsi delle prestazioni è di solito inutile. Le grandi considerazioni su O sono davvero efficaci solo quando inizi a gestire alcune migliaia (o più) di elementi.

Esistono due grandi categorie di contenitori:

  • Contenitori associativi : hanno un’operazione di find
  • Contenitori Simple Sequence

e quindi è ansible creare diversi adattatori su di essi: stack , queue , priority_queue . Lascerò qui gli adattatori, sono sufficientemente specializzati per essere riconoscibili.


Domanda 1: associativa ?

  • Se devi cercare facilmente con una chiave, allora hai bisogno di un contenitore associativo
  • Se hai bisogno di ordinare gli elementi, allora hai bisogno di un contenitore associativo ordinato
  • Altrimenti, passa alla domanda 2.

Domanda 1.1: ordinato ?

  • Se non hai bisogno di un ordine specifico, usa un contenitore unordered_ , altrimenti usa la sua controparte ordinata tradizionale.

Domanda 1.2: Chiave separata ?

  • Se la chiave è separata dal valore, utilizzare una map , altrimenti utilizzare un set

Domanda 1.3: duplicati ?

  • Se vuoi conservare i duplicati, usa un multi , altrimenti no.

Esempio:

Supponiamo che io abbia diverse persone con un ID univoco ad esse associato e vorrei recuperare i dati di una persona dal suo ID nel modo più semplice ansible.

  1. Voglio una funzione di find , quindi un contenitore associativo

    1.1. Non mi importava di meno dell’ordine, quindi di un contenitore unordered_

    1.2. La mia chiave (ID) è separata dal valore a cui è associata, quindi una map

    1.3. L’ID è unico, quindi nessun duplicato dovrebbe insinuarsi.

La risposta finale è: std::unordered_map .


Domanda 2: memoria stabile ?

  • Se gli elementi dovrebbero essere stabili nella memoria (cioè, non dovrebbero spostarsi quando il contenitore stesso viene modificato), quindi usare qualche list
  • Altrimenti, passa alla domanda 3.

Domanda 2.1: Quale ?

  • Accontentarsi di una list ; una forward_list è utile solo per un minor ingombro di memoria.

Domanda 3: dimensioni dinamiche ?

  • Se il contenitore ha una dimensione nota (al momento della compilazione), e questa dimensione non verrà modificata durante il corso del programma e gli elementi sono costruttibili di default oppure è ansible fornire un elenco di inizializzazione completo (usando la syntax { ... } ), quindi utilizzare un array . Sostituisce il tradizionale array C, ma con funzioni utili.
  • Altrimenti, passa alla domanda 4.

Domanda 4: Double-ended ?

  • Se desideri essere in grado di rimuovere elementi sia dal davanti che dal retro, usa un deque , altrimenti usa un vector .

Noterai che, per impostazione predefinita, a meno che tu non abbia bisogno di un contenitore associativo, la tua scelta sarà un vector . Si scopre che è anche la raccomandazione di Sutter e Stroustrup .

Mi piace la risposta di Matthieu, ma ho intenzione di rideterminare il diagramma di stream come questo:

Quando NON usare std :: vector

Di default, se hai bisogno di un contenitore di roba, usa std::vector . Pertanto, ogni altro contenitore è giustificato solo fornendo alcune funzionalità alternative a std::vector .

Costruttori

std::vector richiede che il suo contenuto sia costruibile in movimento, dal momento che deve essere in grado di mescolare gli oggetti in giro. Questo non è un onere emplace da collocare sui contenuti (si noti che non sono richiesti costruttori predefiniti, grazie a emplace e così via). Tuttavia, la maggior parte degli altri contenitori non richiede alcun particolare costruttore (anche in questo caso, grazie a emplace ). Quindi se hai un object in cui non puoi assolutamente implementare un costruttore di mosse, allora dovrai scegliere qualcos’altro.

Un std::deque sarebbe il rimpiazzo generale, con molte delle proprietà di std::vector , ma è ansible inserirlo solo alle estremità del deque. Gli inserti nel mezzo richiedono lo spostamento. Una std::list non pone alcun requisito sul suo contenuto.

Ha bisogno di Bools

std::vector è … non. Bene, è standard. Ma non è un vector nel senso comune del termine, in quanto le operazioni che std::vector normalmente consente sono proibite. E certamente non contiene bool s .

Pertanto, se hai bisogno di un comportamento vector reale da un contenitore di bool s, non lo otterrai da std::vector . Quindi dovrai fare causa con una std::deque .

Ricerca

Se è necessario trovare elementi in un contenitore e il tag di ricerca non può essere solo un indice, potrebbe essere necessario abbandonare std::vector in favore di set e map . Nota la parola chiave ” potrebbe “; uno std::vector ordinato è a volte un’alternativa ragionevole. Oppure il flat_set/map di flat_set/map , che implementa un std::vector ordinato.

Ora ci sono quattro variazioni di questi, ognuno con i propri bisogni.

  • Utilizza una map quando il tag di ricerca non è la stessa cosa dell’object che stai cercando. Altrimenti usa un set .
  • Usare unordered quando si hanno molti oggetti nel contenitore e le prestazioni di ricerca devono assolutamente essere O(1) , piuttosto che O(logn) .
  • Usa multi se hai bisogno di più elementi per avere lo stesso tag di ricerca.

ordinazione

Se è necessario ordinare un contenitore di elementi in base a una determinata operazione di confronto, è ansible utilizzare un set . O un multi_set se hai bisogno di più elementi per avere lo stesso valore.

Oppure puoi usare un std::vector ordinato, ma dovrai tenerlo in ordine.

Stabilità

Quando iteratori e riferimenti sono invalidati a volte è una preoccupazione. Se hai bisogno di un elenco di elementi, in modo tale che hai iteratori / puntatori a quegli elementi in vari altri luoghi, allora l’approccio di std::vector all’invalidazione potrebbe non essere appropriato. Qualsiasi operazione di inserimento può causare l’invalidazione, a seconda delle dimensioni e della capacità corrente.

std::list offre una garanzia: un iteratore e i relativi riferimenti / puntatori associati vengono invalidati solo quando l’elemento stesso viene rimosso dal contenitore. std::forward_list è lì se la memoria è un problema serio.

Se questa è una garanzia troppo forte, std::deque offre una garanzia più debole ma utile. Risultati di invalida da inserimenti nel mezzo, ma gli inserimenti in testa o in coda causano solo l’invalidazione degli iteratori , non i puntatori / riferimenti agli elementi nel contenitore.

Performance di inserimento

std::vector fornisce solo un inserimento economico alla fine (e anche in questo caso, diventa costoso se si soffia la capacità).

std::list è costoso in termini di prestazioni (ogni elemento appena inserito costa un’allocazione di memoria), ma è coerente . Offre anche la capacità, occasionalmente indispensabile, di mescolare gli oggetti in giro praticamente senza alcun costo, oltre a scambiare oggetti con altri contenitori std::list dello stesso tipo senza perdite di prestazioni. Se hai bisogno di mescolare cose in giro, usa std::list .

std::deque fornisce inserimento / rimozione a tempo costante alla testa e alla coda, ma l’inserimento nel mezzo può essere abbastanza costoso. Quindi se hai bisogno di aggiungere / rimuovere elementi sia dal lato anteriore che posteriore, std::deque potrebbe essere quello che ti serve.

Va notato che, grazie alla semantica di spostamento, le prestazioni di inserimento di std::vector potrebbero non essere così brutte come una volta. Alcune implementazioni hanno implementato una forma di copia di elementi basata sulla semantica (la cosiddetta “swaptimization”), ma ora che lo spostamento è parte del linguaggio, è obbligatorio per lo standard.

Nessuna allocazione dynamic

std::array è un contenitore fine se si desidera il minor numero ansible di allocazioni dinamiche. È solo un involucro attorno a un C-array; questo significa che le sue dimensioni devono essere conosciute in fase di compilazione . Se riesci a conviverci, usa std::array .

Detto questo, usare std::vector e reserve una dimensione funzionerebbe altrettanto bene per un std::vector limitato. In questo modo, le dimensioni effettive possono variare e si ottiene solo un’allocazione di memoria (a meno che non si superi la capacità).

Ecco la versione C ++ 11 del diagramma di stream sopra. [pubblicato originariamente senza attribuzione all’autore originale, Mikael Persson ]

Ecco un giro veloce, anche se probabilmente ha bisogno di lavoro

 Should the container let you manage the order of the elements? Yes: Will the container contain always exactly the same number of elements? Yes: Does the container need a fast move operator? Yes: std::vector No: std::array No: Do you absolutely need stable iterators? (be certain!) Yes: boost::stable_vector (as a last case fallback, std::list) No: Do inserts happen only at the ends? Yes: std::deque No: std::vector No: Are keys associated with Values? Yes: Do the keys need to be sorted? Yes: Are there more than one value per key? Yes: boost::flat_map (as a last case fallback, std::map) No: boost::flat_multimap (as a last case fallback, std::map) No: Are there more than one value per key? Yes: std::unordered_multimap No: std::unordered_map No: Are elements read then removed in a certain order? Yes: Order is: Ordered by element: std::priority_queue First in First out: std::queue First in Last out: std::stack Other: Custom based on std::vector????? No: Should the elements be sorted by value? Yes: boost::flat_set No: std::vector 

Si può notare che questo differisce molto dalla versione C ++ 03, principalmente a causa del fatto che non mi piacciono davvero i nodes collegati. I contenitori dei nodes collegati di solito possono essere battuti in termini di prestazioni da un contenitore non collegato, tranne in alcune rare situazioni. Se non sai quali sono queste situazioni e hai accesso a boost, non utilizzare contenitori di nodes collegati. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). Questo elenco si concentra principalmente su contenitori di piccole e medie facciate, perché (A) questo è il 99,99% di ciò che trattiamo in codice, e (B) Un gran numero di elementi richiede algoritmi personalizzati, non contenitori diversi.