上篇文章回顾:
std:sort代码解析 开始
看一段代码会有什么问题。
当数据元素相同时候 stl sort会概率造成core dump(如果你测试,不一定会重现 ,猜一下需要什么条件?)
一、问题 std::sort()在排序的时候,会导致程序core掉。
二、解决办法 条款21 永远让比较函数对相等的值返回false
比较函数的理解
三、原因分析std:sort 分析 完整版请看: 文档注释:https://github.com/wangcy6/weekly/blob/master/stl.md
gcc 使用 4.8.4 版本,
STL源码 在 Linux 系统的位置是:/usr/include/c++/4.8.4/bits (79个文件)
// 大于template <class _Tp>struct greater : public binary_function<_Tp,_Tp,bool>
{ bool operator()(const _Tp& __x, const _Tp& __y) const { return __x > __y; }
};//这个函数对象没有数据成员、没有虚函数、没有显示声明的构造函数和析构函数,且对operator()的实现是内联的。用作STL比较器的函数对象一般都很小greater<int> greaterobj;
greaterobj(3, 5)//等价于greaterobj.operator(3,5) 效果等价于函数调用function(3, 5);
stl_algo.h
Effective STL: Item 21:永远让比较函数对相同元素返回false
template <class _RandomAccessIter>inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
__STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
_LessThanComparable); if (__first != __last) { //只有一个记录 ,不需要排序
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
__lg(__last - __first) * 2);//快速排序,整体有序
__final_insertion_sort(__first, __last); //剩下未排序的数据,直接插入排序 }
}template <class _RandomAccessIter, class _Tp, class _Size>void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit)
{ while (__last - __first > __stl_threshold) { ///长度大于16才进行一次快排分割
if (__depth_limit == 0)
{
partial_sort(__first, __last, __last); //堆排序
return;
}
--__depth_limit;
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1))));////找三个位置的中位数作为快排依据
__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit); //排后一部分
__last = __cut; //排前一部分
}
}
维基百科 内省排序
内省排序(英语:Introsort)是由David Musser在1997年设计的排序算法。 提出了Introspective Sorting(内省式排序)
主要因素: if 递归深度 多大 then 改为堆排序 有不稳定排序改成稳定排序 if 数据少于16个 then 改为 插入排序,降低递归堆栈消耗
上面提到的三种算法各自的优点的综合:
参考
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有