【C++笔记】STL详解：vector容器的实现

前言：

        在学习了vector类的基本使用的前提下，本文将重点分析vector类的常用接口及其应用实现。

一、vector成员变量

vector本质上是一个动态数组，通过原生指针来实现底层维护，为了使得STL接口调用的统一性，我们需要将原生指针重命名为迭代器。

其核心目的是：将数据结构（容器）与操作（算法）分离，并通过一种统一的接口（迭代器）将它们粘合在一起。

成员变量分析

template <class T> class vector { public: // 将原生指针重命名为迭代器，实现接口统一 typedef T* iterator; typedef const T* const_iterator; private: iterator _start; // 指向目前使用空间的头 iterator _finish; // 指向目前使用空间的尾 iterator _end_of_storage; // 指向目前可用空间的尾 };

成员变量分析：        

        

① iterator _start： 指向目前使用空间的头

        
② iterator _finish：指向目前使用空间的尾
   

③ iterator _end_of_storage：指向目前可用空间的尾        

如下图所示：

二、默认成员函数

2.1 无参构造        

vector 默认支持无参构造函数，此时将对象的三个成员变量初始化为空指针。

代码实现

vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) {}

2.2 构造函数：构造n个同类型的值

vector的带参构造函数， 它的作用是：创建一个初始包含 n 个元素的 vector，并且将这些元素全部初始化为给定的 value

函数原型：vector(size_t n, const T& value = T() )

        

函数参数：

        

① size_t n: 表示要初始化的元素个数。

        

② const T& value = T() : 这是你要填入的初始值，这里用到了缺省参数（默认参数）。

        

a. 如果你调用 vector<int> v(5, 10)  ，那么 value 就是 10。

        

b. 如果你只传一个参数 vector<int> v(5)，它就会调用 T()，也就是调用类型 T 的默认无参构造函数（产生一个匿名对象/临时对象）。

   

例如： T 是 int，T() 就会产生 0；如果 T 是 string，就会产生空字符串 ""。这保证了无论如何元素都会被正确初始化。

代码示例：

 //2.构造函数：构造出n个同类型的值 vector(size_t n, const T& value = T()) { //避免多次扩容 reserve(n); //尾插元素 for (size_t i = 0; i < n; i++) { push_back(value); } }

①核心优化 reserve(n)

        

因为 vector 底层是一个动态数组，push_back 每次插入元素时都会检查空间够不够。

        

如果不够，就会触发“开辟新空间 -> 拷贝旧数据 -> 释放旧空间”的昂贵操作。

        

        

如果你不加这行代码，当你插入 1000 个元素时，底层可能会经历好几次反复的扩容。

        

提前调用 reserve(n)，一次性向系统申请好足够容纳 n 个元素的内存，可以直接把后续插入的扩容开销降为 0。

        

        

②数据填充 for 循环与 push_back(value)

        

在确保容量足够的前提下，循环 n 次，每次将 value 尾插到动态数组中，顺便更新内部维护的数组有效元素个数（也就是 size）。

2.3 构造函数：迭代器区间构造

迭代器区间构造，它的作用是接收任意一段具有迭代器特性的区间 [first, last)，并把这段区间里的数据拷贝过来构造一个新的 vector。

注意：这里是具有迭代器特性的容器（并非只限制于vector，还可以是list、map...），进行传入迭代器区间就能进行构造。

                    template<class InputIterator>

函数原型：  vector(InputIterator first, InputIterator last)

        

函数模板：

        

它写成了泛型（独立的函数模板），它就可以接收任意容器的迭代器，甚至包括原生指针。        

        

函数参数：

        

① InputIterator first ：接收任意容器的迭代器，指向区间的起始位置

        

② InputIterator last ： 接收任意容器的迭代器，指向区间的终点位置

代码实现：

