STL源码之vector容器深入学习

任何特定的数据结构都是为了实现某种特定的算法，STL容器也不例外。在进入vector容器的学习之前，我们先来梳理一下有关容器相关的概念。

（1）常用的数据结构包括哪些？array(数组)、list(链表)、tree(树)、stack(堆栈)、queue(队列)、hash table(散列表)、set(集合)、map(映射表)…
（2）根据数据在容器中的排列特性，这些数据结构分类序列式(sequence)和关联式(associative)两种。
（3）所谓序列式容器，其中的元素是可序的(ordered)，但未必有序(sorted)。
（4）C++语言本身提供了一个序列式容器内置数组array，STL另外再提供vector, list, deque, stack, queue, priority-queue等等。
（5）其中stack和queue只是将deque改头换面，技术上被归类为一种配接器(adapter)。

1. 引言
   我们从序列式容器vector开始进入STL容器的学习。我们知道内置数组array是静态空间，一旦配置了就不能改变。如果日后有需求要对数组内容进行扩充怎么办呢？难道要重新申请一个更大的空间，将其数据一一复制到新空间上吗？那将严重导致效率的低效。那还有其他办法？
   有的，vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间纳入新元素。
2. SGI STL vector源码
   当我们沉溺于vector方便、高效的内存处理机制的时候，有没有想过它的内部究竟在怎么实现的呢，来看看SGI STL中vector的部分实现细节，一窥究竟：
   
   C++

   //alloc是SGI STL空间配置器，详情见前面空间配置器相关博文 template <class T, class 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: //以下simple_alloc是SGI STL的空间配置器，详见空间配置器博文 typedf 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_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); } 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() { destroy(start, finish); //全局函数，见配置器相关内容 deallocate(); //这是vector的一个member function } 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); //这是vector的一个member function } void pop_back() { //将最尾端元素取出 --finish; destroy(finish); //全局函数，见配置器相关内容 } 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(bedin() + 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; } };

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

   //alloc是SGI STL空间配置器，详情见前面空间配置器相关博文 template <class T, class 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: //以下simple_alloc是SGI STL的空间配置器，详见空间配置器博文 typedf 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_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); } 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() { destroy(start, finish); //全局函数，见配置器相关内容 deallocate(); //这是vector的一个member function } 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); //这是vector的一个member function } void pop_back() { //将最尾端元素取出 --finish; destroy(finish); //全局函数，见配置器相关内容 } 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(bedin() + 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; } };

3. vetor的迭代器
   （1）vector维护的是一个连续线性空间。
   （2）不论其元素类型为何，普通指针都可以作为vector的迭代器而满足所有必要条件。因为vector迭代器所需要的操作行为，如operator*, operator->, operator++, operator–, operator+, operator-,opreator+=, operator-=，普通指针天生就具备。
   （3）vector支持随机存取，而普通指针正有着这样的能力，所以vector提供的是Random Access Iterator。
   vector中迭代器部分源码：
   
   C++

   template <class T, calss Alloc = alloc> class vector { public: typedef T value_type; typedef value_type* iterator; //vector的迭代器是普通指针 ... };

   1 2 3 4 5 6 7

   template <class T, calss Alloc = alloc> class vector { public: typedef T value_type; typedef value_type* iterator; //vector的迭代器是普通指针 ... };

4. vector的数据结构
   （1）vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围。并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端：
   
   C++

   template <class T, class Alloc = alloc> class vector { ... protected: iterator start; //表示目前使用空间的头 iterator finish; //表示目前使用空间的尾 iterator end_of_storage; //表示目前可用空间的尾 ... };

   1 2 3 4 5 6 7 8 9

   template <class T, class Alloc = alloc> class vector { ... protected: iterator start; //表示目前使用空间的头 iterator finish; //表示目前使用空间的尾 iterator end_of_storage; //表示目前可用空间的尾 ... };

   
   （2）vector实际配置的大小可能比客户端需求量更大一些，以备将来可能扩充。
   （3）使用start, finish, end_of_storage三个迭代器，便可轻易地提供首尾标示、大小、容量、空容器判断、标注运算子[]、最前端元素值、最后端元素值等…:
   
   C++

   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); } };

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   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); } };

   
   结合下图便于理解：
