Mi chiedo quale sia più efficiente.mappa multimappa vs set
std::map< String, std::set<int> >
o
std::multimap< String, int >
EDIT: Non ho intenzione di fare qualcosa di fuori dal comune con queste mappe. Inserimento standard, cancellare, modificare, cercare. La dimensione di ogni serie o stringa con più chiavi non deve essere superiore a 100.
Questo credo dipende dall'implementazione, ma una (in) un'ipotesi:
In pratica dipende dal numero di interi che sarà mantenere nel multimap o std::set. Molto probabilmente un multimap utilizzerà una ricerca lineare dei valori dopo la ricerca del log (n) della chiave. Se si dispone di un numero elevato di valori interi, la ricerca di log (n) dei tasti seguita da una ricerca di log (n) dei valori potrebbe essere leggermente più veloce.
Tuttavia, in termini di efficienza, la memorizzazione di qualsiasi cosa in un map o multimap con una chiave string supererà quasi sicuramente le differenze in entrambi i casi.
Come detto di seguito, un multimap sarà probabilmente più facile da usare e più chiaro da mantenere dando un netto vantaggio.
Non posso dire con certezza, ma dato che multimap è stato progettato per fare ciò che l'altro è espressione, dovrebbe essere meglio essere specifica e usa la multimap, ha molto più senso, ha anche funzioni membro per lavorare con un multimap come concetto, quelle funzioni sarebbero un po 'funky usando l'altro approccio.
std :: multimap < La stringa, int> è molto probabilmente più efficiente in termini di memoria.
Hai una spiegazione logica? –
Il numero di numeri memorizzati è lo stesso in entrambi, ma poiché si utilizzano due alberi neri rossi si utilizza il doppio del numero di sequenze di "mantenimento del libro" piuttosto che necessario. Inoltre, dato che la maggior parte delle implementazioni STL di std :: string utilizzano il conteggio dei riferimenti e la copia sulla semantica di scrittura, i dati utilizzati dalle stringhe potrebbero non essere raddoppiati. Spero che abbia senso mentre scrivo questo sul mio telefono. –
In realtà, non hai dimostrato che una mappa e le serie occupano più spazio di una multimappa (che dire di multimap _additional_business?), Ma in effetti conserverai molto più di due alberi. E questi sono implementati come alberi non è specificato. E non esiste uno spazio dei nomi 'std' nell'STL. E, in realtà, il mio commento aveva lo scopo di provocare l'aggiunta di una motivazione al tuo _answer_;) –
Se non sei felice con quelle risposte finora (non dicendo che non sei) e sono assolutamente costretto a rispondere, io do la mia educato "indovinare" troppo:
Per inserire, il multimap sembra essere più "efficiente". Con l'approccio mappa, devi prima recuperare, quindi eseguire l'operazione sul set. Per eliminare/recuperare, la mappa sembra più "efficiente".
L'opzione "set" eliminerà le duplicazioni di coppie + valore chiave, indipendentemente dal fatto che il multimap non lo consenta.
In realtà non sono equivalenti. A multimap<X,Y> consente di memorizzare coppie chiave-valore duplicate, mentre un map<T, set<X>> no.
multimap<int, int> m;
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 3)); // This changes the size of m!
Mentre
map<int, set<int>> m;
m[2].insert(3);
m[2].insert(3); // This does nothing.
quindi vorrei utilizzare il metodo di se non è necessario duplicare coppie chiave-valore. Anche la sintassi è migliore. Mi aspetto che la differenza nelle prestazioni e nell'uso della memoria non sia così eccezionale.
Definire "efficiente". –
Quali sono le operazioni che si desidera eseguire?Questo definirà i diversi costi, in quanto il primo approccio ti consentirà di eseguire ricerche rapide sia su stringa che su intero e il secondo richiederà di eseguire iterazioni e testare la parte int su ogni valore per cui la stringa è la stessa ... Ma se non hai bisogno di questa operazione, potrebbe essere il caso che la seconda opzione sia migliore in alcuni casi d'uso ... –
per favore guarda la mia modifica –