《STL 源码剖析》学习笔记之容器（一）vector
[图]The Container 2019-08-01
这是 herongwei 的第 82 篇原创
阅读本文大概需要 6.66 分钟
前言
侯捷大师的《STL源码剖析》，实乃一本神书，可以说也是一本很硬核的书了，不管是实验室的师兄师姐，还是牛客网上一些大佬们，都无不推荐此书，想要深入 C++ STL 这一块的，这本书必须掌握！
回想起来，大概在我大二的时候，就买了这本书，现在非常后悔的是，到大学毕业我都没看完这本书==。
人，总是到了某个特定的时期，才会突然醒悟，发现当初的自己为什么没有好好珍惜时间，没有静下来心来研读这些非常棒的书籍==
废话不多说，所谓
「源码之前，了无秘密」
今天先从最基本的容器开始学习吧。
1、容器的概观与分类
容器，置物之所也。
众所周知，常用的数据结构不外乎 array（数组）、list（串行）、tree（树）、stack（堆栈）、queue（队列）、hash table（杂凑表）、set（集合）、map（映像表）…等等。
根据「资料在容器中的排列」特性，这些数据结构分为序列式（sequence）和关系型（associative）两种。
所谓序列式容器，其中的元素都可序（ordered），但未排序（sorted）。
2、vector 容器
先来看看 vector 的源码。
以下是 vector 定义式的源码摘录。虽然 STL规定，欲使用vector者必须先含入
// alloc是 SGI STL的空间配置器template <class T, classAlloc = 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_tdifference_type;protected: // 以下，simple_alloc 是 SGI STL的空间配置器。 typedef 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(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:// 配置空间并填满内容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、vector 是一种动态增长的一种容器，当原来分配的内存用完了之后，会动态扩容，事实上，没有一个容器能在原地内存扩充，因为你要了一块内存之后，这块内存之后的内容或者接下来的内容可能会被使用。
2、vector 的数据安排以及操作方式，与 array 非常像似。两者的唯一差别在于空间的运用弹性。array 是静态空间，一旦配置了就不能改变。vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
3、事实上，扩容的时候，是这样一种机制：会去别的地寻找一块空闲的内存，然后把原来的东西搬过去，这样子所谓的扩充，而不能在原地扩充。
4、vector 是一种前闭后开的容器，在 vector 里头，有一些变量记录着一些信息，分别是三个迭代器
start：表示目前使用空间的头。
finish：目前使用空间的尾。
end_of_storage：目前可用空间的尾。
注意，目前使用空间和目前可用空间是有区别的，看下面的这张图
5、一个 vector 容器基本包含了下面这几个函数，下面分别讲解
1、begin() 返回的是 start
2、end() 返回的是 finish
3、size() 返回的是 size_type(end() - begin()) 为什么这里要这样写法，而不是直接调用 finish - start呢？侯捷大师说道：在使用比较复杂的容器的时候，直接用迭代器相减，可能会出问题，这里用 size 函数可以表示唯一确定函数的使用。
4、capacity() 返回的是 end_of_storage - begin() 的大小 也就是目前可用空间的大小。
5、empty() 只要判断是 begin() == end()即可。
6、二倍增长的原理？
当我们以 使用 push_back() 将新元素安插于 vector 尾端，该函数首先检查是否还有备用空间，如果有，就直接在备用空间上建构元素，并调整迭代器 finish，使 vector变大。如果没有备用空间了，就扩充空间（重新配置、搬移数据、释放原空间）：
细节：上面第二个函数进来，我们可以看到，又做了一次空间检查，这是为何呢？这是因为 insert_aux 函数 除了被 push_back 函数调用之外还会被其它函数调用！所以在那种情况下，需要做一次检查。
else //已无备用空间{ const size_type old_size = size(); const size_typelen = 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; // 将原 vector 的备用空间中的内容也忠实拷贝过来（侯捷疑惑：啥用途？） 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、那么进入 else 语句里面就开始了两倍增长的实现，调用分配器分配。
2、调用 uninitialized_copy函数 将原来 vector 的内容拷贝到新的 vector 内容中去。
3、为新元素设置初值。
4、拷贝安插点后的原内容（因为这个函数也有可能白 insert 函数调用）
注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后建构新元素，并释放原空间。
因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心。
3、vector 的元素操作：pop_back, erase, clear, insert
// 将尾端元素拿掉，并调整大小。void pop_back() { --finish;//将尾端标记往前移一格，表示将放弃尾端元素。 destroy(finish);// destroy是全域函式}// 清除 [first,last) 中的所有元素iterator erase(iterator first, iterator last) { iterator i = copy(last, finish, first);// copy 是全域函式 destroy(i, finish);// destroy是全域函式 finish = finish - (last - first); return first; } void clear() { erase(begin(), end()); }// erase()就定义在上面下面展示 erase(first, last)的动作。
下面展示 vector::insert() 实作内容：从 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; } }}注意，安插完成后，新节点将位于标兵迭代器（上例之 position，标示出安插点）所指之节点的前方—这是 STL 对于「安插动作」的标准规范。
图 4-3b 展示 insert(position,n,x) 的动作。
可以参照图片里的注解，细细体会。
参考资料：《STL源码剖析》（侯捷著）。
欢迎有问题和我交流~
推荐阅读
认真的人，自带光芒！