考虑以下：

在 C++ 中，std::unordered_map 在插入过程中使用哈希函数来确定新插入元素的位置。

但是，std::map在插入过程中 不使用哈希函数，并使用与在任何二叉搜索树中确定新插入元素的位置相同的方法来确定新插入元素的位置。我的意思是在任何二叉搜索树中确定新元素位置的方法是，例如，如果该元素大于当前元素，则向右走，或者如果该元素小于当前元素，则向右走左边。

我的结论100%准确吗？

18

  • 每个问题一个问题。


    – 

  • 2
    是的，通常std::map被实现为树，并且通常被实现为哈希表。这两种实现都不是标准的要求。参见和。std::unordered_map


    – 


  • 这也取决于实施。


    – 

  • 2
    理论上，该标准不需要任何具体的实现，但在实践中，没有很好的方法来实现这些与哈希表/平衡树有本质区别的抽象数据类型。


    – 

  • 1
    @ChristianStieber – 委员会在指定要求时肯定考虑到了可能的实施方案。不过，他们不想把这一点说清楚，因为以后可能会发明更好的方法。


    – 


1 个回答
1

std::map有一个类型参数Compare，需要它为映射的键提供排序，并通过关系equiv(a, b)iff确定键何时相等!comp(a, b) && !comp(b, a)

std::unordered_map有一个类型参数Hash，需要它来提供映射键的散列。它还有一个类型参数Equal，需要以与Hash一致的方式确定键之间的等价性，即hash(a) == hash(b)if equal(a, b)。

这些要求以及某些成员函数的复杂性要求意味着，虽然理论上存在使用不同数据结构进行操作的实现空间，但要符合要求，std::map必须是平衡二叉树，并且std::unordered_map必须是

6

  • 因此，如果我理解正确，您完全同意我的观点：“ std::unordered_map 在插入过程中使用哈希函数来确定新插入元素的位置。但是，std::map 不使用哈希函数插入过程以及如何确定新插入元素的位置”，对吧？


    – 


  • 1
    @f877576 是的，没错


    – 

  • 抱歉打扰您，但我发现这个表提到map不需要哈希函数而unordered_map需要哈希函数这个表中的信息完全正确吗？ @Caleth


    – 


  • 1
    @f877576 这几乎是正确的。它不一定是operator</ operator==，这些只是默认的Compare和Equal分别使用的内容


    – 

  • 1
    @f877576 当您使用 时，您链接的源是正确的std::map<K, V>，因为它实际上与 相同std::map<K, V, std::less<K>, std::allocator<std::pair<const K, V>>>，并且std::less是比较 via 的函数对象类型<，但您可以拥有具有不同比较的映射，例如std::map<K, V, std::greater<K>>顺序std::map<K, V>相反。


    –