Non capisco std::tr1::unordered_map

Question

Ho bisogno di un contenitore associativo che mi faccia indicizzare un determinato oggetto tramite una stringa, ma che mantenga anche l'ordine di inserimento, così posso cercare un oggetto specifico in base al suo nome o semplicemente iterare su di esso e recuperare gli oggetti nello stesso ordine in cui li ho inseriti loro.

io penso questo ibrido di elenco collegato e mappa hash dovrebbe fare il lavoro, ma prima ho provato a usarlo std::tr1::unordered_map pensando che funzionasse nel modo che ho descritto, ma non era così.Quindi qualcuno potrebbe spiegarmi il significato e il comportamento di unordered_map?

---

@wesc:Sono sicuro che std::map è implementato da STL, mentre sono sicuro che std::hash_map NON è in STL (penso che la versione precedente di Visual Studio lo inserisca in uno spazio dei nomi chiamato stdext).

@cristopher:quindi, se ho capito bene, la differenza sta nell'implementazione (e quindi nelle prestazioni), non nel modo in cui si comporta esternamente.

Answer 1

Migliora la documentazione dei contenitori non ordinati

La differenza sta nel metodo con cui si genera la ricerca.

Nei contenitori mappa/set il operator< viene utilizzato per generare un albero ordinato.

Nei contenitori non ordinati, an operator( key ) => index si usa.

Vedi hashing per una descrizione di come funziona.

Answer 2

Hai chiesto il motivo canonico per cui è stato creato Boost::MultiIndex:ordine di inserimento elenchi con ricerca rapida per chiave. Tutorial sul potenziamento del multiindice:ricerca rapida dell'elenco

Answer 3

È necessario indicizzare un contenitore associativo in due modi:

• Ordine di inserimento
• Confronto di stringhe

Tentativo Boost.MultiIndex O Boost.Invasivo.Non l'ho usato in questo modo ma penso che sia possibile.

Answer 4

Scusa, ho letto male il tuo ultimo commento.Sì, hash_map non è in STL, map lo è.Ma unordered_map e hash_map sono gli stessi da quello che ho letto.

mappa -> log (n) inserimento, recupero, iterazione è efficiente (e ordinato per confronto chiave)

hash_map/unordered_map -> inserimento e recupero a tempo costante, il tempo di iterazione non è garantito per essere efficiente

Nessuno di questi funzionerà da solo, poiché la mappa ordina le cose in base al contenuto della chiave e non alla sequenza di inserimento (a meno che la chiave non contenga informazioni sulla sequenza di inserimento al suo interno).

Dovrai fare quello che hai descritto (list + hash_map), oppure creare un tipo di chiave che abbia il numero di sequenza di inserimento più una funzione di confronto appropriata.

Answer 5

IO pensare che unordered_map e hash_map sono più o meno la stessa cosa.La differenza è che STL non ha ufficialmente un hash_map (quello che stai utilizzando è probabilmente una cosa specifica del compilatore), quindi unordered_map è la correzione per tale omissione.

unordered_map è proprio questo...non ordinato.Non puoi dipendere dal fatto che mantenga qualsiasi ordine durante l'iterazione.

Answer 6

Sei sicuro che std::hash_map esista in Tutto Implementazioni STL?SGI STL lo implementa, tuttavia GNU g++ non lo ha (si trova comunque nello spazio dei nomi __gnu_cxx) a partire dalla versione 4.3.1.Per quanto ne so, hash_map è sempre stato non standard e ora tr1 lo sta risolvendo.

Answer 7

@wesc:STL ha std::map...quindi qual è la differenza con unordered_map?Non penso che STL implementerebbe due volte la stessa cosa e la chiamerebbe diversamente.