前言

看到這個(gè)標(biāo)題應(yīng)該會(huì)有很多人一下子就懂了,，也會(huì)有些人感到迷惑，簡(jiǎn)簡(jiǎn)單單排序怎么會(huì)奔潰呢,？我第一次接觸這個(gè)問題還是很久以前剛剛參加工作的時(shí)候,，當(dāng)時(shí)也是寫出了導(dǎo)致程序崩潰的代碼，通過上網(wǎng)查詢解決了問題,，至此以后就對(duì)這個(gè) sort 函數(shù)警惕了一些,，一直記得就是在sort的自定義函數(shù)中判斷條件不要加等號(hào)，至于本質(zhì)的原因一直沒有去探究,，正好最近又改了一個(gè)相關(guān)的問題,，所以決定從源碼和定義的角度來看看為什么會(huì)出現(xiàn)這個(gè)問題。

sort的使用

sort函數(shù)真的挺好用,，比如像下面這樣：

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> values{3, 5, 4, 4, 5, 1};
    std::sort(values.begin(), values.end());

    for (auto v : values) std::cout << v << std::endl;

    return 0;
}

只是 std::sort(values.begin(), values.end()); 這樣簡(jiǎn)簡(jiǎn)單單的一句就完成了vector數(shù)據(jù)從小到達(dá)的排序,，運(yùn)行結(jié)果如下：

albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11
albert@home-pc:/data/cpp$ ./a.out
1
3
4
4
5
5

自定義比較函數(shù)

上面舉的例子是從小到大排序,，這是 sort 函數(shù)的默認(rèn)行為，所以不需要額外的參數(shù),，如果是想從大到小排序,，那么就需要定義一個(gè)比較函數(shù)了，方法也比較簡(jiǎn)單,，寫一個(gè)lambda表達(dá)式就可以了,，比如像下面這樣：

int main()
{
    std::vector<int> values{3, 5, 4, 4, 5, 1};
    std::sort(values.begin(), values.end(), [](int v1, int v2){
        return v1 >= v2;
    });

    for (auto v : values) std::cout << v << std::endl;

    return 0;
}

按照比較函數(shù)定義，我們把數(shù)據(jù)按照前面大于等于后面的方式排序就完成了從大到小的排序的要求,，看看這樣寫有沒有什么問題,？如果這里的等號(hào) = 已經(jīng)引起了你的不適，說明你可能踩過這里的坑,，是的,，這樣寫容易造成崩潰，我們來運(yùn)行一下,。

albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11
albert@home-pc:/data/cpp$ ./a.out
5
5
4
4
3
1

咦,？怎么沒事，我之前用MSVC測(cè)試還會(huì)崩潰的,，難道和編譯器有關(guān),？

當(dāng)我們?cè)龃髷?shù)據(jù)量

std::vector<int> values{3,5,4,4,1,5,4,5,4,5,4,5,4,5,4,5,4,4,5,4,4,4,5,4,5,5,4,5,4,4,5,4,5,4,5,5,5};

// 運(yùn)行結(jié)果如下


albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11 -g
albert@home-pc:/data/cpp$ ./a.out
0
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
1
*** Error in `./a.out': double free or corruption (out): 0x0000000002016c20 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777f5)[0x7ff5ffef77f5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8038a)[0x7ff5fff0038a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7ff5fff0458c]
./a.out[0x4024e2]
./a.out[0x4023ab]
./a.out[0x402226]
./a.out[0x4020a1]
./a.out[0x401edb]
./a.out[0x400c67]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7ff5ffea0840]
./a.out[0x400a39]
======= Memory map: ========
00400000-00403000 r-xp 00000000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
00403000-00404000 r-xp 00003000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
00603000-00604000 r--p 00003000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
00604000-00605000 rw-p 00004000 00:00 212044                     /mnt/d/data/cpp/testsort/a.out
02005000-02037000 rw-p 00000000 00:00 0                          [heap]
7ff5f8000000-7ff5f8021000 rw-p 00000000 00:00 0
7ff5f8021000-7ff5fc000000 ---p 00000000 00:00 0
7ff5ffb70000-7ff5ffc78000 r-xp 00000000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7ff5ffc78000-7ff5ffc7a000 ---p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7ff5ffc7a000-7ff5ffe77000 ---p 0010a000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7ff5ffe77000-7ff5ffe78000 r--p 00107000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7ff5ffe78000-7ff5ffe79000 rw-p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7ff5ffe80000-7ff600040000 r-xp 00000000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7ff600040000-7ff600049000 ---p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7ff600049000-7ff600240000 ---p 001c9000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7ff600240000-7ff600244000 r--p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7ff600244000-7ff600246000 rw-p 001c4000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7ff600246000-7ff60024a000 rw-p 00000000 00:00 0
7ff600250000-7ff600266000 r-xp 00000000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
7ff600266000-7ff600465000 ---p 00016000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
7ff600465000-7ff600466000 rw-p 00015000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
7ff600470000-7ff6005e2000 r-xp 00000000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7ff6005e2000-7ff6005ef000 ---p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7ff6005ef000-7ff6007e2000 ---p 0017f000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7ff6007e2000-7ff6007ec000 r--p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7ff6007ec000-7ff6007ee000 rw-p 0017c000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7ff6007ee000-7ff6007f2000 rw-p 00000000 00:00 0
7ff600800000-7ff600825000 r-xp 00000000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7ff600825000-7ff600826000 r-xp 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7ff600a25000-7ff600a26000 r--p 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7ff600a26000-7ff600a27000 rw-p 00026000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7ff600a27000-7ff600a28000 rw-p 00000000 00:00 0
7ff600b70000-7ff600b71000 rw-p 00000000 00:00 0
7ff600b80000-7ff600b82000 rw-p 00000000 00:00 0
7ff600b90000-7ff600b91000 rw-p 00000000 00:00 0
7ff600ba0000-7ff600ba1000 rw-p 00000000 00:00 0
7ff600bb0000-7ff600bb1000 rw-p 00000000 00:00 0
7ff600bc0000-7ff600bc1000 rw-p 00000000 00:00 0
7fffc026e000-7fffc0a6e000 rw-p 00000000 00:00 0                  [stack]
7fffc10b8000-7fffc10b9000 r-xp 00000000 00:00 0                  [vdso]
Aborted (core dumped)

這次終于崩潰了，但顯示確實(shí)內(nèi)存越界問題,，并且排序后第一個(gè)元素是0,，這不是我們vector中的元素啊，看來肯定是出問題了

反復(fù)嘗試幾次又找到一個(gè)測(cè)試用例：

std::vector<int>values{3,5,4,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5,1,4,5};

運(yùn)行之后直接得到了 Segmentation fault (core dumped) 錯(cuò)誤,，沒錯(cuò),，這就是我想要的,，來從 sort 源碼中看看為什么加了 = 就會(huì)出現(xiàn)崩潰

sort源碼崩潰分析

sort 函數(shù)的源碼還不算太長(zhǎng),，我就一點(diǎn)點(diǎn)來看了

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
        typename iterator_traits<_RandomAccessIterator>::value_type,
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));

這算是個(gè)入口函數(shù)，做了一些類型檢查,，然后就調(diào)用了內(nèi)部的 std::__sort 函數(shù)

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
       _Compare __comp)
    {
      if (__first != __last)
      {
        std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2,
                __comp);
        std::__final_insertion_sort(__first, __last, __comp);
      }
    }

當(dāng)排序范圍不為空時(shí),，函數(shù)會(huì)對(duì)傳入的范圍進(jìn)行排序，為了最大程度的提高效率,，結(jié)合了快排,、堆排和插入排序等多種排序方法，分為 std::__introsort_loop 和 std::__final_insertion_sort 兩個(gè)階段,。

第一階段使用“快排+堆排”的方法,，當(dāng)元素個(gè)數(shù)小于等于 _S_threshold（enum { _S_threshold = 16 }）時(shí)，不做處理,，交給第二階段來做,，對(duì)于元素個(gè)數(shù)大于_S_threshold的序列,，執(zhí)行快排，當(dāng)快排的遞歸深入到一定深度 __depth_limit（通過元素個(gè)數(shù)計(jì)算出來的）時(shí),，不再遞歸深入,，對(duì)待排序元素執(zhí)行堆排序，代碼如下：

  /// 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;
      }
    }

第二階段使用“插入排序”,，當(dāng)元素個(gè)數(shù)小于等于 _S_threshold（enum { _S_threshold = 16 }）時(shí),，執(zhí)行普通的插入排序，當(dāng)大于 _S_threshold 時(shí),，執(zhí)行兩次的“插入”排序操作,，首先使用普通的插入排序來排 [first, _S_threshold) 這個(gè)范圍的元素，然后使用無保護(hù)的插入排序,，完成 [_S_threshold, last) 這個(gè)范圍的排序,。

  template<typename _RandomAccessIterator, typename _Compare>
    void
    __final_insertion_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __last, _Compare __comp)
    {
      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);
    }

其中的普通插入排序沒有什么特別的地方，就是遍歷前邊小于等于_S_threshold個(gè)元素進(jìn)行普通的插入排序,，而后面這個(gè)無保護(hù)的插入排序 std::__unguarded_insertion_sort 往往就是出現(xiàn)問題的地方,，代碼如下：

  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));
    }

  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);
        __last = __next;
        --__next;
      }
      *__last = _GLIBCXX_MOVE(__val);
    }

這段代碼看 __unguarded_insertion_sort 還沒有什么問題，但是 __unguarded_linear_insert 中的邏輯就比較迷幻了,，只有當(dāng) __comp(__val, __next) 的值為false時(shí)才會(huì)停止,。

其中 __comp 就是我們之前自定義的lambda表達(dá)式，我們當(dāng)時(shí)寫的是 return v1 >= v2;,，翻譯過來也就是當(dāng)!(val >= __next) 時(shí),，即后一個(gè)元素小于前一個(gè)元素的時(shí)候停止，那么為什么會(huì)出問題呢,？

我們知道前_S_threshold個(gè)元素我們之前已經(jīng)按照從大到小排好序了,，那么按道理遍歷到這個(gè)區(qū)域就會(huì)找到后一個(gè)元素小于前一個(gè)元素的情況，也就是插入排序遍歷到這就會(huì)停止,，等等,！好像有什么不對(duì)勁，如果這里的元素都相等就找不到停止的情況了,，這就會(huì)造成訪問的越界,，這就是程序崩潰的本質(zhì)原因了。

那么去掉等號(hào)會(huì)是個(gè)什么情況呢,？運(yùn)行到這里就是要找到滿足條件的 !(val > __next)元素時(shí)停止,，也就是找到后一個(gè)元素小于等于前一個(gè)元素的時(shí)候停止，因?yàn)榍?code>_S_threshold個(gè)元素已經(jīng)排好序,，這個(gè)條件是肯定滿足的,，所以不會(huì)出現(xiàn)越界情況，這就是為什么自定義比較函數(shù)中,，兩個(gè)元素相等時(shí)一定要返回false了,。

為什么使用無保護(hù)的插入排序

既然這里這么容易越界,，為什么不判斷一下邊界條件來防止越界，而是用這種無保護(hù)的插入排序呢,？

這里使用無保護(hù)的插入排序原因很簡(jiǎn)單,，就是為了提升效率，因?yàn)槭÷缘粼浇绲臋z查,，少了很多次的比較操作,，效率肯定有了提升，它的前提是左邊必須有已經(jīng)排好序的元素,，所以在函數(shù) __unguarded_insertion_sort 函數(shù)之前先調(diào)用 __insertion_sort 來完成了[0, _S_threshold) 這個(gè)范圍的元素排序,，便是為了后面這個(gè)無保護(hù)插入排序的使用。

C++標(biāo)準(zhǔn)要求

說到這里sort函數(shù)的自定義比較函數(shù)還是太容易出錯(cuò)了,，有沒有什么實(shí)現(xiàn)標(biāo)準(zhǔn)呢,？其實(shí)標(biāo)準(zhǔn)中對(duì)這個(gè)比較函數(shù)的要求寫的很詳細(xì)，具體可以參考 Compare的實(shí)現(xiàn)要求,。

Compare 是一些標(biāo)準(zhǔn)庫函數(shù)針對(duì)用戶提供的函數(shù)對(duì)象類型所期待的一組要求,，其實(shí)就是要滿足嚴(yán)格若排序關(guān)系，翻譯成人話就是自定義的比較函數(shù) comp 需要下面三條要求：

1. 對(duì)于任意元素a,，需滿足 comp(a, a) == false
2. 對(duì)于任意兩個(gè)元素a和b,，若 comp(a, b)==true 則要滿足 comp(b, a)==false
3. 對(duì)于任意三個(gè)元素a、b和c,，若 comp(a, b)==true 且 comp(b, c)==true 則需要滿足 comp(a, c)==true

從這條規(guī)則也能看出我們之前定義的問題：

    std::sort(values.begin(), values.end(), [](int v1, int v2){
        return v1 >= v2;
    });

這個(gè)自定義的比較函數(shù),，當(dāng) v1 和 v2 相等時(shí)，comp(v1, v2)==true,， 但是 comp(v2, v1)的值也是 true,，當(dāng)我們把代碼中的等號(hào) = 去掉以后，也就滿足了條件2,，另外在復(fù)雜的比價(jià)邏輯中,，條件3的傳遞性問題也是需要注意的問題。

構(gòu)造一個(gè)崩潰的示例

理解了前面崩潰的原因,，我們就不需要猜了,，可以直接構(gòu)造一個(gè)百分之百奔潰的測(cè)試用例，因?yàn)榍?6（_S_threshold）個(gè)元素會(huì)使用正常的插入排序,，后面的元素才會(huì)使用無保護(hù)的插入排序，我們其實(shí)構(gòu)造一個(gè)17個(gè)相同元素的vector就可以了,，下面我們來試一下：

int main()
{
    std::vector<int> values{6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6};
    std::sort(values.begin(), values.end(), [](int v1, int v2){
        return v1 >= v2;
    });

    for (auto v : values) std::cout << v << std::endl;

    return 0;
}

運(yùn)行結(jié)果如下：

albert@home-pc:/data/cpp$ g++ testsort.cpp --std=c++11 -g
albert@home-pc:/data/cpp$ ./a.out
0
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
*** Error in `./a.out': double free or corruption (out): 0x0000000001fd9c20 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777f5)[0x7feaf8ef77f5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8038a)[0x7feaf8f0038a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7feaf8f0458c]
./a.out[0x402446]
./a.out[0x40230f]
./a.out[0x40218a]
./a.out[0x402005]
./a.out[0x401e65]
./a.out[0x400bf1]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7feaf8ea0840]
./a.out[0x4009e9]
======= Memory map: ========
00400000-00403000 r-xp 00000000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
00403000-00404000 r-xp 00003000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
00603000-00604000 r--p 00003000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
00604000-00605000 rw-p 00004000 00:00 211636                     /mnt/d/data/cpp/testsort/a.out
01fc8000-01ffa000 rw-p 00000000 00:00 0                          [heap]
7feaf4000000-7feaf4021000 rw-p 00000000 00:00 0
7feaf4021000-7feaf8000000 ---p 00000000 00:00 0
7feaf8b70000-7feaf8c78000 r-xp 00000000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7feaf8c78000-7feaf8c7a000 ---p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7feaf8c7a000-7feaf8e77000 ---p 0010a000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7feaf8e77000-7feaf8e78000 r--p 00107000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7feaf8e78000-7feaf8e79000 rw-p 00108000 00:00 243923             /lib/x86_64-linux-gnu/libm-2.23.so
7feaf8e80000-7feaf9040000 r-xp 00000000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7feaf9040000-7feaf9049000 ---p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7feaf9049000-7feaf9240000 ---p 001c9000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7feaf9240000-7feaf9244000 r--p 001c0000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7feaf9244000-7feaf9246000 rw-p 001c4000 00:00 243912             /lib/x86_64-linux-gnu/libc-2.23.so
7feaf9246000-7feaf924a000 rw-p 00000000 00:00 0
7feaf9250000-7feaf9266000 r-xp 00000000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
7feaf9266000-7feaf9465000 ---p 00016000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
7feaf9465000-7feaf9466000 rw-p 00015000 00:00 180347             /lib/x86_64-linux-gnu/libgcc_s.so.1
7feaf9470000-7feaf95e2000 r-xp 00000000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7feaf95e2000-7feaf95ef000 ---p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7feaf95ef000-7feaf97e2000 ---p 0017f000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7feaf97e2000-7feaf97ec000 r--p 00172000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7feaf97ec000-7feaf97ee000 rw-p 0017c000 00:00 189413             /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21
7feaf97ee000-7feaf97f2000 rw-p 00000000 00:00 0
7feaf9800000-7feaf9825000 r-xp 00000000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7feaf9825000-7feaf9826000 r-xp 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7feaf9a25000-7feaf9a26000 r--p 00025000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7feaf9a26000-7feaf9a27000 rw-p 00026000 00:00 243945             /lib/x86_64-linux-gnu/ld-2.23.so
7feaf9a27000-7feaf9a28000 rw-p 00000000 00:00 0
7feaf9bc0000-7feaf9bc1000 rw-p 00000000 00:00 0
7feaf9bd0000-7feaf9bd2000 rw-p 00000000 00:00 0
7feaf9be0000-7feaf9be1000 rw-p 00000000 00:00 0
7feaf9bf0000-7feaf9bf1000 rw-p 00000000 00:00 0
7feaf9c00000-7feaf9c01000 rw-p 00000000 00:00 0
7feaf9c10000-7feaf9c11000 rw-p 00000000 00:00 0
7ffffb85e000-7ffffc05e000 rw-p 00000000 00:00 0                  [stack]
7ffffc61d000-7ffffc61e000 r-xp 00000000 00:00 0                  [vdso]
Aborted (core dumped)

