in che modo l'inserto multimap di stl's rispetta gli ordini?

Question

Ho alcuni dati forniti con un indice intero. Sto generando continuamente nuovi dati che devono essere aggiunti alla raccolta di dati che ho, ordinati in base a quell'indice, allo stesso tempo voglio essere in grado di iniziare facilmente i dati e scorrere attraverso di essa. Sembra che std :: multimap sia proprio quello di cui ho bisogno.

Tuttavia, ho anche bisogno che i dati con lo stesso indice siano mantenuti nell'ordine in cui è stato inserito, in questo caso significa che quando eseguo l'iterazione dei dati arrivo ai dati precedenti prima dei dati successivi.

Il multimap fa questo?

Non ho trovato alcuna garanzia che questo sia il caso. Nel manuale SGI, non ho visto alcuna menzione di se. L'ho provato sull'implementazione di gcc 4.3.4 e sembrava essere vero per alcuni casi di test limitati, ma ovviamente mi chiedevo se lo standard lo richiedesse e posso fare affidamento su questo fatto.

Modifica: Per essere più chiari in risposta ad alcune delle risposte, volevo che i dati ordinati per primo (non univoco) indice e il secondo per tempo di inserimento. Speravo che forse la seconda parte fosse gratis con multimap, ma sembra che non sia così.

Answer 1

A meno che non mi sia sfuggito qualcosa, lo standard non fornisce alcuna garanzia.

La soluzione più ovvia sarebbe quella di includere un numero di sequenza come chiave secondaria. Ad esempio, nella classe includi un oggetto statico senza segno e ogni volta che crei un oggetto da inserire nella multimap, inserisci il valore corrente nell'oggetto e lo incrementa. Nella funzione di confronto dell'oggetto, usa quel contatore come fattore decisivo per ordinare se i dati che stai utilizzando al momento sono paragonabili. Nota che in questo caso, ogni chiave sarà unica, quindi puoi usare una mappa invece di una multimap.

Answer 2

No non lo farà. Se lo vuoi, dovresti usare un "contenitore di sequenze" come un vettore. Ad esempio, puoi caricare un vettore con std :: pairs?

Answer 3

Sembra multimap è quello che ti serve ...

Tuttavia, ho anche bisogno di dati con lo stesso indice da tenere l'ordine in cui è stato inserito, in questo caso significato che quando eseguo l'iterazione di i dati si arriva ai dati precedenti prima dei dati successivi.

Sarà nell'ordine dell'indice. Se l'indice aumenta nel tempo quando inserisci più elementi, allora sì a causa della natura dell'indice, i dati "precedenti" verranno prima.

Altrimenti, no. È possibile mantenere due multimap sugli stessi dati. Una tenuti in ordine dell'indice, l'altra in ordine di tempo di inserimento:

std::multimap<index, T*> orderedByIndex; 
std::multimap<time, T*> orderedByInsertionTime; 

Dandovi la possibilità di iterare la mappa in entrambe le direzioni.

(Modifica Sto leggendo questo per indicare che a volte si desidera ripetere l'indice o talvolta iterare per tempo di inserimento, ma si veda la risposta sopra se si intende il primo indice quindi il tempo di inserimento.)

Answer 4

Gli elementi che appartiene alla stessa chiave è ordened da lower_bound e upper_bound funzioni quando si recuperano le informazioni, quindi non si ha la garanzia che si accede (tramite equal_range) gli elementi nell'ordine in cui sono stati inserito.

Answer 5

Boost multi_index supporta ciò che si sta cercando di fare, se non si vuole prendere la soluzione data dalla Jerry Coffin.

Answer 6

Se ti ho capito bene, hai bisogno dei dati ordinati per qualche chiave. Ogni volta che si inseriscono 2 oggetti con la stessa chiave, è necessario recuperarli nell'ordine di inserimento.

Se è così, allora devi dare un'occhiata all'implementazione del tuo multimap. A seconda di come gestisce il caso di più inserimenti con la stessa chiave, potrebbe avere o meno questa garanzia. Immagino che lo standard non offra questo tipo di garanzia, dal momento che limiterebbe l'implementazione per un caso molto speciale.

Un altro approccio è quello di andare a fare una mappa (non Multi) e creare un composto chiave. La chiave è composta dalla normale chiave scelta e da un contatore sempre crescente. A confronto, con chiavi uguali, il numero di inserimento rende la chiave unica. In questo modo imponi le chiavi univoche e l'ordine su chiavi uguali "normali" (spero che questo sia comprensibile).

Immagino che l'ultimo approccio sia il più semplice da implementare.

---

Opzione: (non preferibile)

si può sempre andare per un datastructure self-made con questa garanzia. Mi piacerebbe un albero (rosso-nero o AVL per esempio) con un vettore per contenere i dati inseriti. Durante l'iterazione devi trovare il nodo, andare al vettore e iterare sul suo contenuto. Ogni volta che si finisce con il vettore, si continua con il nodo successivo.

Answer 7

Sembra che il nuovo standard (C++ 11) ha modificato questo:

L'ordine delle coppie di valori-chiave cui chiavi confrontare equivalente è l'ordine di inserimento e non cambia. ^{[cppreference]}

ho esitato ad usarlo, però, come questo mi sembra un dettaglio facilmente trascurato quando si modifica la libreria standard di essere C++ 11 compliant ed è il tipo di dettaglio che possa causare errori se in silenzio la libreria del compilatore non è stata implementata correttamente.