C++中的简单hashmap实现

我对C++比较陌生.在Java中,我很容易实例化和使用hashmap.我想知道如何在C++中以一种简单的方式来实现它,因为我看到了很多不同的实现,但对我来说它们都不是很简单.

大多数编译器都应该std::hash_map为您定义; 在即将到来的C++0x标准中,它将成为标准库的一部分std::unordered_map.它上面的STL页面是相当标准的.如果您使用Visual Studio,Microsoft上有一个页面.

如果您想使用您的类作为值,而不是键,那么您不需要做任何特殊的事情.所有基本类型(之类的东西int,char,bool甚至char *)应该"只是工作"作为一个键hash_map.但是,对于其他任何事情,您将不得不定义自己的散列和相等函数,然后编写将其包装在类中的"functor".

假设你的类被调用MyClass并且你已经定义了:

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

您需要定义两个仿函数来将这些方法包装在对象中.

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

并实例化你的hash_map/ hash_setas:

hash_map my_hash_map;
hash_set my_hash_set;

在那之后,一切都应该按预期工作.

在C++中使用hashmaps很容易!这就像使用标准的C++地图.您可以使用您的编译器/库实现,unordered_map或使用boost或其他供应商提供的实现.这是一个快速的样本.如果您按照给出的链接,您会找到更多.

#include 
#include 
#include 

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

看一下boost.unordered及其数据结构.