vevtor与array非常相似，两者唯一差别在于空间运用的灵活性。array是静态空间，一旦配置了就不能改变；vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
vector的实现技术关键在于其对大小的控制以及重新配置时数据移动效率。一旦vector旧有空间满载，如果客户端每新增一个元素，vector内部知识扩充一个元素的空间，实为不智，因为所谓扩充空间，是”配置新空间/移动数据/释放旧空间”的大工程，时间成本很高，故应该加入某种未雨绸缪的考虑。
vector迭代器
vector维护的是一个连续线性空间。它提供的是Random Access Iterators，普通指针都可作为vector的迭代器。
template<class T, class Alloc= alloc>
classvector{
public:
typedef T value_type;
typedef value_type* iterator; //vector的迭代器时普通指针
...
};
根据上述定义，如果客户端写出这样的代码:
vector<int>::iterator ivite;
vector<Shape>::iterator svite;
ivite的型别其实就是int*,svite的型别其实就是Shape*。
vector的数据结构
vector所采用的数据结构非常简单:线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间的尾端。
template<class T, class Alloc= alloc>
classvector{
...
protected:
iteratorstart; //表示目前使用空间的头
iteratorfinish; //表示目前使用空间的尾
iteratorend_of_storage;//表示目前可使用空间的尾
...
};
可运用上面三个迭代器轻松实现以下vector的成员函数：
template<class T, class Alloc= alloc>
classvector{
...
public:
iteratorbegin(){ return start;}
iteratorend(){ return finish;}
size_typesize() const{ returnsize_type(end() - begin());}
size_typecapacity() const{
returnsize_type(end_of_storage - begin());}
bool empty(){ returnbegin() == end();}
referenceoperator[](size_type n){ return *(begin() + n);}
referencefront(){ return *begin();}
referenceback(){ return *end();}
...
};vector的构造与内存管理：constructor,push_back
vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是方便元素大小为配置单位：
template<class T, class Alloc= alloc>
classvector{
protected:
typedef simple_alloc<value_type, Alloc>data_allocator;
...
};
vector提供了许多constructors，其中一个允许我们制定空间大小及初值：
//构造函数，允许指定vector大小n和处置value
vector<size_type n,const T& value>{ fill_initialize(n,value);}
//填充并予以初始化
voidfill_initialize(size_type 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)
{
iteratorresult = data_allocator::allocate(n);
uninitialize_fill_n(result,n, x);
return result;
}
当我们以push_back()将新元素插入vector尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩充空间（重新配置、移动数据、释放空间）：
// 增加一个元素作为最后元素
void push_back(const T& x) {
if (finish !=end_of_storage) { // 还有备用空间
construct(finish,x); // 直接在备用空间将元素，全局函数
++finish; // 调整水位
}
else // 已无备用空间
insert_aux(end(),x);
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iteratorposition, const T& x) {
if (finish !=end_of_storage) { //还有备用空间
//在备用空间起始处构造一个元素，并以vectror最后一个元素值为其初值
construct(finish,*(finish - 1));
// 调整水位
++finish;
//在position后面元素向后移动，并在position插入元素
T x_copy = x;
copy_backward(position,finish - 2, finish - 1);
*position = x_copy;
}
else { //已无备用空间
const size_typeold_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;
__STL_TRY {
// 将原vector的内容拷贝到新vector
new_finish = uninitialized_copy(start,position, new_start);
// 为新元素设定初值x
construct(new_finish,x);
// 调整水位
++new_finish;
//将安插点的原内容也拷贝过来
new_finish = uninitialized_copy(position,finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
// "commitor rollback" 语意：若非全部成功，则一个不留
destroy(new_start,new_finish);
data_allocator::deallocate(new_start,len);
throw;
}
# endif /*__STL_USE_EXCEPTIONS */
// 析构并释放vector
destroy(begin(),end());
deallocate();
// 调整迭代器，指向vector
start = new_start;
finish = new_finish;
end_of_storage =new_start + len;
}
}注意，所谓动态增加大小，并不是在原空间之后持续新空间，而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。
vector的元素操作：pop_back,erase,clear,insert
//将尾端元素拿掉，并调整大小
void pop_back() {
--finish;
destroy(finish);
}
//清除[first,last]中的所有元素
iterator erase(iteratorfirst, iterator last) {
iterator i =copy(last, finish, first); //copy是全局函数
destroy(i,finish); //全局函数
finish = finish - (last - first);
return first;
}
//清除某个位置上的元素
iterator erase(iterator position) {
if (position + 1 !=end()) //如果p不是指向最后一个元素
//将p之后的元素一一向前移动
copy(position + 1, finish, position);
--finish; // 调整水位
destroy(finish); // 全局函数
return position;
}
//清除全部元素。注意并未释放空间，以备未来可能还有加入新元素
void clear() { erase(begin(),end()); }
下图展示了erase[first,last]的操作
下面是vector::insert的实现内容：
//从position开始，插入n个元素，元素初值为x
template <class T, class Alloc>
void vector<T, Alloc>::insert(iteratorposition, size_type n, const T& x) {
if (n != 0) { //当n！=0才进行以下所有操作
if(size_type(end_of_storage - finish) >= n) {
// 备用空间大于等于“新增元素个数”
T x_copy = x;
// 以下计算插入点之后的现有元素个数
const size_typeelems_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_typeold_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);
//以下首先将就vector的插入点之后的元素复制到新空间
new_finish = uninitialized_copy(position,finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
//如果异常发生，实现 "commitor rollback" semantics.
destroy(new_start,new_finish);
data_allocator::deallocate(new_start,len);
throw;
}
# endif /*__STL_USE_EXCEPTIONS */
// 以下清除并释放旧的vector
destroy(start,finish);
deallocate();
// 以下调整水位
start = new_start;
finish = new_finish;
end_of_storage =new_start + len;
}
}
}
原文：http://blog.csdn.net/walkerkalr/article/details/22720367
