为什么未排序的关联容器不实现小于操作符? [英] Why don't unordered associative containers implement the less than operator?
问题描述
无序关联容器 unordered_set ， unordered_map 等不小于运算符 operator< ，既不作为成员函数也不作为成员函数自由功能.为什么?也没有 less 的专业化.SGI STL的 hash _ * 类型也缺少此功能.
The unordered associative containers unordered_set, unordered_map etc do not have a less than operator operator<, neither as a member function nor as a free function. Why? There is no specialization of less either. SGI STL's hash_* types also lack this feature.
如果我们排除基础类型的概念，则所有容器类型都满足定义的常规类型的要求，例如在Stepanov&McJones的编程元素.唯一的例外是无序关联类型，它们缺少 operator< .
If we exclude the concept of underlying types, all container types fulfil the requirements of regular types as defined e.g. in Stepanov & McJones' Elements of Programming. The sole exception are the unordered associative types, which lack operator<.
我无法提出与给定的相等定义相符的这种运算符的有效实现，所以效率可能是原因吗?另一方面，在某些情况下，用于无序关联容器的 operator == 需要重新哈希一个容器的每个元素，并在另一个容器中查找-O(N)平均值，但最坏的情况是O(N²).
I could not come up with an efficient implementation of such an operator that is consistent with the given definition of equality, so might efficiency be the reason? On the other hand, operator== for unordered associative containers in some cases needs to rehash every element of one container and look it up in the other - O(N) average, but worst case O(N²).
推荐答案
从概念上讲，这没有什么意义.考虑一袋不同颜色的大理石.假设您有两袋弹珠:
Conceptually it doesn't make a lot of sense. Consider a bag of different colored marbles. And lets say you have two bags of marbles:
- 包含红色，蓝色，绿色.
- 包含紫色，红色，黄色.
袋子1是<袋子2?
Is bag 1 < bag 2?
即使您将订单与颜色相关联，也要说:
Even if you associate an order to the colors, say:
red < yellow < purple < blue < green
仍然很难说一个袋子是否比另一个袋子少，因为袋子在内部与大理石没有任何关系.也就是说，包1可以以以下6种格式中的任何一种输出:
It is still difficult to say if one bag is less than than the other because internally the bag associates no order to the marbles. That is bag 1 could be output in any of 6 formats, which are all equivalent:
- 红色，蓝色，绿色
- 红色，绿色，蓝色
- 蓝色，红色，绿色
- 蓝色，绿色，红色
- 绿色，红色，蓝色
- 绿色，蓝色，红色
以上六个都不比其他任何一个都少.确实，它们都相等，无论是否<蓝色或蓝色<红色的.袋子不是序列...而是无序序列.
None of the above six are less than any of the other. Indeed, they are all equal, no matter whether red < blue or blue < red. A bag is not a sequence ... it is an unordered sequence.
从历史上看，无序容器也没有相等运算符.但是，询问一个袋子是否包含与另一个袋子相同颜色的大理石确实有意义.这是效率的问题之一.最终提出了算法和建议，以动摇委员会为无序容器添加相等性比较:
Historically the unordered containers also did not have equality operators. However it does make sense to ask if one bag contains the same colored marbles as another bag. And here the issue is one of efficiency. Eventually algorithms and proposals were presented to sway the committee to add equality comparisons for the unordered containers:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
这篇关于为什么未排序的关联容器不实现小于操作符?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
