前言

这本书虽然年代久远但依然很经典。可以详细地了解STL的底层实现机制，同时也可以对常用数据结构，C++内存管理拥有更深的理解。特别对于找工作的C++软件开发工程师帮助很大。

但个人觉得读这本书的过程中可以详略得当，有些只需要大概了解，有些则需要细嚼慢咽。这篇文章记录我在读这本书的过程中印象比较深刻的知识点。

思维导图

图片格式的看起来不直观，请访问在线思维导图:  https://www.processon.com/view/link/5d415690e4b058ef96bba000

第一章、STL概论 1、STL提供六大组件，彼此可以组合套用

（1）容器

（2）算法

（3）迭代器

（4）仿函数：重载了operator()的class或class template

（5）适配器：修饰容器或仿函数或迭代器的东西。比如queue和stack，虽然看上去是容器，但实际上却是deque的一层包装。

（6）配置器：负责空间配置与管理。

第二章、空间配置器 1、STL定义在<memory>中与空间配置相关的有三个部分：

（1）<stl_construct.h>

（2）<stl_alloc.h>

（3）<stl_uninitialized.h>

2、构造和析构的基本工具:contruct()和destroy()

用来构造和析构STL对象，会根据对象类型而选取最优的方式。

3、空间的配置与释放

（1）考虑到小型区块所可能造成的内存破碎问题，SGI设计了双层配置器，第一级配置器直接使用malloc和free，第二季配置器则视情况不同采取不同的策略：

（2）第一级配置器直接调用C函数执行实际的内存操作，并实现类似C++ new handler的机制。

（3）当区块超过128bytes时，视之为足够大，便调用第一级配置器。当配置器小于128bytes时，视之为过小，便采用内存池的方式。每次配置一大块内存，并维护对应之自由链表，下次若再有相同大小的内存需求，就直接从free-list中拔出。如果客端释还小额区块，就由配置器回收到free-list中。为了方便管理，SGI第二季配置器会主动将任何小额区块的内存需求量上调至8的倍数（例如客端要求30bytes，就自动调整为32bytes），并维护16个free-list，大小分别是8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128bytes。

（4）内存池

如果水量充足，就直接调出20个区块返回给free-list，如果不够20则返回不足实际个数。如果一个都拿不出，则调用malloc配置40个区块的空间，其中20个给free-list，剩下的20个留在内存池。如果malloc分配失败，则调用第一级配置器。因为第一级配置器有new-handler机制，获取能够整理出多余的空间。、

（5）内存基本处理工具

uninitialized_copy，uninitialized_fill,uninitialized_fill_n，能够将内存配置与对象构造行为分离开来。并且会对POD（即标量型别或传统C struct）对象采用最有效率的初值填写手法，而对non-POD型别采取最保险安全的做法。

第三章、迭代器概念与traits编程技法 1、迭代器定义

iterator模式定义如下：提供一种方法，使之能够依序巡访某个聚合物所含的各个元素，而无需暴露该聚合物的内部表述方式。

2、Traits编程技法

迭代器通过内嵌型别声明的方式来推到实际参数的类型。

最常用的迭代器相应型别有五种：

（1）value_type，就是对象的型别

（2）difference type，表示两个迭代器之间的距离，因此它可以用来表示一个容器的最大容量。

（3）reference type，函数如果需要传回左值，是以by reference的方式进行的。

（4）pointer type，传回一个左值，令他代表所指之物。

（5）iterator_category

这个就比较重要了，分为五种类型，input iterator，output iterator，fowared iterator，bidirectional iterator，random access iterator，其中含义不言而喻。

3、std::iterator的保证

STL提供了一个Iterators class，如果每个新设计的迭代器都继承自它，就可保证符合STL所需之规范。

第四章、序列式容器

这章之前读过，可参考：https://blog.csdn.net/luchengtao11/article/details/76849570

1.vector

动态增长机制：GCC以2的指数速度增长，vs以1.5倍的速度增长。

而在不断pop的过程中，无论原先分配的空间有多大，都不会动态减少。

迭代器特性：可以以普通指针做迭代器。一旦引起空间重新配置，指向vector的所有迭代器就都失效了。

2.List

List基于双向链表实现

List的插入、删除或者拼合操作不会造成原有迭代器的失效。

List不能用STL 中的sort函数进行排序，而是要用自身的sort函数。List仅支持随机访问迭代器，而List是双向迭代器。

3.deque

是一个双向队列

