implementação hashmap simples em C ++

Question

Eu sou relativamente novo para C ++. Em Java, é fácil para mim para instanciar e usar um hashmap. Eu gostaria de saber como fazê-lo de uma forma simples em C ++, desde que eu vi muitas implementações diferentes e nenhum deles parecia simples para mim.

Answer 1

A maioria dos compiladores deve definir std::hash_map para você; no padrão C++0x vindo, será parte da biblioteca padrão como std::unordered_map . A STL Página sobre ele é bastante normal. Se você usar Visual Studio, Microsoft tem uma página sobre ele.

Se você quiser usar a sua classe como o valor, não como a chave, então você não precisa fazer nada especial. Todos os tipos primitivos (coisas como int, char, bool e até mesmo char *) deve "apenas trabalho" como chaves em um hash_map. No entanto, para qualquer outra coisa que você terá que definir suas próprias funções de hashing e igualdade e, em seguida, escrever "functors" que envolvê-los em uma classe.

Assumindo sua classe é chamado MyClass e você já tiver definido:

size_t MyClass::HashValue() const { /* something */ }
bool MyClass::Equals(const MyClass& other) const { /* something */ }

Você precisará definir dois functors para embrulhar os mesmos métodos com objetos.

struct MyClassHash {
  size_t operator()(const MyClass& p) const {
    return p.HashValue();
  }
};

struct MyClassEqual {
  bool operator()(const MyClass& c1, const MyClass& c2) const {
    return c1.Equals(c2);
  }
};

E instancia seu hash_map / hash_set como:

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map;
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set;

Tudo deve funcionar como esperado depois disso.

Answer 2

Usando HashMaps em C ++ é fácil! É como usar mapa padrão C ++. Você pode usar o seu compilador implementação / biblioteca de unordered_map ou usar o fornecido pelo boost , ou algum outro fornecedor. Aqui está um exemplo rápido. Você vai encontrar mais se você seguir os links lhe foram dadas.

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    typedef std::tr1::unordered_map< std::string, int > hashmap;
    hashmap numbers;

    numbers["one"] = 1;
    numbers["two"] = 2;
    numbers["three"] = 3;

    std::tr1::hash< std::string > hashfunc = numbers.hash_function();
    for( hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i ) {
        std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc( i->first ) << ")" << std::endl;
    }
    return 0;
}

Answer 3

Dê uma olhada boost.unordered , e a sua estrutura de dados .

Answer 4

não ordenada aulas Try do impulso.

Answer 5

Confira simples Hash Mapa (Hash Table) Implementação em C ++ para uma tabela hash básico com tipo genérico chave- pares de valores e estratégia de encadeamento separado.