1. 从零开始手写C++ vector容器
在C++标准库中,vector是最常用的动态数组容器之一。很多初学者虽然会使用vector的各种接口,但对它的底层实现原理却知之甚少。今天我们就来彻底剖析vector的内部机制,并从头开始实现一个简化版的vector容器。
vector本质上是一个动态数组,它能够在运行时根据需要自动调整大小。与普通数组相比,vector的优势在于:
- 自动内存管理
- 动态扩容能力
- 丰富的成员函数
- 随机访问迭代器支持
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. vector的核心架构设计
2.1 底层数据结构
vector的底层实现通常使用三个指针来管理动态数组:
cpp复制template<class T>
class vector {
private:
T* _start = nullptr; // 指向数组首元素
T* _finish = nullptr; // 指向最后一个元素的下一个位置
T* _end_of_storage = nullptr;// 指向分配内存的末尾
};
这种设计有几个关键优势:
- 通过指针差值可以快速计算size和capacity
- 扩容时只需调整指针,不需要移动数据
- 迭代器就是普通指针,实现简单高效
2.2 内存管理策略
vector采用"容量翻倍"的扩容策略:
- 初始容量通常为0或一个小的默认值(如4)
- 每次push_back时检查容量
- 容量不足时,按当前容量的2倍扩容
- 扩容时分配新内存,拷贝数据,释放旧内存
这种策略虽然有时会浪费一些内存,但保证了插入操作的均摊时间复杂度为O(1)。
3. vector关键接口实现详解
3.1 构造函数与析构函数
vector提供了多种构造函数重载:
cpp复制// 默认构造函数
vector() = default;
// 迭代器范围构造
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);
++first;
}
}
// 填充构造
vector(size_t n, const T& val = T()) {
reserve(n);
for (size_t i = 0; i < n; ++i) {
push_back(val);
}
}
析构函数负责释放分配的内存:
cpp复制~vector() {
if (_start) {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
