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
欢迎大家批评指正、评论和转载（请注明源出处），谢谢！