本文涉及到 SGI STL 源码的文件有vector、stl_vector.h、vector.h 等几个文件。
1. 容器
在数据结构的课程中，我们主要研究数据的特定排列方式，以利于搜索、排序等算法，几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL 容器即由一个个特定的数据结构组成，例如向量（vector），链表（list），堆栈（stack），队列（queue），树（tree），哈希表（hash table），集合（set），映射（map）等，根据数据在容器中的排列特性，这些数据接口分为序列式容器（sequence container）和关联式容器（association container）两种，本文主要解读SGI STL中的序列式容器。
所谓序列式容器，其中的元素可序（ordered），但未必有序（sorted）。C++ 本身提供了一个序列式容器——数组（array），STL中还提供了向量（vector），链表（list），堆栈（stack），队列（queue），优先队列（priority queue）等，其中stack和queue只是将deque（双端队列）设限而得到的，技术上可以被归为一种配接器（adaptor）。本系列文章将依次解读SGI STL各容器的关键实现细节。
2. vector 及其数据结构
在STL中，vector的空间在物理上就是连续的，而且是可以动态扩展的，这里的动态扩展，不需要用户去处理溢出的问题，而只需要关心上层逻辑。vector连续物理空间的动态扩展技术是该容器的关键，它主要分为三个步骤：配置新空间，数据移动，释放旧空间。这三个步骤执行的次数以及每次执行时的效率是影响最终 vector 效率的关键因素。为了减少执行的次数，就需要未雨绸缪，每次扩充空间时，成倍增长。而每次执行的效率，就主要是数据移动的效率了。下面，我们依次介绍vector的数据结构，使用的空间配置器和迭代器，以及常用操作。
vector 的数据结构
vector的数据结构很简单，就是一段连续的物理空间，包含起止地址以及已用到的空间的末尾地址这三个成员：
cpp
template <class _Tp, class _Alloc>
class _Vector_base {
protected:
_Tp* _M_start;
_Tp* _M_finish;
_Tp* _M_end_of_storage;
};
class vector : protected _Vector_base<_Tp, _Alloc>{
};
其中 _M_finish 是当前使用到的空间的结束地址，而 _M_end_of_storage 是可用空间的结束地址，前者小于等于后者，当新加入元素使得前者大于后者之后，就需要进行空间扩充了。
3. vector 的配置器
vector的空间配置器 STL 默认的 alloc 即 __default_alloc_template 配置器，即第二级配置器，它对于 POD(plain old data) 类型数据使用内建内存池来应对内存碎片问题，关于该默认配置器的更多介绍请参见本系列第2篇文章 深入理解STL源码(1) 空间配置器 . 除此之外，SGI vector 还定义了一个 data_allocator，为的是更方便的以元素大小为配置单位：
cpp
template <class _Tp, class _Alloc>
class _Vector_base // vector 继承了该基类
protected:
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
}
关于 simple_alloc 的内容见前面的文章，它其实就是简单的对 malloc 等的加一层封装。
vector的内存是在vector的构造或析构、插入元素而容量不够等情况下，需要进行配置。vector 提供了很多的构造函数，具体可见源代码，而更详细的列表并涉及各个版本的说明的列表可以参见C++的文档：cpp references.
4. vector 的迭代器
由于vector使用的物理连续的空间，需要支持随机访问，所以它使用的随机访问迭代器（Random Access Iterators）。也正由于vector使用连续物理空间，所以不论其元素类型为何，使用普通指针就可以作为它的迭代器：
cpp
public:
typedef _Tp value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
注意：vector中所谓的动态增加大小，并不是在原空间之后接连续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后再在其后构造新元素，最后释放原空间。因此，对于vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就失效了，这是vector使用中的一个大坑，务必小心。
5. vector 的常用操作
vector所提供的元素操作很多，这里选取几个常用操作介绍一下。
（1）push_back
cpp
public void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, __x);
++_M_finish;
}
else
_M_insert_aux(end(), __x); // auxiliary insert
}
其中辅助的insert函数的基本逻辑为：按原空间大小的两倍申请新空间，复制原数据到新空间，释放原空间，更新新vector的数据结构的成员变量。
（2）insert
cpp
public iterator insert(iterator __position, const _Tp& __x) {
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end()) {
construct(_M_finish, __x);
++_M_finish;
}
else
_M_insert_aux(__position, __x);
return begin() + __n;
}
与push_back类似，只是push_back 在最后插入，更为简单。insert 首先判断是否为在最后插入且容量足够，如果是最后插入且容量足够就就直接内部实现了。否则还是调用上面的辅助插入函数，该函数中首先判断容量是否足够，容量足的话，先构造一个新元素并以当前vector的最后一个元素的值作为其初始值，然后从倒数第二个元素开始从后往前拷贝，将前一元素的值赋给后一元素，知道当前插入位置。
(3)erase
cpp
public iterator erase(iterator __first, iterator __last) {
iterator __i = copy(__last, _M_finish, __first);
destroy(__i, _M_finish);
_M_finish = _M_finish - (__last - __first);
return __first;
}
与insert相反，该函数将某些连续的元素从vector中删除，所以不存在容量不足等问题，但也不会将没有使用的空间归还给操作系统。这里只有简单的元素拷贝（copy）和元素的析构（destroy）。另外，需要说明的是，对于vector而言clear函数和erase函数是等同的，都只清空对应内存块的值，而不将空间归还给操作系统，所以vector的容量是只增不减的。而对于其他一些容器就有所不同了，比如list之类以node为单位的数据结构。
关于vector的内容就介绍到这里了。