c++ - 使用 set 的 less 或 less_equal

Question

我们可以将函数作为<(less) 运算符传递给 STL 数据结构，例如set, multiset, map, priority_queue, ...

如果我们的函数表现得像<=(less_equal) 会有问题吗？

Answer 1

是的，有问题。

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

更具体地说， the<也用于确定等价（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 是否已经存在。我们知道它是。但是这一套像吐司一样愚蠢，所以它必须检查。为了更容易理解集合执行此操作时会发生什么，我们将最初插入的 10 称为 10A，我们将尝试插入的 10 称为 10B。集合遍历其内部数据结构以寻找位置插入 10B。它最终必须检查 10B 以查看它是否与 10A 相同。关联容器的“相同”的定义是等价的，所以集合测试看 10B 是否等价于 10A。在执行这个测试时，它自然会使用集合的比较功能。在这个例子中，就是 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

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

Answer 3

确实有问题。

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