专栏首页orientlustd::sort coredump 说起

std::sort coredump 说起

@(c++)

core 的原因

c++ 标准库 sort() 默认采用 < 这个 operator 来排序的, 另个一个重载函数增加第三个参数,指定一个比较的函数,函数接受两个参数。 对于基础类型(int,float..),直接调用 sort(start,end) 即可,对于非基础类型的结构体,可以通过重载对象的 < 运算符或者提供一个比较函数。 详见

本文从一个 core 说起 相信很多人在编写使用 sort 都在这个地方翻车,

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class CompareGreater {
    public:
        bool operator()(const int* left, const int* right)
        {
            return *left >= *right;
        }
};

int main(int argc, char *argv[])
{
    vector<int *> verPInt;
    for (int i = 0; i < 18; i++) { // will coredump
        int *pInt = new int;
        if (pInt == NULL) {
            cout << "new faile" << endl;
            goto final;
        }
        *pInt = 1;
        verPInt.push_back(pInt);
    }
    sort(verPInt.begin(), verPInt.end(), CompareGreater());
    for (vector<int *>::iterator iter = verPInt.begin(); iter != verPInt.end(); ++iter) {
        cout << **iter;
    }
    cout << endl;
final:
    for (vector<int *>::iterator iter = verPInt.begin(); iter != verPInt.end(); ++iter) {
        delete *iter;
        *iter = NULL;
    }
    return 0;
}

gdb 查看堆栈,发现是 core 在比较函数里面。

Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x000055e88121e00c in CompareGreater::operator()(int const*, int const*) ()

上述代码,所有元素值相同,当个数大于等于 16个 的时候就会 coredump,查看说明,core 的原因是 :

<font color=#0099ff size=5>std::sort()在排序时,比较函数对相等的元素应该返回 false!如果返回 true,会导致程序coredump</font>

因为定义 cmp(x,x) 返回 true 不符合 Strict_weak_orderings,标准库算法里面很多都要求满足 Strict_weak_orderings,使用时需要格外注意,避免翻车。 上述例子代码只需修改比较函数中,将 >= 改为 >即可修复。

为什么是元素个数大于等于 16个 呢,从 STL 源码可以发现,由于 std::sort() 的排序分2种,当元素个数 >16 <font color=#0099ff>(_S_threshold = 16)</font> 时选择快速排序,<=16 个则选择插入排序 (对象少时快排性能不理想)。按照快排原理,每次都是遍历所有值和一个中间值比较,小的放左边,大的放右边。从STL源代码可看出,std::sort() 在遍历比较时,是没有加边界保护的。如果比较相等的元素返回真,则在极端情况下 (如所有元素值相等时) __first 会出现访问越界,导致coredump。 STL 源码 : /usr/include/c++/7/bits/stl_algo.h(具体目录)

深层次的坑

写测试代码时候,发现比较元素从 vector<int *> 改为 vector<int>,比较函数同样错误的写为 >=,运行程序并不会 core,但是打印比较好的数据,发现数据错了!!坑爹啊,这样的坑更深沉。

测试代码


参考

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • UNIX IPC

    管道一般为有亲缘关系进程提供单路数据流, 通过pipe(int fd[2])创建, 返回两个文件描述符, fd[0] 用于读,fd[1]用于写。 通过 read...

    orientlu
  • FreeRTOS 任务通知

    FreeRTOS 从版本 V8.2.0开始提供任务通知这个功能,每个任务都有一个32位的通知值。按照 FreeRTOS 官方的说法,使用消息通知比通过二进制信...

    orientlu
  • Google 单元测试框架

    到 github 拉取代码或者下载某个版本的 zip 包到本地目录,参考 gtest 中的 README.md 如何编译库和编译自己的代码,下面简单介绍下编译方...

    orientlu
  • 3002 石子归并 3

     时间限制: 1 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 有n堆石子...

    attack
  • 【GPLT】L1-013 计算阶乘和

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • Tip | 数据类型占位 & 降采样 & 像素读取 & Bitmap & Color源码

    下面修改通道的时候使用的是位运算, 其实对比Color源码我们知道这跟调用Color的API是一样的:

    凌川江雪
  • C++ 隐式类型转换

    C++定义了一组内置类型对象之间的转换标准,在必要的时候它们被编译器隐式的转换 1、任何两种或多种类型的数据和变量混合操作的时候,最宽的数据类型成为目标转换类型...

    用户1215536
  • HDU-1003 Max Sum(动态规划,最长字段和问题)

    Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J...

    ShenduCC
  • Leetcode 525. Contiguous Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • SQL基础之 时间戳

    本文转载:http://www.cnblogs.com/liuhh/archive/2011/05/14/2046544.html

    跟着阿笨一起玩NET

扫码关注云+社区

领取腾讯云代金券