C ++中的简单hashmap实现

StackOverflow https://stackoverflow.com/questions/266206

  •  06-07-2019
  •  | 
  •  

题

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

有帮助吗？

解决方案

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

如果您想使用您的类作为值，而不是键，那么您不需要做任何特殊的事情。所有原始类型（如 int ， char ， bool ，甚至 char * ）都应该“正常工作”。作为 hash_map 中的键。但是，对于其他任何事情，您必须定义自己的散列和相等函数，然后编写“仿函数”。将它们包装在一个类中。

假设您的类名为 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_set 实例化为：

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

之后一切都应该按预期工作。

其他提示

在C ++中使用hashmaps很简单！这就像使用标准的C ++地图。您可以使用 unordered_map 的编译器/库实现，或使用提升，或其他一些供应商。这是一个快速的样本。如果你按照你给出的链接，你会发现更多。

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

请参阅 boost.unordered ，及其数据结构。

尝试使用boost的无序课程。

查看带有通用类型密钥的基本哈希表的简单哈希映射（哈希表）在C ++中的实现价值对和单独的链接策略。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top