STL vector实现机制

vector的数据安排以及操作方式与array非常类似。两者的唯一差别在于空间的运用的灵活性。
array是静态空间，一旦配置好了就不能再改变了。如果程序需要一个更大空间的array，只能自己再申请一个更大的array，然后将以前array中的内容全部拷贝到新的array中。
vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新的元素。
vector的关键技术在于其对大小的控制以及重新配置时的数据移动效率。

原文链接：http://blog.csdn.net/linux_ever/article/details/50974924
vector采用的数据结构很简单：线性的连续空间。
它以两个迭代器start和finish分别指向配置得来的连续空间中目前已经被使用的空间。迭代器end_of_storage指向整个连续空间的尾部。
为了降低空间配置时候的速度，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。
如果vector在增加一个元素的时候，超过了自身最大的容量。vector则将自身的容量扩充至原来的两倍。
扩充空间需要经过的步骤：重新配置空间，元素移动，释放旧内存空间。（vector机制将旧空间中的备用空间也拷贝到新空间来了，感觉没必要）
一旦vector空间重新配置，则指向原来vector的所有迭代器都失效了，因为vector的地址改变了。
1、Vector是顺序容器，是一个动态数组，支持随机存取、插入、删除、查找等操作，在内存中是一块连续的空间。在原有空间不够情况下自动分配空间。vector随机存取效率高，但是在vector插入元素，需要移动的数目多，效率低下。
2、Map是关联容器，以键值对的形式进行存储，方便进行查找。关键词起到索引的作用，值则表示与索引相关联的数据。以红黑树的结构实现，插入删除等操作都在O(logn)时间内完成
3、Set是关联容器，set中每个元素只包含一个关键字。set支持高效的关键字查询操作——检查一个给定的关键字是否在set中。set也是以红黑树的结构实现，支持高效插入、删除等操作
在c++ STL中，当调用clear()成员函数时，并没有释放内存，clear只是将数组中的元素置为空了。释放内存需要delete。