STL源码剖析——序列式容器#1 Vector
在学完了Allocator、Iterator和Traits编程之后，我们终于可以进入STL的容器内部一探究竟了。STL的容器分为序列式容器和关联式容器，何为序列式容器呢？就是容器内的元素是可序的，但未必有序。C++本身就提供了一种序列式容器array（即数组），而STL就提供了多种序列式容器，这些容器都是基于常见的数据建构开发出来的，例如vector、list、deque等等。接下来我们将会对STL里的所有序列式容器进行逐一的学习。
本节要学的容器就是我们日常开发中使用最多的vector，vector的数据安排以及操作方式，与array非常相似。两者唯一的区别在于空间运用的灵活性。array是静态空间，配置了其大小就不能被改变，如果空间满了，要换大的，这只能自己手动来：配置新空间，将元素从旧址一一复制过去，再把原来的空间释放。而vector是动态空间，随着元素的加入，它内部会自行扩充空间，进行元素的复制并释放旧空间。所以在使用上，我们更趋向于使用vector而非array，因为不用考虑元素个数的问题，很适合动态元素个数的情况。我们不必因为害怕空间不足而一开始就要求一个大块头的array了。
我们先从vector类里的public部分出发，因为这部分是我们在使用vector时经常接触到的一些接口，从这些接口开始逐渐深挖，探究其里面的运作机制。为了能够更好的了解vector内部，我们把vector的public部分再细分为五个部分学习，分别是vector的迭代器、vector的数据结构、vector的构造与析构、vector的内存管理、vector的元素操作。
Vector的迭代器
template <class T, class Alloc = alloc>
class vector {
public:
// 1. 这里是vector的迭代器部分，包含迭代器的各种特性，在上几节中有详解
typedef T value_type; // (1)
typedef value_type* pointer; // (2)
typedef const value_type* const_pointer;
typedef const value_type* const_iterator;
typedef value_type& reference; // (3)
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type; // (4)
// 以下，由于vector 所维护的是一个连续线性空间，所以不论其元素类型为何，
// 原生指针都可以作为其迭代器而满足所有需求。
typedef value_type* iterator;
...
}
vector维护的的是一个连续线性的空间，所以不论其元素类型是什么，普通指针都能作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator*，operator->，operator++，operator--，operator+，operator-，operator+=，operator-=，普通指针天生就具备。vector支持随机存取，而普通指针正有着这样的能力。所以vector提供的是Random Access Iterators。例如
vector<int>::iterator it;
vector<Shape>::iterator its;
it的类型其实就是int*，its的类型其实就是Shape*。
Vector的数据结构
在讨论Vector数据结构之前，我们可以先看看我们经常用到的一些并与之相关的函数的实现：
template <class T, class Alloc = alloc> // 預設使用 alloc 為配置器
class vector {
public:
...
//获取指向首元素的迭代器
iterator begin() { return start; }
const_iterator begin() const { return start; } //获取指向容器末尾的迭代器
iterator end() { return finish; }
const_iterator end() const { 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); }
const_reference operator[](size_type n) const { return *(begin() + n); }
// 取出第一個元素內容，可作左值
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
// 取出最後一個元素內容
reference back() { return *(end() - ); }
const_reference back() const { return *(end() - ); }
...
}
可以看到在这几个函数中涉及到了几个变量start、finish和end_of_storage，而它们都是迭代器类型iteartor（从返回类型中看出），而对应它们的定义，vector是把它放到了protected部分：
protected:
...
iterator start; //表示目前使用空间的头
iterator finish; //表示目前使用空间的尾，指向最后一个元素的下一位置（空的）
iterator end_of_storage; //表示目前可用空间的尾
这三个迭代器是用来管理vector的存储空间的，那么究竟vector的空间是如何的呢？是连续还是不连续的呢？我们可以从上面某些函数定义里获得结论，例如size()或是capacity()，其定义就是两首尾迭代器的相减，可见vector的数据结构就是连续线性空间。而finish与end_of_storage的区别就是：为了降低空间配置时的速度成本（减少因容量不够而多次扩充造成的成本），vector实际配置的大小可能比用户的需求量更大一些，以备将来可能的需求增加。这便是容量（capacity）的概念。一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector便得另觅居所。
Vector的构造与析构
在创建vector对象时，我们经常用到的一种构造函数是：
vector(size_type n, const T& value) { fill_initialize(n, value); }
例如vector<int> iv(2, 9); ，用的就是上面这个构造函数，它能创建一个具有n个元素其值为value的数组。从其构造函数的定义中能看到，里面仅仅是一个转调用而已，而fill_initialize()又是什么来头呢？我们在protected部分发现了它的踪迹：
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value); // 配置空间并设置空间的首端
finish = start + n; //设置使用空间的尾端
end_of_storage = finish; //使用总空间的尾端
}
我们发现这个函数只是负责初始化容器3个管理空间的迭代器，而真正配置空间的还另有其人：allocate_and_fill()，而它里面又是怎样的？情理之内，我们又是在protected部分找到的它的定义：
protected:
// 专属空间配置器，每次配置一个元素大小
typedef simple_alloc<value_type, Alloc> data_allocator; iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n); // 配置n个元素空间
__STL_TRY{
// 全局函数，將result所指之未初始化空间设定初值為为x，n个
// 定义于 <stl_uninitialized.h>。
uninitialized_fill_n(result, n, x);
return result;
}
// "commit or rollback" 語意：若非全部成功，就一个不留。
__STL_UNWIND(data_allocator::deallocate(result, n));
}
能看到这个函数分为两部分，一是分配空间：用了在protected部分定义好的一个simple_alloc对象data_allocator，而这个simple_alloc类我们之前在学习空间配置器时已经有所了解，就是一个有四个成员函数的类，而这四个成员函数里面都是转调用（allocate()就是其中之一），调用的是alloc类里面真正负责分配内存的函数，这里不再赘述。在分配完空间后，第二部分就是对刚分配好的空间进行内容的填充，这里用到的一个函数就是uninitialized_fill_n()它的功能是将result所指的未初始化的空间初始化为n个值为x的元素，再往里深究的话，就会发现去到STL的算法世界了（uninitialized_fill_n函数里的仍有转调用的函数fill_n()，其函数定义在了<stl_algobase.h>里），所以我们就到此为止了，知道这个函数的功能就好，而至于这个函数的源码，我打算在之后专门拿一节来学习这个内存处理的基本工具（它是之一）。
至此，我们了解了vector构造函数的调用逻辑就是vector()→fill_initialize()→allocate_and_fill()→allocate()与uninitialized_fill_n()。
Vector的内存管理
我们前面也有提到，当vector容器内部空间已被填满时，再往其加入元素会进行寻找更大的空间，把旧址的内容复制到新空间，再释放旧空间的这么一个过程。我们知道这是在空间已满且再往其加入元素时发生的，那其中的乾坤就应该发生在push_back函数内部。
// 在容器尾部增加一个元素
void push_back(const T& x) {
if (finish != end_of_storage) { // 还有备用空间
construct(finish, x); // 直接在备用空间构建元素
++finish; // 调整已使用空间的尾部迭代器
}
else // 已无备用空间
insert_aux(end(), x);
}
push_back函数内部会做一个判断，判断此时容器空间是否被填满，如果没有就如常构建；如果满了就转调用另外一个函数insert_aux来处理：
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
if (finish != end_of_storage) {
//这部分负责insert函数的，与push_back无关，因为finish==end_of_storage不会进入这部分
construct(finish, *(finish - ));
++finish; T x_copy = x;
copy_backward(position, finish - , finish - );
*position = x_copy;
}
else { // 已无备用空间
const size_type old_size = size();
const size_type len = old_size != ? * old_size : ;
// 以上配置原则：如果原大小为0，则配置 1（个元素大小）；
// 如果原大小不为0，则配置原大小的两倍，
// 前半段用來放置原内容，后半段准备用來放置新内容。 iterator new_start = data_allocator::allocate(len); // 实际配置大小
iterator new_finish = new_start;
__STL_TRY{
// 將原vector 的內容拷贝到新 vector。
new_finish = uninitialized_copy(start, position, new_start);
// 为新元素设定初值x
construct(new_finish, x); ++new_finish;
//此处也是对应与insert函数的情况的，因为于push_back而言，此时的情况是position(就是end()) == finish
new_finish = uninitialized_copy(position, finish, new_finish);
} # ifdef __STL_USE_EXCEPTIONS
catch (...) {
// "commit or rollback" 语意：若非全部成功，就一个不留。
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */ // 析构并释放原vector
destroy(begin(), end());
deallocate(); // 调整迭代器，指向新vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
insert_aux不仅负责在push_back时为其新增空间，也负责在insert时为其新增空间，但由于现在我们讨论的是push_back函数，所以我们先把关于insert函数的部分忽略不谈，等我们学到insert函数时再去讨论。我们可以把insert_aux函数分为3部分：分配新空间、复制并新增内容、析构并释放旧空间。
- 分配新空间
从代码或注释中我们可以了解到vector扩充空间时，其容量的分配原则，那就是如果此时容器容量为0，则配置一个元素大小的空间；如果此时容器不为0（即容器被填满的情况），则配置两倍原来大小的空间。
2. 拷贝旧内容，构建新内容
该函数用了uninitialized_copy函数来完成拷贝旧内容，该函数的功能就是：将一容器某区间的内容[start, position)复制到一未被初始化的空间里（第三个参数的指针指向该区间）。于push_back而言，position就是旧vector的end()，所以就会把整个旧vector复制到新空间里去。然后再利用construct()构建新元素放在旧内容的后面。而uninitialized_copy函数会与uninitialized_fill_n一起放在内存处理的基本工具这一节中学习。
3. 析构并释放旧空间
利用destroy析构，deallocate释放。最后调整管理空间的迭代器指向新vector。
可以看到，所谓的动态增加大小，并不是在原空间之后接续新空间，而是以原大小的两倍另外配置一块更大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放元空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。
Vector的元素操作
vector提供的元素操作有很多，这里只挑几个比较常用的逐一学习，例如pop_back()、erase()、clear()和insert()。
- pop_back()——弹出容器最后一位元素，但切记vector的pop_back()并不返回弹出的元素，要想获取弹出的元素，最好先用back()获取，再用pop_back()弹出。
void pop_back() {
--finish; //finish是指向最后一个元素的下一位置，所以先自减，指向最后一个元素
destroy(finish); //再把它析构
}
- erase(iterator first, iterator last)——该函数清除[first, last)中的所有元素。
iterator erase(iterator first, iterator last) {
iterator i = copy(last, finish, first); //先把后面不在清除范围内的元素，往清除范围内复制，覆盖其内容，获取覆盖后的位置
destroy(i, finish); //覆盖后，后面空间的内容已经失去意义，析构之
finish = finish - (last - first); //调整已使用空间的尾部迭代器
return first;
}
- erase(iterator position)——清除某个位置上的元素
iterator erase(iterator position) {
if (position + != end()) // 如果 p 不是指向最后一个元素
copy(position + , finish, position);// 將 p 之后的元素一一向前移动
//并把最后一个元素析构
--finish;
destroy(finish);
return position;
}
copy函数的功能是将[position+1, finish)区间的元素复制到position指向位置上，与uninitialized_copy的区别就是，前者是复制到已经有内容的空间上（覆盖），后者是复制到未被初始化的空间上，这个函数的源码跟uninitialized_copy()、uninitialized_fill_n()一起放在内存处理的基本工具这一节中学习。
- insert(iterator position, size_type n, const T& x)——从position开始，插入n个值为x的元素。由于该函数面对不同的情况有不同的处理方式，所以决定分开情况来讲：
第一种情况是，备用空间大于新增元素个数n，此情况下又分文两种情况：一是「安插点之后的现有元素个数」大于「新增元素个数」，二是「安插點之后的现有元素个数」小于等于「新增元素个数」，两种情况的处理方式不同。
「安插点之后的现有元素个数」大于「新增元素个数」:
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
if (n != ) { // 当 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) {
// 「安插点之后的现有元素个数」大于「新增元素个数」
// 先将尾端倒数「新增元素个数」（即倒数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 // 「安插點之后的现有元素个数」小于等于「新增元素个数」
...
}
「安插點之后的现有元素个数」小于等于「新增元素个数」：
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
if (n != ) { // 当 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) {
// 「安插点之后的现有元素个数」大于「新增元素个数」
...
}
else {
// 「安插點之后的现有元素个数」小于等于「新增元素个数」
//计算「新增元素个数」与「安插點之后的现有元素个数」的差值（n - elems_after），并从尾端开始，填充该差值个数的新值元素
uninitialized_fill_n(finish, n - elems_after, x_copy);
finish += n - elems_after; // 將vector 尾端标记后移
//再将「安插點之后的现有元素」全部复制到新尾端之后
uninitialized_copy(position, old_finish, finish);
finish += elems_after;
//这样从安插点开始，空出了「新增元素个数」的空位能给予安放新值
fill(position, old_finish, x_copy);
}
}
else { // 备用空间小于“新增元素个数”
...
｝
...
｝
第二种情况就是：备用空间小于新增元素个数n，处理方式就比上面容易理解多了：
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
if (n != ) { // 当 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) {
// 「安插点之后的现有元素个数」大于「新增元素个数」
}
else {
// 「安插點之后的现有元素个数」小于等于「新增元素个数」
}
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;
}
}
}
最新文章
- [BZOJ4200][Noi2015]小园丁与老司机
- UGUI text image 等加Shadow OutLine等
- Java冒泡随笔
- [翻译]:SQL死锁-死锁排除
- Java for LeetCode 233 Number of Digit One
- （转）2G到C-RAN网络架构的演进
- sprint3与总结
- Mac上的终端（Terminal）启动缓慢
- block中防止循环引用的一个高大上的宏定义
- jQuery 事件的命名空间
- JS 实现中英文翻译
- jquery easyui datebox单击文本框显示日期选择
- PHP READ PPT FILE
- Sublime Text个性化设置
- AC+DP练习
- 如何运行代码apk安装
- kindeditor修改图片上传路径-使用webapi上传图片到图片服务器
- 》》ajax加蒙版
- Function：html结构转字符串形式显示
- 数据挖掘概念与技术15--为快速高维OLAP预计算壳片段
热门文章
- MySQL Error：Warning: (1366, "Incorrect string value: '\\xF0\\x9F\\x98\\x82\\xF0\\x9F...' for column 'xxx' at row 2")
- 洛谷 P4281 [AHOI2008] 紧急集合 题解
- WinDbg 图形界面功能(三)
- C++中继承 声明基类析构函数为虚函数作用，单继承和多继承关系的内存分布
- Lightning Web Components 组件样式（四）
- 设置多个className
- D3.js的v5版本入门教程（第四章）—— 理解Update、Enter、Exit
- 微信小程序之使用wx:for遍历循环
- 2019暑假Java学习笔记（一）
- #C++初学记录（set进阶#acm cf 190802 B. Subsegments）