vector源码2(参考STL源码--侯捷)
vector源码(参考STL源码--侯捷)-----空间分配导致迭代器失效
vector源码3(参考STL源码--侯捷):pop_back、erase、clear、insert
vector的构造和内存管理
vector所采用的数据结构非常简单：线性连续空间，它是由两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端：
class vector //详细源码可见
{
..........
protected:
typedef simple_alloc<value_type,Alloc> data_allocator; //simple_alloc是SGI STL的空间配置器
iterator start; //表示目前使用空间的头
iterator finish; //表示目前使用空间的尾
iterator end_of_storage; //表示目前可用空间的尾
..........
为了降低空间速配成本，vector的实际配置大小是原来容器大小的2倍，见下图：
#include<bits/stdc++.h>
using namespace std; int main(){
vector<int> v(,);
cout<<v.size()<<" "<<v.capacity()<<endl; //3 3
v.push_back();
cout<<v.size()<<" "<<v.capacity()<<endl; //4 6
v.push_back();v.push_back();v.push_back();
cout<<v.size()<<" "<<v.capacity()<<endl; //7 12 for(int i=;i<v.size();i++){ //3 3 3 5 6 7 8
cout<<v[i]<<' ';
}
cout<<endl; v.pop_back();v.pop_back();
cout<<v.size()<<" "<<v.capacity()<<endl; //5 12
v.pop_back();
cout<<v.size()<<" "<<v.capacity()<<endl; //4 12 vector<int>::iterator it=find(v.begin(),v.end(),);
if(it!=v.end())
v.erase(it);
cout<<v.size()<<" "<<v.capacity()<<endl; //3 12 it=find(v.begin(),v.end(),);
if(it!=v.end())
v.insert(it,,);
cout<<v.size()<<" "<<v.capacity()<<endl; //7 12 for(int i=;i<v.size();i++){ //7 7 7 7 3 3 3
cout<<v[i]<<' ';
}
cout<<endl; v.clear();
cout<<v.size()<<" "<<v.capacity()<<endl; //0 12
return ;
}vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位，data_allocator::deallocate(n)表示配置n个元素空间，vector提供许多constructors一个允许我们指定空间大小及初值。
/构造函数，允许指定vector大小n和初值value
vector(size_type n,const T& value){fill_initialize(n,value);}
//填充并初始化
void fill_initialize(size_type n,const T& value){ //用于vector初始赋值
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)
/*全局函数,uninitialized_fill_n()有3个参数：
迭代器first指向欲初始化空间的地址的起始处
*初始化空间的大小n
*初始化的值x*/
uninitialized_fill_n(result,n,x);
return result;
}
uninitialled_fill_n()会更根据第一参数类型来决定是使用算法fill_n()或反复调用construct()；fill_n()多用于初始化多个相同数据，construct()多用于插入一个数据。
当我们利用push_back()插入元素是，vector会先检查备用空间是否充足，如果充足，尾部插入数据，否则，先扩充空间，再插入数据，这里就要考虑到重新分配、移动数据、释放空间的问题。
void push_back(const T& x){//添加元素
if(finish !=end_of_storage)//是否超出最大可容纳空间{
/*全局函数，construct()接收一个指针p和一个初值value，该函数的用途就是将
初值value设定到指针锁指的空间上。
*/
construct(finish,x);
++finish;
}
else {
insert_aux(end(),x); //vector的成员函数
}
}
insert_aux ()的具体实现如下：
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-));
++finish;
T x_copy=x;
copy_backward(position,finish-,finish-);//将position到finish-2位置的元素后移到finish-1位置
*position=x_copy;
}
else{//已无备用空间
const size_type old_size=size();
const size_type len=old_size !=? *old_size:;
//以上配置原则：如果为0，则配置1，否则配置原来大小的2倍
iterator new_start=data_allocator::allocate(len);//实际配置
iterator new_finish=new_start;
try{
//将原vector元素拷贝过来
new_finish=uninitialized_copy(start,position,new_start);//迭代器start指向欲初始化空间的起始位置、迭代器position指向输入端的位置结束(前闭后开)、迭代器new_start指向输出端的起始位置
//为新元素设置初值
construct(new_finish,x);
++finish;
//将原vector的备用空间中的内容也从新拷贝过来
new_finish=uninitialized_copy(position,finish,new_finish);
}
catch(...){
destory(new_start,new_finish);
data_allocator::deallocate(new_start,len);
throw;
}
//析构释放原vector
destory(begin(),end());
deallocate();
//调整迭代器，指向新的vector
start=new_start;
finish=new_finish;
end_of_storage=new_start+len;
}
}可以看到，动态增加是直接开辟新的2倍的空间，进行数据的复制，而不是直接在原来vector后面开辟空间，因为无法保证其后面是否有足够空间，这也就说明指向原vector的所有迭代器就都失效了(查看示例)。
