vector 是动态数组，随着新元素的加入，它的内部会自行扩充空间以容纳新元素。
vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一如稍早所说，是“配置新空间/数据移动/释放旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。稍后我们便可看到 SGI vector 的空间配置策略。
以下是 vector 定义的源码摘录。SGI STL 将 vector 实现于更底层的 <stl_vector.h>。
// alloc 是 SGI STL 的空间配置器，见第二章
template <class T, class Alloc = alloc>
class vector {
public:
// vector 的嵌套类型定义
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
// simple_alloc 是 SGI STL 的空间配置器，见 2.2.4
typedef simple_alloc<value_type, Alloc> data_allocator;
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
void insert_aux(iterator position, const T& x);
void deallocate() {
if (start)
data_allocator::deallocate(start, end_of_storage - start);
}
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_t size() const { return size_type(end() - begin()); }
size_t capacity() const { return size_type(end_of_storage - begin()); }
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
vector() : start(0), finish(0), end_of_storage(0) { }
vector(size_type n, const T& value) { fill_initialize(n, value); }
vector(int n, const T& value) { fill_initialize(n, value); }
vector(long n, const T& value) { fill_initialize(n, value); }
explicit vector(size_type n) { fill_initialize(n, T()); }
~vector() {
destroy(start, finish); // 见 2.2.3
deallocate(); // member function
}
reference front() { return *begin(); } // 第一个元素
reference back() { return *(end() - 1); } // 最后一个元素
void push_back(const T& x) { // 将元素插入至最尾端
if (finish!= end_of_storage) {
construct(finish, x); // 见 2.2.3
++finish;
}
else
insert_aux(end(), x); // member function
}
void pop_back() { // 删除最后一个元素
--finish;
destroy(finish); // 见 2.2.3
}
iterator erase(iterator position) { // 删除指定位置的元素
if (position + 1 != end())
copy(position + 1, finish, position); // 后续元素向前移动
--finish;
destroy(finish); // 见 2.2.3
return position;
}
void resize(size_type new_size, const T& x) {
if (new_size < size())
erase(begin() + new_size, end());
else
insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }
protected:
// 配置空间并填满内容
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n);
uninitialized_fill_n(result, n, x); // 见 2.2.3
return result;
}
};普通指针可以作为 vector 的迭代器而满足所有必要条件。vector 支持随机存取，而普通指针正有这样的能力。所以，vector 提供的是 Random Access Iterator。
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; //vector 的迭代器是普通指针
...
};根据上述定义，如果写出这样的代码：
vector<int>::iterator ivite;
vector<Shape>::iterator svite;ivite 的类型其实就是 int*，svite 的类型其实就是 Shape*。
vector 所采用的数据结构是线性连续空间。它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端：
template <class T, class Alloc = alloc>
class vector {
...
protected:
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
...
};为了降低空间配置时的速度成本，vector 实际配置的大小可能比用户需求量更大一些，以备扩充。这便是容量的观念。一旦容量等于大学奥，便是满载。下次再有新增元素，整个 vector 就扩容。
运用 start, finish, end_of_storage 这三个迭代器，就可以很容易的提供首位标示、大小、容量、空容器判断、下标运算符、最前端数值、最后后端数值等功能。
vector 缺省使用 alloc 作为空间配置器，并据此另外定义了一个 data_allocator，为的是更方便以元素大小为配置单位：
template <class T, class Alloc = alloc>
class vector {
...
protected:
// simple_alloc<> 见 2.2.4
typedef simple_alloc<value_type, Alloc> data_allocator;
...
};于是，data_allocator::allocate(n) 表示配置 n 个元素的空间。
vector 提供许多 ctors，其中一个允许我们指定空间大小及初值：
// 构造函数，允许指定 vector 大小 n 和初值 value
vector(size_t n, const T& value) { fill_initialized(n, value); }
// 填充并予以初始化
void fill_initialized(size_t n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
// 配置而后填充
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n); // 配置 n 个元素的空间
uninitialized_fill_n(result, n, x); // 全局函数，见 2.3
return result;
}uninitialized_fill_n() 会根据第一参数的类型特性决定使用 fill_n() 或 construct() 来完成任务（见 2.3）。
当我们以 push_back() 将新元素插入 vector 尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 finish，使 vector 变大。如果没有备用空间，就扩充空间。
void push_back(cont T& x) {
if (finish != end_of_storage) { // 还有备用空间
construct(finish, *(finish - 1)); // 将元素构造到备用空间 见 2.2.3
++finish; // 调整迭代器
}
else // 没有备用空间
insert_aux(end(), x); // member function
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
if (finish!= end_of_storage) { // 还有备用空间
// 在备用空间起始处构造一个元素，并以 vector 最后一个元素值为其初值
construct(finish, *(finish - 1));
++finish; // 调整迭代器
T x_copy = x;
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
}
else { // 已无备用空间
const size_type old_size = size();
const size_type len = old_size!= 0? 2 * old_size : 1;
// 配置原则：如果原大小为 0，则配置 1
// 如果原大小不为 0，则配置原大小的两倍
// 前半段用来放置数据，后半段准备用来放置新数据
iterator new_start = data_allocator::allocate(len); // 实际配置
iterator new_finish = new_start;
try {
// 将原 vector 的内容拷贝到新 vector
new_finish = uninitialized_copy(start, position, new_start);
// 为新元素设定初值 x
construct(new_finish, x);
// 调整迭代器
++new_finish;
// 将按插点的原内容也拷贝过来 （提示：该函数也可能被 insert(p, x) 调用）
new_finish = uninitialized_copy(position, finish, new_finish);
} catch (...) {
// "commit or rollback" semantics
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
// 析构并释放原 vector
destroy(begin(), end());
deallocate();
//调整迭代器，指向新 vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}动态增加大小，是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后再原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。
// 将尾端元素拿掉， 并调整大小
void pop_back() {
--finish; // 将尾端标记往前一格，表示放弃尾端元素
destroy(finish); // 见第二章
}
// 清除 [first, last) 中的所有元素
void erase(iterator first, iterator last) {
iterator i = copy(;ast, finish, first); // 见第六章
destroy(i, finish); // 见第二章
finish = finish - (last - first);
return first;
}
// 清除某个位置上的元素
iterator erase(iterator position) {
if (position + 1 != end())
copy(position + 1, finish, position);
--finish;
destroy(finish);
return position;
}
void clear() { erase(begin(), end()); }
// 从 position 开始，插入 n 个元素，元素初值为 x
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const value_type& x) {
if (n != 0) { // 当 n != 0 时才进行以下所有操作
if (size_type(end_of_storage - finish) >= n) { // 如果大小足够
T x_copy = x;
// 以下计算插入点之后的现有元素个数
const size_type elems_after = finish - position;
iterator old_finish = finish;
if (elems_after > n) { // 如果插入点之后的元素个数大于新增元素个数
uninitialized_copy(finish - n, finish, finish);
finish += n; // 将 vector 尾端标记后移
copy_backward(position, old_finish - n, old_finish);
fill(position, position + n, x_copy); // 从新插入点开始填入新值
}
else {
// 插入点之后的现有元素个数小于等于新增元素个数
uninitialized_fill_n(finish, n - elems_after, x_copy);
finish += n - elems_after;
uninitialized_copy(position, old_finish, finish);
finish += elems_after;
fill(position, old_finish, x_copy);
}
}
else {
// 备用空间小于新增元素个数
// 首先按决定新长度：旧长度的两倍，或就长度+新元素个数
const size_type old_size = size();
const size_type len = old_size + max(old_size, n);
// 以下配置新的 vector 空间
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
// 首先将旧 vector 的插入点之前的元素复制到新空间
new_finish = uninitialized_copy(start, position, new_start);
// 再将新增元素填入新空间
new_finish = uninitialized_fill_n(new_finish, n, x_copy);
// 再将旧 vector 的插入点之后的元素复制到新空间
new_finish = uninitialized_copy(position, finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
// "commit or rollback" semantics
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
// 删除旧 vector
destroy(start, finish);
deallocate();
// 更新 vector 的开始点和结束点
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}注意，插入完成后，新节点位于 position 节点的前方。
