C++ vector容器底层深度剖析与模拟实现
🔥近津薪荼：个人主页
🎬个人专栏：《c语言基础知识详解》《c++基础知识详解》
✨每个优秀的人，
都有一段沉默的时光，
❄️那段时光是付出了很多努力，
却得不到结果的日子,我们把它叫做扎根，
⭐️祝您也祝我早日破土而出，巨木参天。
简介：本文主要以手打代码的方式来实现vector的各接口功能，带大家深入了解vector的底层原理~
目录
1 模板的使用说明
在C++中，模板是实现泛型编程的重要工具，它允许我们编写与数据类型无关的代码。vector容器正是通过模板技术实现的，可以存储任意类型的数据：
template<class T> class vector { // ... 实现细节 };这里的T是类型参数，当我们创建vector对象时，需要指定具体的类型
vector<int> intVector; // 存储int类型的vector vector<string> strVector; // 存储string类型的vector vector<double> dblVector; // 存储double类型的vector模板的使用让vector具有了极强的通用性，可以容纳各种数据类型，从基本类型到自定义类类型。
2 vector深度剖析及模拟实现
2.1 vector的成员变量
vector底层使用动态数组实现，通过三个指针来管理内存：
private: iterator _start = nullptr; // 指向数组的开始位置 iterator _finish = nullptr; // 指向最后一个元素的下一个位置 iterator _end_of_storage = nullptr; // 指向分配内存的末尾在这里，给了三个指针缺省值nullptr初始化。
2.2 构造函数
vector提供了多种构造函数来满足不同的初始化需求：、
2.2.1 指定大小和初始值的构造函数
vector(size_t n, const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(val); } } 使用示例：
vector<int> v1(5); // 包含5个0的vector vector<int> v2(3, 10); // 包含3个10的vector vector<string> v3(2, "hello"); // 包含2个"hello"的vector2.2.2 迭代器范围构造函数
template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } }这个构造函数是函数模板，可以接受任意类型的迭代器：
int arr[] = {1, 2, 3, 4, 5}; vector<int> v1(arr, arr + 5); // 从数组构造 vector<int> v2(v1.begin(), v1.end()); // 从另一个vector构造2.2.3 拷贝构造函数（现代写法）
vector(const vector<T>& v) { vector<T> tmp(v.begin(), v.end()); swap(tmp); }现代写法通过创建临时对象并交换资源，代码简洁且异常安全~
2.3 赋值运算符重载
vector<T>& operator=(vector<T> tmp) { swap(tmp); return *this; }2.4 容量相关操作
2.4.1 reserve 开空间
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { for (size_t i = 0; i < sz; i++) { std::swap(tmp[i], _start[i]); } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } }- 使用
std::swap而不是直接赋值，这样可以高效地交换资源（） - 如果直接使用
memcpy，对于管理资源的类（如string）会导致浅拷贝问题！ - 重新计算
_finish和_end_of_storage指针
2.4.2 用resize 调整大小
void resize(size_t n, T val = T()) { if (n < size()) { // 缩小size，只是移动_finish指针 _finish = _start + n; } else { reserve(n); // 可能需要扩容 while (_finish < _start + n) { *_finish = val; ++_finish; } } }这里使用匿名对象做缺省参数。
使用示例：
vector<int> v = {1, 2, 3}; v.resize(5); // 变为 {1, 2, 3, 0, 0} v.resize(2); // 变为 {1, 2}2.4.3 size和capacity
size_t capacity() const { return _end_of_storage - _start; } size_t size() const { return _finish - _start; }2.5 元素访问操作
2.5.1 下标运算符
T& operator[](size_t i) { assert(i < size()); return _start[i]; } const T& operator[](size_t i) const { assert(i < size()); return _start[i]; }提供const和非const版本，支持读写访问和只读访问。
2.6 修改操作
2.6.1 push_back 尾部添加元素
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; }扩容策略：初始为0时分配4个元素空间，否则每次扩容为原来的2倍。
2.6.2 pop_back 尾部删除元素
void pop_back() { assert(!empty()); --_finish; }2.6.3 insert 在指定位置插入元素
iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); // 扩容 if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } // 挪动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; }扩容后需要重新计算pos的位置，因为_start可能改变了。
2.6.4 erase 删除指定位置元素
iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; }3 vector迭代器失效问题
迭代器失效是使用vector时需要特别注意的问题，不当使用会导致未定义行为。
3.1 insert失效问题
当在vector中插入元素时，如果引起扩容，所有迭代器都会失效。
void test_vector2() { bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); auto it = v.begin() + 3; v.insert(v.begin(), 0); // 可能引起扩容 // insert以后，it失效了，不能再使用 // *it = 10; // 错误！未定义行为 }3.2 erase失效问题
erase操作会使被删除元素及其后面所有元素的迭代器失效。
void test_vector3() { bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); auto it = v.begin() + 2; v.erase(v.begin()); // 删除第一个元素 // it失效了，不能访问，访问结果未定义 // cout << *it << endl; // 错误！ }3.3 删除所有的偶数
正确使用erase删除元素的模式：
void test_vector4() { bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); // 正确做法：接收erase的返回值 auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); // erase返回下一个有效迭代器 } else { ++it; } } // 错误做法：直接递增迭代器 // auto it = v.begin(); // while (it != v.end()) // { // if (*it % 2 == 0) // { // v.erase(it); // erase后it失效 // } // ++it; // 错误：对失效迭代器递增 // } }3.4 不同编译器对迭代器失效的检查
不同编译器对迭代器失效的检查严格程度不同：
- Debug模式下通常会进行严格的迭代器检查
- Release模式下可能没有检查，导致难以发现的bug
- Linux的gcc编译器检查就会比较宽松
3.5 扩容之后，迭代器已经失效了
vector<int> v = {1, 2, 3}; auto it = v.begin(); v.push_back(4); // 可能引起扩容 // it已经失效，不能再使用3.6 erase删除的迭代器如果是最后一个元素
vector<int> v = {1, 2, 3}; auto it = v.begin() + 2; // 指向3 it = v.erase(it); // 删除最后一个元素 // 此时it == v.end()，不能解引用3.7 string的迭代器失效
与vector类似，string在插入、扩容操作、erase之后，迭代器也会失效。
4 本文代码完整展示
（一）vector.h
#pragma once #include <iostream> #include <assert.h> using namespace std; namespace bit { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } // 构造函数 - 指定大小和初始值 vector(size_t n, const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(val); } } vector(int n, const T& val = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(val); } } // 迭代器范围构造函数 template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } } // 默认构造函数 vector() = default; // 拷贝构造函数（现代写法） vector(const vector<T>& v) { vector<T> tmp(v.begin(), v.end()); swap(tmp); } // 赋值运算符（现代写法） vector<T>& operator=(vector<T> tmp) { swap(tmp); return *this; } // 交换两个vector void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } // 清空元素 void clear() { _finish = _start; } // 判断是否为空 bool empty() const { return _start == _finish; } // 预留空间 void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { for (size_t i = 0; i < sz; i++) { std::swap(tmp[i], _start[i]); } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } // 调整大小 void resize(size_t n, T val = T()) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish < _start + n) { *_finish = val; ++_finish; } } } // 获取容量 size_t capacity() const { return _end_of_storage - _start; } // 获取元素个数 size_t size() const { return _finish - _start; } // 下标运算符 T& operator[](size_t i) { assert(i < size()); return _start[i]; } const T& operator[](size_t i) const { assert(i < size()); return _start[i]; } // 尾部添加元素 void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; } // 尾部删除元素 void pop_back() { assert(!empty()); --_finish; } // 在指定位置插入元素 iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } // 删除指定位置元素 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; } // 析构函数 ~vector() { if (_start) { delete[] _start; _start = _finish = _end_of_storage = nullptr; } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; }（二）Test.c
#include "vector.h" #include <iostream> using namespace std; namespace bit { // 打印vector内容 void Print(const vector<int>& v) { for (auto e : v) { cout << e << " "; } cout << endl; } // 测试基本操作 void test_vector1() { cout << "测试基本操作:" << endl; bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v[0]++; // 修改第一个元素 Print(v); // 范围for遍历 for (auto e : v) { cout << e << " "; } cout << endl; } // 测试insert操作 void test_vector2() { cout << "\n测试insert操作:" << endl; bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); Print(v); v.insert(v.begin(), 0); // 头部插入 Print(v); // 注意：insert后迭代器可能失效 auto it = v.begin() + 3; v.insert(it, 30); // 指定位置插入 Print(v); } // 测试erase操作 void test_vector3() { cout << "\n测试erase操作:" << endl; bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.erase(v.begin()); // 删除第一个元素 Print(v); auto it = v.begin() + 2; v.erase(it); // 删除指定位置元素 Print(v); } // 测试删除特定元素（删除所有偶数） void test_vector4() { cout << "\n测试删除所有偶数:" << endl; bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); cout << "删除前: "; for (auto e : v) { cout << e << " "; } cout << endl; // 正确删除方法 auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); // 接收erase返回值 } else { ++it; } } cout << "删除后: "; for (auto e : v) { cout << e << " "; } cout << endl; } // 测试resize操作 void test_vector5() { cout << "\n测试resize操作:" << endl; bit::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); cout << "原始vector: "; for (auto e : v) { cout << e << " "; } cout << endl; v.resize(3); // 缩小 cout << "resize(3): "; for (auto e : v) { cout << e << " "; } cout << endl; v.resize(20, 5); // 扩大并填充 cout << "resize(20, 5): "; for (auto e : v) { cout << e << " "; } cout << endl; } // 测试拷贝构造和赋值 void test_vector6() { cout << "\n测试拷贝构造和赋值:" << endl; bit::vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(6); cout << "v1: "; for (auto e : v1) { cout << e << " "; } cout << endl; // 拷贝构造 bit::vector<int> v2(v1); cout << "v2(拷贝v1): "; for (auto e : v2) { cout << e << " "; } cout << endl; // 赋值操作 bit::vector<int> v3 = {10, 20, 30, 40}; v1 = v3; cout << "v1(赋值后): "; for (auto e : v1) { cout << e << " "; } cout << endl; // 指定大小构造 bit::vector<int> v4(10, 1); cout << "v4(10个1): "; for (auto e : v4) { cout << e << " "; } cout << endl; bit::vector<char> v5(10, 'x'); cout << "v5(10个x): "; for (auto e : v5) { cout << e << " "; } cout << endl; } // 测试string类型vector void test_vector7() { cout << "\n测试string类型vector:" << endl; bit::vector<string> v1; v1.push_back("111111111111111111111111"); v1.push_back("222222222222222222222222"); v1.push_back("333333333333333333333333"); v1.push_back("444444444444444444444444"); v1.push_back("555555555555555555555555"); for (auto& e : v1) { cout << e << " "; } cout << endl; } } int main() { bit::test_vector1(); bit::test_vector2(); bit::test_vector3(); bit::test_vector4(); bit::test_vector5(); bit::test_vector6(); bit::test_vector7(); return 0; }C++ vector基于动态数组实现，通过三个指针管理内存。核心风险是迭代器失效：insert可能扩容使所有迭代器失效；erase使被删位置后迭代器失效，必须通过it=erase(it)接收返回值。采用2倍扩容策略，现代写法通过swap实现安全拷贝。连续存储支持高效随机访问，但需警惕迭代器失效这一主要陷阱。
阅文辛苦啦，吃透这些不容易，休息一下把~~
我们下期再见~
