STL容器和算法

1、C++的STL介绍（内存管理、allocator、函数、实现机理、多线程实现）

STL一共提供六大组件，包括容器、算法、迭代器、仿函数、配接器和配置器，彼此可以组合套用。容器通过配置器取得数据存储空间，算法通过迭代器存取容器内容，仿函数可以协助算法完成不同的策略变化，配接器可以应用于容器、仿函数和迭代器。

容器：各种数据结构，如vector、list、deque、set、map，用来存放数据，从实现的角度来讲是一种类模板。

算法：各种常用的算法，如sort（插入、快排、堆排序），search（二分查找），从实现的角度来讲是一种方法模板。

迭代器：从实现的角度来看，迭代器是一种将operator*，operator->，operator++，operator--等指针相关操作赋予重载的类模板，所有的STL容器都有自己的迭代器。

仿函数：从实现的角度来看，仿函数是一种重载了operator()的类或者类模板。可以帮助算法实现不同的策略。

配接器：一种用来修饰容器或者仿函数或迭代器接口的东西。

配置器：负责空间配置与管理，从实现的角度讲，配置器是一个实现了动态空间配置、空间管理、空间释放的类模板。

拓展：内存管理allocator

SGI设计了双层级配置器，第一级配置器直接使用malloc()和free()完成内存的分配和回收。第二级配置器则根据需求量的大小选择不同的策略执行。

对于第二级配置器，如果需求块大小大于128bytes，则直接转而调用第一级配置器，使用malloc()分配内存。如果需求块大小小于128bytes，第二级配置器中维护了16个自由链表，负责16种小型区块的次配置能力。

即当有小于128bytes的需求块要求时，首先查看所需需求块大小所对应的链表中是否有空闲空间，如果有直接返回，如果没有，则向内存池中申请所需需求块大小的内存空间，如果申请成功，则将其加入到自由链表中。如果内存池中没有空间，则使用malloc()从堆中进行申请，且申请到的大小是需求量的二倍（或二倍+n附加量），一倍放在自由空间中，一倍（或一倍+n）放入内存池中。

如果malloc()也失败，则会遍历自由空间链表，四处寻找“尚有未用区块，且区块够大”的freelist，找到一块就挖出一块交出。如果还是没有，仍交由malloc()处理，因为malloc()有out-of-memory处理机制或许有机会释放其他的内存拿来用，如果可以就成功，如果不行就报bad_alloc异常。

STL中序列式容器的实现：

vector：是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。vector维护的是一个连续的线性空间，而且普通指针就可以满足要求作为vector的迭代器（RandomAccessIterator）。vector的数据结构中其实就是三个迭代器构成的，一个指向目前使用空间头的iterator，一个指向目前使用空间尾的iterator，一个指向目前可用空间尾的iterator。当有新的元素插入时，如果目前容量够用则直接插入，如果容量不够，则容量扩充至两倍，如果两倍容量不足，就扩张至足够大的容量。

扩充的过程并不是直接在原有空间后面追加容量，二十重新申请一块连续空间，将原有的数据拷贝到新空间中，再释放原有空间，完成一次扩充。需要注意的是，每次扩充是重新开辟的空间，所以扩充后，原有的迭代器会失效。

List：与vector相比，list的好处就是每次插入或删除一个元素，就配置或释放一个空间，而且原有的迭代器也不会失效。STL list是一个双向链表，普通指针已经不能满足list迭代器的需求，因为list的存储空间是不连续的。list的迭代器必需具备前移和后退功能，所以list提供的是Bidirectionallterator。list的数据结构中只要一个指向node节点的指针就可以了。

deque：vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。所谓双向开口，就是说deque支持从头尾两端进行元素的插入和删除操作。相比于vector的扩充空间的方式，deque实际上更加贴切的实现了动态空间的概念。deque没有容量的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并连接起来。

由于要维护这种整体连续的假象，并提供随机存取的接口（即也提供RandomAccessIterator），避开了“重新配置，复制，释放”的轮回，代价是复杂的迭代器结构。也就是说除非必要，我们应该尽可能的使用vector，而不是deque。

那么我们回过来具体说deque是如何做到维护整体连续的假象的，deque采用一块所谓的map作为主控，这里的map实际上就是一块大小连续的空间，其中每一个元素，我们称为节点node，都指向了另一端连续线性空间称为缓冲区，缓冲区才是deque的真正存储空间主体。

SGI STL是允许我们指定缓冲区的大小的，默认0表示使用512bytes缓冲区。当map满载时，我们选用一块更大的空间来作为map，重新调整配置。deque另外一个关键的就是它的iterator的设计，deque的iterator中四个部分，cur指向缓冲区现行元素，first指向缓冲区的头，last指向缓冲区的尾（有时会包含备用空间），node指向管控中心。所以总结来说，deque的数据结构中包含了指向第一个节点的iterator start，和指向最后一个节点的iterator finish，一块连续空间作为主控map，也需要记住map的大小，以备判断何时配置更大的map。

stack：是一种先进后出的数据结构，只有一个出口，stack允许从最顶端新增元素，移除顶端元素，取得最顶端元素。deque是双向开口的数据结构，所以使用deque作为底部结构并封存器头端开口，就形成了一个stack。

queue：是一种先进先出的数据结构，有两个出口，允许从最低端加入元素，取得最顶端元素，从最底端新增元素。就形成了一个queue。（其实list也可以实现deque）

heap：堆并不属于STL容器组件，它是个幕后英雄，扮演priority_queue的助手，priority_queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高（数值最高）的元素开始取。大根堆（binary max heap）正具有这样的性质，适合作为priority_queue的底层机制。

大根堆是一个满足每个节点的键值都大于或等于其子节点键值的二叉树（具体实现是一个vector，一块连续空间，通过维护某种顺序来实现这个二叉树），新加入元素时，新加入的元素要放在最下一层为叶节点，即具体实现是填补在由左至右的第一个空格（即把新元素插入在底层vector的end()），然后执行一个所谓上溯的程序：将新节点拿来与父节点比较，如果其键值比父节点大，就父子对换位置，如此一直上溯，知道不需要对换或直到根节点为止。当取出一个元素时，最大值在根节点，取走根节点，要割舍最下层最右边的右节点，并将其值重新安插至最大堆，最末节点放入根节点，进行一个下溯程序：将空间节点和其较大的节点对调，并持续下方，知道叶节点为止。

priority_queue：底层时一个vector，使用heap形成的算法插入，获取heap中元素的算法，维护这个vector，以达到允许用户以任何次序将任何元素插入容器内，但取出时一定是从优先权最高（数值最高）的元素开始区的目的。

slist：STL list是一个双向链表，slist是一个单向链表。