常用的数据结构：array\list\tree\stack\queue\hash table\set\map…
1.1 vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。因为“配置新空间/数据移动/释放旧空间”是一个大工程。
1.2 vector的迭代器提供的是Random Access Iterators。
`typedef value_type* iterator; //vector的迭代器是普通的指针`1.3 vector所采用的数据结构：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端。
注意①：增加新元素（s）时，如果超过当时的容量，则容量会扩充至两倍。如果两倍容量仍不足，就扩充至足够大的容量。
②：容量的扩张必须经历“重新配置、元素移动、释放原空间”等过程。
2.1 list的节点(node)
//是个双向链表 template <class T> struct __list_node { typedef void* void_pointer; void_pointer prev; //型别为void*，其实可以设为__list_node<T>* void_pointer next; T data; }2.2 list的迭代器是Bidirectional iterator。由于STL list是一个双向链表，还是一个环状双向链表，迭代器必须具备前移、后移的能力，并有能力进行正确的递增、递减、取值、成员存取等操作。
list的一个重要性质：插入操作和接合操作都不会造成原有的list迭代器失效，甚至list的元素删除操作，只有“指向被删除元素”的那个迭代器失效，其他的迭代器不受影响。
2.3 list内部提供一个所谓的迁移操作(transfer)：将某连续范围内的元素迁移到某个特定位置之前。
//将[first,last)内的所有元素移动到position之前 void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { // Remove [first, last) from its old position. __last._M_node->_M_prev->_M_next = __position._M_node; __first._M_node->_M_prev->_M_next = __last._M_node; __position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position. _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } }deque是一种双向开口的连续线性空间。虽然deque也提供Ramdon Access Iterator，但它的迭代器并不是普通指针。
3.1 deque和vector的差异：
1）deque允许与常数时间内对起头端进行元素的插入或移除操作。
2）deque没有所谓容量(capacity)观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
3）deque系由一段一段的定量连续空间构成，一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置，复制，释放”的轮回，代价则是复杂的迭代器架构。
4）deque采用一块所谓的map作为主控，这里所谓map是一小块连续空间，其中每个元素都是指针，指向另外一段（较大的）连续线性空间，称为缓冲区。当map使用率已近满载，便需要再找一块更大的空间来作为map,配置策略为reallocate_map()。
3.2 deque的迭代器：
1）假设现在产生一个deque<int>,并令其缓冲区大小为32，于是每个缓冲区可容纳32/sizeof(int)=8个元素，经过某些操作之后，deque拥有20个元素，那么begin()和end()所传回的两个迭代器应该如下图。这两个迭代器事实上一直保持在deque内，名为start和finish。20个元素需要20/3=8个缓冲区，所以map使用了三个节点，迭代器start内的cur指针指向缓冲区的第一个元素，迭代器finish内的cur指向缓冲区的最后元素（的下一位置）。注意，最后一个缓冲区尚有备用空间，稍后如果有新的元素要插入尾端，可直接拿此备用空间来使用。
2）deque迭代器最关键的就是：一旦行进到缓冲区边缘，视前进或后退而定，可能需要调用set_node()跳一个缓冲区：
void set_node(map+pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); }3.3 deque的数据结构：
3.4 deque的构造与内存管理：
3.5 deque的元素操作：pop_back,pop_front,erase,insert
stack是一种先进后出(First In Last Out,FILO)的数据结构。它只有一个出口，stack允许新增元素、移除元素、取得最顶端元素。但除最顶端外，没有其他方法可以存取stack的其他元素。换言之，stack不允许有遍历的行为。
SGI STL便以deque作为缺省情况下的stack底部结构。由于stack是以底部容器deque完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter（配接器）,因此，STL stack往往不被归类为container（容器），而被归类为container adapter。
queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口。queue允许新增元素、移除元素、从底端加入元素、取得最顶端元素（queue不允许有遍历行为）。
1）heap并不属于STL容器组件，扮演priority queue的助手，priority queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先级最高（也就是数值最高）的元素开始取。binary max heap 正是具有这样的特性，适合作为priority queue的底层机制。
2）以array表达tree的方式，称为隐式表述法（implicit representation）。这样就可以使用一个array和一组heap算法（用来插入元素、删除元素、取极值，将某一组数据排列成一个heap）。array的缺点是无法动态的改变大小，因此可以使用vector代替。STL供应的是max-heap。
3）push_heap算法：
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. //执行percolate up（上溯）程序 template <class _RandomAccessIterator, class _Distance, class _Tp> void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value) { _Distance __parent = (__holeIndex - 1) / 2; while (__holeIndex > __topIndex && *(__first + __parent) < __value) { *(__first + __holeIndex) = *(__first + __parent); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = __value; }4）pop_heap算法:
//执行percolate down（下溯） template <class _RandomAccessIterator, class _Distance, class _Tp> void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { _Distance __topIndex = __holeIndex; _Distance __secondChild = 2 * __holeIndex + 2; while (__secondChild < __len) { if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) __secondChild--; *(__first + __holeIndex) = *(__first + __secondChild); __holeIndex = __secondChild; __secondChild = 2 * (__secondChild + 1); } if (__secondChild == __len) { *(__first + __holeIndex) = *(__first + (__secondChild - 1)); __holeIndex = __secondChild - 1; } __push_heap(__first, __holeIndex, __topIndex, __value); }注意：pop_heap之后，最大元素只是被置放于底部容器的最尾端，尚未被取走，如果要取其值，可使用底部容器(vector)所提供的back()操作函数，如果要移除它，可以使用底部容器(vector)所提供的pop_back()操作的函数。
5）sort_heap算法：
因为每次pop_heap可获得heap中键值最大的元素，如果持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素（因为pop_heap会把键值最大的元素放在底部容器的最尾端），当整个程序执行完毕时，便有了一个递增的序列。
注：之前的版本，没有class _Compare选项，不允许指定“大小比较标准”，现在可以通过_Compare来设定比较标准。
template <class _RandomAccessIterator, class _Compare> void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); while (__last - __first > 1) pop_heap(__first, __last--, __comp); }这里g++编译器和vc++编译器，有不同的做法，对于g++,只是把pop出来的放在尾端，而vc++对于不是堆的vector，编译能通过，执行时会报错。
6）make_heap算法：
对于make_heap有两种函数重载，可指定“大小比较标准”：
template <class _RandomAccessIterator, class _Compare> inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)和默认“大小比较标准”：
template <class _RandomAccessIterator> inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)核心算法为：
template <class _RandomAccessIterator, class _Compare, class _Tp, class _Distance> void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; _Distance __parent = (__len - 2)/2; while (true) { __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)), __comp); if (__parent == 0) return; __parent--; } }概念：priority_queue是一个拥有权值观念的queue，它允许加入新元素、移除旧元素、审视新元素等功能。由于是一个queue，所以只能在底端加入元素，在顶端取出元素。
priority_queue带有权值概念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列。缺省情况下，priority_queue利用一个max-heap完成。
slist概述:STL list是个双向链表，迭代器属于双向的Bidirectional iterator，而SGI STL另提供了一个单向链表，名为slist，迭代器属于单向的Forward iterator。
注意：slist的插入顺序，完全是倒序的！
附录：STL源码： http://www.sgi.com/tech/stl/download.html
