前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >小王职场记STL(2)std:sort解析

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

作者头像
早起的鸟儿有虫吃
发布于 2023-03-28 01:16:47
发布于 2023-03-28 01:16:47
66500
代码可运行
举报
文章被收录于专栏:算法之美算法之美
运行总次数:0
代码可运行

上篇文章回顾:

小王职场记 谈谈你的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个文件)

目录:

小王职场记 谈谈你的STL理解(1)

函数对象模块

  • 定义: 重载了“operaotr()”操作符的普通类对象 , 这个对象具备了具有函数行为 调用类(), 相当于调用类.成员函数()
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制

// 大于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行代码)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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)。
  • 在递归过程中,如果递归层次过深,使用堆排序来处理 复杂度

参考

  1. http://feihu.me/blog/2014/sgi-std-sort/
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
图解|从武侠角度探究STL排序算法的奥秘
众所周知STL是借助于模板化来支撑数据结构和算法的通用化,通用化对于C++使用者来说已经很惊喜了,但是如果你看看STL开发者强大的阵容就意识到STL给我们带来的惊喜绝不会止步于通用化,强悍的性能和效率是STL的更让人惊艳的地方。
C语言与CPP编程
2021/07/27
4730
图解|从武侠角度探究STL排序算法的奥秘
一道面试题引起的...
在STL的sort中,在数据量大时候,采用快排,分段递归排序。一旦分段后的数据量小于某个阈值,为了避免快排的递归调用引起的额外开销,此时就采用插入排序。如果递归层次过深,还会采用堆排序。
高性能架构探索
2021/04/13
3880
深入理解快速排序和STL的sort算法
为了证明笔者没有放弃这块阵地,整合三篇去年的文章,今天一起来学习一下:快速排序及其优化 和 STL的sort算法
C语言与CPP编程
2020/12/02
1.4K0
深入理解快速排序和STL的sort算法
选择、插入排序、sort
这一篇我们一起来学习实践下选择排序和插入排序,然后再一起分析下CPP的STL中排序算法的实现,结束排序算法的阶段。
派大星在吗
2021/12/15
4490
STL 选择、插入排序
选择排序则是先假设一个为最小值,然后用这个值和后面所有的内容一一进行比较大小,每轮进行一次交换。选择排序是先确定位置,在找值。
大发明家
2021/12/17
6150
快排究竟有多快?
[导读] 前面文章改变世界的5大算法,一文中提到快速排序算法对世界影响巨大,估计很多人不以为然,本文来尝试解读一下为啥。
逸珺
2020/06/02
1.4K0
快排究竟有多快?
【C++】STL 算法 ⑥ ( 二元谓词 | std::sort 算法简介 | 为 std::sort 算法设置 二元谓词 排序规则 )
" 谓词 ( Predicate ) " 是一个 返回 布尔 bool 类型值 的 函数对象 / 仿函数 或 Lambda 表达式 / 普通函数 , 可用于对某个条件进行检查 ;
韩曙亮
2024/01/08
3170
【C++】STL 算法 ⑥ ( 二元谓词 | std::sort 算法简介 | 为 std::sort 算法设置 二元谓词 排序规则 )
【数据结构初阶】排序算法(中)快速排序专题
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
fhvyxyci
2024/09/29
1520
【数据结构初阶】排序算法(中)快速排序专题
Leetcode-378.有序矩阵中第K小的元素
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。(从升序角度来看,第个k,k越大越靠后)
早起的鸟儿有虫吃
2019/08/20
1.5K0
算法笔记之排序
最近在看《算法笔记》,如果单从算法来说,这本书真正做到了短小精悍,首先以排序入题,那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过程就叫“排序”.排序是一种非常基础的算法,有着广泛的理论和实践基础。对一个排序算法来说,一般从如下3个方面衡量算法的优劣: 时间复杂度:主要是分析关键字的比较次数和记录的移动次数。 空间复杂度:分析排序算法中需要多少辅助内存 稳定性:若两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,则称这种算法是稳定的;反之,就是不稳定的。 排序算法
xiangzhihong
2018/02/05
9290
算法笔记之排序
【数据结构】排序算法---快速排序(动图演示)
算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
Crossoads
2024/10/22
4200
【数据结构】排序算法---快速排序(动图演示)
【线上问题】P1级公司故障,年终奖不保
前段时间,某个同事找我倾诉,说是因为strict weak ordering导致程序coredump,给公司造成数百万损失,最终评级故障为P0级,年终奖都有点不保了,听完不禁一阵唏嘘。
高性能架构探索
2022/08/25
5270
【线上问题】P1级公司故障,年终奖不保
.NET 排序 Array.Sort<T> 实现分析
System.Array.Sort<T> 是.NET内置的排序方法, 灵活且高效, 大家都学过一些排序算法,比如冒泡排序,插入排序,堆排序等,不过你知道这个方法背后使用了什么排序算法吗? 先说结果,
全球技术精选
2021/10/09
6680
.NET 排序 Array.Sort<T> 实现分析
C++ || 一个简单的 ::std::sort 怎么就能造成堆溢出呢?
T2不就是重载一下 sort 的比较函数吗?看坑神的b站录象[1],再看看评论,才知道 C++ 中的一个惊天大坑。得益于4个月来对 y 总高质量代码风格与良好书写习惯的阅读与模仿,我在考试时“幸运”地避开了这个坑。
Piper蛋窝
2021/09/15
1.4K0
C++ || 一个简单的 ::std::sort 怎么就能造成堆溢出呢?
【算法复习4】C++ STL 中的 sort()和Java 语言中的 Collections.sort()通用的、高性能的排序函数
为了避免快速排序里,递归过深而堆栈过小,导致堆栈溢出,我们有两种解决办法:第一种是限制递归深度。一旦递归过深,超过了我们事先设定的阈值,就停止递归。第二种是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程,这样就没有了系统栈大小的限制。
韩旭051
2021/04/14
1K0
【算法复习4】C++ STL 中的 sort()和Java 语言中的 Collections.sort()通用的、高性能的排序函数
【字节跳动】第十二讲 数据结构与算法 | 青训营笔记
张云浩:字节跳动-程序语言团队成员,目前主要研究方向包括但不限于性能优化、(并发)数据结构和算法等领域。
了凡银河系
2022/08/22
8620
【字节跳动】第十二讲 数据结构与算法 | 青训营笔记
【初阶数据结构】常见五大排序算法及部分算法优化讨论
1.排序:所谓排序,就是使一串记录或者数据,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
ZLRRLZ
2024/12/13
1810
【初阶数据结构】常见五大排序算法及部分算法优化讨论
day11 | 数据结构与算法 | 第三届字节跳动青训营笔记
当然,今天这篇文章在《字节跳动技术团队》也有讲到《打造 Go 语言最快的排序算法》
千羽
2023/01/14
3600
C++ STL 标准模板库(排序/集合/适配器)算法
C++ 标准模板库STL,是一个使用模板技术实现的通用程序库,该库由容器container,算法algorithm,迭代器iterator,容器和算法之间通过迭代器进行无缝连接,其中所包含的数据结构都是目前最优解,该库既能保证软件代码的高可复用性,又能保证代码具有相当高的执行效率,STL库是ANSI/ISO的C++标准的具体实现,任何标准库的实现都是以源码形式释出的.
王瑞MVP
2022/12/28
6790
9.1 C++ STL 排序、算数与集合
C++ STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的模板函数和容器,用于处理各种数据结构和算法。在STL中,排序、算数和集合算法是常用的功能,可以帮助我们对数据进行排序、统计、查找以及集合操作等。
王瑞MVP
2023/08/17
2340
推荐阅读
相关推荐
图解|从武侠角度探究STL排序算法的奥秘
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验