从零实现 C++ Vector
💬 欢迎讨论：学习过程中有问题吗？随时在评论区与我交流。你们的互动是我创作的动力！
👍 支持我：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友吧！
🚀 一起成长：欢迎分享给更多对计算机视觉和图像处理感兴趣的小伙伴，让我们共同进步！
前言
在现代 C++ 编程中，容器类 vector 是不可或缺的数据结构。作为一个动态数组，它提供了高效的随机访问和动态内存管理。为了加深对 vector 的理解，本文将从零开始模拟实现一个 vector，详细解析其核心机制。我们不仅会展示基础的构造、拷贝、扩展和元素插入操作，还将采用现代 C++ 的最佳实践来优化代码，尤其是在异常安全和性能上。
通过从浅入深的分步骤实现与测试，希望让读者能够全面掌握 vector 的核心逻辑与细节。本教程不仅适合初学者，也适合想深入理解 C++ STL 背后实现的开发者。
1. 基本结构与初始化细分
1.1 空构造函数的实现与测试
- 实现一个空的
vector，不分配任何内存。 - 测试是否创建了容量为0的
vector。
实现代码：
namespace W { template<class T> class vector { public: typedef T* iterator; vector() : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr) {} size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }
测试用例：
void TestEmptyVector() { W::vector<int> v; assert(v.size() == 0); // 验证大小 assert(v.capacity() == 0); // 验证容量 assert(v.empty()); // 验证是否为空 std::cout << "TestEmptyVector passed" << std::endl; }
输出：
TestEmptyVector passed
1.2 带大小和默认值的构造函数
- 初始化一个给定大小的
vector，并使用默认值填充。 - 测试构造后大小、容量是否符合要求。
实现代码：
namespace W { template<class T> class vector { public: typedef T* iterator; vector(size_t n, const T& value = T()) { _start = new T[n]; _finish = _start + n; _endOfStorage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = value; // 填充默认值 } } size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } T& operator[](size_t pos) { return _start[pos]; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }
测试用例：
void TestInitVector() { W::vector<int> v(5, 10); assert(v.size() == 5); // 验证大小 assert(v.capacity() == 5); // 验证容量 assert(!v.empty()); // 验证非空 for (size_t i = 0; i < 5; ++i) { assert(v[i] == 10); // 验证默认值 } std::cout << "TestInitVector passed" << std::endl; }
输出：
TestInitVector passed
1.3 拷贝构造函数
- 实现
vector的拷贝构造函数。 - 测试拷贝后的
vector是否完全复制原来的内容和容量。
实现代码：
namespace W { template<class T> class vector { public: typedef T* iterator; vector(const vector<T>& v) { size_t n = v.size(); _start = new T[n]; _finish = _start + n; _endOfStorage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = v._start[i]; // 复制数据 } } size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } T& operator[](size_t pos) { return _start[pos]; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }
测试用例：
void TestCopyVector() { W::vector<int> v1(5, 10); W::vector<int> v2(v1); assert(v2.size() == 5); // 验证大小 assert(v2.capacity() == 5); // 验证容量 for (size_t i = 0; i < 5; ++i) { assert(v2[i] == 10); // 验证数据拷贝 } std::cout << "TestCopyVector passed" << std::endl; }
输出：
TestCopyVector passed
1.4 赋值操作符的实现
- 实现赋值操作符重载。
- 测试两个
vector赋值后，是否正确拷贝了内容和容量。
实现代码：
namespace W { template<class T> class vector { public: typedef T* iterator; vector<T>& operator=(const vector<T>& v) { if (this != &v) { delete[] _start; // 释放旧的空间 size_t n = v.size(); _start = new T[n]; _finish = _start + n; _endOfStorage = _finish; for (size_t i = 0; i < n; ++i) { _start[i] = v._start[i]; // 复制数据 } } return *this; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } T& operator[](size_t pos) { return _start[pos]; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } private: iterator _start; iterator _finish; iterator _endOfStorage; }; }
测试用例：
void TestAssignVector() { W::vector<int> v1(5, 10); W::vector<int> v2 = v1; // 赋值操作 assert(v2.size() == 5); // 验证大小 assert(v2.capacity() == 5); // 验证容量 for (size_t i = 0; i < 5; ++i) { assert(v2[i] == 10); // 验证数据拷贝 } std::cout << "TestAssignVector passed" << std::endl; }
输出：
TestAssignVector passed
2. 容量管理的实现与测试
2.1 reserve函数：动态扩容
- 实现
reserve函数，测试在容量不足时是否能正确扩展。
实现代码：
namespace W { template<class T> class vector { public: void reserve(size_t n) { if (n > capacity()) { size_t oldSize = size(); T* tmp = new T[n]; for (size_t i = 0; i < oldSize; ++i) { tmp[i] = _start[i]; } delete[] _start; _start = tmp; _finish = _start + oldSize; _endOfStorage = _start + n; } } }; }
测试用例：
void TestReserveVector() { W::vector<int> v(5, 10); v.reserve(10); // 预留容量 assert(v.capacity() == 10); // 验证容量扩展 for (size_t i = 0; i < 5; ++i) { assert(v[i] == 10); // 验证数据保持不变 } std::cout << "TestReserveVector passed" << std::endl; }
输出：
TestReserveVector passed
2.2 resize函数：改变大小
- 实现
resize函数，测试增加或减少vector大小。
实现代码：
namespace W { template<class T> class vector { public: void resize(size_t n, const T& value = T()) { if (n < size()) { _finish = _start + n; // 缩小大小 } else { reserve(n); for (iterator it = _finish; it != _start + n; ++it) { *it = value; // 填充新值 } _finish = _start + n; } } }; }
测试用例：
void TestResizeVector() { W::vector<int> v(5, 10); v.resize(8, 20); // 扩展大小并填充新值 assert(v.size() == 8); // 验证扩展后大小 for (size_t i = 0; i < 5; ++i) { assert(v[i] == 10); // 验证原值不变 } for (size_t i = 5; i < 8; ++i) { assert(v[i] == 20); // 验证新值 } std::cout << "TestResizeVector passed" << std::endl; }
输出：
TestResizeVector passed
3. 元素插入与删除
3.1 push_back函数：向vector末尾插入元素
3.1.1 需求分析
push_back是vector中最常用的操作之一。需要确保：
- 当空间不足时，进行自动扩容。
- 插入的元素位于现有元素的末尾。
实现思路
- 检查容量是否足够，若不足则扩容（通常容量加倍）。
- 将新元素插入到当前末尾。
- 更新
_finish指针，指向新的末尾。
实现代码：
namespace W { template<class T> class vector { public: void push_back(const T& x) { // 如果空间不足，扩展容量为当前容量的两倍 if (_finish == _endOfStorage) { size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2; reserve(newCapacity); } // 在末尾插入新元素 *_finish = x; ++_finish; } private: T* _start; T* _finish; T* _endOfStorage; }; }
测试用例：
void TestPushBackVector() { W::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); assert(v.size() == 3); // 验证插入后的大小 assert(v.capacity() >= 3); // 验证容量是否自动扩展 assert(v[0] == 1 && v[1] == 2 && v[2] == 3); // 验证插入的元素是否正确 std::cout << "TestPushBackVector passed" << std::endl; }
输出：
TestPushBackVector passed
【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化2:https://developer.aliyun.com/article/1617541
