概述

• std::sort 是不穩(wěn)定的排序。在使用的時候，需要嚴格遵守排序準則，否則會導致異常產生。

問題描述

• 外網玩家發(fā)來bug：某天晚上，一個排行榜發(fā)生第一名A和第二名B，在數據為發(fā)生變化的情況下，會不停的交替更換。

• 經查，該排行榜的排序規(guī)則functor 是

  bool compare_function(const std::shared_ptr<Data> lhs, const std::shared_ptr<Data> rhs)
  {
      if (lhs->detail->socre != rhs->detail->socre)
          return lhs->detail->socre > rhs->detail->socre;
      return lhs->detail->update_time < rhs->detail->update_time;
  }
  
  std::vector<std::shared_ptr<Data>> vec;
  std::sort(vec.begin(), vec.end(),compare_function);
  

  也就是說，比較的時候有兩個比較順序，先比較score, 而后比較 update_time(當時時間戳：秒)。
  湊巧的是，外網日志顯示，第一名和第二名的不僅 score 相等，而且 update_time 也相等。

  需要比較的兩個key都相等。這個地方會不會是導致問題的根源？

排序準則

---摘自《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

這就意味著：必須區(qū)分less 和equal， 一個像operator <= 這樣的準則并不滿足條件

根據排序準則，發(fā)現 compare_function 確實有問題

驗證問題

下面寫一個類似的代碼來驗證問題。

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)

描述：
    - 第一行是原始打印
    - 第二行是第一次排序后的打印
    - 第三行是第二次排序后的打印
發(fā)現兩次排序打印的結果居然不一樣, 且相同數值score的元素位置大相徑庭。Why？

std::sort 排序原理

具體排序規(guī)則詳見-《STL源碼剖析》 6.7.9
對于STL的sort算法，數據量大的時候，采用QuickSort, 分段遞歸排序。
一旦分段后的數據量小于某個門檻，為避免QuickSort 的遞歸調用帶來過大的額外負荷(overhead)，就改用InsertionSort。 
如果遞歸層次過深。還會改用HeapSort。

- QuickSort 快速排序 -- 不穩(wěn)定
    + 算法描述，假設S代表將被處理的序列
        1）如果S的元素個數為0或1，結束
        2）取S中的任何一個元素，作為樞軸(pivot)v
        3）將S分割為L,R兩段，使L內的每個元素均小于或等于v；使R段內的每一個元素大于或等于v
        4）對L、R遞歸執(zhí)行QuickSort

- InsertionSort 插入排序-- 穩(wěn)定

- HeapSort 堆排序-- 不穩(wěn)定

穩(wěn)定：      如果a原本在b前面，而a=b，排序之后a仍然在b的前面
不穩(wěn)定：    如果a原本在b的前面，而a=b，排序之后a可能會出現在b的后面

解決問題

只需要優(yōu)化排序準則即可：

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

總結

由于std::sort 內部調用了 QuickSort 和 HeapSort 造成排序是不穩(wěn)定的，所以導致對相同元素序列調用 std::sort 導致排行榜會發(fā)生變化。因此在使用排序的時候，必須遵守排序準則，避免產生意外的bug。