排序中遇到的一个小陷阱

发表于 | 分类于 | 本文总阅读量 次
字数统计: 608 字 | 阅读时长 ≈ 2 分钟

我们都知道，C++STL中允许我们去重载<，来实现自定义元素的比较。但我们在自定义比较时，我们要注意一些问题。首先就是，STL规定的<是一种严格弱序关系，满足反自反性（f(x,x)为假），非对称性（f(x,y)与f(y,x)结果不同），传递性（f(x,y)为真，f(y,z)为真，则f(x,z)也为真），既需要满足即<表达的关系是一种严格小于关系，而不能是小于等于。严格弱序关系保证了一些性质，即严格弱序的<可以用来表达其他的运算符。

a > b：!(a < b)

a == b：!(a < b) && !(b < a)

a !=b：(a < b) || (b < a)

a <= b：!(b < a)

a >= b：!(a < b)

而对于不严格的比较来说，比如在关系中，严格弱序与非严格就会出现不同的结果。因此在重载时如果不满足严格弱序会出现各种各样的问题，包括不限于RE，TLE等等。

我在之前的代码当中也是出现过这个错误，本来是写一个比较复杂，有多重条件的比较函数，其中有一项是，当值为x时，该元素就要无条件排在最前面（值为x的元素保证只有一个），而当时我只写了对于f(a,b)来说，如果ax，则直接返回1，但是这样写有一个问题，它是不满足严格弱序的。对于非对称性而言，f(x,y)一定能返回真，但是f(y,x)却不一定能返回假，所以我们在这里定义的比较函数是不满足非对称性的，也就是说不满足严格弱序，因此这样的函数是会出现问题的。

那么怎么解决呢？我们只需要在再加一条，否则如果b==x的话，则返回0。

1
2
3
4
5
f(a,b):
	if(a==x):
    return 1
   else if(b==x)
   	 return 0

通俗的来说，就是在定义比较函数时要记得自己定义的情况考虑了反面，考虑了所有情况，尽量写成return a<b的形式或者也可以写成

1
2
3
4
if a<b:
	return 1
else if a>b:
	return 0

的形式，但是注意写成后者一定要写全，一定要把后面的情况考虑到