进行std::sort的元素为什么要保证严格弱序?

  这个问题是面试腾讯光子的时候面试官提的,当时的问题是:sort自定义comp函数能用>=吗?当时的我想comp函数只要函数签名是对的应该就没问题吧,于是答了可以。面试结束后总感觉哪里不对,耿耿于怀,几番搜寻也只找到说要保证严格弱序,原理网上基本却没有。只能求助于源码了,打开<<STL源码剖析>>,看了一遍sort的实现,还是没能找出问题所在(这里要给自己提个醒,思考得不够)。我不服,又在网上搜索了一遍结合源码,终于找到了答案。

  首先补充一下满足严格弱序的3个条件:

    1.两个关键字不能同时严格弱序于对方。

    2.如果a严格弱序于b,且b严格弱序于c,则a必须严格弱序于c。

    3.如果存在两个关键字,任何一个都不严格弱序于另一个,则这两个关键字是相等的。

  sort采用的排序算法是IntroSort,是一种混合型算法。简单来说就是利用快排将要排序的数组分隔成大致有序的几段,  根据递归深度和分隔开的小段长度情况看是否采取堆排序,最后再进行插入排序。这样的话能在最坏情况下将时间复杂度推进到O(nlogn)。在SGISTL实现的插入排序是这么写的:

 1 void __unguarded_linear_insert(RandomAccessIterator last, T value)
 2 {
 3     RandomAccessIterator next = last;
 4     --next;
 5     while(value < *next)
 6     {
 7          *last = *next;
 8          last = next;
 9          --next;
10     }
11     *last = value;
12 }

  将注意力放在第5行的while循环上,你会发现这里并没有判断边界,原因是stl以严格弱序为前提且在进入这个函数前会保证有哨兵在数组的前方。(这里代码是直接使用的小于,使用自定义comp的时候将while里的<判断换成comp理解就可以了。)

  那么如果我们元素不严格弱序的话,在全是相等元素的情况下,这个while会无限循环下去,最终造成数组越界!

  其实不止在插入排序这块,在快速排序进行分割的时候也会出现类似的问题,这里就不再多说了。

原文地址:https://www.cnblogs.com/RookieSuperman/p/12375563.html