一生中总会遇到这样的情况，你的内心已经兵荒马乱天翻地覆了；
可是在别人看来你只是比平时沉默了一点，没有人会觉得奇怪；
这种战争，注定是单枪匹马。——白岩松

1.六大组件及其关系

Container(容器) 各种基本数据结构
Adapter(适配器) 可改变containers、Iterators或Function object接口的一种组件
Algorithm(算法) 各种基本算法如sort、search…等
Iterator(迭代器) 连接containers和algorithms
Function object(函数对象)
Allocator(分配器)

1.1 容器-Container

1.1.1 定义

容纳、包含一组元素或元素集合的对象.

1.1.2 七种基本容器

向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）

1.1.3 序列式容器

序列式容器Sequence
containers,其中每个元素均有固定位置——取决于插入时机和地点，和元素值无关。（vector、deque、list）

list:双向链表

• 基于双向环状链表实现;尾部有空白节点（为满足左闭右开）；内部有一个 last 迭代器指向尾端空白节点（其 next 为 begin
  迭代器）。
• 插入和删除快，但是随机访问比较慢,时间复杂度为O(1)；
• 需要频繁进行插入或删除操作且不需要过多地在序列内部进行长距离跳转，应该选择list；
• List 不能使用算法 sort（只接受随机存取迭代器），值接受双向迭代器，不支持随机存取迭代器，它有自己内置的 sort。

vector

• 动态数组，基于数组的实现，从后面插入和删除元素,push_back,pop_back，随机访问快 ，插入和删除慢，因为会造成内存块的拷贝，时间复杂度为O(n)。

• 迭代器在增加数据，内存扩容时必定失效，因为内存地址都变了，删除数据时看编译器情况，vs会失效。

• 维护三个迭代器：start，finish，end_of_storage。

内存分配

• vector动态数组只会增加内存，不会删除空间，当空间不够时会自动申请另一片更大的空间，然后把原有数据拷贝过去，并删除原来的空间的数据，但是存储空间不会释放，要等到vector调用析构函数的时候才会释放空间。

扩容原则

• VS2015 下配对源码 每次扩容50%，原来空间大小9，扩容之后9+9/2=13; Ubuntu 下源码是按每次增长两倍算；

• 若原本空间为0，第一次配置扩容为1，否则按1.5或2倍来来算。

强制释放内存
clear()函数只会清空数据，并不会释放内存，一般采用swap函数释放空间。通过创建临时拷贝对象，调用swap之后来释放原对象内存空间。vector< int>(v).swap(v);注意：这里的swap是泛型算法里的swap函数，不是容器里的。

注意

并不是所有的STL容器的clear成员函数的行为都和vector一样。事实上，其他容器的clear成员函数都会释放其内存。比如另一个和vector类似的顺序容器deque。

deque(双向队列):

• 与vector类似，也是基于数组，但是支持开始端插入元素：push_front；
• 与vector相比元素存取和迭代器动作稍慢，但是内存分配方面优于vector；
• c++标准建议：vector是那种应该在默认情况下使用的序列。如果大多数插入和删除操作发生在序列的头部或尾部时，应该选用deque。
• 使用中控器 map，存的指针，指向实际存储块

迭代器失效

• a. 在deque容器首部或者尾部插入元素不会使得任何迭代器失效；
• b. 在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效；
• c. 在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

1.14 关联式容器

关联式容器Associative

containers，元素位置取决于特定的排序准则以及元素值，和插入次序无关。（set、multiset、map、multimap）

set

一对一， 内部结构采用红黑树的平衡二叉树。自动排序，默认升序，不允许重复值。

multiset

类同set，允许重复值

map (key,value)

一对多， 内部结构采用红黑树的平衡二叉树。自动排序，默认升序，不允许重复值
multimap:类同map，允许重复值

红黑树

五大特性

• 每个节点或者是黑色，或者是红色。

• 根节点是黑色。

• 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]

• 如果一个节点是红色的，则它的子节点必须是黑色的。

• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树插入结点

