Invalid operator< assertion error解析

这两天忙着在准备3月份打PAT考试，许久没有接触刷题了，各种生疏各种忘记，刷题速度那是一个慢，真是为自己智商着急。今天刷题碰到了一个有意思的编程习惯性错误，好几道题都涉及到自定义排序，需要自己重写<操作符号，我在调试的时候，程序提示assertion error: Invalid operator<，思考了很久也没有发现问题，在网上搜寻了这个问题，大概是理解了，将我对这个问题的理解总结一下。

 

案例：如自定义结构体Cmp

struct Cmp
{
    int field1,field2;
    bool operator<(const Cmp& cmp)
	{
	    if(this->field1 < cmp.field1) return true;
		else if(this->field2 < cmp.field2) return true;
		return false;
	}
};

 此结构体的大小主要是按照field1进行排列，如果field1排不出来，就按照field2进行排列。这段代码看上去没有什么问题，但是如果使用algorithm stl中的sort函数对含有此类型的数组进行排序，在debug模式下会出现断言失败的提示，即invalid operator<，表示这个自定义的比较函数不严格，可能会有问题。

 

仔细分析，也很容易看出来这段代码错在什么地方，在第二个if判断中，我们仅仅是判断了第二个field大小，忘记加上对第一个field的限制了，把该if判断改成

else if(this->field2 < cmp.field2 && this->field1 == cmp.field1)

 发现警告消失了，为什么会这样呢？标准库中的sort函数为什么要我们这么写？

 

sort函数要求比较函数是strict weak ordering的，而strict weak ordering必须满足三个条件：

1） Strict: pred (X, X) is always false.  X跟X自己比为false

2） Weak: If ! pred (X, Y) && !pred (Y, X), X==Y. 当X<Y和Y<X都不成立时，X等于Y

3）Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z). 当X<Y,Y<Z时，X<Z成立，即排序的一个传递性。

 

用一个实例来说明问题。假设有三个变量，m1(1,2),m2(2,1),m3(1,2)。（括号内的两个数分别表示field1和field2的值。在前面有问题的代码下，我们可以判断：

1）m1<m2，并且m2<m3，根据条件3，m1<m3，但是很明显m1跟m3是一样的，应该是相等的！ 

2）也可以发现在该规则下，m2<m1也成立！根据条件1，推导出m1竟然与m2相等，m1==m2！

这两个情况明显不符合常理，如果允许程序这样运行，最后的结果谁也想不到会排成什么样子。

 

综上所述，在写比较函数的时候一定要小心，不要粗心大意漏掉了条件。这也告诫了我们编译器给出的各种提示警告，还是老老实实地去遵守比较好，不然到后来吃了哑巴亏也不知道是什么地方出了问题。