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

Question

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

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

---

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

Answer 1

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

1. 包含红色、蓝色、绿色。
2. 包含紫色、红色、黄色。

包 1 < 包 2 吗？

即使您将订单与颜色相关联，请说:

red < yellow < purple < blue < green

仍然很难说一个袋子是否小于另一个袋子，因为袋子内部没有将任何顺序与弹珠联系起来。也就是说，bag 1 可以以 6 种格式中的任何一种输出，它们都是等效的:

1. 红、蓝、绿
2. 红、绿、蓝
3. 蓝色、红色、绿色
4. 蓝色、绿色、红色
5. 绿色、红色、蓝色
6. 绿色、蓝色、红色

以上六个都不小于其他任何一个。事实上，无论是红<蓝还是蓝<红，它们都是平等的。一个包不是一个序列……它是一个无序序列。

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

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf