STL源码剖析总结_第二章-空间配置器

STL整理 v2 by Felix021使用STL的时候很需要注意的一点是, STL的区间都是左闭右开的.e.g. [start, end) 表示从start开始到end之前一个位置1. list头文件: #include<list>实例化： list<类型>ListName原型：namespace std {template <class T, class Allocator = allocator<T> >class list;}2. vector头文件： #include<vector>实例化： vector<类型>VectorName原型：namespace std {template <class T, class Allocator = allocator<T> > class vector;}成员函数：对vector进行排序可以使用STL的sort, stable_sort, partition, partial_sort, nth_element, 可以用STL的unique算法对其进行排重，但是一定要这么写：vt.erase(unique(vt.begin(), vt.end()), vt.end());使用STL的remove或remove_if算法删除指定元素：vt.erase(remove(vt.begin(), vt.end(), Type &value), vt.end());vt.erase(remove_if(vt.begin(), vt.end(), testfunc), vt.end());回收vector占用的空间：vector<TYPE>(vt).swap(vt); //回收vt中多余元素占用的空间vector<TYPE>().swap(vt); //回收vt占用的所有空间也就是创建一个匿名的空的vector<TYPE>类型变量(前一句还执行了用vt对其初始化)并与vt交换，然后这个变量在这条语句结束时被自动释放。

《STL源码剖析》读后感读了这本书后，对StL的知识有了深入的了解，以前觉得神秘、遥远的StL变得清晰可见!本书主要以SgIStL为标准讲解，并未标准的StL。

StL主要是以模板为基础，实现了强大的泛型功能，只要传给其满足规则的参数，即可实现对各种自定义类型的操作。

StL主要包括空间配置器、迭代器、序列容器、关联容器、泛型算法、仿函数、配接器等。

空间配置器负责为对象分配内存、管理内存的使用。

迭代器是一种smartpointer，是连接容器和算法的桥梁。

迭代器类需要实现很多指针的操作符功能。

StL 有五种类型的迭代器，只有遵循这五种标准才可以和算法无缝连接。

序列式容器有vector、list、deque、stack、queue、heap等，容器内部需要有自己的迭代器，需要由空间配置器来分配管理内存，实现一系列添加、删除、查找等操作。

deque是一种双向开口的数据类型，stack 和queue的底层容器就是deuqe，只是关闭了某些操作，完成了堆栈和队列的数据结构。

heap在取出数据的时候一定是从优先级最高的数据开始的，其底层是一个vector结合一个完全二叉树，就实现了优先取优先级高的数据。

关联式容器有set、map、multiset、multimap、hash_set、hash_map、hash_multiset、hash_multimap。

前四个的底层机制是树结构，准确的说是红黑树(RB-tree)。

后四个的底层机制是hashtable(散列表)，三类表是一种。

关联容器没有头尾，而是按照键值放到合适的位置，查询键值是必须具有良好的搜寻效率。

关联容器内部结构是一个平衡二叉搜索树，为了防止数据放入树时的不够随机造成的树不平衡而影响搜索效率，需要由算法调整树的结构，保持树的平衡。

实现平衡二叉搜索树的有AvL-tree，RB-tree，AA-tree，AvL-tree里面有单旋转和双旋转算法，后面两个树没怎么了解。

STL六⼤组件容器（Container）算法（Algorithm）迭代器（Iterator）仿函数（Function object）适配器（Adaptor）空间配置器（allocator）1、容器作为STL的最主要组成部分－－容器，分为向量（vector），双端队列(deque)，表(list)，队列（queue），堆栈(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。

容器特性所在头⽂件<vector>向量vector可以⽤常数时间访问和修改任意元素，在序列尾部进⾏插⼊和删除时，具有常数时间复杂度，对任意项的插⼊和删除就有的时间复杂度与到末尾的距离成正⽐，尤其对向量头的添加和删除的代价是惊⼈的⾼的<deque>双端队列deque基本上与向量相同，唯⼀的不同是，其在序列头部插⼊和删除操作也具有常量时间复杂度<list>表list对任意元素的访问与对两端的距离成正⽐，但对某个位置上插⼊和删除⼀个项的花费为常数时间。

<queue>队列queue插⼊只可以在尾部进⾏，删除、检索和修改只允许从头部进⾏。

按照先进先出的原则。

<stack>堆栈stack堆栈是项的有限序列，并满⾜序列中被删除、检索和修改的项只能是最近插⼊序列的项。

即按照后进先出的原则<set>集合set由节点组成的红⿊树，每个节点都包含着⼀个元素，节点之间以某种作⽤于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序，具有快速查找的功能。

但是它是以牺牲插⼊删除操作的效率为代价的<set>多重集合multiset和集合基本相同，但可以⽀持重复元素具有快速查找能⼒<map>映射map由{键，值}对组成的集合，以某种作⽤于键对上的谓词排列。

具有快速查找能⼒<map>多重集合multimap⽐起映射，⼀个键可以对应多了值。

c++stl 源码剖析笔记
C++ STL（标准模板库）是C++标准库的一部分，它包含了许多常用的数据结构和算法，如向量、列表、映射、排序、搜索等。

STL 的源码剖析是一个相当复杂的话题，因为STL的实现涉及到大量的模板和元编程技术。

下面我将从几个方面对STL的源码进行剖析。

首先，STL的源码剖析可以从数据结构入手。

比如，我们可以深入研究STL中向量（vector）和映射（map）等数据结构的实现原理，了解它们是如何利用模板和迭代器来实现通用性和高效性的。

其次，STL的源码剖析也涉及到算法的实现。

STL中包含了大量的算法，如排序、查找、拷贝等，这些算法的实现往往涉及到迭代器和函数对象的使用，可以通过分析这些算法的源码来深入理解STL的设计思想和实现细节。

另外，STL的源码剖析还需要关注STL的底层实现。

STL的底层实现往往依赖于各种数据结构和算法，比如红黑树、哈希表等。

通过分析STL底层实现的源码，可以更好地理解STL的性能特点和使用注意事项。

此外，STL的源码剖析还需要关注STL的扩展性和可移植性。

STL的实现通常会考虑到各种平台和编译器的兼容性，因此可以通过分析STL的源码来了解其如何实现可移植性和扩展性。

总的来说，STL的源码剖析是一个庞大而复杂的工程，需要对C++模板、元编程、数据结构、算法等方面有深入的理解。

通过深入剖析STL的源码，可以更好地理解STL的设计思想和实现细节，从而更好地应用STL来解决实际问题。

侯捷老师——STL源码剖析侯捷老师是国内知名的C++专家，他在C++领域有着很高的知名度和影响力。

他的《STL源码剖析》是一本非常经典的C++书籍，深入剖析了C++标准模板库（Standard Template Library，STL）的源代码，并详细解释了其设计思想和实现细节。

下面是对这本书的1200字以上的介绍。

《STL源码剖析》是一本写给C++程序员的经典著作，它由侯捷老师亲自编写，内容非常详尽和深入。

这本书主要介绍了C++标准模板库（STL）的源代码，并解析了其中的设计思想和实现细节。

通过阅读这本书，读者可以更好地理解STL的底层原理，提高自己的C++编程能力。

这本书共分为13个章节，每个章节都涉及了STL的不同组件和特性。

书中的内容既包括理论知识，也包括具体的代码实现。

侯捷老师用通俗易懂的语言和形象生动的例子，对STL的各个组件进行了详细介绍。

他从容器、迭代器、算法和函数对象等方面入手，逐步展开对STL的剖析。

每一章的结尾都有相关的练习题，读者可以通过做题来巩固所学知识。

在《STL源码剖析》中，侯捷老师对STL的源代码进行了深入分析，解释了其中的设计思想和实现原理。

他通过对容器的底层结构和操作进行剖析，揭示了STL的高效性和灵活性。

在对算法和函数对象的讲解中，他详细介绍了STL中的各种常用算法，并解释了它们的内部实现原理。

通过这种深入的分析，读者可以更好地理解STL的运作机制，并能够灵活运用STL进行程序设计。

除了对STL源代码的剖析，侯捷老师还对STL的使用和扩展进行了说明。

他介绍了STL的使用注意事项和常见问题，并给出了一些实用的编程技巧和优化建议。

此外，他还展示了如何扩展STL，给出了一些自定义容器和算法的示例。

这些内容对于想要深入学习和应用STL的读者来说是非常有价值的。

总的来说，侯捷老师的《STL源码剖析》是一本非常权威和深入的C++书籍，对于想要深入学习STL的C++程序员来说是一本必读之作。

STL源码剖析学习笔记
deque的迭代器
deque的迭代器除了⼀些型别定义，主要有以下四个数据成员：
typedef T** map_pointer;
T* cur;
T* first;
T* last;
map_pointer node;
deque的主要的数据成员：
protected:
iterator start;
iterator finish;
map_iterator map;
size_type map_size;
可以看到deque维护了两个迭代器。

迭代器的node指向连续空间map某⼀个元素，first和last指向某个缓冲区的起始和结束，⽽cur指向当前元素。

deque的两个迭代器的cur有特别意义，start.cur指向第⼀个缓冲区的第⼀个元素的位置，finish.cur指向最后缓冲区的最后⼀个元素的位置。

所以两个迭代器的first,last和node很可能完全⼀样（同⼀个缓冲区）,cur才是区分他们的根本。

⽽迭代器其实提供给外界的假象就是它是⼀个连续空间，iterator的⾏为就像是cur的⾏为。

所以iterator ite，在++时，只需把cur++即可；在两个迭代器相减时只需把两者的cur 相减；⽐较两个迭代器是否相等时，只需看⼆者cur是否相等，当然，以上的⼤前提是⼀定要考虑是否跨缓冲区间！即迭代器默默维护的first,last,node。

要注意的是start和finish元素增长的⽅向是相反的，⼀个是last---->first,⼀个是first----->last。

“STL”（Standard Template Library）标准模版库概述目录STL概念 (2)STL组成部分 (2)容器 (2)迭代器 (4)算法 (4)什么时候用STL (5)容器模板的使用 (5)容器模板中的常用函数 (6)STL概念STL（Standard Template Library），即标准模板库从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。

这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。

STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。

STL现在是C++的一部分，因此不用额外安装什么。

在C++标准中，STL被组织为下面的17个头文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。

STL组成部分STL可分为六个部分。

⏹容器(containers)⏹迭代器(iterators)⏹空间配置器(allocator)⏹配接器(adapters)⏹算法(algorithms)⏹仿函数(functors)容器在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。

经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。

（⼀）STL体系结构基础介绍⼀、STL六⼤部件 容器(Containers)：存放元素，内存由分配器搞定 分配器(Allocator)：⽀持容器的内存分配 算法：操作容器元素的函数。

与OO不同（⾯向对象将元素与函数放到⼀个类⾥），GP（模板编程）将数据放⼊容器，操作⽅法放⼊算法中。

迭代器(Iterator): 算法和容器之间的桥梁，通过迭代器，算法才能去操作容器中的元素。

迭代器就是泛化的指针。

适配器(Adapters)：对其他组件进⾏转换。

仿函数(Functors)：⾃定义类的相关操作（⽐如⾃定义类A，计算其两个实例的相加、相减等，即操作符重载）。

⼆、⼀个例⼦使⽤六⼤部件 通常allocator那部分不⽤写。

三、容器遍历 前闭后开区间 使⽤auto，for遍历 auto的其他⽤法四、容器结构与分析 1、顺序容器 Array:固定⼤⼩，连续空间存放 Vector: 当容量不够时，allocator在背后重新分配 Deque: 双端队列 List: 双向链表 ForwardList：单向链表 2、关联容器（包括Unordered_Containers） 关联容器的查找很快 Map/Set：⼀般⽤红⿊树实现（左右⾼度平衡的⼆叉树） MultiMap/MultiSet: key可重复的。

Map是key-value，Set是key-key。

⽆序容器：元素存放的位置是不固定的，由hash-table实现（⽬前最好的实现⽅式是seperate chaining）。

五、容器使⽤ 1、编码习惯 （1）为每个独⽴的程序创建namesapce; (2) 在⽤到变量时才定义变量，但不缩进； 2、vector （1）因为单向，只能通过push_back存放元素（从头存放需要移动整个vector）; (2) 当空间不⾜，重新分配内存时，内存两倍增长； （3）可以通过front,back访问⾸尾元素，data访问⾸地址（vector, array, list）； 3、List 标准库有sort,各个容器也有⾃带sort，排序尽量⽤⾃带的sort。

STL就是Standard Template Library（C++标准模板库），下面是关于STL中的各种内容STL中的几个基本概念：1.容器：可容纳各种数据类型的数据结构。

可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。

容器分为三大类：（1) 顺序容器vector：后部插入/删除，直接访问deque：前/后部插入/删除，直接访问list：双向链表，任意位置插入/删除1) vector 头文件<vector>实际上就是个动态数组。

随机存取任何元素都能在常数时间完成。

在尾端增删元素具有较佳的性能。

2) deque 头文件<deque>也是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。

在两端增删元素具有较佳的性能。

3) list 头文件<list>双向链表，在任何位置增删元素都能在常数时间完成。

不支持随机存取。

上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。

（2)关联容器set：快速查找，无重复元素multiset ：快速查找，可有重复元素map：一对一映射，无重复元素，基于关键字查找multimap ：一对一映射，可有重复元素，基于关键字查找，前2者合称为第一类容器关联式容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。

关联式容器的特点是在查找时具有非常好的性能。

1) set/multiset: 头文件<set>set 即集合。

set中不允许相同元素，multiset中允许存在相同的元素。

2) map/multimap: 头文件<map>map与set的不同在于map中存放的是成对的key/value。

并根据key对元素进行排序，可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的key值。

上述4种容器通常以平衡二叉树方式实现，插入和检索的时间都是O(logN)（3)容器适配器stack：LIFO queue：FIFO priority_queue：优先级高的元素先出对象被插入容器中时，被插入的是对象的一个复制品。

STL源码剖析STL（Standard Template Library）是C++标准库中的一部分，它提供了一系列的模板类和函数，用于操作各种数据结构和算法，包括vector、list、map、set等容器，以及sort、find、c ount等算法。

