Quando scegliere std :: vector su std :: map per i dati valore-chiave?

Question

Considerando l'effetto positivo della cache e della località dei dati durante la ricerca nella memoria primaria, tendo ad utilizzare std::vector<> con gli elementi valore-chiave std::pair<> -like ed eseguo ricerche lineari per entrambi, se so che la quantità totale di elementi chiave-valore sarà mai essere "troppo grande" per influire negativamente sulle prestazioni.

Ultimamente sto in un sacco di situazioni in cui ho sapere in anticipo che io sarà avere enormi quantità di oggetti di valore-chiave e hanno quindi optato per std::map<> fin dall'inizio.

Mi piacerebbe sapere come si prendono le decisioni per il contenitore corretto in situazioni come quelle sopra descritte.

Ti

• usa sempre std::vector<> (o simili)?
• utilizzare sempre std::map<> (o simile)?
• ha una sensazione istintiva per dove nel range di conteggio articoli uno è preferibile rispetto all'altro?
• qualcosa di completamente diverso?

Grazie!

Answer 1

Uso solo raramente lo std::vector con una ricerca lineare (tranne in congiunzione con la ricerca binaria come descritto di seguito). Suppongo che per una piccola quantità di dati sarebbe meglio, ma con quei piccoli dati è improbabile che qualcosa possa fornire un enorme vantaggio.

A seconda del modello di utilizzo, una ricerca binaria su un std::vector può avere senso comunque. Un std::map funziona bene quando è necessario aggiornare i dati regolarmente durante l'uso.In alcuni casi, tuttavia, si caricano alcuni dati e quindi si utilizzano i dati, ma dopo aver caricato i dati, rimane per lo più statico (cioè, cambia molto poco, se non del tutto).

In questo caso, può avere molto senso caricare i dati in un vettore, ordinarlo se necessario, quindi effettuare ricerche binarie sui dati (ad esempio std::lower_bound, std::equal_range). Ciò fornisce praticamente il meglio di entrambi i mondi: ricerche binarie a bassa complessità e utilizzo della cache buona da località di riferimento elevate (ad esempio, il vettore è contiguo, in contrapposizione alla struttura collegata di un std::map). La mancanza, naturalmente, è che le inserzioni e le eliminazioni sono lente, ma questa volta ho usato la tua idea originale: memorizza i dati appena inseriti separatamente fino a raggiungere un certo limite, e solo dopo riordinarli con il resto del dati, quindi una singola ricerca consiste in una ricerca binaria del corpo principale dei dati, seguita da una ricerca lineare della (piccola quantità) di dati appena inseriti.

Answer 2

Non sceglierei mai la scelta solo per motivi di "efficienza" (forse falsi), ma sempre su cosa farò effettivamente con il contenitore. Voglio memorizzare i duplicati? L'ordine di inserimento è importante? A volte voglio cercare il valore e non la chiave? Quel tipo di cose.

Answer 3

Quasi sempre preferisco usare map (o unordered_map, quando un contenitore di hash ha più senso) rispetto a un vettore.

Detto questo, penso che il tuo ragionamento sia al contrario. Tenderei ad usare un vettore solo quando ci sono enormi quantità di dati, dal momento che un vettore sarà un footprint di memoria più piccolo.

Con il giusto tipo di set di dati, è possibile caricare un vettore e quindi ordinare e binary_search con un ingombro ridotto e le caratteristiche di prestazioni simili a una mappa, in particolare se il set di dati è stabile dopo il carico.

Answer 4

Hai considerato l'utilizzo di strutture di dati ordinati? Tendono ad offrire ricerche logaritmiche e inserti - un compromesso ragionevole. Personalmente non ho regole rigide oltre a quelle che mi piacciono per la capacità di digitare un valore leggibile/comprensibile.

Naturalmente c'è anche molta discussione sull'efficienza delle mappe rispetto a liste/vettori (ordinate e non ordinate) - se la tua chiave è una stringa di 10.000 caratteri, può richiedere più tempo per confrontare le stringhe che per cercare attraverso un elenco di pochi elementi, quindi assicurati di poter confrontare in modo efficiente anche le chiavi.

Answer 5

Perché non stai prendendo in considerazione unordered_map?