template<class InputIterator> vector(InputIterator first, InputIterator last) { //迭代器的区间构造 while (first != last) { push_back(*first); ++first; } }

有了这个设计，你可以做到下面这些极其方便的操作：

// 1. 用数组的指针区间来构造 int arr[] = {1, 2, 3, 4, 5}; vector<int> v1(arr, arr + 5); // 2. 用 std::list 的迭代器来构造 list<int> myList = {10, 20, 30}; vector<int> v2(myList.begin(), myList.end()); // 3. 用 std::string 的迭代器来构造字符 vector string str = "hello"; vector<char> v3(str.begin(), str.end());

为什么数组的原生指针也能支持迭代器区间构造呢？

        

        

①当你写下 vector<int> v1(arr, arr + 5); 时，编译器会去检查 arr（它的类型是 int* 原生指针）是否满足这三个要求：

        

②支持 != 吗？ 当然支持。int* 之间可以通过 != 来比较内存地址是否相同（arr != arr + 5 是完全合法的指针比较）。

        

③支持 * 吗？支持。*arr 可以直接解引用，拿到指针指向的那块内存里的 int 值。

        

④支持 ++ 吗？支持。++arr 是基础的指针算术运算，它会让指针在内存中向后移动 sizeof(int) 个字节，精确地指向下一个元素。

        

因为 int* 完美支持这三个操作，所以编译器欣然接受了它！

在编译的瞬间，编译器会在后台为你默默 “实例化”（生成）了一份专属的代码，看起来就像这样：

// 编译器自动为你生成的隐藏版本：把 InputIterator 替换成了 int* vector(int* first, int* last) { while (first != last) { push_back(*first); ++first; } }

2.4 拷贝构造函数

自定义 vector 类的拷贝构造函数，它的作用是使用一个已经存在的 vector 对象（v1）来初始化一个新的 vector 对象（v2）。

函数原型：vector(const vector<T>& v)        

        

注意事项：vector 类需要实现深拷贝，已经存在的 vector 对象（v1）来初始化一个新的 vector 对象（v2）,两个对象的维护的空间不相同。    

1. 代码实现：传统写法

vector(const vector<T>& v) { //创建临时对象 T* tmp = new T[v.capacity()]; //拷贝内容 for (size_t i = 0; i < v.size(); i++) { tmp[i] = v[i]; } //更新 新空间 _start = tmp; _finish = tmp + v.size(); _end_of_storage = tmp + v.capacity(); }

2.代码实现：现代写法

vector(const vector<T>& v) { //2.现代写法 reserve(v.capacity()); for (size_t i = 0; i < v.size(); i++) { push_back(v[i]); } }

代码解析：

        

1. reserve 实现了“空间独立”（物理隔离）

        

当代码执行 reserve(v.capacity ()) 时，reserve 函数内部的逻辑会去向操作系统申请一块全新的堆内存（底层通常是 new T[capacity]）。

        

这意味着，当前正在创建的新对象（v2），它的底层指针（_start）指向了一个刚刚分配出来的全新地址，而不是去复制源对象（v1）的地址。

        

此时 v2 和 v1 在物理上彻底成为了互不相干的两块内存区域。

        

        

2. push_back 实现了“数据复制”（内容填充）

       

在 for 循环中，push_back(v[i]) 负责把源对象 v1 里的元素挨个放入 v2 的新空间里。

        

这里隐藏着一个非常重要的细节——类型 T 的拷贝行为：

        

a. 如果 T 是内置类型（如 int, char）：v[i] 取出的是具体的值（比如数字 5），push_back 直接把 5 塞进新开辟的内存里。这是没有任何问题的。

        

b. 如果 T 是自定义类型（如 std::string 或另一个 vector）：当执行 push_back(v[i]) 时，实际上会调用类型 T 自己的赋值运算符。

        

这意味着，如果是vector<string>，push_back 会触发 string 自身的赋值运算符重载，这样就保证了哪怕 vector 里面存的是复杂的指针对象，也能实现“层层递进”的深拷贝。

2.5 赋值重载函数

自定义 vector 类的赋值运算符重载函数，用于处理两个已存在对象间的赋值操作，例如： v1 = v2 。

                  template<class T>

函数原型：vector<T>& operator= (vector<T> v)

   

注意事项：vector 类需要实现深拷贝，已经存在的 vector 对象（v1）赋值给已经存在的 vector 对象（v2）, 保持两个对象的维护的空间不相同。 

代码实现：现代写法copy-and-swap

template<class T> void vector<T>::swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } //5.赋值重载函数 vector<T>& operator= (vector<T> v) { swap(v); return *this; } 

核心拆解：Copy-and-Swap 的三步魔法

        

请特别注意这个函数的参数：vector<T> v，它是按值传递（传值），而不是按引用传递（没有 &）！ 这是一个极其关键的伏笔。

        

假设我们执行了 v1 = v2 ，下面是底层的执行全过程：

        

        

1. 魔法第一步：利用“传值”让编译器打工（触发拷贝构造）

        

因为参数是 vector<T> v（传值），当执行 v1 = v2 时，编译器会自动调用你的“拷贝构造函数”，用 v2 作为一个模版，在内存里偷偷复制出一个局部的、全新的临时对象 v。

        

这个 v 拥有独立的新空间，里面装满了和 v2 一模一样的数据。

        

此时的状态：v1 还是旧数据，v2 是源数据，v 是 v2 的完美克隆体。

        

        

2. 魔法第二步：狸猫换太子（执行 swap(v)）

        

进入函数体后，执行了 swap(v) ，这里的 swap 会把你写的类内部的三个指针（_start, _finish, _end_of_storage）进行互换。

        

交换前：v1 指向自己那块旧的、不要的内存；v 指向刚刚深拷贝出来的新内存。

        

交换后：v1 瞬间“窃取”了 v 的新内存！ 而 v 被塞满了 v1 原来的旧内存垃圾。

        

        

3. 魔法第三步：借刀杀人，自动清理垃圾（函数结束）

        

当函数执行到右括号 } 时，局部变量 v 的生命周期结束了。

        

系统会自动调用 v 的析构函数。

        

此时 v 手里拿着的正好是 v1 换给它的“旧垃圾空间”。于是，v 在临死前，顺手把 v1 原本该释放的旧内存给清理得干干净净！

        

        

4. 最后，return *this

        

只是为了支持连续赋值操作（比如 v1 = v2 = v3;），返回当前对象自己。

三、迭代器相关函数

3.1 begin

代码示例：

typedef T* iterator; const typedef T* const_iterator; //begin iterator begin() { return _start; } const_iterator begin() const { return _start; } 

3.2 end

代码示例：

typedef T* iterator; const typedef T* const_iterator; // end iterator end() { return _finish; } const_iterator end() const { return _finish; } 

四、容量大小相关函数

4.1size

如下图所示：size的大小

代码实现：

size_t size() const { return _finish - _start; }

4.2 capacity

如下图所示：计算capacity

代码实现：

size_t capacity() const { return _end_of_storage - _start; }

4.3 reserve

函数原型：void reserve(size_t n);

        

函数功能：

        

① 当 n > capacity 时才扩容。

                

② 当 n <= capacity 时不做任何操作。

代码实现

 //扩容函数reserve的实现：只进行扩容，不进行缩容 template<class T> void vector<T>::reserve(size_t n) { if (n > capacity()) { //存储旧空间的元素个数，防止因为_start迭代器 和 _finsh迭代器 没有同步更新而出现size计算错误 size_t oldsize = size(); //新空间的大小 size_t newcapacity = n; //申请新空间 T* tmp = new T[newcapacity]; //将旧空间的内容拷贝到新空间上 for (size_t i = 0; i < oldsize; i++) { tmp[i] = _start[i]; } //释放旧空间 if(_start) delete[] _start; //更新头部迭代器的指向 _start = tmp; //更新尾部迭代器的指向 _finish = tmp + oldsize; //更新存储容量的尾部 _end_of_storage = tmp + newcapacity; } }

1. 扩容门槛检查

        

        

作用：判断传入的容量 n 是否真的大于当前的容量。

        

意义：如果 n 小于或等于当前容量，说明现有的空间完全够用，直接什么都不做（这就保证了它“不缩容”的特性）。

        

        

2.  拯救程序的关键：保存 oldsize（极其重要！）

        

        

作用：提前把当前的元素个数（size）存到一个临时变量里。

        

为什么要这么做？ 

        

在你的 vector 实现中，size() 函数通常是这样计算的：return _finish - _start;。

        

如果在后面我们先执行了 _start = tmp;（把 _start 指向了新空间），但 _finish 还没更新，依然指向旧空间。

        

此时再调用 size()，就会变成 旧空间的尾指针 减去 新空间的头指针。

        

两个指向不同内存块的指针相减，会导致未定义行为（通常会算出一个极其巨大的垃圾数字）。

        

这会直接导致后面计算 _finish = tmp + size() 时指针越界，程序当场崩溃。

        

        

3. 申请新空间与数据搬家

        

        

        

申请空间：new T[newcapacity] 在堆区开辟了一块全新的、连续的内存。

        

数据搬家：通过 for 循环，将旧空间里的数据挨个赋值给新空间。

        

注：这里执行的是 T 类型的赋值操作（=），如果 T 是自定义类型（比如 MyString），这里会安全地触发 MyString 的赋值运算符重载，完成深拷贝。

        

        

4. 释放旧空间（过河拆桥）

        

        

        

作用：数据已经安全转移到新家，旧房子（旧内存）就必须交还给操作系统，否则就会导致内存泄漏。

        

细节：加上 if(_start) 是个好习惯，防止对空指针进行操作（虽然在 C++ 中 delete[] nullptr 是合法的、不会报错的，但显式判断能让逻辑更严谨）。

        

        

5. 更新内部指针（乔迁新居）

        

        

        

最后一步，将 vector 内部维护的三个核心“导航仪”全部更新到新空间的正确位置上，这里就用到了第一步提前保存好的 oldsize，精准定海神针，算出 _finish 的正确位置。

4.4 resize

函数原型：void resize(size_t n, const T& val = T());

        

函数功能： 通常用于初始化 

        

① 当所给值n > 当前 size 时，扩展 size 到该值，新增元素为指定值（默认 0）。

        
② 当所给值n < 当前 size 时，缩小 size 到该值，超出部分元素被移除。

代码实现：

//设置容器个数resize函数的实现：调整容器大小，使其包含 n 个元素。 template<class T> void vector<T>::resize(size_t n, const T& value) { reserve(n); if (n < size()) { _finish = _start + n; } else { while (_finish < _start + n) { *_finish = value; ++_finish; } } }

代码详解：

        

1. 兜底保护：提前扩容

        

        

作用：无论你要把有效元素变成多少个，首先保证底层的物理空间足够大。

        

细节：回忆一下你写的 reserve 逻辑，它有句判断 if (n > capacity())。

        

a. 如果传入的 n 比当前容量小，reserve 什么都不会做；

        

b .如果 n 超出了当前容量，它就会乖乖去申请新内存。这行代码就是一个完美的“兜底守卫”。

        

        

2. 场景 A：缩小有效数据范围 (缩容 / 截断)

        

        

        

作用：如果你要求的元素个数 n 比现在实际的元素少，那就直接把尾指针 _finish 往回挪。

        

举例：原来有 5 个元素，你调用 resize(3)，系统直接把 _finish 移动到第 3 个元素后面。

        

核心要点：物理内存（capacity）并没有变小，被“抛弃”的那 2 个元素其实还在内存里，只是对于 vector 来说，它们已经变成了“不可见”的废弃数据。

        

这就是所谓的“只改 size，不缩 capacity”。

        

        

3. 场景 B：扩大有效数据范围 (填补)

        

        

        

作用：如果你要求的元素个数 n 比现在多，那么不仅空间要够（第一步的 reserve 已经保证了），还需要把多出来的位置填满。

        

怎么填？ 通过 value 参数，如果你调用 resize(10, 100)，多出来的位置就会全被赋值为 100。

        

默认值 T()：注意你函数声明里的参数 const T& value = T()。

        

如果你只写了 resize(10)，系统会调用类型 T 的默认构造函数（比如 int 就是 0，string 就是空字符串 ""）来自动填充这些新位置。

4.5 empty

如图所示：当_finish == _strat 是，vector容器为空

代码示例：

bool empty() { return _start == _finish; }

五、修改容器相关函数

5.1 push_back

函数原型： void push_back(const T& x)

        

函数功能：在vector容器的末尾添加元素

代码实现：

//尾插函数push_back的实现：向容器中尾插一个元素 template<class T> void vector<T>::push_back(const T& x) { //判断是否要扩容 if (_end_of_storage == _finish) { //进行扩容 size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } //在尾部插入一个元素x , 如果是自定义类型需要手动补充赋值重载 *(_finish) = x; //更新尾部的指向 ++_finish; } 

5.2 pop_back

函数原型：void pop_back();

        

函数功能：删除vector容器的最后一个元素

代码实现：

//尾删函数pop_back的实现：删除容器尾部的一个元素 template<class T> void vector<T>::pop_back() { assert(!empty()); if (_finish != _start) { --_finish; } }

5.3 insert

函数原型：iterator insert(iterator pos, const T& x);       

        

函数功能： 在所给迭代器pos位置插入一个元素

代码实现：

 template<class T> typename vector<T>::iterator vector<T>::insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); //1.判断是否需要进行扩容 if (_end_of_storage == _finish) { //计算相对位置 size_t abs_site = pos - begin(); //进行扩容 size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); //更新pos位置，若进行扩容则指向pos位置的迭代器失效 pos = begin() + abs_site; } //2.挪动数据 iterator last = end(); while (last > pos) { *last = *(last-1); --last; } //3.插入数据 *pos = x; //4.更新迭代器位置 ++_finish; return pos; }

