1. 从零开始手写C++ vector容器
在C++标准库中，vector是最常用的动态数组容器之一。很多初学者虽然会使用vector的各种接口，但对它的底层实现原理却知之甚少。今天我们就来彻底剖析vector的内部机制，并从头开始实现一个简化版的vector容器。
vector本质上是一个动态数组，它能够在运行时根据需要自动调整大小。与普通数组相比，vector的优势在于：
- 自动内存管理
- 动态扩容能力
- 丰富的成员函数
- 随机访问迭代器支持
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;
}
}
注意：析构时要先检查_start是否为nullptr，避免对空指针调用delete[]
3.2 拷贝控制
现代C++风格的拷贝赋值实现：
cpp复制void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> v) {
swap(v);
return *this;
}
这种实现利用了拷贝构造函数和swap函数，代码简洁且异常安全。
3.3 容量管理
reserve和resize是vector的核心容量管理函数：
cpp复制void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
T* tmp = new T[n];
// 深拷贝元素
for (size_t i = 0; i < old_size; ++i) {
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n; // 缩小
} else {
reserve(n);
while (_finish < _start + n) {
*_finish = val;
++_finish;
}
}
}
关键点：reserve只增不减，resize可以缩小size但不释放内存
3.4 元素访问
提供安全的元素访问接口：
cpp复制T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const {
assert(pos < size());
return _start[pos];
}
4. 迭代器实现与失效问题
4.1 迭代器设计
vector的迭代器就是原生指针的简单包装：
cpp复制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迭代器具有最高效的性能。
4.2 迭代器失效场景
vector操作中最需要注意的就是迭代器失效问题：
-
插入导致的失效：
- 扩容会使所有迭代器失效
- 插入位置后的迭代器可能失效
-
删除导致的失效：
- 被删除元素后的迭代器失效
- 删除可能触发缩容，使所有迭代器失效
解决方案是更新迭代器：
cpp复制iterator insert(iterator pos, const T& val) {
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage) {
size_t offset = pos - _start;
reserve(capacity() ? capacity() * 2 : 4);
pos = _start + offset; // 更新迭代器
}
// 插入逻辑...
return pos; // 返回新迭代器
}
5. 完整实现与测试
5.1 vector.h完整代码
cpp复制#pragma once
#include <iostream>
#include <algorithm>
#include <cassert>
namespace my {
template <typename T>
class vector {
public:
// 迭代器类型定义
typedef T* iterator;
typedef const T* const_iterator;
// 构造与析构
vector() = default;
~vector() { clear(); delete[] _start; }
// 容量相关
size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
bool empty() const { return _start == _finish; }
// 元素访问
T& operator[](size_t pos) { return _start[pos]; }
const T& operator[](size_t pos) const { return _start[pos]; }
// 迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
// 修改操作
void push_back(const T& val);
void pop_back();
iterator insert(iterator pos, const T& val);
iterator erase(iterator pos);
void clear() { _finish = _start; }
private:
T* _start = nullptr;
T* _finish = nullptr;
T* _end_of_storage = nullptr;
void reserve(size_t n);
};
// 成员函数实现...
} // namespace my
5.2 测试用例
cpp复制void test_vector() {
my::vector<int> v;
// 测试push_back和扩容
for (int i = 0; i < 10; ++i) {
v.push_back(i);
std::cout << "size: " << v.size()
<< ", capacity: " << v.capacity() << "\n";
}
// 测试迭代器
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
// 测试insert和迭代器失效
auto it = v.begin() + 5;
v.insert(it, 99);
std::cout << "After insert: ";
for (auto x : v) std::cout << x << " ";
std::cout << "\n";
// 测试erase
it = v.begin() + 3;
v.erase(it);
std::cout << "After erase: ";
for (auto x : v) std::cout << x << " ";
std::cout << "\n";
}
6. 实现中的关键问题与解决方案
6.1 深拷贝问题
在reserve实现中，直接使用memcpy会导致浅拷贝问题：
cpp复制// 错误做法 - 浅拷贝
memcpy(tmp, _start, size() * sizeof(T));
// 正确做法 - 深拷贝
for (size_t i = 0; i < size(); ++i) {
tmp[i] = _start[i]; // 调用元素的拷贝赋值
}
6.2 异常安全
现代C++风格的赋值操作符提供了强异常保证：
cpp复制vector<T>& operator=(vector<T> other) {
swap(other);
return *this;
}
这种实现如果在拷贝构造时抛出异常，不会影响原对象。
6.3 类型萃取
在实际STL实现中，会使用类型萃取技术来优化某些操作：
cpp复制// 伪代码 - 实际STL中的优化
if (std::is_trivially_copyable<T>::value) {
memcpy(dest, src, n * sizeof(T));
} else {
for (size_t i = 0; i < n; ++i) {
dest[i] = src[i];
}
}
7. 性能优化建议
- 预留容量：如果知道元素数量，提前reserve避免多次扩容
- 移动语义：为vector添加移动构造函数和移动赋值操作符
- emplace_back：实现原位构造，避免临时对象构造和拷贝
- 小型缓冲区优化：对小vector使用栈内存避免堆分配
实现emplace_back的例子：
cpp复制template <typename... Args>
void emplace_back(Args&&... args) {
if (_finish == _end_of_storage) {
reserve(capacity() ? capacity() * 2 : 4);
}
new (_finish) T(std::forward<Args>(args)...);
++_finish;
}
通过这次完整的vector实现，我们深入理解了动态数组容器的内部工作原理。在实际项目开发中，理解这些底层机制能帮助我们更高效地使用STL容器，并在必要时实现自定义的优化容器。