每当我需要存储与特定类型的值相关联的一些数据（键值-例如字符串或其他对象）时，我通常使用C ++ stdlib map。 stdlib map实现基于树，提供比标准数组或stdlib向量更好的性能（O(log n)）。
我的问题是，您是否了解任何C ++“标准”哈希表实现，可以提供更好的性能（O(1)）？类似于Java API中的Hashtable类可用的内容。
9个回答
82
如果您正在使用C++11，则可以访问
如果您正在使用带有TR1的C++03，则可以访问类
在所有情况下，也有相应的
<unordered_map>和<unordered_set>头文件。它们提供了类std::unordered_map和std::unordered_set。如果您正在使用带有TR1的C++03，则可以访问类
std::tr1::unordered_map和std::tr1::unordered_set，使用相同的头文件（除非您正在使用GCC，在这种情况下，头文件是<tr1/unordered_map>和<tr1/unordered_set>）。在所有情况下，也有相应的
unordered_multimap和unordered_multiset类型。- Chris Jester-Young
4
6在GCC中，您需要使用头文件名称<tr1/unordered_map>和<tr1/unordered_set>。这是GCC的一个怪癖。 :-) - C. K. Young
VS2008的功能包已被SP1取代。 - Ferruccio
据我所知，VC9功能包和SP1 tr1::unordered_*实现附带了发布说明，警告其性能不够优秀。我认为这个问题最终会得到解决。 - jwfearn
谢谢，Ferruccio！我已经采纳了你的修复建议。（我在编辑评论中拼错了你的名字，对此我深表歉意，但我现在似乎没有办法去更正它。） - C. K. Young
2
Visual Studio在头文件<hash_map>中拥有类stdext::hash_map，而gcc在同一头文件中拥有类__gnu_cxx::hash_map。
- Adam Rosenfield
2
如果它们有相同的接口，使用命名空间别名和一些预处理器工作很容易实现支持它们两个的实现。 - Jasper Bekkers
我知道，我知道，这是已经弃用的东西。并非每个同事都会被说服切换到VS 2008或安装Boost。所以，这里有一个不错的技巧，可以将它们组合起来：
namespace std { #ifdef __GNUC__ using namespace __gnu_cxx; #else using namespace stdext; #endif } - ypnos2
在 <unordered_map> 中，有一个名为 std::tr1::unordered_map 的类。
如果您没有 tr1，请获取 boost，并使用 <boost/unordered_map.hpp> 中的 boost::unordered_map。
- rlbond
1
请参考 SGI 的 std::hash_map。
这也包含在 STLPort 发行版中。
- Adam Tegen
1
它可能被包含在STLPort中，但仍然不是“标准”，正如问题所寻求的。没有名为hash_map的“标准”类；它被称为unordered_map，并且在TR1中。 - C. K. Young
1
- Ben Collins
3
它可能得到广泛支持，但并不是“标准”，正如提问者所要求的那样。只有TR1设施可以被认为是标准。 - C. K. Young
我想表达的意思是，如果所有编译器供应商都支持它（或者stdlibc++供应商，视情况而定），那么它可能是一个足够好的“标准”替代品。顺便说一句，TR1还不是“标准”。它已被接受为下一个标准，这足以让供应商实现它（我的观点...） - Ben Collins
我认为这只适用于libstdc++版本>= 4.0？ - rogerdpack
1
如果您的编译器支持TR1扩展，请使用它们。如果不支持，则boost.org有一个版本，除了std::命名空间之外，它非常相似。在这种情况下，可以使用using声明，以便稍后切换到std::。
- MSalters
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接