代码详细讲解：

        

                

0. 门禁检查：防范非法指针

        

        

作用：确保传入的 pos 是一个合法的范围。

        

细节：注意这里是 <= _finish，因为 insert 允许在当前数据的最末尾（也就是紧挨着最后一个元素的后面一个位置）进行插入，这其实就等同于 push_back 尾插。

        

        

1. 破解“迭代器失效”

        

        

发生了什么？  假设当前 vector 空间满了，触发了 reserve 扩容。

        

回忆一下你写的 reserve 函数，它会在底层 new 出一块全新的内存，把旧数据搬过去，然后把旧内存释放掉 (delete[] _start)。

                

        

致命危机：

        

传入的参数 pos 原本是指向旧内存里某个位置的指针。

        

一旦 reserve 执行完毕，旧内存被释放，pos 瞬间就变成了一个指向垃圾地址的野指针（这就是著名的“迭代器失效”）

        

如果此时你再往 *pos 里存数据，程序当场崩溃。

        

        

完美化解：

        

先用 pos - begin() 算出了 pos 距离首元素的相对偏移量 (abs_site)。

        

等新家建好之后，再拿着新家的首地址 begin() 加上偏移量，重新找回新家里的对应位置。

        

        

2. 挪动数据：为新元素腾出空间

        

        

