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

stable_sort自定义比较函数踩坑(粗浅理解)

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

相关文章: