21.令比较函数在等值情况下返回false（严格弱序化）

Posted on | In

set崩坏惨案

</br>
假设存在一个set:

1
2
3
set<int,less_equal<int> > s;//以<=排序
s.insert(10);
s.insert(10);//再次试图插入

显然我们在调用第二次insert之前，set必须判断10在不在里面。我们把首先插入的10记作10A，将后来想要插入的10记作10B.
set首先遍历自己找出在哪儿适合插入10B，并且最终比较10B与10A是否相同（基于等价的相同）。前文已经描述过，关联容器在判断相同时使用的是如下表达式：
1
!c.key_comp()(x, y) && !c.key_comp()(y, x);

那么针对本例中的set,有相同判断式（此式与比较函数并不相同，不要混淆）如下：
1
!(10A <= 10B) && !(10B <= 10A)

显然false&&false是false，所以set认为10A与10B不相同，于是set里面有了两个10.(夭寿啦）。通过使用less_equal作为比较器，我们成功地破坏了set。（在实测中，编译器会在运行期报错，提示比较器无效）
上述实例中导致相同判断式失效最关键的原因在于比较函数对两个等值对象返回了true。
在关联容器中必须牢记，对于两个相等的值，比较函数必须返回false.

实例分析

</br>
我们之前写过对指针的升序版本比较函数，如果我们现在需要一个降序版本（不用说，把之前的拿出来改一改）：

1
2
3
4
5
6
struct StringPtrGreater://无效比较器
    public binary_function<const string*,const string*, bool> {
        bool operator()(const string *ps1, const string *ps2) const{
            return !(*ps1 < *ps2);对原有排序原则取反 <变成了>=
        }
};

该比较器是无效的，因为它对相等的值返回true（基于>=)真正的比较器如下：

1
2
3
4
5
6
struct StringPtrGreater://无效比较器
    public binary_function<const string*,const string*, bool> {
        bool operator()(const string *ps1, const string *ps2) const{
            return *ps1 > *ps2;
        }
};

比较函数对等值对象必须返回false的原因

</br>
比较函数的返回值表明的是在此函数定义的排序方式下，一个值是否大于另一个。相等的值绝不该一个大于另一个，所以比较函数总应该对相等的值返回false。

mutiset与mutimap同样适用的原因

</br>
有人会觉得该条款只对set与map有效，muti则不在此列，但实际上并非如此

1
2
3
multiset<int, less_equal<int> > s;
s.insert(10);
s.insert(10);

如果我们对s调用equal_range成员函数（标注所有与输入元素等值的元素的范围），但由于比较函数认为10A与10B并不相同，所以它们无法同时出现在范围内。

总结

</br>
从技术上说，比较函数应该严格遵守弱序化，其体现之一就是确保两个相等的值比较时返回false.