vector是动态空间，内存空间是连续的。
template<class T, class Alloc = alloc>
class vector{
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator; //定义迭代器，原生指针做迭代器，因为vector的内存空间是连续的
typedef value_type& reference;
typedef size_t size_type; //尺寸类型
typedef ptrdiff_t difference_type;
protected:
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_od_storage - start);
}
}
void fill_initialize(size_type n, const T& value){ //填充元素
start = allocate_and_fill(n, value);
finish = start + n; //初始化时finish和end_of_storage一致，也就是说capacity和size相等
end_of_storage = finish;
}
public:
iterator begin() { return start; } //迭代器的头
iterator end() { return finish; } //迭代器的尾
size_type size() const { return size_type(end() - begin()); } //容器容纳元素的大小
size_type 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(){
destory(start, finish); //调用对象析构函数
deallocate(); //释放内存
}
reference front() { //返回第一个元素
return *begin();
}
reference back() { //返回最后一个元素
return *(end() - 1);
}
void insert(iterator position, size_type n, const T& x); //在迭代器的某个位置插入一个元素
void push_back(const T& x){
if(finish != end_of_storage){ //vector还有足够的空间
construct(finish, x);
++finish;
}else{ //没有足够的空间
insert_aux(end(), x); //扩充空间
}
}
void pop_back(){
--finish;
destroy(finish); //析构该对象，vector的内存保留
}
iterator erase(iterator position){ //清除某位置上的元素
if(position + 1 != end()){
copy(position + 1, finish, position); //所有元素前移一位
}
--finish;
destroy(finish);
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); //根据元素的类别，决定如何复制元素
return result;
}
}
为了降低空间配置时的速度成本，vector实际制的大小可能比客户端需求量大一些，以备将来可能的扩充。这就是容量的概念。也就是end_of_storage的意义。
template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){ //push_backinsert都可能会调用该函数
if(finish != end_of_storage){
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 ? old_size * 2 : 1; //申请两倍之前的空间大小
iterator new_start = data_allocator::allocate(len); //分配内存
iterator new_finish = new_start;
try{
new_finish = uninitialized_copy(start, position, new_start); //复制原来的元素到新的内存空间
construct(new_finish, x);
++new_finish;
new_finish = uninitialized_copy(position, finish, new_finish); //position之后的元素也移到新的内存中
}catch(...){
destory(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
destory(begin(), end());
deallocate();
start = new_start; //调整迭代器，指向新的vector内存
finish = new_finish;
end_of_storage = new_start + len; //end_of_storage和finish开始不一样
}
}
template<class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x){
if(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;
//不用使用额外的空间，把元素后移n个位置
if(elems_after > n){ //插入点之后的现有元素个数大于新增元素个数
uninitialized_copy(finish - n, finish, finish);
finish += n;
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);
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
new_finish = uninitialized_copy(start, position, new_start);
new_finish = uninitialized_fill_n(new_finish, n, x);
new_finish = uninitialized_copy(position, finish, new_finish);
}
#ifdef __STL_USE_EXCEPTIONS
catch(...){
destory(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
#endif
destory(begin(), end());
deallocate();
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}
对于vector来说，它的重点在于内存的申请，因为vector是一个动态数组。
