Qual è il modo migliore di usare una HashMap in C++?

Question

So che STL ha un'API HashMap, ma non riesco a trovare alcuna documentazione valida e completa con buoni esempi a riguardo.

Qualsiasi buon esempio sarà apprezzato.

Answer 1

L'STL include i contenitori ordinati e non ordinati (std::map e std::unordered_map). In una mappa ordinata gli elementi sono ordinati per chiave, inserire e l'accesso è in O (log n)). Solitamente STL utilizza internamente red black trees per le mappe ordinate. Ma questo è solo un dettaglio di implementazione. In una mappa non ordinata inserire e l'accesso è in O (1). È solo un altro nome per un hashtable.

Un esempio con (ordinato) std::map:

#include <map> 
#include <iostream> 
#include <cassert> 

int main(int argc, char **argv) 
{ 
    std::map<std::string, int> m; 
    m["hello"] = 23; 
    // check if key is present 
    if (m.find("world") != m.end()) 
    std::cout << "map contains key world!\n"; 
    // retrieve 
    std::cout << m["hello"] << '\n'; 
    std::map<std::string, int>::iterator i = m.find("hello"); 
    assert(i != m.end()); 
    std::cout << "Key: " << i->first << " Value: " << i->second << '\n'; 
    return 0; 
} 

uscita:

 
23 
Key: hello Value: 23 

Se avete bisogno di ordinare nel vostro contenitore e stanno bene con la O (log n) runtime poi basta usare std::map .

In caso contrario, se si ha realmente bisogno di un hash-table (O (1) inserimento/accesso), controlla std::unordered_map, che ha un simile al std::map API (ad esempio, nell'esempio di cui sopra non resta che cercare e sostituire map con unordered_map).

Il contenitore unordered_map è stato introdotto con la revisione C++11 standard. Pertanto, a seconda del compilatore, è necessario abilitare le funzionalità di C++ 11 (ad esempio quando si utilizza GCC 4.8 è necessario aggiungere -std=c++11 a CXXFLAGS).

Anche prima della versione C++ 11 GCC supportato unordered_map - nel namespace std::tr1. Così, per i vecchi compilatori GCC si può provare a utilizzare in questo modo:

#include <tr1/unordered_map> 

std::tr1::unordered_map<std::string, int> m; 

E 'anche parte della spinta, cioè è possibile utilizzare il corrispondente boost-header per una migliore portabilità.

Answer 2

A hash_map Una versione precedente, non standardizzata di ciò che per scopi di standardizzazione è denominata unordered_map (attualmente disponibile come parte di TR1 e sarà inclusa in C++ 0x). Come suggerisce il nome, è diverso da std::map principalmente in essere non ordinato - se, ad esempio, di eseguire iterazioni attraverso una mappa begin()-end(), si ottiene elementi in ordine a chiave , ma se si scorre attraverso un unordered_map da begin() a end(), si ottengono gli articoli in un ordine più o meno arbitrario.

Si prevede normalmente che un unordered_map abbia una complessità costante. In altre parole, un inserimento, una ricerca, ecc., Richiede essenzialmente una quantità di tempo fissa, indipendentemente dal numero di elementi presenti nella tabella. Un std::map ha una complessità logaritmica sul numero di elementi che vengono archiviati, il che significa che il tempo per inserire o recuperare un elemento aumenta, ma molto lentamente, man mano che la mappa aumenta. Ad esempio, se impiega 1 microsecondo per cercare 1 milione di articoli, allora ci si può aspettare che occorra circa 2 microsecondi per cercare uno dei 2 milioni di articoli, 3 microsecondi per uno di 4 milioni di articoli, 4 microsecondi per uno di 8 milioni articoli, ecc.

Dal punto di vista pratico, tuttavia, non è tutta la storia. Per sua natura, un semplice hash table ha una dimensione fissa. Adattarlo ai requisiti delle dimensioni variabili per un contenitore per scopi generici è in qualche modo non banale. Di conseguenza, le operazioni che (potenzialmente) aumentano o riducono la tabella (ad es. Inserimento e cancellazione) sono spesso relativamente lente. Le ricerche, che non possono cambiare le dimensioni del tavolo, sono generalmente molto più veloci. Di conseguenza, la maggior parte delle tabelle basate su hash tendono ad essere al loro meglio quando si effettuano molte ricerche e relativamente pochi inserimenti e cancellazioni. Per le situazioni in cui inserisci molti dati, quindi esegui un'iterazione della tabella una volta per recuperare i risultati (ad es. Contando il numero di parole univoche in un file) è probabile che un std::map sia altrettanto veloce e molto probabilmente ancora più veloce.

Quando l'ordine è definito dal terzo parametro del modello quando si crea la mappa, std::less<T> per impostazione predefinita.

Answer 3

Ecco un esempio più completo e flessibile che non tralascia necessaria comprende generare errori di compilazione:

#include <iostream> 
#include <unordered_map> 

class Hashtable { 
    std::unordered_map<const void *, const void *> htmap; 

public: 
    void put(const void *key, const void *value) { 
      htmap[key] = value; 
    } 

    const void *get(const void *key) { 
      return htmap[key]; 
    } 

}; 

int main() { 
    Hashtable ht; 
    ht.put("Bob", "Dylan"); 
    int one = 1; 
    ht.put("one", &one); 
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one"); 
} 

Ancora non non è particolarmente utile per le chiavi, a meno che non sono predefiniti come puntatori, in quanto un valore corrispondente ha vinto' lo faccio! (Tuttavia, dal momento che uso normalmente stringhe per le chiavi, sostituendo "stringa" per "const void *" nella dichiarazione della chiave dovrebbe risolvere questo problema.)

Answer 4

come utilizzare una funzione di classe personalizzata e hash con unordered_map

questa risposta unghie IT: C++ unordered_map using a custom class type as the key

Estratto: uguaglianza: funzione

struct Key 
{ 
    std::string first; 
    std::string second; 
    int   third; 

    bool operator==(const Key &other) const 
    { return (first == other.first 
      && second == other.second 
      && third == other.third); 
    } 
}; 

Hash:

namespace std { 

    template <> 
    struct hash<Key> 
    { 
    std::size_t operator()(const Key& k) const 
    { 
     using std::size_t; 
     using std::hash; 
     using std::string; 

     // Compute individual hash values for first, 
     // second and third and combine them using XOR 
     // and bit shifting: 

     return ((hash<string>()(k.first) 
      ^(hash<string>()(k.second) << 1)) >> 1) 
      ^(hash<int>()(k.third) << 1); 
    } 
    }; 

}