完全符合預(yù)期,，如果再刪除vector中的一個(gè)元素就不會(huì)崩潰了。

平臺(tái)差異

這篇文章的代碼編譯和運(yùn)行都是在Linux下完成的,，但是我之前在Windows上測(cè)試時(shí),，可不需要最少17個(gè)元素的前提,，這是為什么呢？因?yàn)樵谖④涍@一套編譯環(huán)境下,，直接檢測(cè)了Compare中的條件2,，并且是以斷言的方式給出提示的，所以與Linux上的運(yùn)行表現(xiàn)還有一些差異,。

總結(jié)

• 使用 std::sort 函數(shù)自定義比較函數(shù)時(shí),，需要滿足嚴(yán)格弱排序性，若 comp(a, b)==true 則 comp(b, a)==false,，那么在比較函數(shù)中兩個(gè)元素相等的情況要返回false
• 使用 std::sort 函數(shù)出現(xiàn)崩潰是往往是不滿足嚴(yán)格若排序性,，但是在復(fù)雜的比較函數(shù)中也可能不滿足傳遞性
• std::sort 為了把排序效率提高到極致，綜合使用了快排,、堆排,、插入排序等多種排序方法
• std::sort 在不同的平臺(tái)實(shí)現(xiàn)不同，當(dāng)比較函數(shù)不滿足嚴(yán)格若排序時(shí),，gcc環(huán)境下至少有17個(gè)元素才會(huì)崩潰,，而 MSVC 則在Debug時(shí)沒有元素個(gè)數(shù)限制，會(huì)通過斷言直接判斷這個(gè)條件是否滿足

可是啊 總有那風(fēng)吹不散的認(rèn)真 總有大雨也不能抹去的淚痕~