C++中的字典/哈希表对象是什么？

Question

C++中的字典/哈希表对象是什么？

c++dictionary

13

我正在寻找一个在C++中与C#中的HashTable或Dictionary实现类似功能的实现。STL中是否包含此类对象，如何使用它？

- cam

4个回答

5

STL有std::map

- spoulson

1

map是一棵平衡树，而不是哈希容器。 - Joe

@joe - 问题是关于C++ STL中哈希表或字典类的，因此 std::map 可以胜任。 - gnud

1

@gnud：OP还说“具有类似于C#中的功能”，如果你谈论性能特征，只有unordered_map适合。 - Joe

2

我相信你正在寻找map。请在这里查看更多信息。

- Jason Punyon

2

STL的std::map可以用来构建字典。通常情况下，std::map使用搜索树实现，而不是哈希表。这意味着查找和插入具有不同的性能特征，与C#中的HashMap相比，在非常大的映射中，平均查找速度会变慢，特别是如果映射中的对象在内存中分散的情况下。

在新的C++标准TR1中，你可以使用std::tr1::unordered_map和std::tr1::unordered_multimap，它们通常使用哈希表实现。如果你的编译器没有提供这些库，可以使用来自http://www.boost.org/的实现。

另一个选择是Google的sparse_hash。

- gnud

在std::map中查找本质上不比在hash_map中慢。只有hash_map的渐近性能是O(1) vs. O(log n)，但对于足够大的1值，log n可能更快。即使在实践中，这通常也是情况，而且找到一个好的哈希函数比实现正确的operator<要困难得多。 - gimpf

刚才重新读了一遍，你说的是“经常”，而不是总是，这是我的错。然而，“经常”意味着大多数人使用具有超过1000个条目的字典，并使用正确的哈希函数。根据工作领域和公司内部的技能水平，这可能确实不太可能。 - gimpf

也许“经常会更慢”有点过于苛刻了。我的观点主要是它们具有不同的性能特征。 - gnud

还有MCT的closed_hash_map，类似于Google的dense_hash_map，但没有对键的限制。 - user319799

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dean Harding · Accepted Answer

实际上，为了与.NET的Dictionary/Hashtable完全相同，您需要使用hash_map或unordered_map（std::map实现为二叉树），hash_map是SC++L的扩展。我知道的大多数编译器都有hash_map，而且显然boost直到C++0x在所有编译器中可用之前都有unordered_map，因此您应该能够轻松使用它。