因为红黑树上面的第4个特点，因此当向红黑树中插入新的节点时，应该将新节点标注为红色。向红黑树中插入节点看的是插入节点的父节点和叔父节点。

红黑树旋转

右旋
插入D结点，此时的树不满足红黑树性质，需要旋转，这里需要对A进行右旋转；以 A-B轴右旋，对A右旋，A成为B的右孩子，B的右孩子成为A的左孩子；

同理，若需要左旋，则是以A-B轴右旋，对A左旋，A成为B的左孩子，B的左孩子成为A的右孩子。

1.2迭代器-Iterators

1.2.1定义

• 迭代器Iterators，用来在一个对象群集（collection of
  objects）的元素上进行遍历。这个对象群集或许是个容器，或许是容器的一部分。

迭代器的主要好处

• 为所有容器提供了一组很小的公共接口。

• 迭代器以++进行累进，以*进行提领，因而它类似于指针，我们可以把它视为一种smart pointer。比如++操作可以遍历至群集内的下一个元素。至于如何做到，取决于容器内部的数据组织形式。

• 每种容器都提供了自己的迭代器，而这些迭代器能够了解容器内部的数据结构。
  迭代器是一种智能指针，智能指针定义为存储指向动态分配对象指针的类，迭代器封装了指针的同时，还对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构。如operator++运算符，对于数组就是普通的++下一个元素，对于链表则是先去next，再取元素。

1.2.2 迭代器分类

在STL中原生指针也是一种迭代器，除此之外还有五种迭代器

Input Iterator：此迭代器不允许修改所指的对象，即是只读的。支持==、!=、++、*、->等操作。

Output Iterator：允许算法在这种迭代器所形成的区间上进行只写操作。支持++、*等操作。

Forward Iterator：允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持Input Iterator和Output Iterator的所有操作。

Bidirectional Iterator： 允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持Forward Iterator的所有操作，并另外支持–操作。

Random Access Iterator：包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下

vector 随机访问
deque 随机访问
list 双向
set 双向
multiset 双向
map 双向
multimap 双向
stack 不支持
queue 不支持
priority_queue 不支持

1.3 算法-Algorithm

1.3.1 定义

算法Algorithms，用来处理群集内的元素。它们可以出于不同的目的而搜寻、排序、修改、使用那些元素。通过迭代器的协助，我们可以只需编写一次算法，就可以将它应用于任意容器，这是因为所有的容器迭代器都提供一致的接口。

1.4 适配器-Adapter

1.4.1 定义

适配器是一种类，为已有的类提供新的接口，目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合

1.4.2 三种类型的适配器

容器适配器：用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器，stack，queue， priority_queue可以基于vector和deque，采用最大堆来实现，因为需要随机存取迭代器，只有这两个；

迭代器适配器（反向迭代器、插入迭代器、IO流迭代器）

函数适配器（函数对象适配器、成员函数适配器、普通函数适配器）

1.5 函数对象（仿函数）-function object

1.5.1定义

一个行为类似函数的对象，它可以没有参数，也可以带有若干参数，任何重载了调用运算符operator()的类的对象都满足函数对象的特征，函数对象可以把它称之为smart function。

STL中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象，需要包含头文件< functional>。

1.6 分配器-allocator（*）

1.6.1 定义

• 负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
• 隐藏在这些容器后的内存管理工作是通过STL提供的一个默认的allocator实现的。当然，用户也可以定制自己的allocator，只要实现allocator模板所定义的接口方法即可，然后通过将自定义的allocator作为模板参数传递给STL容器，创建一个使用自定义allocator的STL容器对象，如：
  stl::vector< int, UserDefinedAllocator> array;
• 大多数情况下，STL默认的allocator就已经足够了。这个allocator是一个由两级分配器构成的内存管理器，当申请的内存大小大于128byte时，就启动第一级分配器通过malloc/free直接向系统的堆空间分配，如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round
  up成8的倍数）从对应的空闲块列表取表头块给用户。

这种做法有两个优点
（1)小对象的快速分配。

• 小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。

(2)避免了内存碎片的生成。

• 程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。