vector 源码解析

,

作为C++的第一个容器，vector在设计上有着许多值得我们学习的地方，这篇博文旨在记录 vector 的源码学习经历。当然关于 STL 源码解析，一本侯捷的《STL 源码剖析》就足够了，在这本书中作者详细的介绍了 C plus plus 的 STL “组件”的每一个函数。因此这篇文章不应该照搬书中的内容，如果只是单纯的照搬书中的知识，那么这篇文章就没有任何存在的价值。

额，怎么开始呢？ 所有的程序本质上是 data structure 和 algorithm。vector 作为 STL 中序列式容器的一员，自然也遵循着这一原理。

vector 的数据结构

vector 中的数据结构实现十分简单，你可以想象成三个指针,分别指向 ① 当前内存空间的首部(第一个元素) ② 当前内存空间的尾部 ③ 最后一个元素。
vector 数据结构

vector 的内存管理策略策略

vector 相较于 array能够自我的对内存空间进行控制，自由的改变自身容量的大小。但这就意味着，vector 需要为我们动态的维护内存空间的大小,如果当前的容器已经装不下新的元素时，那么会申请一块更大的内存空间,并将原来的元素 copy 到新地址，并释放掉旧的地址空间。

1
2
3
4
5
6
7
8
9
10
11
12
// vector 中的插入单个元素形如：
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){
	if(finish != end_of_storage) { //还有剩余空间
		//将position 之后的元素向后移动 
	} else { //已经没有剩余的空间了
		const size_type old_size = size();
    	const size_type len = old_size != 0 ? 2 * old_size : 1; //申请两倍的新空间
		iterator new_start = data_allocator::allocate(len);//申请空间
		//构造新空间copy, 插入元素,释放旧空间等等
	}
}

可以看见,每当当前的空间满了的时候，vector 需要做很多的额外的工作才能在正确的位置上插入新的元素。 因此避免重新申请(reallocation)内存空间对于高效的 vector 的使用十分重要。

下面将简要的证明,每次申请新的内存的空间为什么总是旧空间的两倍。

  • 我们假设一开始的空间为 1，插入10个元素,如果空间满,这时我们重新申请新的空间大小为之前的两倍
插入的元素 1 2 3 4 5 6 7 8 9 10
插入新元素的代价 1 1 1 1 1 1 1 1 1 1
移动元素的代价 1 2 4 8

不难看出 n 次插入过程的整体花费包含 n 次插入新元素的花销，以及 $\lfloor \lg (n-1) \rfloor$ 旧元素的花销。因此，整体的花销代价为：$ n + \sum_{i=0}^{ \lfloor \lg (n-1) \rfloor}{2^i} $ 。这个几何级数$\leqslant 2n$ ，所以最终的代价为 $O(n)$,平摊到 n 次插入操作,每次的代价为 O(1)

使用 vector 的技巧

通过阅读 vector 的源码，不难发现 vector 在设计上，尽可能的为我们提供高效率。但这并不代表我们就可以高枕无忧了。要想更加有效的使用 STL ,编码技巧是并不可少的。
对于 vector 的使用，我们除了注意不要频繁的申请新的空间(因为这样会付出极大的代价)，我们还需要对于额外的内存空间进行控制。vector 使用每次扩大为之前的两倍的策略使得最终插入操作到的代价为 O(1),这是时间上的优化，但 vector 不能从空间上进行优化，用户在使用 vector 时，应当注意空间上的浪费。

我们应该在使用在 vector 之前提供足够的空间来避免之后的重新申请内存空间。除默认构造函数外，vector 还为我们提供了诸多其他的构造函数，这使得我们能一开始就指定容器的容量大小

1
2
3
4
5
6
7
//构造函数
vector() : start(0), finish(0), end_of_storage(0) {}

vector(size_type n, const T& value) { 
	fill_initialize(n, value); //申请空间为n,并全部初始化为 value
}
//其他构造函数....

但事先成功的预测容器大小绝非易事。我们要做的是尽可能的提供足够的空间的同时，避免空间上的浪费。
另一个注意的点是：vector 提供的 resize() 函数并不能用来更改内存空间的大小。使用这个函数需要你提供参数 new_size 来指出你需要保留的容器的大小。如果给定的参数大于当前的容器的大小，那么该函数就会进行填充操作。而如果给定的参数小于容器当前的大小，那么该函数就会进行擦除操作。

1
2
3
4
5
6
7
void resize(size_type new_size) { resize(new_size, T()); }
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);
}

vector 为我们提供了 size()函数，通过这个函数我们能给知道当前元素的个数.因此，通过以下的代码我们就能将当前的元素的个数为 5。

1
2
vector<int> v(10,0);
v.resize(5); //保留5个元素

但是请注意这时 vector 的容量依旧是10，因为 vector 并不会更改 end_of_storage 的值，vector 会做的是调用多余元素的析构函数(如果有的话)，释放这部分空间。

要想更改当前容器的容量大小，在《Effective STL》 一书中Item 17，作者为什么提供了一种策略 —— 使用 **”the swap trick”**。

1
2
3
4
5
class Widget{};
vector<Widget> widgets;
//...插入元素等操作

vector<Widget>(widgets).swap(widgets);//删除当前容器的备用空间

vector(widgets) 会创建一个匿名的 vector 对象，而构造过程调用的是 vector 的copy构造函数。

1
2
3
4
5
6
7
//vector 的 copy构造函数
vector(const vector<T, Alloc>& x) {
	//这里只会申请 x.end() - x.begin() 个空间大小，也就是当前元素的个数,并完成 copy 元素操作
	start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
	finish = start + (x.end() - x.begin());
	end_of_storage = finish;
}

这样得到的匿名对象就没有额外的备用空间。之后在调用swap()函数交换匿名对象和源对象的三个状态迭代器(start、finish、end_of_storage)。

1
2
3
4
5
6
//只会交换 迭代器状态 ，因为 copy 元素操作由 copy构造函数完成了
  void swap(vector<T, Alloc>& x) {
    __STD::swap(start, x.start);
    __STD::swap(finish, x.finish);
    __STD::swap(end_of_storage, x.end_of_storage);
  }

随后匿名对象被销毁，销毁的是原 start 指向的空间。

使用copy构造函数创建临时对象是必须的，如果我们调用默认构造函数来构造对象，那么我们会删除掉所有的元素。

1
2
vector<Widget> widgets;
vector<Widget>().swap(widgets); //这会clear 掉 widgets的元素，并将容量设置为0