当前位置： 首页>后端>正文

stable_sort自定义比较函数踩坑（粗浅理解）

后端2024-04-27 22:11:29

1. 概述

“好记性不如烂笔头”，本篇文章是“遇到的疑难杂症”的首篇。本文主要介绍了今天工作中遇到的STL stable_sort算法自定义比较函数的问题，只是粗浅的介绍，具体的解释待学习好STL源码后再解释（对STL这个大宝藏只是停留在使用的层次，而且还没用好）。

2. 问题描述

工作中遇到一个bug，大概的情况可以用如下的代码表示：

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

struct Student
{
    int id;
    int num;
};

void printStuId(const Student& stu1, const Student& stu2)
{
    std::cout << stu1.id << ", " << stu2.id << std::endl;
}

int main()
{
    std::vector<Student> stus{{1, 2}, {2, 2}};
    std::stable_sort(stus.begin(), stus.end(),
        [](const Student& stu1, const Student& stu2)
        {
            printStuId(stu1, stu2);
            return stu1.num <= stu2.num;
        }
    );

    std::cout << stus.at(0).id << std::endl;

    return 0;
}

我的需求是输入两个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.xamrdz.com/backend/34z1936643.html

相关文章：