作用：要把新元素插到 pos 的位置，就必须把 pos 及其后面的所有元素统统往后平移一位。

        

细节：注意看这个 while 循环，它是从后往前（从右向左）搬运的！

        

它先拿 end()（当前最后一个元素的后一个空位），把倒数第一个元素搬到这里，再把倒数第二个搬到倒数第一个的位置……

        

        

3 . 插入数据，更新迭代器

        

        

作用：位置腾出来了，直接把我们要插入的 x 放入 *pos 即可。

        

细节：因为多了一个元素，所以维护有效数据边界的指针 _finish 必须往后移动一位。

        

        

4. 为什么还要 return pos;？

        

        

        

作用：把更新后的、合法的迭代器位置交还给外面的调用者。

        

意义：这也是为了防范“迭代器失效”。

        

如果外部函数在使用 insert，插入完毕后，外部原本拿着的那个指向该位置的指针可能因为扩容已经失效了。

        

把新的 pos 返回去，外部接收后就可以继续安全地使用这个迭代器了。

5.4 erase

函数原型： iterator erase(iterator pos);

        

函数功能：删除所给迭代器在pos位置的元素

代码实现：

 template<class T> typename vector<T>::iterator vector<T>::erase(iterator pos) { //1.判断容器是否为空 assert(pos >= _start); assert(pos < _finish); //2. 挪动数据 iterator it = pos+1; while (it != end()) { *(it-1) = *it; ++it; } //3.更新尾部迭代器 --_finish; return pos; } 

代码详细讲解：         

        

        

1. 门禁检查：防范越界与空容器

        

        

作用：确保你要删除的位置是一个真实存在的数据。

        

 极其关键的区别：

        

a.在写 insert 时，边界条件是 pos <= _finish（带等于号），因为你可以在最后一个元素的后面强行插入（等价于尾插）。

        

b. 在 erase 里，必须是 < _finish（绝对不能等于），因为 _finish 指向的是最后一个有效数据的下一个位置（那是一个没有初始化的废弃空间）。

        

你当然不能去“删除”一个根本不存在的空气，同时，这也顺便保证了如果容器为空（_start == _finish），断言会直接报错拦截。

        

        

2. 挪动数据：向前覆盖，填补空缺

        

        

发生了什么？

        

假设你要删除数组里的第 3 个元素（pos），系统并不是真的用橡皮擦把那个位置擦掉。

        

而是直接把第 4 个元素盖到第 3 个位置上，第 5 个盖到第 4 个上……一路盖到最后。

        

        

方向的讲究：注意这里的 while 循环，它是 从前往后（从左向右）搬运的！

        

它先拿 pos 后面的第一个元素（it），覆盖掉 pos 的位置（*(it-1) ），接着 it 往后走，继续覆盖……

        

        

对比一下：insert 为了不压碎数据，必须从后往前搬；而 erase 为了填补前面被删除的坑，必须从前往后搬。

        

一旦方向搞反，整个数组的数据都会变成一模一样的重复值！

        

        

3. 更新尾部迭代器

        

        

作用：数据全部往前挪了一位，最后面自然就空出了一个废弃位置。所以管理有效数据的 _finish 指针必须往前退一步（size 随之减 1）。

                

物理本质：在 C++ 的 vector 中，所谓的“删除”，在底层其实仅仅是数据的覆盖加上尾指针的后退，底层开辟的物理内存（capacity）并没有发生任何缩小（不缩容原则）。

        

        

4. 返回值：解决 C++ 中臭名昭著的**“迭代器失效”**问题

        

        

作用：返回被删除元素紧挨着的下一个元素的新位置（因为后面的元素往前填补了，所以新位置其实还是当前的 pos 迭代器）。

        

为什么非要返回？ 这又是为了解决 C++ 中臭名昭著的 “迭代器失效” 问题。

                

        

场景演示：想象一下，如果你在一个 for 循环里一边遍历一边删除所有的偶数：

        

当你删除了当前位置的偶数后，后面的元素会全部往前挤。

        

此时如果你拿着原本的旧迭代器继续 ++，就会完美错过刚刚挤过来的新元素！返回更新后的 pos，能让外部调用者安全地接住变化后的新位置，继续无缝遍历。

5.5 clear

函数原型：void clear() ；

        

函数功能：把“逻辑上的有效元素”抹除，但底层向操作系统申请的物理内存（capacity）依然死死地攥在手里。   

代码实现：

void clear() { _finish = _start; }

六、访问容器相关函数

6.1 operator[]

函数原型：

        

①T& operator[](size_t pos)

        

②const T& operator[](size_t pos)const                

        

函数功能：返回向量容器中位置为 n 的元素的引用。

代码实现：

T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; }

既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。