在C ++中使用HashMap的最好方法是什么?

我知道STL有一个HashMap API,但是我找不到任何有关这方面很好的例子。

任何好的例子将不胜感激。

STL包含有序和无序的映射( std::mapstd::unordered_map )容器。 在有序映射中,元素按键sorting,插入和访问在O (log n)中)。 通常,STL内部使用红黑树作为有序地图。 但是这只是一个实现细节。 在一个无序的地图插入和访问是在O(1)。 这只是哈希表的另一个名字。

(有序) 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; } 

输出:

 23
关键:你好值:23

如果你需要在你的容器中进行sorting,并且使用O(log n)运行时,那么就使用std::map

否则,如果你真的需要一个散列表(O(1)插入/访问),检查出std::unordered_map ,它有一个类似于std::map API(例如在上面的例子中,你只需要search和replace与unordered_map map )。

unordered_map容器是在C ++ 11标准版本中引入的。 因此,根据您的编译器,您必须启用C ++ 11function(例如,在使用GCC 4.8时,必须将-std=c++11添加到CXXFLAGS中)。

甚至在C ++ 11版本之前,GCC支持unordered_map – 在命名空间std::tr1 。 因此,对于旧的GCC编译器,你可以尝试像这样使用它:

 #include <tr1/unordered_map> std::tr1::unordered_map<std::string, int> m; 

这也是boost的一部分,也就是说你可以使用相应的boost-header来提高可移植性。

hash_map是一个较旧的,非标准化的版本,称为unordered_map (目前可作为TR1的一部分,将包含在C ++ 0x中)。 顾名思义,它与std::map的区别主要在于无序 – 例如,如果您通过从begin()end()的映射进行迭代,则按键1顺序获取项目,但如果迭代通过从begin()end()unordered_map ,你可以获得或多或less任意顺序的项目。

unordered_map通常被期望具有不变的复杂性。 也就是说,无论表中有多less项目,插入,查找等基本上都需要一段固定的时间。 一个std::map复杂度是对象的数量的对数 – 这意味着插入或检索一个项目的时间增长,但非常缓慢 ,随着地图变大。 例如,如果需要1微秒来查找100万个项目中的一个,则可以预计花费大约2微秒来查找200万个项目中的一个,400万个项目中的一个为3微秒,800万个中的一个为4微秒物品等

从实际的angular度来看,这不是真的整个故事。 就本质而言,简单的哈希表具有固定的大小。 使其适应通用容器的可变尺寸要求是有点不重要的。 因此,(可能)增长或缩小表(例如插入和删除)的操作通常相对较慢。 查找,不能改变表的大小,通常要快得多。 因此,大多数基于散列表的表往往是最好的时候,你做了很多的查找和相对较less的插入和删除。 对于插入大量数据的情况,然后迭代一次表来检索结果(例如,计算文件中唯一字的数量), std::map速度可能会一样快,甚至很可能更快。

1在您创build地图时,订单由第三个模板参数定义,默认情况下为std::less<T>

这是一个更完整,更灵活的例子,不会遗漏必要的包含来产生编译错误:

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

仍然不是特别有用的键,除非它们被预定义为指针,因为匹配的值不会! (但是,由于我通常使用string作为键,因此在键的声明中将“string”replace为“const void *”应该可以解决这个问题。