目录
vector的实现：
1. 先来看看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; ： 用来计算对象的个数
可以看出来指针和迭代器是一样的，因为vector是线性的，直接用裸指针就能模拟迭代器的行为，这里不需要过多考虑。
2. 在来看看空间配置器：
typedef simple_alloc<value_type,Alloc> data_allocator;
前面章节讲了 simple_alloc 是对一级/二级空间配置器内部的申请内存/释放内存接口的封装，具体用哪个配置器，取决于 __USE_MALLOC 这个宏来决定。
3. 在来看看核心3个管理内存块的字段：
Iterator start; ：内存块的起始地址
Iterator fnish; ：内存块的实际总共用了的结束地址
Iterator end_of_storage; ：整个内存块的结束地址
可以看出来在源码这里采用迭代器定义了3个核心字段，也就是指针，指针也能和指针进行运算，其实只需要知道内存块的起始地址 + 实际用了的大小 + 总共的大小也能代替后2个字段用指针的情况。
4. 构造函数/析构函数；
vector():start(0),finish(0),end_of_stroage(0) { } ：无参构造
vector(size_type n,const T& value) { fill_initialize(n,value); } ：指定大小，指定对象拷贝构造
vector(int n,const & 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(); ：析构 vector 对象
5. 其他成员接口：
void insert_aux(iterator position,const T& x); ：插入元素
void deallocate(); ： 释放内存块
void fill_initialize(size_type n,const T& value); ：指定大小，指定对象拷贝构造
iterator allocate_and_fill(); ：指定大小，指定对象拷贝构造
iterator begin(); ：起始地址
iterator end(); ：结束地址
size_type size() const; ： 实际用了的大小
bool empty() const; ：是否为空
reference operator[ ](size_type n); ：重载 [ ]
reference front(); ：取头部元素reference back(); ：取尾部元素
void push_back(const T&); ：尾部插入元素
void pop_back(); ：尾部删除元素
iterator erase(iterator position); ：删除指定元素
void resize(size_type new_size,const T&); ：扩容
void resize(size_type new_size); ：扩容
void clear(); ：只是让指针归0，并不会释放内存
下面来看看上述接口的具体实现；
template <class T,class Alloc = aloc>
class vector
{
public:
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:
typedef simple_alloc<value_type,Alloc) data_allocator;
iterator start;
iterator finish;
iterator end_of_storage;
void deallocate()
{
// start 不为空则调用空间配置器的释放函数，注意不是析构，仅仅是释放
if(start) data_allocator::deallocate(start,end_of_storage - start);
}
void fill_initialize(size_type n,const T& value)
{
start = allocate_end_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(result,n,x);
return result;
// 上面2个函数前章讲过
}
public:
iterator begin(){ return start; } // 返回内存块的起始地址
iterator end(){ return end; } // 返回内存块实际使用的元素个数的地址
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); } // 重载 []
reference front(){ return *begin(); } // 返回头部元素
reference back(){ return *(end() - 1); } // 返回尾部元素
void push_back(const T& x) // 插入对象
{
// 如果还有剩余空间
if(finish != end_of_storage)
{
// 并构造对象
construct(finish,x);
++finish;
}
// 否则尾插并扩容
else insert_aux(end(),x);
}
void pop_back() // 删除尾部元素
{
--finish;
destroy(fnish); // 析构元素
}
iterator erase(iterator position) // 删一个
{
// 区分边界情况，不能等于实际有效元素的下一个迭代器
if(position + 1 != end()) copy(position + 1,finish,position);
--finish;
destroy(finish); // 析构元素
return position; // 返回下一个迭代器
}
iterator erase(iterator first,iterator last) // 删一个区间
{
iterator i = copy(last,finish,first); // 删除区间并返回 finish - 区间大小的迭代器
destroy(i,finish); // 析构这个区间后面到finish的元素
finish = finish - (last - first); // 更新元素
return frsit; // 返回区间的起始地址
}
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:
void insert_aux(iterator position,const T& x) // 扩容插入元素
{
// 前面push_back已经检查了，但这个函数可能被多个接口调用，双重保险
if(finish != end_of_storage)
{
construct(fnish,x); // 还有元素就直接构造对象
++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; // 一开始为空就给一
// 个，否则给2倍的旧空间
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);
}
catch(...) // 拷贝旧数据失败旧把新申请的空间进行析构和释放
{
destroy(new_start,new_finish);
data_allocator::deallocate(new_start,len);
throw;
}
// 析构旧空间和释放
destroy(begin(),end());
deallocate();
// 更新3个指针
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
void insert(iterator position,size_type n,const T& x)
{
if(n != 0) // 至少插入一个元素
{
if(size_type(end_of_storage - finish) >= n) // 剩余空间满足需要的大小
{
T x_copy = x; // 和前面的insert_aux一样
const size_type elems_after = finish - position; // 记录pos到尾的长度
iterator old_finish = finish; // 记录尾迭代器
if(elems_after > n) // 如果pos后面的实际有效长度大于n
{
// 先把 finish - n 到 finish 这个区间元素挪到 finish后面
uninitialized_copy(finish - n,finish,finish);
// 调整 finish
finish += n;
// 在把 pos 指向的元素挪到 finish - n 的元素挪到旧的finish后面
copy_backward(position,old_finish - n,old_finish);
// 在从 pos 位置填充
fill(position,position + n,x_copy);
[ 1 , 2 , 3 , 4 , 5 , 6 , _ , _ , _ , _ ]
// 假设在4插入2个 -1
// 先把 finish - n -> 指向 5 ~ finish(6) 挪到finish后面，6的后面
[ 1 , 2 , 3 , 4 , 5 , 6 , 5 , 6 , _ , _ ]
// 调整finish到最后一个6的下一个位置
// 在把 pos(4) 到 旧的(finish - n)(第一个5，这是开区间不算5)，此时就值挪动一个4
// 挪到旧的finish位置，第一个6
[ 1 , 2 , 3 , 4 , 5 , 4 , 5 , 6 , _ , _ ]
// 在把 pos 到 pos + n ，也就是 2 个位置进行拷贝
// [ 1 , 2 , 3 , -1 , -1 , 4 , 5 , 6 , _ , _ ]
}
else // 如果pos后面的实际有效长度大于n
{
// [ 1 , 2 , 3 , 4 , 5 , 6 , _ , _ , _ , _ ]
// 假设在5位置插入3个-1
// 先从 finish 开始 拷贝 n - elems_after 个元素：3 - 2 个 -1
// [ 1 , 2 , 3 , 4 , 5 , 6 , -1 , _ , _ , _ ]
// 在调整 finish 到最后一个-1的后面
// 在从 pos 位置到 旧的finish 也就是 5，6拷贝到新的finish后面，-1的后面
// [ 1 , 2 , 3 , 4 , 5 , 6 , -1 , 5 , 6 , _ ]
// 最后从 pos 位置到旧的finish这个区间逐个 拷贝 -1
// [ 1 , 2 , 3 , 4 , -1 , -1 , -1 , 5 , 6 , _ ]
uninitialized_fill_n(finish, n - elems_after,x_copy);
finish += n - elems_after;
ininitialized_copy(position,old_finish,finish);
fill(position,old_finish,x_copy);
}
}
else
{
// 计算旧的实际的元素个数
const size_type old_size = size();
// 计算极端情况 n 比2个旧元素个数还大的情况
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(...)
{
destroy(new_start,new_finish);
data.allocator::deallocate(new_start,len);
throw;
}
#endif // 析构释放旧的空间
destroy(start,finish);
deallocate();
// 最后在更新成员3个核心字段
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}
}