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

问题描述

我知道STL有一个HashMap API，但是我找不到任何好的和详细的文档，有良好的例子。

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

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

Any good examples will be appreciated.

推荐答案

STL包括有序和无序映射（ std :: map 和 std :: unordered_map ）容器。在有序映射中，元素按键排序，插入和访问位于 O （log n）中）。通常，STL内部使用红黑树进行有序映射。但这只是一个实现细节。在无序映射中，插入和访问在O（1）中。

The STL 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 STL 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.

一个使用（排序） std :: map 的示例：

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!\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
Key: hello Value: 23

如果您需要在您的容器中订购，使用O（log n）运行时，然后只需使用 std :: map 。

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

否则，需要一个哈希表（O（1）插入/访问），检出 std :: unordered_map ，它有一个类似于 std :: map API（例如，在上面的示例中，您只需要搜索并用 unordered_map 替换 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).

unordered_map 容器是用 C ++ 11标准修订版。因此，根据您的编译器，您必须启用C ++ 11功能（例如，当使用GCC 4.8时，必须将 -std = c ++ 11 添加到CXXFLAGS） 。

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).

甚至在C ++ 11发布之前，GCC支持 unordered_map - 在命名空间 std :: tr1 因此，对于旧的GCC编译器，您可以尝试使用它：

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;

它也是boost的一部分，即你可以使用相应的 boost-header 以提高可移植性。

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

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