std库sort排序函数的crash

某天一个同事在做代码版本升级

Qt4 to Qt5 - Obsolete Members for <QtAlgorithms>

• qSort => std::sort & qSort(list) => std::sort(list.begin, list.end)
• qStableSort => std::stable_sort & qStableSort(list) => std::stable_sort(list.begin, list.end)
• qGreater => std::greater
• qLess => std::less
• qSwap => std::swap

按照这个规则，其中有一行代码

        qSort(_rawDataList2.begin(), _rawDataList2.end(), callback);

改成

        std::sort(_rawDataList2.begin(), _rawDataList2.end(), callback);

但是这样改却引起了程序的crash。

根据经验，crash在std底层库，那肯定是一些通用性的问题，于是在谷歌上检索到这么一条有用信息。实现std::sort的比较函数 lessThan(const T& left, const T& right) {/满足严格排序/} 需要满足以下规则。

strict weak ordering

This is a mathematical term to define a relationship between t>wo objects.

Its definition is:

Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself.

这里有个关键的一点是，如果两个被比较的对象相等，那么比较函数需要满足 lessThan(left, right) == lessThan(right, left) = false。

在C++中，我们穷举两个被比较对象的所有可能，一个"operatior <()的函数" 他的规则应该如下表示，

X a;

X b;

如果不遵循这个规则，设计了比较函数，那么std::sort可能会陷入死循环，进而导致crash。

而QT的qSort没有这个问题。