5. vector的构造与内存管理：constructor, push_back
   （1）我们在配置器部分已经说过，SGI STL配置器默认使用alloc作为空间配置器，并据此另外定义了一个data::allocator，为的是更方便以元素大小为配置单位。
   （2）uninitialized_fill_n()会根据第一参数的类型特性(type traits)决定使用算法fill_n()或反复调用constructor()来完成任务。
   （3）使用push_back()将新元素插入vector尾端时，该函数首先检查是否还有备用空间？
   有—>直接在备用空间上构造元素，并调整迭代器finish。
   无—>扩充空间（重新配置、移动数据、释放原空间）
   
   
   C++

   void push_back(const T& x) { //将元素插入至最尾端 if(finish != end_of_storage) { construct(finish, x); //全局函数 ++finish; } else insert_aux(end(), x); //这是vector的一个member function } template <class T, class Alloc = alloc> void vector<T, Alloc>::insert_aux(iterator position, const T& x) { if (finish != end_of_storage) { //在备用空间起始处构造一个元素，并以vector最后一个元素值为其初始值 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; //以上配置原则：如果原大小为0，则配置1（个元素大小）； //如果原大小不为0， 则配置原大小的两倍， //前半段用来放置原数据，后半段准备用来放置新数据 iterator new_start = data_allocator::allocate(len); //实际配置 iterator new_finish = new_start; try { //将原vector的内容拷贝到新vector new_finish = uninitialized_copy(start, position, new_start); //将新元素设定初值x construct(new_finish, x); //调整水位 ++new_finish; //将安插点的原内容也拷贝进来（提示：本函数也可能被insert(p,x)调用） new_finish = uninitialized_copy(position, finish, new_finish); } catch(...) { //"commit or rollback" semantics destroy(new_start, new_finish); data_allocator::deallocate(new_start, len); throw; } //析构并释放原vector destroy(begin(), end()); deallocate(); //调整迭代器，指向新vector start = new_start; finish = new_finish; end_of_storage = new_start + len; } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

   void push_back(const T& x) { //将元素插入至最尾端 if(finish != end_of_storage) { construct(finish, x); //全局函数 ++finish; } else insert_aux(end(), x); //这是vector的一个member function }   template <class T, class Alloc = alloc> void vector<T, Alloc>::insert_aux(iterator position, const T& x) { if (finish != end_of_storage) { //在备用空间起始处构造一个元素，并以vector最后一个元素值为其初始值 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; //以上配置原则：如果原大小为0，则配置1（个元素大小）； //如果原大小不为0， 则配置原大小的两倍， //前半段用来放置原数据，后半段准备用来放置新数据 iterator new_start = data_allocator::allocate(len); //实际配置 iterator new_finish = new_start; try { //将原vector的内容拷贝到新vector new_finish = uninitialized_copy(start, position, new_start); //将新元素设定初值x construct(new_finish, x); //调整水位 ++new_finish; //将安插点的原内容也拷贝进来（提示：本函数也可能被insert(p,x)调用） new_finish = uninitialized_copy(position, finish, new_finish); } catch(...) { //"commit or rollback" semantics destroy(new_start, new_finish); data_allocator::deallocate(new_start, len); throw; } //析构并释放原vector destroy(begin(), end()); deallocate(); //调整迭代器，指向新vector start = new_start; finish = new_finish; end_of_storage = new_start + len; } }

   
   （4）所谓动态增加大小，并不是在原空间之后接续新空间(因为无法保证原空间之后尚有可供配置空间)。
   （5）而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素并释放原空间。
6. vector的元素操作：pop_bcak, erase, clear, insert
   vector所提供的元素操作很多，这里主要讲insert():
   
   C++

   //从position开始，插入n个元素，元素初值为x template <class T, class Alloc> void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) { if ( n != 0){ //当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; if (elems_after > n) { //“插入点之后的现有元素个数”大于“新增元素个数” uninitialized_copy(finish - n, finish, finish); finish += n; //将vector尾端标记后移 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); //以下配置新的vector空间 iterator new_start = data_allocator::allocate(len); iterator new_finish = new_start; __STL_TRY { //以下首先将旧vector的插入点之前的元素复制到新空间 new_finish = uninitialized_copy(start, position, new_start); //以下再将新增元素(初值皆为n)填入新空间 new_finish = uninitialized_fill_n(new_finish, n, x); //以下再将旧vector的插入点之后的元素复制到新空间 new_finish = uninitialized_copy(position, finish, new_finish); } #ifdef __STL_USE_EXCEPTIONS catch(...) { //如有异常发生，实现”commit or rollback"semantics destroy(new_start, new_finish); data_allocator::deallocate(new_start, len); throw; } #endif /* __STL_USE_EXCEPTIONS */ //以下清楚并释放旧的vector destroy(start, finish); deallocate(); //以下调整水位标记 start = new_start; finish = new_finish; end_of_storage = new_start + len; } } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

   //从position开始，插入n个元素，元素初值为x template <class T, class Alloc> void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) { if ( n != 0){ //当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; if (elems_after > n) { //“插入点之后的现有元素个数”大于“新增元素个数” uninitialized_copy(finish - n, finish, finish); finish += n; //将vector尾端标记后移 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); //以下配置新的vector空间 iterator new_start = data_allocator::allocate(len); iterator new_finish = new_start; __STL_TRY { //以下首先将旧vector的插入点之前的元素复制到新空间 new_finish = uninitialized_copy(start, position, new_start); //以下再将新增元素(初值皆为n)填入新空间 new_finish = uninitialized_fill_n(new_finish, n, x); //以下再将旧vector的插入点之后的元素复制到新空间 new_finish = uninitialized_copy(position, finish, new_finish); } #ifdef __STL_USE_EXCEPTIONS catch(...) { //如有异常发生，实现”commit or rollback"semantics destroy(new_start, new_finish); data_allocator::deallocate(new_start, len); throw; } #endif /* __STL_USE_EXCEPTIONS */ //以下清楚并释放旧的vector destroy(start, finish); deallocate(); //以下调整水位标记 start = new_start; finish = new_finish; end_of_storage = new_start + len; } } }

   
   其中copy_backward()函数实现的是逆向拷贝。

   参考：STL源码剖析