【C++ STL】序列式容器Vector
1. vector概述
vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于array是静态分配，一旦配置就不能改变。而vector是动态空间分配，随着元素的加入，它的内部机制会自动扩展空间来容纳新元素。Vector实现的技术，关键在于其对大小的控制以及当空间重新配置时数据的移动效率。一旦vector旧空间满载，如果客户端在每新增一个元素，vector内部只是重新分配一个元素空间，实不明智，因此，在vector内部的设计机制中加入了未雨绸缪的考虑。
2.vector的函数列表
为了可以使用vector，必须在你的头文件中包含下面的代码：
#include <vector>
Vectors 包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。
函数列表如下:
Constructors 构造函数
Operators 对vector进行赋值或比较
assign() 对Vector中的元素赋值
at() 返回指定位置的元素
back() 返回最末一个元素
begin() 返回第一个元素的迭代器
capacity() 返回vector所能容纳的元素数量(在不重新分配内存的情况下）
clear() 清空所有元素
empty() 判断Vector是否为空（返回true时为空）
end() 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
erase() 删除指定元素
front() 返回第一个元素
get_allocator() 返回vector的内存分配器
insert() 插入元素到Vector中
max_size() 返回Vector所能容纳元素的最大数量（上限）
pop_back() 移除最后一个元素
push_back() 在Vector最后添加一个元素
rbegin() 返回Vector尾部的逆迭代器
rend() 返回Vector起始的逆迭代器
reserve() 设置Vector最小的元素容纳数量
resize() 改变Vector元素数量的大小
size() 返回Vector元素数量的大小
swap() 交换两个Vector
3.vector的迭代器
vector维护的是一个连续线性空间，所以vector不论其元素型别为何、普通指针都可以作为vector的迭代器，因为vector迭代器所需要的操作行为，如operator *，operator ->， operator --，opeartor++,operator -=,普通指针天生都具备，所以vector提供的是random
Access Iterators。
源码如下：
template<class T>
class Vector{
typedef T value_type;
typedef T* iterator;
......
};
如果客户端写出如下定义：
vector<double>::iterator dVec;
vector<Shape>::iterator sVec;
则dvec的型别为double*,sVec的型别为Shape*;
4.vector的数据结构
vetcor所采用的数据结构非常简单:连续线性空间，它以两个迭代器类型start和finish来分别表示vetcor分配的空间的开始位置和结束位置，迭代器end_of_storage表示配置的空间未使用的空间的尾端即备用空间，
template<class T,class Alloc=alloc>
class Vector{
........
iterator start;
iterator finish;
iterator end_of_storage;
.........
};
因此运用start,finish,end_of_storage可以很方便的获得首尾标识，vector的大小（finish-start）,vector的容量（end_of_storage-start）,空容器判断，最前端元素值，最后端元素值，
template<class T,class Alloc=alloc>
class vector{
. ......
iterator begin(){
return start;
}
iterator end(){
return end;
}
size_type size()const{
return size_type(end-start);
}
bool empty()const{
return begin()==end();
}
.........
};
5.vector的内存管理
vector的迭代器就是最简单的指向容器内类型的指针。其内部有三个指针，start（指向数据存储区的首地址），finish（已使用的数据区的尾端），end_of_storage（指向容量尾端，容量一般富余），当遇到满载的情况，finish指针和
end_of_storage 指针相等，也就是容量用完的时候，如果继续插入元素，就会扩容。
需要扩容的时候，空间适配器就会从新寻找一块更大的内存空间（因为vector内部是一块连续的内存），然后start指向新内存首地址，原始数据复制，新数据插入，同时更新finish以及end_of_storage即可。扩容的规模一般是原始容量的两倍。vector空间是按照动态增加大小的，所谓动态增加并不是在原空间之后在接新空间（因为无法保证原空间后面还有可配置的空间），而是以原大小的两倍另外配置一块更大的区块，然后将原内容拷贝过去，并释放原空间。因此，对vector的操作，一旦引起空间的重新配置，指向原空间的所有迭代器将全部失效，这点要引起注意。当我们以push_back()将新元素插入vector的尾端时，该函数首先将检查是否有还有备用空间，如果有就直接在备用空间上构造元素，并调整finish的大小，如果没有备用空间就扩充空间(重新配置，移动数据，释放原空间)。
测试程序:
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
vector<int> ivec(2,9);
cout<<"size="<<ivec.size()<<endl; //size=2
cout<<"capacity="<<ivec.capacity()<<endl; //capacity=2;
ivec.push_back(1);
cout<<"size="<<ivec.size()<<endl; //size=3
cout<<"capacity="<<ivec.capacity()<<endl; //capacity=4;
ivec.push_back(2);
cout<<"size="<<ivec.size()<<endl; //size=4
cout<<"capacity="<<ivec.capacity()<<endl; //capacity=4;
ivec.push_back(3);
cout<<"size="<<ivec.size()<<endl; //size=5
cout<<"capacity="<<ivec.capacity()<<endl; //capacity=8;
return 0;
}