将数据分为多个存储区域，存储区域的指针存储在map存储区中，当map区域不够大时可以动态增长。所以deque可以在常数时间在首尾进行存取操作，也支持随机访问。

但是代价就是复杂的迭代器，从而导致在许多方面表现的都比vector差。

 

deque的迭代器具有以下元素：

T *cur; //此迭代器所指之缓冲区的当前元素T *first; //此迭代器所指缓冲区的头T *last; //此迭代器所指之缓冲区的尾（个人觉得last所指区域为非法区域，即未分配区域，强行访问会造成崩溃）map_pointer node; //指向管控中心

 deque的迭代器的++操作，远比vector的复杂：

void set_node(map_pointer new_node){ node = new_node; first = *new_node;//新缓冲区的第一个元素的指针 last = first + difference_type(buffer_size); //新缓冲区的末尾}self& opertator++(){ ++cur; //切换到下一个元素 if (cur == last) //如果已经到达了当前缓冲区的尾端 { set_node(node+1); //切换到下一个缓冲区 cur = first; //也就是指向新缓冲区的第一个元素 } return *this;}

 

4.stack

statck可以基于多种容器实现，默认是基于deque

statck只能在尾部对元素进行存取，不允许遍历行为，不提供迭代器。

考虑过STL中为什么默认的stack是基于deque而不是vector,个人认为其实到底选哪个要看具体的应用场景。deque在各种情况下表现的都一般，但不差。比如如果疯狂push()，deque只需要增加缓冲区即可，而vector则需要请求一块更大的内存区域，把所有元素搬进新区域，再把原有区域释放。显然，在这种情况下，deque的性能是更优的。

5.queue

可以基于多种容器实现，默认是deque

值允许在尾部添加元素，在首部删除元素，不允许遍历行为，不提供迭代器。

6.heap

如果用vector来存储二叉树。如果v[1]是根节点，则v[i]的父节点为v[i/2],v[i]的子节点为v[2*i]和v[2*i+1]。真是巧了

插入：先添加到尾部，然后不断与父节点比较，不断上升。

删除：先将根节点与最后一个节点交换位置，然后将最后一个节点（即原来的根节点）弹出，然后再讲根节点（即原来的最后一个节点）不断下降。

初始化：初始化有两种方式，第一种是插入法，第二种是调整法，可参考：https://blog.csdn.net/chen_lin111/article/details/50477642

 

第五章、关联式容器

这章可谓是干货满满呀。

1、二叉搜索树

任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。其增删改查都很简单。

2、AVL-tree

在二叉搜索树的基础上，要求任何节点的左右子树高度相差最多1。

当插入新节点时可能会改变平衡状态，此时需要重新调整。只需要调整“插入点指根节点”路径上，平衡状态被破坏之各节点中最深的哪一个，假设此点为X，分为四种情况：

插入点位于X的左子节点的左子树–左左插入点位于X的左子节点的右子树–左右插入点位于X的右子节点的左子树–右左插入点位于X的右子节点的右子树–右右

对于1，4情况，可以采用单旋转操作调整解决，对于2，3情况，可以采用双旋转操作调整解决。

3、红黑树

红黑树在二叉搜索树的基础上需要满足以下规则：

每个节点不是黑色就是红色根节点为黑色如果节点为红色，其子节点必须为黑色任一节点至NULL的任何路径，所含之黑节点数必须相同。

STL为什么选择红黑树而不是AVL-tree?

红黑树的平衡性是比AVL-tree弱的，但是搜索效率几乎相等。两者的插入和删除操作都是O(logn),但是就旋转操作而言，AVL-tree是O(n)，而红黑树是O（1）

 

4.set 

基于红黑树实现。

不能通过迭代器改变元素值。（如果改变的话会破坏红黑树的结构）。

插入和删除操作都会导致之前的迭代器失效。

对于关联容器，使用自身的find()函数会比使用STL的find()更加有效。

5.map

不能通过迭代器改变key值，但是可以改变value值，删除和插入操作不会使之前的迭代器失效。
Insert操作返回的是pair,first是被插入元素的迭代器，second是bool,表示是否插入成功

Mulimap、mulitset与普通的map和set差不多，只不过是允许有重复值。

6.hash_table

线性探测：f(value)=value%length+i;

二次探测：f(value)=value%length+i^2

开链：相同key值的value以链表的方式保存在同一个桶中。当元素个数大于桶的个数时就重建，然后再插入重建后的相应位置。

hash_map和hash_set都是基于hash_table.

vs说hash_map和hash_set都过时了，要用unordered_map,unorder_set，性能最佳。