【STL】vector的实现原理

原理"/>

【STL】vector的实现原理

今日记

清晨降至，我醒了。打开博客，回想昨日学习，大抵是忘得差不多了。回味从入眠至今，本人内心诚实便是：放弃了吧。但小学生的假装努力，终究要的。千头万绪，不知从何写起。回想之前博客从未留心，现自然无从下笔。但昨日，侯捷老师一番讲诉，实则精彩，便依他吧！

一、概述

array 的使用，自古有之，与C中数组无异，只是叫法不同，罢了。

而vector的数据安排以及操作方式与array极为相似，两者的不同主要在于空间运用的灵活性。array是静态空间，一旦存满，就得分配更大的空间，所有琐碎的操作都得客户自己完成。而vector是动态空间，内部可以自行扩充，容纳新元素。

vector的实现技术，关键在于其对大小的控制以及重新分配时的数据移动效率。本章所采用vector版本为 SGI STL 2.91版本。

二、vector定义摘要

以下是vector部分定义的代码摘录。

_Alloc是SGI STL的空间配置器，具体详见【STL】空间配置器||分配器（Allocators）

template <class T, class Alloc = alloc>  // 默认alloc为迭代器
class vector {
public:// 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; 	protected:// 空间配置器typedef simple_alloc<value_type, Alloc> data_allocator;iterator start;//vector采用线性空间，两个迭代器指向数据的头跟尾iterator finish;iterator end_of_storage;//end_of_storage 执行容器尾//往position插入元素x及申请内存void insert_aux(iterator position,const T&x);void deallocate(){if(start) data_allocator::deallocate(start,end_of_storage - start);} void fill_initialize(size_type n,const T& value){start = allocate_and_fill(n,value);finish = start + n;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); }reference front() { return *begin(); }reference back() { return *(end() - 1); }//默认初始化vector() : start(0), finish(0), end_of_storage(0) {}~vector(){destroy(start, finish);deallocate();}//后续讲到void push_back(const T& x) {....	}  void pop_back() {...	}// 将迭代器position指向的节点删除iterator erase(iterator position) {...	}

三、vector的迭代器

因为vector是一个连续线性空间，普通指针可以作为迭代器满足所有条件。所以，vector提供的是Random Access Iterators。

template <class T,class Alloc=alloc>
class vector{
public:typedef T value_type;typedef value_type* iterator;//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;    //表示目前可用空间的尾
...
}

vector实际大小要比客户需求更大一些，以备将来的扩充，这便是容量（capacity）的概念。

通过start , finish , end_of_storage 三个迭代器，可以得到首尾、大小、容量、以及 [ ] 元素符 … 等。

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的构造和内存管理

push_back()

void push_back(const T& x)
{if (finish != end_of_storage) { //还有备用空间construct(finish, x);       //全局函数++finish;                   //调整finish}else  {							//无备用空间insert_aux(end(), x);       //vector member function}
}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;                           // 调整finishT 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 * ols_size : 1;// 以上配置原则，如果原大小为0，则配置1（个元素）// 如果原大小不为0，则配置原大小的两倍// 前半段用来放置源数据，后半段准备用来放置新数据iterator new_start = data_allocator::allocate(len); // 实际配置iterator new_finish = new_start;try {// 将原 vector 的内容拷贝到新的 vector// uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);// 迭代器 first 指向输入端的起始位置, 迭代器 last 指向输入端的结束位置(前闭后开区间)// 迭代器 result 指向输出端(欲初始化空间)的起始位置new_finish = uninitialized_copy(start, position, new_start);// 为新元素设定初值xconstruct(new_finish, x);// 调整finish++new_finish;// 将安插点的原内容也拷贝过来new_finish = uninitialized_copy(position, finish, new_finish);}catch (...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}// 析构并释放原 vectordestory(begin(), end());deallocate();// 调整迭代器, 指向新 vectorstart = new_start;finish = new_finish;end_of_storage = new_start + len;}
}

动态扩容是只分配一个原来大小两倍的新空间, 然后将源数据拷贝到新空间, 再在新空间构造新元素, 最后释放原空间。一旦引起空间重新配置，指向原Vector的所有迭代器失效。

pop_back():将尾端元素拿掉，并调整大小

void pop_back(){--finish;destroy(finish);
}

erase[ first , lase ) : 清除[ first , lase )中的所有元素。

iterator erase(iterator first,iterator last){iterator i=copy(last,finish,first); // 将后面元素拷贝到删除位置destroy(i,finish);finish=finish-(last-first); //调整尾部位置return first;
}

使用erase会造成迭代器失效问题，可以通过erase方法的返回值来获取下一个元素迭代器。

earse(iterator position） : 清楚某个位置上元素

iterator earse(iterator position）{if(position+1!=end()) copy(position+1,finish,position);--finish;destory(finish);return position;
}

在这里，我认为positon中的内容已经被下一个position中的内容覆盖了(所以并不是网上说的，迭代器指向了下一个元素，地址并没有变只是内容变了)

大抵上，是因为编译器强行在earse之后将迭代器中的成员变量_Myproxy值置为空了，此时不可以直接操作++。而返回的迭代器是重新构造的，是用Position重新构造的一个临时变量迭代器的_Myproxy值的，所以遍历时earse，要用iter = earse(iter)的返回值。先判断返回值是否等于end再做++，不然会报返回野指针的错误

void clear():清空

void clear(){ erase(begin(),end()); }

insert（position, n, x）: 从position位置开始，插入n个元素，初始值为x。

参考资料：
《STL源码剖析》- 侯捷