比较函数应该这样写

近期在review开发代码时,发现有这样的一类提交,开发把所有比较函数中的等号都去掉了,类似这样。

聪明的小编开始思考,开发为啥要这样做呢?经过和开发的沟通了解,发现一条小编不清楚的comp函数的“Strict Weak Ordering”原理,如果比较函数编写不得当,那么很有可能会使代码coredump,从而带来严重的质量隐患。

core的原因是什么呢,c++ 标准库 sort() 在对基础类型排序时,直接调用 sort(start,end) 即可,对于非基础类型的结构体,可以通过重载函数提供一个比较函数。sort() 的内部排序使用插入排序和快速排序,当sort函数选择快速排序时,根据快排规则,如果当比较元素相同返回真时,此时比较元素将会继续向下遍历,在极端情况下,例如程序中所有元素都是一样的情况下,就会出现访问越界,结果就是导致程序出现segment fault。

那么什么样的比较函数才是足够安全健壮的呢,已经有一套规则去对比较函数进行约束,

如果一个comp函数要满足“Strict Weak Ordering”,

意味着它应该满足如下特征:(https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings):

(a) 反自反性:也即comp(x, x)必须是false

(b) 非对称性:也即如果comp(x, y)和comp(y, x)的结果必然相反

(c) 可传递性:也即如果comp(x, y)为true,comp(y, z)为true,那么comp(x, z)必然为true

小编写了代码去验证这个问题,发现sort函数已经对代码的弱序化进行了校验和保护,当排序内容大小一致时,且规则中包含等号,则会命中以下异常。

虽然在sort函数上这个问题已经添加了保护校验,但是我们自己编写的排序器和比较函数也应该注意满足“Strict Weak Ordering”,避免访问越界等其他意外再次发生。

本文分享自微信公众号 - 搜狗测试(SogouQA)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券