一次公司项目代码引发了宕机，源于std::sort。相似代码贴在下面。由于std::sort 第三个参数写的不对造成的。
源码：
using Vec = std::vector<std::pair<int, int>>;
void print_elem(const Vec& vec, const std::string& str)
{
std::stringstream oss;
for (const auto& item : vec)
{
oss << "(" << item.first << "--" << item.second << ")";
}
std::cout << str << oss.str() << std::endl;
}
Vec getVec(uint32_t size)
{
Vec vec;
for (uint32_t i = 0; i < size; i++)
{
vec.emplace_back(i, rand() % 2 + 1);
}
print_elem(vec, "origin: ");
std::sort(vec.begin(), vec.end(),
[&vec](const std::pair<int, int>& lhs, const std::pair<int, int>& rhs)
{
print_elem(vec, "sort: ");
return lhs.second >= rhs.second;
});
return vec;
}
int main()
{
srand(time(NULL));
const Vec vec = getVec(17);
return 0;
}
编译：g++ sort.cpp -g -o sort，执行
[cn@sort] ./sort.o
origin: (0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
sort: (8-2)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(0-1)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
......
sort: (15-2)(14-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (15-2)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
sort: (273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
free(): invalid pointer
已放弃 (核心已转储)
最开始存放的元素是：(0-1)(1-2)(2-2)(3-2)(4-2)(5-1)(6-1)(7-2)(8-2)(9-2)(10-1)(11-1)(12-2)(13-1)(14-2)(15-2)(16-2)
调用std::sort 之后，在中间的过程中出现了非法元素：273-0
(273-0)(15-2)(14-2)(12-2)(9-2)(7-2)(4-2)(3-2)(2-2)(1-2)(8-2)(13-1)(11-1)(10-1)(0-1)(6-1)(5-1)
生成了core文件，使用 gdb调试一下
[cn@sort] gdb -c core --se sort.o
Reading symbols from sort.o...
[New LWP 340173]
Core was generated by `./sort.o'.
Program terminated with signal SIGABRT, Aborted.
#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50 ../sysdeps/unix/sysv/linux/raise.c: 没有那个文件或目录.
(gdb) bt
#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1 0x00007fc877d18859 in __GI_abort () at abort.c:79
#2 0x00007fc877d833ee in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7fc877ead285 "%s\n")
at ../sysdeps/posix/libc_fatal.c:155
#3 0x00007fc877d8b47c in malloc_printerr (str=str@entry=0x7fc877eab4ae "free(): invalid pointer") at malloc.c:5347
#4 0x00007fc877d8ccac in _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:4173
#5 0x000055a8ec33cdf8 in __gnu_cxx::new_allocator<std::pair<int, int> >::deallocate (this=0x7ffc51d279e0,
__p=0x55a8edd28000) at /usr/include/c++/9/ext/new_allocator.h:128
#6 0x000055a8ec33c59a in std::allocator_traits<std::allocator<std::pair<int, int> > >::deallocate (__a=...,
__p=0x55a8edd28000, __n=32) at /usr/include/c++/9/bits/alloc_traits.h:470
#7 0x000055a8ec33bc3a in std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::_M_deallocate (
this=0x7ffc51d279e0, __p=0x55a8edd28000, __n=32) at /usr/include/c++/9/bits/stl_vector.h:351
#8 0x000055a8ec33b420 in std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::~_Vector_base (
this=0x7ffc51d279e0, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:332
#9 0x000055a8ec33b475 in std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::~vector (
this=0x7ffc51d279e0, __in_chrg=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:680
#10 0x000055a8ec339c9d in main () at sort.cpp:30
(gdb) f 5
#5 0x000055a8ec33cdf8 in __gnu_cxx::new_allocator<std::pair<int, int> >::deallocate (this=0x7ffc51d279e0,
__p=0x55a8edd28000) at /usr/include/c++/9/ext/new_allocator.h:128
128 ::operator delete(__p);
(gdb) f 4
#4 0x00007fc877d8ccac in _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:4173
4173 malloc.c: 没有那个文件或目录.
(gdb) f 3
#3 0x00007fc877d8b47c in malloc_printerr (str=str@entry=0x7fc877eab4ae "free(): invalid pointer") at malloc.c:5347
5347 in malloc.c
(gdb) f 2
#2 0x00007fc877d833ee in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7fc877ead285 "%s\n")
at ../sysdeps/posix/libc_fatal.c:155
155 ../sysdeps/posix/libc_fatal.c: 没有那个文件或目录.
(gdb) f 1
#1 0x00007fc877d18859 in __GI_abort () at abort.c:79
79 abort.c: 没有那个文件或目录.
最后发现是 delete 的时候宕机-----在 std::sort 排序过程中将 vector 写坏了。
下面再来看看 std::sort 都干了些啥？
std::sort 排序思想
- 当元素的数量超过 _S_threshold(16) 的时候， 采用QuickSort 的方式;
- 为了避免递归调用 __introsort_loop 层数过深，采用 HeapSort 的方式
- __depth_limit 由 std::__lg(__last - __first) * 2 计算而来
- 最后采用 InsertSort 来实现。
// /usr/include/c++/9/bits/stl_algo.h
template <typename _RandomAccessIterator, typename _Compare>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
// ...
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}
template <typename _RandomAccessIterator, typename _Compare>
inline void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
if (__first != __last)
{
// 首先调用__introsort_loop 进行内部排序-快速排序、堆排序，完成局部有序
std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2, __comp);
// 最后调用插入排序-完全有序
std::__final_insertion_sort(__first, __last, __comp);
}
}
// 其中的 std::__lg(__n) 控制分割恶化； 找出 2^k <= n, 如： n=100 时, k=6; n=10,k=3
size lg(size n)
{
size k = 0;
for (k = 0; n > 1; n >>= 1) ++k;
return k;
}
QuickSort
排序思想 ：将待排序的数据元素序列中选取一个数据元素为基准，通过一趟扫描把待排序的元素分成两个部分，一部分元素关键字都小于或等于基准元素关键字，而另一部分元素关键字都大于或等于基准元素关键字。对各部分数据再进行不断的划分，直至整个序列都有序为止
1）选中待排序列中的第一个元素为基准，复制到 r[0],然后将该位置置空。设置两个指针， low-指向第一个数据元素， high-指向最后一个元素
2）从后向前扫描，若 r[high] 大于或等于基准关键字，则 high 向前移动一个位置。直到 r[high] 小于基准关键字，此时 r[high] 与 r[low0] 交换
3）从前向后扫描，若 r[low] 小于或等于基准关键字，则 low 向后移动一个位置。直到 r[low ] 大于于基准关键字，此时 r[low] 与 r[high] 交换
4）一直重复 2）和 3），直到 low == high 时，令 r[low] = [0], 以 r[low] 为基准将待排序划分为前后两个序列
5）重复 2）3）4），通过不断的划分，一直到各部分只有一个数据。整个序列排序完成
quick_sort.png
空间复杂度：最好- O(log2N), 最坏- O(N)
时间复杂度：平均复杂度- O(NLog2N) O(n²)
稳定性： 不稳定
-
__introsort_loop
/// This is a helper function for the sort routine. template <typename _RandomAccessIterator, typename _Size, typename _Compare> void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp) { while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) { // 快速排序深度达到限制后，为了避免递归层数过深，进行堆排序 std::__partial_sort(__first, __last, __last, __comp); return; } --__depth_limit; // 寻找分割点，在右侧进行递归，后进行左侧递归 _RandomAccessIterator __cut = std::__unguarded_partition_pivot(__first, __last, __comp); std::__introsort_loop(__cut, __last, __depth_limit, __comp); __last = __cut; } } /// This is a helper function... template <typename _RandomAccessIterator, typename _Compare> inline _RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // 先找到中间位置，然后取三个位置的中值赋给__first _RandomAccessIterator __mid = __first + (__last - __first) / 2; // 然后取三个位置的中值赋给__first std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, __comp); // 对 __first, __last 进行分割，并返回分割点__cut, 使 [__first, __cut] 中间的元素不大于pivot, [__cut, last] 中间的元素不小于__cut return std::__unguarded_partition(__first + 1, __last, __first, __comp); } /// Swaps the median value of *__a, *__b and *__c under __comp to *__result template <typename _Iterator, typename _Compare> void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp) { // 此函数希望在 a, b, c 三个数中找到一个中值，并放在result中 if (__comp(__a, __b)) { if (__comp(__b, __c)) std::iter_swap(__result, __b); // a < b < c else if (__comp(__a, __c)) std::iter_swap(__result, __c); // a < c < b else std::iter_swap(__result, __a); // c < a < b } else if (__comp(__a, __c)) std::iter_swap(__result, __a); // b <= a < c else if (__comp(__b, __c)) std::iter_swap(__result, __c); // b <= c <= a else std::iter_swap(__result, __b); // c <= b <= a } /// This is a helper function... template <typename _RandomAccessIterator, typename _Compare> _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp) { // 对 __first, __last 进行分割，并返回分割点__cut, 使 [__first, __cut] 中间的元素不大于pivot, [__cut, last] 中间的元素不小于__cut while (true) { while (__comp(__first, __pivot)) // __first < __pivot 当 __first >= __pivot 跳出循环 ++__first; --__last; while (__comp(__pivot, __last)) // __pivot < __last 当 __pivot >= __last 跳出循环 --__last; if (!(__first < __last)) // __first >= __last 表示 first 和 last 相遇了，结束循环 return __first; // 返回分割点的位置 std::iter_swap(__first, __last); // 不满足分割要求，交换大小值， 此时：__first >= __pivot >= __last ++__first; } }
__unguarded 前缀的函数表示 函数没有越界检测
HeapSort
建堆过程--大顶堆
-
将待排序的数据构成一课完全二叉树，从最后一个非叶子节点 N/2 开始，检查该节点是否满足大顶堆要求
- r[i] 的关键字是否大于等于其左右孩子的关键字的值，若不满足，则将 r[i] 与 r[2i] 、 r[2i+1] 中的较大者交换
采用以上方式继续调整其他非叶子节点。如果与 r[i] 交换的时非叶子节点，交换后可能不符合堆的定义，还需要对与 r[i]交换的孩子节点继续调整，使得该节点为根的完全二叉树仍然满足大顶堆的要求
继续重复以上步骤，直到对根节点调整完成
heapSort.gif
堆排序
- 将堆顶元素 r[1] 与最后一个节点 r[n] 交换
- 输出该叶子节点对应的数据元素并使其离堆
- 将序列按找建堆的方法调整为大顶堆
- 重复以上步骤，直到所有数元素有序输出
时间复杂度：平均时间复杂度 O(nLog2N)
空间复杂度：O(1) 仅仅需要提供一个供交换的辅助存储空间
稳定性： 不稳定
__partial_sort
template <typename _RandomAccessIterator, typename _Compare>
inline void __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
{
// 建堆
std::__heap_select(__first, __middle, __last, __comp);
// 排序
std::__sort_heap(__first, __middle, __comp);
}
/// This is a helper function for the sort routines.
template <typename _RandomAccessIterator, typename _Compare>
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
{
std::__make_heap(__first, __middle, __comp);
for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
if (__comp(__i, __first))
std::__pop_heap(__first, __middle, __i, __comp);
}
InsertSort
插入排序基本思路：将待排序的数据元素插入到已经排好的有序表中，得到一个新的有序表
1）将第1个数据元素看作一个已排好的有序表
2）将第 i (2 <= i <=n) 个数据元素关键字 Ki 一次与前面数据元素的关键字进行比较，将所有关键字大与 Ki 的数据元素一次后移一个位置，直到某个数据元素 Kj 的关键字小于或等于Ki，然后将第i个数据元素插入到关键 Kj 元素后面，完成第 i 个数据元素的插入
3）经过n - 1 次插入操作后，所有元素数据构成一个关键字有序的序列
insertionSort.gif
空间复杂度：O（1）
时间复杂度 O(n^2)
稳定性：稳定
__final_insertion_sort
/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
// 数据量超过 _S_threshold(16)
if (__last - __first > int(_S_threshold))
{
std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp);
}
else // 数据量小采用插入排序
std::__insertion_sort(__first, __last, __comp);
}
/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
if (__first == __last)
return;
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
if (__comp(__i, __first))
{ // 如果 *i < *first, 则将 [first, i] 区间的元素向后一定一个位置，然后将 i 位置的元素移动到first
typename iterator_traits<_RandomAccessIterator>::value_type __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);
}
else
{
// 如果 *i >= *first 则需要在(first, i) 区间找合适的位置插入
std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
}
}
}
/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
inline void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, __gnu_cxx::__ops::__val_comp_iter(__comp));
}
/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
typename iterator_traits<_RandomAccessIterator>::value_type __val = _GLIBCXX_MOVE(*__last);
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, __next))
{
*__last = _GLIBCXX_MOVE(*__next); // 将当前位置的数值后移一位， 然后next 一直前移
__last = __next;
--__next;
}
*__last = _GLIBCXX_MOVE(__val); // 此时所有的元素均已经完成了前移，此时的 last 就是合适的位置
}
不稳定性
struct Entry
{
Entry(uint32_t id) : user_id(id) {}
uint32_t user_id = 0;
uint32_t score = 0;
};
bool cmp(const Entry& lhs, const Entry& rhs)
{
return lhs.score > rhs.score;
}
void print_ele(const std::vector<Entry>& vec)
{
std::stringstream oss;
for (const auto& item : vec)
{
oss << "(" << item.user_id << "-" << item.score << ")";
}
std::cout << "element: " << oss.str() << std::endl;
}
int main()
{
std::vector<Entry> vec;
for (uint32_t idx = 0; idx < 20; idx++)
{
Entry entry(idx);
entry.score = 1000;
vec.emplace_back(std::move(entry));
}
vec[5].score = 111111;
vec[6].score = 111111;
print_ele(vec);
std::sort(vec.begin(), vec.end(), cmp);
print_ele(vec);
std::sort(vec.begin(), vec.end(), cmp);
print_ele(vec);
return 0;
}
/*
[cn@build] ./sort/sort
element: (0-1000)(1-1000)(2-1000)(3-1000)(4-1000)(5-111111)(6-111111)(7-1000)(8-1000)(9-1000)(10-1000)(11-1000)(12-1000)(13-1000)(14-1000)(15-1000)(16-1000)(17-1000)(18-1000)(19-1000)
element: (5-111111)(6-111111)(10-1000)(19-1000)(18-1000)(17-1000)(16-1000)(15-1000)(14-1000)(13-1000)(12-1000)(11-1000)(0-1000)(9-1000)(8-1000)(7-1000)(4-1000)(3-1000)(2-1000)(1-1000)
element: (6-111111)(5-111111)(1-1000)(2-1000)(3-1000)(4-1000)(7-1000)(8-1000)(9-1000)(0-1000)(11-1000)(12-1000)(13-1000)(14-1000)(15-1000)(16-1000)(17-1000)(18-1000)(19-1000)(10-1000)
*/
解决方案
// 将排序准则优化
bool cmp(const Entry& lhs, const Entry& rhs)
{
if (lhs.score != rhs.score)
return lhs.score > rhs.score;
return lhs.user_id < rhs.user_id;
}
排序准则
---摘自《C++标准库》7.7
- 1、必须是非对称的
对operator < 而言，如果 x < y 为true，那么 y < x 为false;
对判断式(predicate) op() 而言, 如果op(x, y) 为true， 那么op(y, x) 为false。
- 2、必须是可传递性的
对operator < 而言，如果 x < y 为true 且 y < z 为true， 那么 x < z 为true
对判断式(predicate) op() 而言, 如果op(x, y) 为true 且 op(y, z) 为true， 那么 op(x, z) 为true
- 3、必须自反的
对operator < 而言，x < x 永远为false;
对判断式(predicate) op() 而言, op(x, x) 永远为false。
- 4、必须有等效传递性
如果 a 等于 b 且 b 等于 c，那么a必然等于 c
对操作符 <, 若 !(a < b) && !(b < a)为true且 !(b < c) && !(c < b) 为true，那么!(a < c) && !(a < b) 也为true
对于判断是 op(), 如果op(a,b)、op(b,a)、op(b,c)和op(c,b) 都为false， 那么op(a,c)、op(c,a)也为false
这就意味着：必须区分less 和equal， 一个像operator <= 这样的准则并不满足条件
