使用set更少或更少_equal

Question

我们可以通过一个功能<(少)运算符STL数据结构,例如set,multiset,map,priority_queue,...

如果我们的函数就像<=(less_equal)那样有问题吗？

Answer 1

是的,有一个问题.

形式上,比较函数必须定义严格的弱排序,而<=不是这样做.

更具体地说,<它也用于确定等价(x并且y等效于iff !(x < y) && !(y < x)).这不适用于<=(使用该运算符会使您的集合相信对象永远不会等效)

Answer 2

从Effective STL - > Item 21.总是让比较函数对于相等的值返回false.

创建一个集合,其中less_equal是比较类型,然后在集合中插入10:

set<int, less_equal<int> > s; // s is sorted by "<="
s.insert(10); //insert the value 10

现在再次尝试插入10:

s.insert(10);

对于此插入调用,该集必须确定10是否已存在.我们知道它是.但这套装置像烤面包一样愚蠢,所以必须检查.为了更容易理解当集合执行此操作时会发生什么,我们将调用最初插入10A的10和我们尝试插入10B的10.该集合通过其内部数据结构寻找到的位置插入10B.它最终必须检查10B以查看它是否与10A相同.关联容器的"相同"的定义是等价的,因此设置测试以查看10B是否等于10A.执行此测试时,它自然使用集合的比较功能.在这个例子中,那个运算符是<=,因为我们指定less_equal作为集合的比较函数,而less_equal表示运算符.因此,集合检查此表达式是否为真:

!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence

那么,10A和10B都是10,所以10A <= 10B显然是正确的.同样清楚的是,10B <= 10A.因此上述表达简化为

!!(true)&&!(true)

这简化为

false && false

这简直是​​假的.也就是说,该组结论10A和10B不相等,因此不相同,因此将10B插入到10A旁边的容器中.从技术上讲,这个动作产生了未定义的行为,但几乎普遍的结果是该集合最终得到了值10的两个副本,这意味着它不再是一个集合.通过使用less_equal作为我们的比较类型,我们已经破坏了容器!此外,任何等值返回true的比较函数都会做同样的事情.根据定义,等值不等同!

Answer 3

确实存在问题.

比较函数应该满足严格的弱排序,而<=不是.