深入剖析STL源码之vector详解——基于GCC 2.9
vector 概述
vector 的数据安排和操作相比 array 唯一的区别就是更加灵活。array 是静态空间，一旦配置好了就无法改变；vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
vector 的实现技术，关键在于其对大小的控制以及重新配置时对数据移动效率。
vecotr 迭代器、构造与内存管理
以下是 vector 定义的源码摘录 （GCC 2.9） ，图片中只展示了一部分。SGI STL将 vector 的实现于更底层的 <stl_vector.h>。
vector 所采用的数据结构非常简单：线性连续空间。它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已经被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端。
为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求量大一些，以备将来可能的扩充。这便是容量（capacity）的观念。也就是说，一个 vector 的容量永远等于其大小。一旦容量等于大小，便是满载，下次再有新元素增加，整个 vector 就需要扩充，如下图。
运用 start、finish、end_of_storage 三个迭代器，便可轻易地提供首位标示、大小、容量、空容器判断、标注( [ ] ) 运算子、最前端元素值、最后端元素值等。
vector 的元素操作
关键源码解析
push_back
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/*
！！！ finish指向的是最后一个位置的后一个 「左闭，右开」
*/
void push_back(const T& x) { // 将元素插入最尾端
if (finish != end_of_storage) { // 还有剩余空间
construct(finish, x); // 在 finish 指向的位置用拷贝构造构造一个 x
++finish; // 尾指针后移
} else {
insert_aux(end(), x); // 调用辅助函数，负责扩容并插入
}
}
// insert_aux() 是 vector 的私有成员函数。当空间不足时，它负责重新分配内存并插入元素 x
// 这里使用了模板参数 T（元素类型）和 Alloc（内存分配器）
template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
// 虽然从 push_back 中已经判断了一次，但 insert_aux 也可能被其他函数调用，所以需要再次检查
if (finish != end_of_storage) {
// 将最后一个元素向后复制一份
// 在 finish 所指的位置构造一个和前一个元素相同的新对象
construct(finish, *(finish - 1));
++finish;
// 先拷贝一份 x，防止后续的 copy_backward 覆盖了原数据（比如 x 是 vector 内部某一位置的元素）
T x_copy = x;
// 将从 position 开始到 finish - 2 的元素向后移动一位，为 position 腾出位置
// 注意范围是 [position, finish - 2) 向后挪到 [position+1, finish - 1)
copy_backward(position, finish - 2, finish - 1);
// 在空出的位置插入新元素
*position = x_copy;
} else {
const size_type old_size = size();
// 如果不是空容器，扩容为原来的 2 倍；否则分配一个元素空间
const size_type len = old_size != 0 ? 2 * old_size : 1;
// 用 allocator 分配一块新的内存区域（未初始化）
Iterator new_start = data_allocator::allocate(len);
// 初始化新的 finish 指针，用来记录新内存中最后一个构造元素的位置
Iterator new_finish = new_start;
try {
// 把旧内存中从 start 到 position 的元素「左闭，右开」，复制构造到 new_start 开始的空间中
// uninitialized_copy()返回的是：指向新空间中最后一个被构造元素的“下一个位置”
new_finish = uninitialized_copy(start, position, new_start);
construct(new_finish, val);
++new_finish;
// 将 position 到 finish 的旧数据继续复制到新空间的后面
new_finish = uninitialized_copy(position, finish, new_finish);
} catch (...) { // 若在拷贝或构造过程中抛出异常，需销毁已构造的对象并释放新内存
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
// 销毁旧内存中的所有对象（调用析构函数），但不释放内存
destroy(begin(), end());
// 释放 vector 原来分配的那块内存，不析构对象
data_allocator::deallocate(start, end_of_storage - start);
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}pop_back
1
2
3
4void pop_back() {
--finish;
destory(finish);
}erase
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// 清除 [first, last) 中的所有元素
// 返回值是：删除元素后，新元素被移动到的那个位置（即 first，现在是新值的起始位置）
iterator erase(iterator first, iterator last) {
// 把 [last, finish) 的元素向前移动到从 first 开始的位置
// 即把被删元素后面的内容整体前移，覆盖被删除的部分
/*
原数据: [A] [B] [C] [D] [E] [F]
↑ ↑ ↑
first last finish
假设 fist指向C、last指向 E（删除 C、D）
将 [last, finish) = [4, 6) = E, F 拷贝到 first（index 2） 的位置
操作后: [A] [B] [E] [F] [E] [F]
↑
i（返回结果）
此时 i 指向新数据末尾的下一个位置，原来index 4、5上的值变成了冗余，需要销毁
*/
iterator i = copy(last, finish, first);
// 显式销毁 [i, finish) 区间的内容（这些是“旧的冗余副本”，已经被移动过来，不再需要）
destory(i, finish);
// 调整 finish 指针，表示当前 vector 中有效元素的新末尾
finish = finish - (last - first);
return first;
}
// 返回删除位置的迭代器，此时它指向的是移动后的新元素
iterator erase(iterator position) {
//如果position不是最后一个元素，就把它后面的所有元素往前移动一个位置，覆盖掉当前这个要删除的元素
if (position + 1 != end()) {
copy(position + 1, finish, position);
}
// 将 finish 指针向前移动一位，因为元素被删掉了, 表示 vector 的“有效长度”减 1。
--finish;
// 销毁逻辑上已经无效的最后一个元素（冗余数据）
destory(finish);
return position;
}clear
1
2
3
4
5
6
7
8
9
10
11
12
13
14void clear() {
erase(begin(), end());
}
/*
begin() 和 end() 都是当前类（vector）的成员函数；
erase() 也是当前类的成员函数；
在成员函数内部，调用本类其他成员成员时，可以省略 this-> 前缀；
编译器会默认认为你是在调用当前对象的成员。
上面函数等价于：
void clear() {
this->erase(this->begin(), this->end());
}
*/insert
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
92
93// 从 position 位置开始，插入 n 个元素，元素的初值为 x
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
if (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 = 2， x = 9
原数据: [0] [1] [2] [3] [4] [5]
↑ ↑
position(1) finish(6)
1.将[6-2, 6) 的元素移动到下标 6 开始的位置
1.操作后: [0] [1] [2] [3] [4] [5] [-4-] [-5-]
↑
finish(6)
2.更新finish （finish = 6 + 2）
2.操作后: [0] [1] [2] [3] [4] [5] [-4-] [-5-]
↑ ↑ ↑
position(1) old_finish(6) finish(8)
3.将[1, 6-2) 的元素向后复制到区间 [6 - (6 - 2 - 1), 6)----> [3, 6)
3.操作后: [0] [1] [2] [-1-] [-2-] [-3-] [-4-] [-5-]
↑ ↑ ↑
position(1) old_finish(6) finish(8)
*/
// 将 [finish - n, finish) 的元素移动到finish开始的位置-----预留空间足够插入 n 个元素
// 是在尚未构造的空间调用拷贝构造函数，把末尾的 n 个元素重新构造到finish后面
uninitialized_copy(finish - n, finish, finish);
finish += n;
// 将插入点后多余的元素搬后面，腾出插入空间
// 把区间 [position, old_finish - n) 的元素，从后往前搬移，复制到[old_finish - (old_finish - n - position), old_finish) 区间
// 也就是说，把原来插入点之后紧跟着的元素，整体往后移动 n 个位置
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();
// 新分配空间大小 len：是当前大小加上较大的那个——old_size 和 插入数量 n 的较大值
// 这保证了容量扩张至少翻倍，避免频繁扩容
const size_type len = old_size + max(old_size, n);
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
/*
假设原 vector 元素为 [1, 2, 3, 4]，容量是4，准备在 position（下标2，元素3）插入3个值为7的新元素
old_size = 4， n = 3
len = 4 + max(4, 3) = 8 （容量扩张到8）
内存操作：
1.新分配8个元素空间
2.复制 [1, 2] 到新内存 ------ [1, 2, -, -, -, -, -, -]
3.在下标2、3、4位置构造3个7 ------ [1, 2, 7, 7, 7, -, -, -]
4.复制 [3, 4] 到下标5、6位置 ------ [1, 2, 7, 7, 7, 3, 4, -]
5.释放旧内存，更新指针
final:
[1, 2, 7, 7, 7, 3, 4]
size = 7, capacity = 8
*/
// 将原 vector 中 [start, position) 的元素复制到新空间，从 new_start 开始
// uninitialized_copy()返回的是：指向新空间中最后一个被构造元素的“下一个位置”
new_finish = uninitialized_copy(start, position, new_start);
// 从 new_finish 位置开始构造 n 个值为 x 的元素（插入的新元素），new_finish再次更新
new_finish = uninitialized_fill_n(new_finish, n, x);
// 将原 vector 中 [position, finish) 的元素复制到新空间后面，紧跟插入的新元素之后。
// new_finish 最终指向新空间中所有元素的尾后地址
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch(...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
// 销毁并释放旧内存，更新指针
destroy(start, finish);
data_allocator::deallocate(start, end_of_storage - start);
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}
测试
下面是一个简短的测试程序，重点观察构造方式、元素的添加、以及大小、容量的变化
1 | // vector-test.cpp |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 chengoasis！