STL的设计思想是将数据结构和算法分离，使得用户可以通过简单的组合和调用，完成复杂的数据处理任务。

STL的源码实现是一个非常庞大和复杂的工程，涉及到各种数据结构、算法、模板技术、编译器优化等方面的知识。

本文将从几个方面来剖析STL的源码实现，包括容器、迭代器、算法等方面。

一、容器STL提供了多种容器，包括vector、list、deque、map、set等。

这些容器都是模板类，可以存储不同类型的数据，并且支持各种常用的操作，比如插入、删除、查找、排序等。

以vector为例，其源码实现主要包括以下几个部分：1. 构造函数和析构函数：vector的构造函数可以接受多种参数，比如默认构造函数、指定大小的构造函数、拷贝构造函数等。

析构函数用于释放vector占用的内存。

2. 迭代器：vector提供了多种迭代器，包括普通迭代器、反向迭代器、常量迭代器等。

迭代器是STL的核心概念之一，它可以让用户通过类似指针的方式来访问容器中的元素。

3. 容量和大小：vector提供了多种方法来查询容器的大小和容量，比如size()、capacity()、e mpty()等。

4. 插入和删除：vector提供了多种方法来插入和删除元素，比如push_back()、pop_back()、insert()、erase()等。

5. 访问元素：vector提供了多种方法来访问容器中的元素，比如at()、front()、back()等。

二、迭代器迭代器是STL的核心概念之一，它可以让用户通过类似指针的方式来访问容器中的元素。

S TL提供了多种迭代器，包括普通迭代器、反向迭代器、常量迭代器等。