Einfache hashmap Implementierung in C ++

Question

Ich bin relativ neu in C ++. In Java ist es einfach für mich, einen hashmap zu instanziiert und zu verwenden. Ich würde gerne wissen, wie es auf einfache Art und Weise in C ++ zu tun, da ich mir viele verschiedene Implementierungen und keiner von ihnen sah einfach gesehen haben.

Answer 1

Die meisten Compiler sollten std::hash_map für Sie definieren; im kommenden C++0x Standard, wird es Teil der Standardbibliothek als std::unordered_map sein. Die STL Seite auf es ist ziemlich Standard. Wenn Sie Visual Studio verwenden, Microsoft hat eine Seite auf sie.

Wenn Sie Ihre Klasse als Wert verwenden möchten, nicht als Schlüssel, dann brauchen Sie nichts Besonderes zu tun. Alle primitiven Typen (Dinge wie int, char, bool und sogar char *) sollten „einfach funktionieren“ als Schlüssel in einem hash_map. Doch für alles andere müssen Sie Ihre eigene Hashing und Gleichheitsfunktionen definieren und dann schreiben „functors“, dass sie in einer Klasse wickeln.

Angenommen, Ihre Klasse heißt MyClass und Sie haben bereits definiert:

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

Sie müssen zwei functors definieren, um diese Methoden in Objekten wickeln.

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);
  }
};

Und instanziiert Ihre hash_map / hash_set wie:

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

Alles sollte so danach erwartet.

Answer 2

Mit Hashmaps in C ++ ist ganz einfach! Es ist wie mit Standard-C ++ Karte. Sie können Ihre Compiler / Bibliothek Implementierung von unordered_map verwenden oder die von boost oder ein anderer Anbieter. Hier ist eine kurze Probe. Sie werden mehr finden, wenn Sie die Links folgen Sie gegeben wurden.

#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

Hier finden Sie aktuelle Boost.Unordered und seine Datenstruktur .

Answer 4

Versuchen Sie die Boost- ungeordnete Klassen.

Answer 5

Schauen Sie sich einfachen Hash-Map (Hash Table) Implementierung in C ++ für eine grundlegende Hash Table mit generischem Typ Tasten- Wert-Paare und eine separate Verkettungsstrategie.