Contenitori STL ordinati dinamicamente

Question

Sono abbastanza nuovo in STL, quindi mi chiedevo se ci sono contenitori ordinabili dinamicamente?Al momento il mio pensiero attuale è quello di utilizzare un vettore insieme ai vari algoritmi di ordinamento, ma non sono sicuro che esista una selezione più appropriata data la (presumibilmente) complessità lineare dell'inserimento di voci in un vettore ordinato.

Per chiarire "dinamicamente", sto cercando un contenitore di cui posso modificare l'ordinamento in fase di esecuzione, ad es.ordinarlo in ordine ascendente, quindi riordinarlo successivamente in ordine discendente.

Answer 1

Se sai che effettuerai l'ordinamento in base a un singolo valore ascendente e discendente, allora set è tuo amico.Utilizza un iteratore inverso quando vuoi "ordinare" nella direzione opposta.

Se i tuoi oggetti sono complessi e li ordinerai in molti modi diversi in base ai campi membro all'interno degli oggetti, probabilmente ti conviene usare un vettore e un ordinamento.Prova a eseguire gli inserimenti tutti in una volta, quindi chiama sort una volta.Se ciò non è fattibile, la deque potrebbe essere un'opzione migliore rispetto al vettore per grandi raccolte di oggetti.

Penso che se ti interessa Quello livello di ottimizzazione, faresti meglio a profilare il tuo codice utilizzando dati reali.(Che è probabilmente il miglior consiglio che qualcuno qui può dare:potrebbe non avere importanza che chiami sort dopo ogni inserimento se lo fai solo una volta ogni luna blu.)

Answer 2

Ti consigliamo di dare un'occhiata a std::map

std::map<keyType, valueType>

La mappa viene ordinata in base all'operatore < fornito per keyType.

O

std::set<valueType>

Ordinato anche in base all'operatore < dell'argomento modello, ma non consente elementi duplicati.

C'è

std::multiset<valueType>

che fa la stessa cosa di std::set ma consente elementi identici.

Consiglio vivamente "The C++ Standard Library" di Josuttis per ulteriori informazioni.È la panoramica più completa della libreria std, molto leggibile e piena zeppa di informazioni oscure e non così oscure.

Inoltre, come menzionato in 17 di 26, vale la pena leggere Effective Stl di Meyers.

Answer 3

Sembra che tu voglia a contenitore multiindice.Ciò ti consente di creare un contenitore e di indicare a quel contenitore i vari modi in cui potresti voler attraversare gli elementi in esso contenuti.Il contenitore conserva quindi più elenchi di elementi e tali elenchi vengono aggiornati a ogni inserimento/eliminazione.

Se vuoi davvero riordinare il contenitore, puoi chiamare il file std::sort funzione su qualsiasi std::deque, std::vector, o anche un semplice array in stile C.Quella funzione accetta un terzo argomento facoltativo per determinare come ordinare i contenuti.

Answer 4

IL stl non fornisce tale contenitore.Puoi definire il tuo, supportato da a set/multiset o a vector, ma dovrai riordinare ogni volta che la funzione di ordinamento cambia chiamando sort (per un vector) o creando una nuova raccolta (for set/multiset).

Se vuoi semplicemente passare dall'ordinamento crescente all'ordinamento decrescente, puoi utilizzare l'iteratore inverso sul tuo contenitore chiamando rbegin() E rend() invece di begin() E end().Entrambi vector E set/multiset sono contenitori reversibili, quindi funzionerebbe per entrambi.

Answer 5

std::set è fondamentalmente un contenitore ordinato.

Answer 6

Dovresti assolutamente usare un set/mappa.Come dice Hazzen, ottieni O(log n) insert/find.Non lo otterrai con un vettore ordinato;puoi ottenere O(log n) find usando la ricerca binaria, ma l'inserimento è O(n) perché l'inserimento (o l'eliminazione) di un elemento può causare lo spostamento di tutti gli elementi esistenti nel vettore.

Answer 7

Non è così semplice.Nella mia esperienza inserisci/elimina viene utilizzato meno spesso di trova.Il vantaggio del vettore ordinato è che richiede meno memoria ed è più adatto alla cache.Se si dispone di una versione compatibile con le mappe STL (come quella che ho collegato prima) è facile passare avanti e indietro e utilizzare il contenitore ottimale per ogni situazione.

Answer 8

in teoria un contenitore associativo (set, multiset, map, multimap) dovrebbe essere la soluzione migliore.

In pratica dipende dal numero medio di elementi che inserisci.per meno di 100 elementi un vettore è probabilmente la soluzione migliore a causa di:- Evitare la dealloction di allocazione continua - Cache Friendly A causa della località dei dati Questi vantaggi probabilmente supereranno comunque l'ordinamento continuo.Ovviamente dipende anche da quante inserzioni-cancellazioni devi fare.Eseguirai l'inserimento/eliminazione per frame?

Più generalmente:stai parlando di un'applicazione critica per le prestazioni?

ricordati di non ottimizzare prematuramente...

Answer 9

La risposta è come sempre dipende.

set E multiset sono appropriati per mantenere gli elementi ordinati ma sono generalmente ottimizzati per un insieme bilanciato di aggiunta, rimozione e recupero.Se hai operazioni di ricerca virili, allora un sorted vector potrebbe essere più appropriato e quindi utilizzarlo lower_bound per cercare l'elemento.

Anche il tuo secondo requisito di ricorrere a un ordine diverso in fase di esecuzione significherà effettivamente questo set E multiset non sono appropriati perché il predicato non può essere modificato in fase di esecuzione.

Consiglierei quindi un vettore ordinato.Ma ricordati di passare lo stesso predicato a lower_bound che sei passato all'ordinamento precedente poiché i risultati saranno indefiniti e molto probabilmente errati se passi il predicato sbagliato.

Answer 10

Set e multiset utilizzano un albero binario sottostante;puoi definire l'operatore <= per uso personale.Questi contenitori si mantengono ordinati, quindi potrebbe non essere la scelta migliore se si cambiano i parametri di ordinamento.I vettori e gli elenchi sono probabilmente la soluzione migliore se hai intenzione di ricorrere parecchio;in generale l'elenco ha il proprio ordinamento (solitamente un mergesort) ed è possibile utilizzare l'algoritmo di ricerca binaria stl sui vettori.Se prevalgono gli inserti, la lista supera il vettore.

Answer 11

Le mappe e i set STL sono entrambi contenitori ordinati.

Secondo la raccomandazione del libro di Doug T: il libro STL di Josuttis è il migliore che abbia mai visto sia come libro di apprendimento che di riferimento.

STL efficace è anche un libro eccellente per apprendere i dettagli più nascosti di STL e cosa dovresti e non dovresti fare.

Answer 12

Per il vettore ordinato "compatibile STL" vedere A.AssocVector di Alexandrescu da Loki.