原创,转载请注明出处:STL库list::sort()实现深度解析 list模板的定义以及一些基本成员函数的实现这里我就不赘述了,还不清楚的同学可以到网上查找相关资料或者直接查看侯捷翻译的<STL源码剖析>相应章节.我之所以写这篇笔记是因为当时看到list::sort()源码时一时没看懂,后来在VS项目里一步步跟踪数据变化发现了其中的奥秘,被其简洁高效的非递归归并排序的实现方法所震撼(侯捷在<STL源码剖析>上注释说此sort实现使用了快排,应该是弄错了),下面直接进入主题. li

转载自:http://www.cnblogs.com/imAkaka/articles/2407877.html STL的sort()算法,数据量大时采用Quick Sort,分段递归排序,一旦分段后的数据量小于某个门槛,为避免Quick Sort的递归调用带来过大的额外负荷,就改用Insertion Sort.如果递归层次过深,还会改用Heap Sort.本文先分别介绍这个三个Sort,再整合分析STL sort算法(以上三种算法的综合) -- Introspective Sorting(内省

(0)文件夹 STL 之 vector源码实现(云算法<< [] = 重载, new delete,throw catch) STLc++中string类的源码 堆(stack) 之 c 和 c++模板实现(空类默认成员函数 初谈引用 内联函数) 第一次实现list模板(幼稚的我) 浅析STL 谓词 + 仿函数 + 函数指针(c) 队列(queue) 之 c++模板实现(友元函数和运算符重载) STL 之 初识set multiset(map multimap) C++map类型 之 简单介绍

一.简介 mt allocator 是一种以2的幂次方字节大小为分配单位的空间配置器,支持多线程和单线程.该配置器灵活可调,性能高. 分配器有三个通用组件:一个描述内存池特性的数据,一个包含该池的策略类,该池将实例化类型链接到公共或单个池,以及一个从策略类继承的类,该类是实际的分配器. 描述内存池特

1.C++标准库和STL C++标准库以header files形式呈现: C++标准库的header files不带后缀名(.h),例如#include <vector> 新式C header files 不带后缀名.h,例如#include<cstdio> 旧式C header files (带有后缀名.h)仍然可用,例如#include <stdio.h> 新式headers内的组件封装于namespace “std”.     using namespace s

以STL 的运用角度而言,空间配置器是最不需要介绍的东西,它总是隐藏在一切组件(更具体地说是指容器,container)的背后,默默工作默默付出. 一.分配器测试 测试代码 #include <list> #include <stdexcept> #include <string> #include <cstdlib> //abort() #include <cstdio> //snprintf() #include <algorithm&

一.摘要 STL的空间分配器(allocator)定义于命名空间std内,主要为STL容器提供内存的分配和释放.对象的构造和析构的统一管理.空间分配器的实现细节,对于容器来说完全透明,容器不需关注内存分配和回收的策略细节如何. STL allocator需实现如下4个标准接口 pointer all

