c++ - hash_set::upper_bound() 是如何工作的？

Question

Visual C++ 是如何stdext::hash_set<T>::upper_bound()工作的？
哈希表如何还能保持元素排序？！

我试图阅读源代码，但很难破译 STL 代码......甚至在概念上，我也无法理解：哈希表如何比较元素？

Answer 1

各种unordered_xxx模板使用哈希函数将对象分类到桶中。进入同一桶的对象被分组，以便比较相等的对象是相邻的（其中“比较相等”意味着“a < b是假的并且b < a是假的，或者，对于谓词版本，pr(a,b)是假的并且pr(b,a)是假的”）。lower_bound()返回一个迭代器，该迭代器指向与传递的值匹配的第一个对象；upper_bound()返回一个迭代器，该迭代器超过与传递的值匹配的最后一个对象。不涉及全局排序。

Answer 2

哈希表不需要保持元素排序；它只需要将任何新插入的元素与当前最高值进行比较并相应地更新。无需排序。

至于它如何比较元素：这就是运算符的用途。只要类型 <T> 实现了 '>' 操作符，它就可以被排序。您可以为您的类编写自己的 > 运算符，但它必须支持严格的排序（例如，在比较“abc”和“abcdef”时，您必须确定在这种情况下哪个“更大”）。