在 C++ 中使用 HashMap 的最佳方法是什么? [英] What is the best way to use a HashMap in C++?

问题描述

我知道 STL 有一个 HashMap API，但我找不到任何好的和详尽的文档以及关于这方面的好例子.

任何好的例子都会受到赞赏.

解决方案

标准库包括有序映射和无序映射(std::map 和 std::unordered_map) 容器.在有序映射中，元素按键排序，插入和访问在 O(log n).通常标准库内部使用 红黑树 来制作有序地图.但这只是一个实现细节.在无序映射中，插入和访问在 O(1) 中.它只是哈希表的另一个名称.

带有(有序)std::map:

的示例

#include <map>#include <iostream>#include <cassert>int main(int argc, char **argv){std::map;米；m[你好"] = 23;//检查key是否存在if (m.find("world") != m.end())std::cout <<"地图包含关键世界！
";//取回std::cout <<m["你好"] <<'
';std::map::iterator i = m.find("hello");断言(我！= m.end())；std::cout <<键:" <

输出:

<上一页>23键:你好值:23

如果您需要在您的容器中订购并且对 O(log n) 运行时没有问题，那么只需使用 std::map.

否则，如果您确实需要哈希表(O(1) 插入/访问)，请查看 std::unordered_map，它与 std::map API(例如，在上面的示例中，您只需搜索并将 map 替换为 unordered_map).

unordered_map 容器是随 C++11 标准引入的 修订.因此，根据您的编译器，您必须启用 C++11 功能(例如，使用 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>米；

也是boost的一部分，即可以使用对应的boost-header 以获得更好的可移植性.

I know that STL has a HashMap API, but I cannot find any good and thorough documentation with good examples regarding this.

Any good examples will be appreciated.

解决方案

The standard library includes the ordered and the unordered map (std::map and std::unordered_map) containers. In an ordered map the elements are sorted by the key, insert and access is in O(log n). Usually the standard library internally uses red black trees for ordered maps. But this is just an implementation detail. In an unordered map insert and access is in O(1). It is just another name for a hashtable.

An example with (ordered) 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!
";
  // retrieve
  std::cout << m["hello"] << '
';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '
';
  return 0;
}

Output:

23
Key: hello Value: 23

If you need ordering in your container and are fine with the O(log n) runtime then just use std::map.

Otherwise, if you really need a hash-table (O(1) insert/access), check out std::unordered_map, which has a similar to std::map API (e.g. in the above example you just have to search and replace map with unordered_map).

The unordered_map container was introduced with the C++11 standard revision. Thus, depending on your compiler, you have to enable C++11 features (e.g. when using GCC 4.8 you have to add -std=c++11 to the CXXFLAGS).

Even before the C++11 release GCC supported unordered_map - in the namespace std::tr1. Thus, for old GCC compilers you can try to use it like this:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

It is also part of boost, i.e. you can use the corresponding boost-header for better portability.

这篇关于在 C++ 中使用 HashMap 的最佳方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！