[图]The Container 2019-08-01
前言
侯捷大师的《STL源码剖析》，实乃一本神书，可以说也是一本很硬核的书了，不管是实验室的师兄师姐，还是牛客网上一些大佬们，都无不推荐此书，想要深入 C++ STL 这一块的，这本书必须掌握！
回想起来，大概在我大二的时候，就买了这本书，现在非常后悔的是，到大学毕业我都没看完这本书==。
人，总是到了某个特定的时期，才会突然醒悟，发现当初的自己为什么没有好好珍惜时间，没有静下来心来研读这些非常棒的书籍==
废话不多说，所谓
「源码之前，了无秘密」
今天先从最基本的容器开始学习吧。
1、容器的概观与分类
容器，置物之所也。
众所周知，常用的数据结构不外乎 array（数组）、list（串行）、tree（树）、stack（堆栈）、queue（队列）、hash table（杂凑表）、set（集合）、map（映像表）…等等。
根据「资料在容器中的排列」特性，这些数据结构分为序列式（sequence）和关系型（associative）两种。
所谓序列式容器，其中的元素都可序（ordered），但未排序（sorted）。
2、vector 容器
先来看看 vector 的源码。
以下是 vector 定义式的源码摘录。虽然 STL规定，欲使用vector者必须先含入，但 SGI STL 将 vector 实作于更底层的<stl_vector.h>。
不要被这一部分源码吓跑，如果阅读源码有困难，可以先跳过这部分，直接看后面的注解。
// 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源码剖析》（侯捷著）。