stable_sort自定義比較函式踩坑（粗淺理解）-有解無憂

1. 概述 “好記性不如爛筆頭”，本篇文章是“遇到的疑難雜癥”的首篇，本文主要介紹了今天作業中遇到的STL stable_sort演算法自定義比較函式的問題，只是粗淺的介紹，具體的解釋待學習好STL原始碼后再解釋（對STL這個大寶藏只是停留在使用的層次，而且還沒用好）， 2. 問題描述 作業中遇到一個bug，大概的情況可以用如下的代碼表示：

我的需求是輸入兩個Student物件，根據Student的num進行升序排序，輸出結果是排序后首個Student物件的id值，如代碼所示，采用lambda函式實作了比較規則，各位看下是不是沒有什么問題？其實問題很大： 1.printStuId(stu1, stu2)函式的輸出居然是"2, 1" 2.stus.at(0).id的結果居然是2 這是什么鬼，完全沒有邏輯，當場裂開，哈哈哈，問題1是沒問題的，只不過我不知道而已，問題2的代碼跑了兩年都沒問題，奇了怪，一臉無奈， 3. 問題解決 3.1 問題1的解決 閱讀了STL stable_sort的原始碼，它給出的解釋如下： "Sorts the elements in the range @p [__first,__last) in ascending order, such that for each iterator @p i in the range @p [__first,__last-1), @p __comp(*(i+1),*i) is false." 大家看懂了吧，是不是和自己之前的理解不同呢？我自己的理解一直是" __comp(*i, *(i+1)) is true"，請原諒我的無知，C++的設計總是有些與正常思維不一致，但肯定有它的原因，待我研究好了再解釋， 3.2 問題2的解決 問題2的代碼跑了兩年都沒問題，為什么突然就出問題了，是因為出現了兩個Student物件num相等的場景，即比較規則出現了相等，通過查資料（參考文獻1、2和3），解釋如下： "Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. 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." 里面提到了"Strict Weak Ordering"的概念，它要求必須滿足以下的條件： 1.反自反性：即comp(x, x)必須是false 2.非對稱性：即若comp(x, y)和comp(y, x)，其結果必然相反 3.可傳遞性：即若comp(x, y)為true, comp(y, z)為true，那么comp(x, z)必然為true 上述代碼的自定義comp違反了1/2兩條，所以stable_sort使用出現了問題，另外根據問題1中的解釋，也可以得出Student物件的順序變了，但是我使用的是stable_sort排序，對于相等的元素相對位置應該不變才對，導致我一度很懵，解決辦法就是將"return stu1.num <= stu2.num;"修改為"return stu1.num < stu2.num;"， 4. 總結 STL函式提供的comp函式都要滿足Strict Weak Ordering，從中可見理解基本概念是多么地重要，“不僅要知其然，還要知其所以然”，下一步繼續研究下資料結構與演算法和STL原始碼了，Stay hungry, stay foolish! 5. 參考文獻 1.cplusplus, https://www.cplusplus.com/reference/algorithm/stable_sort/ 2.《Effective STL》條款21: 永遠讓比較函式對相等的值回傳false 3.SGI-STL, http://www.sgi.com/tech/stl/StrictWeakOrdering.html 歡迎大家批評指正、評論和轉載（請注明源出處），謝謝！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295917.html

標籤：C++

上一篇：Easylogging++的使用及擴展

下一篇：C++類結構體與json相互轉換