当前位置：首页 > news >正文

【STL源码剖析】从源码看 vector：底层扩容逻辑与内存复用机制

news 2025/8/7 6:13:50

文章目录

前言
vector的数据结构
vector的迭代器
- 基础迭代器
- 借迭代器实现的函数
vector的构造和内存管理
- vector构造
vector的元素操作
- vector的push_back
- vector的pop_back
- vector的erase
- vector的insert

引用侯捷所著《STL源码剖析》（2002，华中科技大学出版社）前言内容：
人们常说，不要从轮子重新造起，要站在巨人的肩膀上，面对扮演轮子角色的这些STL组件，我们是否有必要深究其设计原理或实现细节呢？答案固人而异。从应用的角度思考，你不需要探索实现细节一一然而相当程度地认识底层实现，对实际运用绝对有帮助，从技术研究与本质提升的角度看，深究细节可以让你得族掌握一切一不论是为了重温数据结构和算法，或是为了扮演轮子角色，或是想要进一步扩张别人的轮子，都帮可因此获得深厚扎实的基础：天下大事，必作于细！参观飞机工厂不能让你学得流体力学、也不能让你学会开飞机。但是如果你既会开飞机又操流体力学，参观飞机工厂可以带给你最大的乐趣和价值。

本文并不适合STL初学者。对于那些熟练掌握 C++ 模板和 STL 的日常使用，理解内存分配与对象生命周期，并且有扎实的数据结构基础，希望深刻了解STL实现细节，从而得以提升对STL的扩充能力，或是希望藉由观察STL源代码，学习世界一流程序员身手，并藉此彻底了解各种被广泛运用之数据结构和算法的人，本文可能更适合你。

前言

为什么C++中要设计vector这个容器，相信使用过vector容器的都会发现，使用起来好像和数组一摸一样，只不过在操作的时候直接调用接口而不是自己对数组进行操作。vector底层实际上就是在维护一块动态开辟的空间，它把如何维护，维护的细节都封装起来的，用户通过一些对外开放的接口对这块空间进行操作；这就使得使用者只需要调用想做的操作，而不再需要控制维护一些管理时的繁琐细节，比如空间够不够？中间插入时要先挪动数据…

本篇博客将从5个部分来剖析解释vector的源码：

vector 的数据结构；
vector 的迭代器；
vector 的构造和内存管理；
vector 的操作接口；

本文的源码主要来自 SGI STL（Silicon Graphics, Inc. 实现的 STL 版本）；
关于源码可以到在线网站查看：源码网站，也可以下载源码压缩包：压缩包

vector的数据结构

为了降低频繁扩容的成本，vector实际配置的空间大小可能比客户端要求的更大一些，以备将来可能的扩容。这也就是说vector要维护一个比正在使用的空间更大的空间。换句话说，vector不仅有大小，还用容量，并且容量永远大于等于vector的大小。

vector管理的是线性的地址空间，采用的数据结构非常简单，使用三个指针/迭代器来对该线性空间进行管理，分别是：

start指向使用空间的起始位置；
finish指向使用空间的末尾；
end_of_storage指向可用空间的末尾。

如图是vector管理的示意图：
请添加图片描述

vector的迭代器

基础迭代器

vector维护的是连续线性的空间，不论内部存储的是什么类型，都是对线性空间进行操作和管理，这也就意味着vector中元素存储的地址是线性递增的，所以使用普通指针就可以满足对迭代器的需求，如operator* ，operator-> ，operator-- …，没有必要再对迭代器进行封装。

所以上面的start，finish，end_of_storage都是一个个的迭代器，本质就是一个个指向临界位置的指针，这三个迭代器也是vector类的默认成员。

template <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;             typedef value_type* iterator;                // 本质就是T*typedef const value_type* const_iterator;    // 本质就是const T*typedef value_type& reference;typedef const value_type& const_reference;typedef value_type* pointer;typedef const value_type* const_pointer;typedef size_t size_type;typedef ptrdiff_t difference_type;           // 一个__int64常用来对地址加减是的类型转换protected:iterator start;iterator finish;iterator end_of_storage;

借迭代器实现的函数

有了上面三个迭代器来划分空间的各个边界，判断容器是否满，容器已经使用空间的数量，以及容器的begin迭代器和end迭代器，解引用操作等，都可以直接实现。

template <class T, class Alloc = alloc>
class vector {
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); }
reference front() { return *begin(); }
reference back() { return *(end() - 1); }

vector的构造和内存管理

vector构造

看一下在项目中最常使用的vector构造，指定空间大小和初始值。

