STL Vector 底层原理与核心接口详解
1. Vector 概述
Vector 的数据安排以及操作方式于 array 非常相似，二者唯一差别在于对空间的灵活运用。 Array 是静态空间，一旦配置，不能改变，用户要重新配置空间，移动元素，释放旧空间。Vector 的内部机制会自行扩充空间。 因此 Vector 给我们带来了很大的灵活性，不用担心空间不够用而去开一个大 Array。 Vector 的技术实现在于对大小的控制以及数据分配时的移动效率。
引：如果旧空间用满了，每加一个元素就扩容（配置新空间，挪动数据，释放旧空间），时间成本高，实为不智，所以应有未雨绸缪的考虑。
2. Vector 的迭代器
Vector 维护的是一个连续的线性空间，普通的指针可以满足要求，操作行为如：operator*, operator->, operator++, operator--, operator+, operator-, operator+=, operator-=。Vector 支持随机存取，而普通指针正有这样的能力。
底层代码：
// vector 的迭代器
template<class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; // vector 的迭代器是普通指针
// ...
};
3. Vector 的数据结构
非常简单，呈现连续空间，用两个迭代器 start，finish 分别指向配置得来的连续空间被已使用的范围，用迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端：其实就是最后一个空间的下一个位置。
底层代码：
template<class T, class Alloc = alloc>
class vector {
// ...
protected:
iterator start; // 目前使用空间的头
iterator finish; // 目前使用空间的尾
iterator end_of_storage; // 目前可用空间的尾
};
为降低空间配置速度成本，Vector 实际配置的大小可能比用户需求更大，以备扩容，这就是容量（capacity），Vector 的容量大于等于其大小。 运用 start, finish, end_of_storage 三个迭代器可以容易实现大小，容量，首尾，判断，[], begin(), end()……
底层代码：
// 用 start, finish, end_of_storage 实现
template< , = alloc>
vector {
:
iterator () { start; }
{ finish; }
{ (() - ()); }
{ (end_of_storage - ()); }
{ () == (); }
reference [](size_type n) { *(() + n); }
{ *(); }
{ *(() - ); }
};
