大数字字符串排序触发std::out_of_range、SIGABRT报错排查与修复
报错原因解析与修复方案
报错的具体含义
日志中抛出的std::out_of_range类型异常、附带what(): stol的错误信息,以及后续触发的SIGABRT进程终止,是两个连锁引发的问题:
- 代码中调用
stol()将数字字符串转换为long int类型时,传入的字符串所代表的数值已经超出long int的可表示范围。按照C++标准定义,当stol无法在不损失精度的前提下完成转换时,会主动抛出std::out_of_range异常。 - 程序没有对该异常做捕获处理,C++运行时会默认终止当前进程,最终产生core dump、触发SIGABRT信号的现象。
结合题目给出的输入规则,这个报错是必然会出现的:输入的数字字符串最长可达1e6位,而常规运行环境下,64位long int最多只能存储18-19位十进制数字,超长数字根本不可能被装入固定长度的整数类型,强行转换必然触发越界。
现有代码的其他性能隐患
除了触发越界报错的逻辑缺陷,当前实现还存在两个会导致执行失败的性能问题:
- 采用冒泡排序实现排序逻辑,时间复杂度为$O(n^2)$,当输入数组规模较大时,排序效率极低,极易出现执行超时。
- 排序过程中会对相同的字符串反复调用
stol()做转换,重复转换的开销极大,进一步拉高了整体运行时间。
修复方案
核心逻辑
完全不需要将长数字字符串转换为整数形式,直接利用字符串本身的特征就可以准确比较数值大小,比较规则非常简单:
- 题目给出的是无前置零的正整数字符串,因此字符串长度越长,对应的整数值越大。
- 如果两个字符串长度相等,那么字符串本身的字典序排序结果,与对应整数值的大小顺序完全一致。
可直接运行的实现代码
vector<string> bigSorting(vector<string> unsorted) { // 基于字符串特征自定义比较规则,调用标准库排序 sort(unsorted.begin(), unsorted.end(), [](const string& a, const string& b) { // 长度不同时,长度更短的字符串对应数值更小 if (a.size() != b.size()) { return a.size() < b.size(); } // 长度相同时,直接比较字符串字典序即可匹配数值大小 return a < b; }); return unsorted; }
方案适配性
- 从根源上消除了超长数字转整数的需求,自然不会触发
stol的越界异常,哪怕单条字符串达到1e6位长度也可以正常处理。 - 用标准库的内省排序替代手写冒泡排序,时间复杂度从$O(n^2)$降低到$O(n\log n)$,可以支撑更大规模的输入数组。
- 字符串逐位比较的效率很高,遇到第一个不同的字符就可以停止比较,不需要遍历整个长字符串。
内容的提问来源于stack exchange,提问作者Samit Kapoor
相关产品推荐
相关产品推荐

