在C ++中使用HashMap的最好方法是什么？
我知道STL有一个HashMap API，但是我找不到任何有关这方面很好的例子。
任何好的例子将不胜感激。
STL包含有序和无序的映射（ std::map和std::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 *”应该可以解决这个问题。
