sort函數(shù)奇遇記
1.問題簡述
??最近在用C++的sort函數(shù)排序vector元素時，遇到一個錯誤养匈，特地在此記錄一下秋度。我將當(dāng)時出錯的代碼抽象一下，類似于下面這種形式惯疙。
int main() {
vector<int> nums = { 5,8,5,6,4,7,56,8 };
sort(nums.begin(), nums.end(), [](int a, int b) {
return a <= b; });
return 0;
}
??這段代碼看似沒任何問題翠勉，但是會遭遇到嚴(yán)重的運行時錯誤，通過測試發(fā)現(xiàn)霉颠，只有當(dāng)比較函數(shù)為<=对碌，且nums數(shù)組中存在重復(fù)元素時才會錯誤。而修改也比較簡單蒿偎，將lambda函數(shù)里面的<= 改為 < 即可朽们。
2.問題剖析
??為了進(jìn)一步弄清楚產(chǎn)生這個現(xiàn)象的原因，我查看了Cplusplus
上sort函數(shù)中comp參數(shù)的介紹诉位，如下所示：
Binary function that accepts two elements in the range as arguments, and returns a value convertible to . The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
??由其定義可知comp參數(shù)必須基于一種定義的嚴(yán)格弱序來判斷第一個參數(shù)是否在第二個參數(shù)之前骑脱。那么什么是嚴(yán)格弱序呢？其實嚴(yán)格弱序就是兩個的對象（比如a和b）的一種關(guān)系苍糠，該關(guān)系必須滿足以下特性（我們定義嚴(yán)格弱序關(guān)系的符號為叁丧，例如
，即為
嚴(yán)格弱序于
）：
- 互斥性椿息，如果
歹袁，那么
一定為假；
- 傳遞性寝优，如果
，那么一定有
;
- 如果
都不成立孟抗，那么 a 一定等于 b；
??其實钻心，這里我們也能猜出凄硼，sort函數(shù)的comp參數(shù)，其實是定義一個判斷參數(shù)a和參數(shù)b是否嚴(yán)格弱序的布爾函數(shù)捷沸，如果是嚴(yán)格弱序則返回true摊沉，否則返回false；
??回到我們那段出錯的代碼痒给，我們可以看一下lambda函數(shù)是否符號嚴(yán)格弱序的定義说墨。我們可以發(fā)現(xiàn)骏全，當(dāng)a==b時，a<=b 和 b<= a都成立尼斧，即同時成立，這違反了互斥性原則棺棵，因此函數(shù)會參數(shù)運行時錯誤楼咳。弄清楚了原因，修改起來也十分簡單烛恤，而且以后在寫相關(guān)的sort函數(shù)的comp參數(shù)時一定要注意這一點母怜。
3.總結(jié)
- 有時候用了很久沒出問題的函數(shù)，不一定代表你真的熟悉了他棒动，其實你有可能還是理解錯了糙申，只是并沒有遇到能讓你出錯的應(yīng)用場景，而一旦出錯后果將不堪設(shè)想船惨。每一次看似成功的運行柜裸，都加強(qiáng)了自己對其盲目的自信，進(jìn)而加大了以后遇到意外狀況的debug難度和隱患粱锐。
- (https://www.cplusplus.com)是一個寶庫疙挺。
