使用set的less或less_equal

Question

我们可以将函数作为<(less)运算符传递给set、multiset、map、priority_queue等STL数据结构。

如果我们的函数行为类似于<=(less_equal)，会有问题吗？

Answer 1

来自生效的STL ->项目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);

对于这个插入调用，set必须确定10是否已经存在。我们知道这是真的。但是集合是愚蠢的，所以它必须检查。为了更容易理解set执行此操作时发生的情况，我们将初始插入的10称为10A，而我们尝试插入的10 10B.The set遍历其内部数据结构，查找要插入10B的位置。它最终必须检查10B，看看它是否与10A相同。关联容器的“相同”的定义是等价的，因此set测试10B是否等于10A。在执行此测试时，它自然会使用set的比较函数。在本例中，这是operator<=，因为我们指定less_equal作为集合的比较函数，而less_equal表示运算符。因此，该集合检查该表达式是否为真：

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

好的，10A和10B都是10，所以10A <= 10B很明显是真的。同样明显的是，10B <= 10A。因此，上面的表达式简化为

!!(true)&&!(true)

这就简化为

false && false

这是完全错误的。也就是说，set得出结论，10A和10B不等价，因此不相同，因此它将10B与10A一起插入到容器中。从技术上讲，此操作会产生未定义的行为，但几乎通用的结果是，集合最终得到值10的两个副本，这意味着它不再是集合。通过使用less_equal作为比较类型，我们破坏了容器！此外，任何相等值返回true的比较函数都会做同样的事情。根据定义，相等的值是不等价的！

Answer 2

是的，确实有个问题。

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

更具体地说，<还用于确定等价性(x和y等价的当且仅当!(x < y) && !(y < x))。这并不适用于<= (使用该运算符会让您的set相信对象永远不是等价的)

Answer 3

确实存在一个问题。

比较函数应该满足<=不满足的strict weak ordering。