template <class T, class Alloc = alloc>
class vector {
public:vector(size_type n, const T& value) { fill_initialize(n, value); }protected:void fill_initialize(size_type n, const T& value) {start = allocate_and_fill(n, value);    // 开辟n个T类型的空间,并初始化为value finish = start + n;                     // 设置已使用空间的结束位置end_of_storage = finish;                // 设置容积边界}iterator allocate_and_fill(size_type n, const T& x) {iterator result = data_allocator::allocate(n);  // 开辟n个T类型的空间,底层就是malloc__STL_TRY {    // 宏就是tryuninitialized_fill_n(result, n, x);          // 将刚开辟好的空间进行初始化return result;}__STL_UNWIND(data_allocator::deallocate(result, n)); // 宏可以理解为catch}typedef simple_alloc<value_type, Alloc> data_allocator;

uninitialized_fill_n会根据第一个参数的类型，看内置类型还是自定义类型，如果内置类型就调用fill_n()来进行空间的初始化，如果时自定义类型，就调用construct()来进行放入构造对象实现初始化。

vector的元素操作

vector的push_back

在插入元素之前，vector会先判断容量够不够，是否需要扩容。此处扩容并不是直接在容器后面开辟新的空间，因为无法保证后面的空间是否被使用了，此处采用的方式是开辟一整块新的空间，将原数据拷贝过来，释放原来数据，最后将要插入的数据进行插入。

为了防止扩容时对原数据的拷贝和删除，vector在扩容的时候不是用一个扩一个，而是一次扩二倍。

template <class T, class Alloc = alloc>
class vector {
public:void push_back(const T& x) {if (finish != end_of_storage) {    // 空间够construct(finish, x);          // 直接在finish位置调用T类型的构造++finish;                      // 让finish指向下一个位置}else                               // 空间不够insert_aux(end(), x);              // 该函数实际上是用来实现指定位置插入的,此处是指定在end()结尾位置插入}
};template <class T, class Alloc>       // 指定位置position插入x
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {if (finish != end_of_storage) {      // 空间够construct(finish, *(finish - 1));  // 将finish-1位置的数据拷一份到finish++finish;           T x_copy = x;                     copy_backward(position, finish - 2, finish - 1);  // 将[positon , finish - 2]向后移动一位 ; copy_backward拷贝函数,从后往前拷贝, 将[position , finish - 2] 的数据拷贝到 finish - 1 位置,从后往前拷贝*position = x_copy;}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);      // 开空间iterator new_finish = new_start;                       __STL_TRY {new_finish = uninitialized_copy(start, position, new_start);   // 拷前半部分construct(new_finish, x);                              // 调构造,插入元素++new_finish;new_finish = uninitialized_copy(position, finish, new_finish); // 拷后半部分}#ifdef  __STL_USE_EXCEPTIONS catch(...) {destroy(new_start, new_finish); data_allocator::deallocate(new_start, len);throw;}
#endif /* __STL_USE_EXCEPTIONS */destroy(begin(), end());             // 释放原空间deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}
}

提醒：在对vector进行任何操作的时候，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了，所以在对vector进行增删后，原迭代器的使用要谨慎。

vector的pop_back

在pop_back中直接让finish向前移动一位，将删除位置视为可被覆盖，再调用删除位置对应元素的析构即可。

template <class T, class Alloc = alloc>
class vector {
public:void pop_back() {--finish;               // finish向前移动   destroy(finish);        // 调用析构}

vector的erase

先看一下erase删除区间[first , last)的实现：

  iterator erase(iterator first, iterator last) {iterator i = copy(last, finish, first); // 用[last,finish]的数据覆盖[first, last]destroy(i, finish);                     // 调用[i , finish) 析构 finish = finish - (last - first);       // 调整指针的位置 return first;}

请添加图片描述

删除指定位置的元素：

  iterator erase(iterator position) {if (position + 1 != end())                 copy(position + 1, finish, position);  // 将[position + 1 , finish)数据整体向前移动一位--finish;                                // finish向前移一位destroy(finish);                         // 将finish位置元素析构return position;}

vector的insert

此处以 void insert (iterator pos, size_type n, const T& x);在指定位置插入n个x数据：

分为两种情况：空间够，空间不够。

先看第一种：空间足够：

在空间足够的情况下，就只需要考虑对原数据的移动问题了。
在库中，将数据的移动分为了两种：

插入的个数 n < finish - position即position后面的有效数据比插入数据多，此时是：
1. 将[position , finish)分成了两组：[position , finish - n)和 [finish - n , finish)；
2. 先将[finish - n , finish)数据拷贝到finish后面；
3. 再将[position , finish - n)的数据拷贝到finish前面，最后插入数据；!
插入的个数 n >= finish - position即position后面的有效数据比插入数据少或等于，此时是：
1. 因为新增的数据一定会放到finish后面，所以先在finish后面插入 n - (finsh - position)个元素；
2. 再将[position,finish)的数据放到finish + n - (finsh - position)的后面；
3. 最后再将[position , finish)赋值为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) {uninitialized_copy(finish - n, finish, finish);  // 拷贝[finish - n ,finish)到finish后面finish += n;copy_backward(position, old_finish - n, old_finish); // 拷贝[position , old_finish - n]到old_finish前面fill(position, position + n, x_copy);            // 插入目标元素}else {uninitialized_fill_n(finish, n - elems_after, x_copy);  // 在finish后面插入缺少的目标元素finish += n - elems_after;uninitialized_copy(position, old_finish, finish);       // 将[position , old_finish)移动到finish的后面  finish += elems_after;fill(position, old_finish, x_copy);                     // 插入剩余的x元素}}else {// ......
}

第二种情况，空间不够，整体分五步：

先扩容；
将原来[start , position)的数据拷贝到新地址；
再新地址new_start + position的后面插入新增的元素；
将[position , finish)整体移动到new_satrt + position + n的后面；
最后进行收尾，将原空间释放，更新start和finish.

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) { // 空间足够}else {const size_type old_size = size();        const size_type len = old_size + max(old_size, n);iterator new_start = data_allocator::allocate(len);   // 开辟新空间iterator new_finish = new_start;                      __STL_TRY {new_finish = uninitialized_copy(start, position, new_start);  // 拷贝[start , positoin) 的数据到新空间new_finish = uninitialized_fill_n(new_finish, n, x);          // 插入目标元素new_finish = uninitialized_copy(position, finish, new_finish); // 将[start + position , finish)拷贝到new_satrt + position + n后面}
#         ifdef  __STL_USE_EXCEPTIONS catch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);               // 释放原空间deallocate();                         // 析构start = new_start;finish = new_finish;end_of_storage = new_start + len;}}