vector是动态空间,随着元素的加入,它的内部机制会自行扩充空间以容纳新的元素。vector的实现技术,关键在于对大小的控制以及重新配置时的数据移动效率。
一、vector的数据结构
vector采用线性连续空间,以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端。
template<class T, class Alloc = alloc> class vector{ ... protected: iterator start; //表示目前使用的空间的头 iterator finish; //表示目前使用的空间的尾 iterator end_of_storage; //表示目前可用的空间的尾 ... };
函数
iterator begin(){return start;} iterator end(){return finish;}
size_type size() const {end() - begin();} size_type capacity() const() {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); } template<class T, class Alloc> void vector<T,Alloc>::insert_aux(iterator position, const T& x){ 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 2*old_size : 1;
//old_size开始为0,分配空间1,old_size不为0,扩充为原来的两倍
//分配器分配内存 iterator new_start = data_allocator::allocate(len); iterator new_finish = new_start; //内存拷贝 try{ new_finish = uninitialized_copy(start, position, new_start);
//将原vector内容拷贝到新vector内容
construct(finish, x);
++new_finish; //调整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(); //调整迭代器,指向新vector start = new_start; finish = new_finish; end_of_storage = new_start + len; } }