为什么无序关联容器不实现小于运算符？

Question

无序关联容器unordered_set、unordered_map等没有小于运算符operator<，既不是成员函数也不是自由函数。为什么？ less 也没有专业化。 SGI STL 的 hash_* 类型也缺少此功能。

如果我们排除底层类型的概念，所有容器类型都满足定义的常规类型的要求，例如在 Stepanov 和 McJones 的 编程基础 中。唯一的例外是无序关联类型，它缺少 operator<.

我想不出一个与给定的相等性定义一致的运算符的有效实现，那么效率可能是原因吗？另一方面，operator== 对于无序关联容器在某些情况下需要重新散列一个容器的每个元素并在另一个容器中查找它 - O(N) 平均，但最坏情况 O(N²)。

Answer 1

从概念上讲，它没有多大意义。考虑一袋不同颜色的弹珠。假设你有两袋弹珠：

袋子 1 < 袋子 2 吗？

即使您将颜色的顺序关联起来，也可以说：

red < yellow < purple < blue < green

仍然很难说一个袋子是否比另一个袋子少，因为袋子内部与弹珠没有关联。即bag 1可以输出6种格式中的任意一种，都是等价的：

None 以上六个都比其他任何一个都少。实际上，无论是红色 < 蓝色还是蓝色 < 红色，它们都是平等的。包不是一个序列...它是一个无序序列。

从历史上看，无序容器也没有相等运算符。然而，询问一个袋子是否包含与另一个袋子颜色相同的弹珠确实是有意义的。这里的问题是效率之一。最终提出了算法和提案来影响委员会为无序容器添加相等比较：

Why don't unordered associative containers implement the less than operator?