【STL源码剖析】第四章 序列式容器 之 vector底层实现
第四章 序列式容器(sequence containers)
vector
vector概述
vector的数据安排以及操作方式,与array非常相似。两者的唯一差别在于空间的运用的灵活性。array是静态空间,一旦配置了就不能改变;vector的动态空间 ,随着元素的加入,它的内部机制会自行扩充空间以容纳新元素。vector的实现技术,关键在于对其大小的控制以及重新配置时的数据移动效率。
vector迭代器
vector维护的是一个连续线性空间,所以不论其元素型别为何,普通指针都可以作为vector的迭代器而满足所有必要条件,因为vector迭代器所需要的操作,如operator*、operator->、operater++、operater--、operator-、operator+、operator+=、operator-=,普通指针天生就具备。vecotr支持随机存取,而普通指针正有这样的能力,所以,vecotr提供的是Random Access Iterators。
template<class T, class Alloc = alloc> class vector{ public: typedef T value_type; typedef value_type* iterator;//vector的迭代器是普通指针 ... };
根据定义,如果客户端写出这样的代码:
vector<int>::iterator ivite; vector<Shap>::iterator svite;
ivite的型别其实就是int*
,svite的型别其实就是Shape *
。
vector数据结构
vector采用线性连续空间的数据结构。它以两个迭代器start和finish分别指向配置的来的连续空间中目前已被使用的范围,并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端:
template<class T,class Alloc = alloc> class vector{ ... protected : iterator start ; //表示目前使用空间的头 iterator finish ; // 表示目前使用空间的尾 iterator end_of_storage ; //表示目前可用空间的尾 };
为了降低空间配置时的速度成本,vector实际配置的大小可能比客户需求量大一些,以备将来可能的扩展。这便是容量(capacity)的观念。
template<class T, class Alloc = alloc> class vector{ ... 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);} reference front(){return *begin();} reference back(){return *(end()-1);} ... }
vector构造与内存管理
vector缺省使用alloc作为空间配置器,并据此另外定义了一个data_allocator,为的是更方便以元素大小为配置单位:
template<class T, class Alloc = alloc> class vector{ protected: typedef simple_alloc<value_type,Alloc> data_allocator; ... }
于是,data_allocator::allocate(n)表示配置n个元素空间。
当我们以push_back()将新元素插入vector尾端时,该函数先检查是否还有备用空间,如果有就直接在备用空间上构造元素,并调整迭代器finish,使vector变大。不过没有备用空间,就扩充空间(重新配置、移动数据、释放原空间):
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)); //在备用空间起始处构造一个元素,以vector最后一个元素值为其初值 ++finish; //调整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 new_size = old_size != 0 ? 2 * old_size : 1; iterator new_start = data_allocator::allocate(new_size); iterator new_finish = new_start; try{ new_finish = uninitialized_copy(start, position, new_start);//将原vector的内容拷贝到新vector construct(new_finish, x); ++new_finish; new_finish = uninitialzed_copy(position, finish, new_finish);//将安插点的原内容也拷贝过来 } catch (excetion e){ destroy(new_start, new_finish);//如果发生异常,析构移动的元素,释放新空间 data_allocator::deallocate(new_start, new_size); }//析构并释放原空间 destroy(begin(), end()); deallocator(); start = new_start; //调整迭代器 finish = new_finish; end_of_storage = new_start + new_size;//调整迭代器 } }
所谓动态增加大小,并不是在原空间之后接续空间(因为无法包装原空间之后尚有可配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将原来内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了。
vector元素操作
pop_back()实现
void pop_back(){ --finish; //将尾端标记往前移一格,表示放弃尾端元素 destory(finish); }
erase()实现
//清除[first,last]中的所有元素 iterator erase(iterator first,iterator last){ iterator i=copy(last,finish,first); destroy(i,finish); finish=finish-(last-first); } //清除某个位置上的元素 iterator erase(iterator position){ if(position+1!=end()) copoy(position+1,finish,position); --finish; destory(finish); return position; } //清除所有元素 void clear() {erase(begin(),end());}
insert()实现