一.容器概览 上图为 GI STL 2.9的各种容器.图中以内缩方式来表达基层与衍生层的关系.所谓的衍生,并非继承(inheritance)关系,而是内含(containment)关系.例如 heap 内含一个 vector,priority-queue 内含一个 heap,stack  和 queue 都含一个 deque,set/map/multiset/multimap 都内含一个 RB-tree,hast_x都内含一个 hashtable. 二.序列式容器(sequential cont

普通的stl::set,查找时只能传入key_type. 不能使用属性值查找. 例如: /* an employee record holds its ID, name and age */ class employee { public: int id; std::string name; int age; public: employee():id(){} employee(int id_,std::string name_,int age_):id(id_),name(name_),age

摘要 迭代器是一种行为类似指针的对象,本文介绍iterator与traits的关系,以及对traits内容的补充.包含stl_iterator.h的部分内容,并用c++11对其进行略微改写. iterator的五种类型 上篇文章已经介绍了这五种类型的特征,它们只是为了激活重载机制而设定,并不需要其他成员.它们的定义如下: //五种迭代器类型 struct input_iterator_tag{}; struct output_iterator_tag{}; struct forward_iter

一.摘要 pool_allocator是一种基于单锁内存池的空间分配器,其内部采用内存池思想,通过构建16个空闲内存块队列,来进行内存的申请和回收处理.每个空闲队列管理的内存块大小固定,且均为8的倍数,范围从8到128字节,按8的倍数递增.该空间分配器最小分配单位为8字节,低于128字节(含128)

本篇文章开始,进行STL源码剖析的一些知识点,后续系列笔记全是参照<STL源码剖析>进行学习记录的 STL在现在的大部分项目中,实用性已经没有Boost库好了,毕竟STL中仅仅提供了一些容器供编码者实用,Boost库相对而言全面了许多,所以更适合做一些项目的开发.但STL源码中依然有很多我们值得学习,思考的地方,包括现在大部分面试,都会问及到STL的框架源码部分.所以决定将这本书其中重要的几个部分拉出来做个笔记,以加深记忆并和大神们探讨探讨. 先简单介绍一下STL中的大致组成部分,一张图就明了

在 STL 库中,关于二分搜索实现了4个函数. bool binary_search (ForwardIterator beg, ForwardIterator end, const T& value) 判断 [beg, end) 中是否存在 value 的值. ForwardIterator lower_bound (ForwardIterator beg, ForwardIterator end, const T& value) ForwardIterator upper_bound 

本文主要分析gcc4.8版本的stl list的源码实现,与vector的线性空间结构不同,list的节点是任意分散的,节点之间通过指针连接,好处是在任何位置插入删除元素都只需要常数时间,缺点是不能随机访问,查询复杂度是O(n),n为list中的元素个数.所以list非常适合应用与数据插入删除频繁的场景. 一. list节点 list节点定义如下, struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_pre

上篇简单介绍了gcc4.8提供的几种allocator的实现方法和作用,这是所有stl组件的基础,容器必须通过allocator申请分配内存和释放内存,至于底层是直接分配释放内存还是使用内存池等方法就不是组件需要考虑的事情.这篇文章开始分析gcc4.8 stl的容器源码实现.stl的容器分为序列式容器和关联式容器,前者包括vector,list,queue以及stack等常用数据结构,后者包含了map,set以及hash table等比较高级的结构,本文就从使用最广泛也是最基础的vector开始

SGI STL sort源码 temlate <class RandowAccessIterator> inline void sort(RandowAccessIterator first, RandowAccessIterator last){ if(first ! = last){ _introsort_loop(first, last, value_type(first), _lg(last-first)*); _fina,_insertion_sort(first, last); }

看侯捷翻译那本<STL源码剖析>中list内置sort的算法,书中注释说是quick sort,看了半天没看明白, template <class T, class Alloc> template <class T, class Alloc> void list<T, Alloc>::sort() if (node->next == node || link_type(node->next)->next == node) return; l

注:关于排序算法,博主写过[数据结构排序算法系列]数据结构八大排序算法,基本上把所有的排序算法都详细的讲解过,而之所以单独将java集合中的排序算法拿出来讲解,是因为在阿里巴巴内推面试的时候面试官问过我,让我说说java集合框架中用的哪种排序算法,当时回答错了,(关于面试详细过程请参看:[阿里内推一面]记我人生的处女面)面试结束后看了一下java源码,用的是折半插入排序算法,本来早就打算写此博客,但是因为准备鹅厂的在线考试,而鹅厂在我心中的地位是最高的,为了准备鹅厂的在线考试,自己基本上把所有事

[算法1-排序](.NET源码学习)& LINQ & Lambda 说起排序算法,在日常实际开发中我们基本不在意这些事情,有API不用不是没事找事嘛.但必要的基础还是需要了解掌握. 排序的目的是为了让无序的数据,变得"有序".此处的有序指的是,满足当前使用需求的顺序,除了自带的API,我们还可以自定义比较器对象.使用LINQ语句.Lambda表达式等方式完成排序.本文将逐一介绍十大排序,并着重介绍分析基于C#的LINQ常用语句和Lambda表达式,二者对排序的实现. [

最近在看 侯捷的 STL源码分析,发现了以下的这个list 排序算法,乍眼看去,实在难以看出它是归并排序. 平常大家写归并排序,通常写的是 递归版本..为了效率的考虑,STL库 给出了如下的 归并排序的迭代版本. 1. MergeSort 的递归版本 首先分析下 MergeSort 的递归版本是如何工作的.递归版本代码可参考 http://blog.csdn.net/shoulinjun/article/details/19290237 考虑如下的例子,对一个长度为 8 的数组进行归并排序. 2

SGI  STL的list的函数的实现源码大致如下: //list 不能使用sort函数,因为list的迭代器是bidirectional_iterator, 而sort //sort函数要求random_access_iterator template<class T,class Alloc> void list<T,Alloc>::sort() { //如果元素个数小于等于1,直接返回 if(node->next==node||node->next->next