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 提供的是BidirectionalIterator。 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
是⼀种先进先出的数据结构，有两个出⼝，允许从最底端加⼊元素，取得最顶端元素，从最底 端新增元素，从最顶端移除元素。 deque 是双向开⼝的数据结构，若以 deque 为底部结构并封闭其底端的出口，和头端的⼊⼝，就形成了⼀个 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 是⼀个单向链表。