Come stai dicendo I assume the buckets can get big..., è meglio usare std::list. La ricerca è lineare in entrambi i casi, ma l'aggiunta di elementi è costante in std::list.
I guess they're all the same, since data isn't ordered - No, non lo sono. Se lo fossero, ci sarebbe un solo contenitore. Ogni contenitore ha i suoi vantaggi e svantaggi, i diversi contenitori vengono utilizzati per diverse situazioni.
Un po 'di informazioni su di vettore:
std::vector ha capacità, è per questo che ha capacity() e size() metodi. Sono entrambi diversi. Quindi, supponiamo che la capacità sia 4 e tu abbia 2 elementi, quindi la dimensione sarà 2. Quindi, aggiungendo un altro elemento incrementeremo la dimensione (sarà 3) ed è tutto molto veloce.
Ma cosa succede quando devi aggiungere 5+ elementi e la capacità è 4? completamente nuovo memoria viene allocata, tutti vecchi elementi sono copiati nella nuova memoria, tutti vecchi elementi sono distrutti (loro distruttori sono chiamati, se tipi definiti dall'utente). Quindi la vecchia memoria deve essere liberata. Si tratta di operazioni costose se si pensa che aggiungere/rimuovere elementi sarà più frequente.
È possibile evitare questo, utilizzando il metodo std::vector::reserve per riservare un po 'di memoria in anticipo e non riallocare nuova memoria tutto il tempo e copiare tutto più e più volte. Ma questo è utile quando conosci la dimensione approssimativa di questi vettori. Suppongo che tu non sia nella tua situazione (riservare molta memoria non è una buona soluzione anche tu - non dovresti sprecare memoria proprio come quello) Quindi, di nuovo, preferirei std :: list.
Oppure doppio hash.
In ogni caso, questo, che ripartisce di nuova memoria e la copia di oggetti non accadrà che spesso, come std::vector è "intelligente", e quando allocare nuovo spazio, ma non aumenta la capacità con 1 solo elemento o qualcosa del genere. Penso che lo raddoppi, ma non ne sono sicuro. Argh, non so come si chiami esattamente in inglese ... Probabilmente qualcosa come "tempo cumulativo/memoria" o "complessità cumulativa":?Non so:/
NOTA: Qualunque cosa scegliate, vi suggerisco di prestare attenzione alla funzione hash. È il più importante qui. Un contenitore di hash NON dovrebbe contenere troppi elementi con lo stesso hash. Quindi, il mio consiglio è di cercare una buona funzione di hash e quindi questo non avrà importanza.
Speranza che ha aiutato (:
EDIT: vi consiglio di questo articolo - comparing std::vector and std::deque - è perfetta - a confronto l'utilizzo della memoria (allocazione, deallocando, in crescita), l'utilizzo della CPU, ecc mi piacerebbe raccomandare l'intero articolo
fonte
2010-11-20 23:38:46
Vector OK, non necessariamente ottimale. potrebbe compararlo con 'list' e/o' deque' .Se i tuoi bucket non sono autorizzati a diventare grandi, 'vector' può sovra-allocare.Tutti i tre hanno una ricerca lineare. la struttura di noi che può battere il tempo di ricerca lineare è un'altra hashtable (o lo stesso tavolo di nuovo), come nel doppio hashing. Senza un ordine non c'è nulla nelle librerie standard: tutto ciò che fanno è cose con ordini e sequenze pure. –
'deque' può essere migliore di' vector', perché non deve mai riallocare e spostare tutto. L'accesso è leggermente più lento, push_back è potenzialmente molto più veloce, a seconda di quanto costano gli elementi da copiare. 'list' tipicamente fa più allocazione di memoria di entrambi e potrebbe essere più lento per questo motivo. –