小王职场记STL(2)std:sort解析

程序员小王

发布于 2023-03-28 09:16:47

3410

发布于 2023-03-28 09:16:47

文章被收录于专栏：架构说架构说

上篇文章回顾：

小王职场记谈谈你的STL理解（1）

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个文件)

函数对象模块

定义：重载了“operaotr()”操作符的普通类对象，这个对象具备了具有函数行为调用类(), 相当于调用类.成员函数()


// 大于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

std:compare：

Effective STL： Item 21：永远让比较函数对相同元素返回false

std:sort（5行代码）

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; //排前一部分
 }
}

std:sort描述

维基百科内省排序

内省排序（英语：Introsort）是由David Musser在1997年设计的排序算法。提出了Introspective Sorting(内省式排序)

这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。
2000年6月，SGI的C++标准模板库的stl_algo.h中的不稳定排序算法采用了Musser的内省排序算法。在此实现中，切换到插入排序的数据量阈值为16个。

主要因素： if 递归深度多大 then 改为堆排序有不稳定排序改成稳定排序 if 数据少于16个 then 改为插入排序，降低递归堆栈消耗

上面提到的三种算法各自的优点的综合：

在数据量很大时采用正常的快速排序，此时效率为O(logN)。
一旦分段后的数据量小于某个阈值，就改用插入排序，因为此时这个分段是基本有序的，这时效率可达O(N)。
在递归过程中，如果递归层次过深，使用堆排序来处理 复杂度

参考

http://feihu.me/blog/2014/sgi-std-sort/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

sort

本文分享自 Offer多多微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度