1. 揭开C++ vector的神秘面纱：三指针模型解析
在C++标准库中，vector是最常用的动态数组容器之一。很多开发者只停留在使用层面，对其底层实现原理知之甚少。今天我将带大家深入vector的底层实现，从三指针模型开始，逐步实现一个完整的vector类。
vector本质上是一个动态管理的连续内存块，通过三个指针精确控制内存的使用情况：
_start：指向内存块的起始位置（第一个元素的地址）_finish：指向最后一个有效元素的下一个位置_end_of_storage：指向内存块的末尾（容量的边界）
这三个指针构成了vector的核心控制机制。通过它们，我们可以轻松计算出vector的当前状态：
cpp复制size_t size() const {
return _finish - _start; // 有效元素个数
}
size_t capacity() const {
return _end_of_storage - _start; // 总容量
}
注意：这里使用指针相减而不是直接维护size和capacity变量，是因为指针运算能更直观地反映内存布局，也减少了维护额外变量的开销。
2. vector迭代器设计与实现
2.1 迭代器的本质
vector的迭代器本质上就是原生指针的封装，得益于连续内存的特性，vector的迭代器支持随机访问，这是它与list等容器的重要区别。
cpp复制template<class T>
class vector {
public:
using iterator = T*; // 迭代器就是原生指针
using const_iterator = const T*;
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
};
2.2 迭代器使用示例
下面是一个简单的测试用例，展示了如何使用迭代器遍历vector：
cpp复制void Print(const vector<int>& v) {
// 范围for循环（本质也是使用迭代器）
for (auto e : v) {
cout << e << " ";
}
cout << endl;
// 传统下标访问
for (size_t i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
void test_vector1() {
vector<int> v;
v.push_back(1);
v.push_back(2);
// ... 添加更多元素
Print(v);
}
提示：范围for循环是C++11引入的语法糖，底层实际上是通过调用begin()和end()实现的迭代器遍历。
3. vector核心接口实现
3.1 构造与析构
我们先从最基本的构造和析构函数开始：
cpp复制vector() = default; // 使用编译器生成的默认构造函数
~vector() {
if (_start) {
delete[] _start; // 释放内存
_start = _finish = _end_of_storage = nullptr;
}
}
注意：现代C++中，我们可以在成员声明时直接赋予初始值（nullptr），这样构造函数可以完全省略。
3.2 容量管理
3.2.1 reserve实现
reserve函数用于预分配内存，避免频繁扩容带来的性能损耗：
cpp复制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++) {
tmp[i] = _start[i]; // 调用元素的拷贝构造函数
}
delete[] _start; // 释放旧内存
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
关键点：这里不能使用memcpy，因为对于含有指针的复杂类型（如string），memcpy会导致浅拷贝问题。必须逐个元素调用拷贝构造函数。
3.2.2 resize实现
resize用于调整vector的大小：
cpp复制void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n; // 缩小size
} else {
reserve(n); // 确保有足够容量
while (_finish < _start + n) {
*_finish = val; // 填充新元素
++_finish;
}
}
}
注意：当n大于当前size时，新元素会用val初始化。val有默认值T()，即类型的默认构造值。
3.3 元素操作
3.3.1 push_back与pop_back
尾插和尾删是vector最高效的操作：
cpp复制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; // 只需移动指针，元素会被后续操作覆盖
}
扩容策略：初始容量为0时分配4个元素空间，之后每次扩容为原来的2倍。这是STL常用的策略，在空间和时间效率之间取得平衡。
3.3.2 insert与erase实现
中间插入和删除操作需要移动元素，时间复杂度为O(n)：
cpp复制iterator insert(iterator pos, const T& x) {
assert(pos >= _start && pos <= _finish);
// 处理可能的扩容
if (_finish == _end_of_storage) {
size_t offset = pos - _start; // 保存偏移量
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + offset; // 修正pos
}
// 从后向前移动元素
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = x; // 插入新元素
++_finish;
return pos;
}
iterator erase(iterator pos) {
assert(pos >= _start && pos < _finish);
// 从前向后移动元素
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos; // 返回被删除元素的下一个位置
}
为什么从后向前移动？因为从前向后会覆盖尚未移动的元素。想象一下memmove的实现原理。
3.3.3 元素访问
实现operator[]提供数组式访问：
cpp复制T& operator[](size_t i) {
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const {
assert(i < size());
return _start[i];
}
注意：这里没有做边界检查（为了效率），只在调试模式下通过assert检查。STL的实现也是如此。
4. vector使用中的陷阱与解决方案
4.1 迭代器失效问题
vector的某些操作会导致迭代器失效，这是常见的问题来源。
4.1.1 扩容导致的失效
任何可能引起扩容的操作（push_back、insert、reserve等）都会使所有迭代器失效：
cpp复制vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 可能导致扩容
// it现在可能指向已释放的内存，使用它是未定义行为
解决方案：在可能扩容的操作后，重新获取迭代器。
4.1.2 删除导致的失效
erase操作会使被删除元素及其后的迭代器失效：
cpp复制// 错误示例
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it % 2 == 0) {
v.erase(it); // it失效后继续使用
}
}
// 正确做法
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) {
it = v.erase(it); // 使用返回值更新迭代器
} else {
++it;
}
}
经验：erase返回被删除元素的下一个有效迭代器，应该总是使用这个返回值更新迭代器。
4.2 浅拷贝问题
如果vector存储的是含有指针的自定义类型，简单的内存拷贝会导致多个对象共享同一块内存：
cpp复制// 错误示例：使用memcpy拷贝元素
T* tmp = new T[new_capacity];
memcpy(tmp, _start, sizeof(T) * size()); // 对于string等类型会导致浅拷贝
解决方案：必须使用元素的拷贝构造函数或移动语义：
cpp复制for (size_t i = 0; i < size(); i++) {
tmp[i] = _start[i]; // 调用拷贝赋值运算符
}
4.3 异常安全问题
vector的实现需要考虑异常安全，确保在发生异常时不会泄漏资源或破坏数据一致性：
cpp复制void push_back(const T& x) {
if (_finish == _end_of_storage) {
size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
T* tmp = new T[new_capacity]; // 可能抛出bad_alloc
try {
for (size_t i = 0; i < size(); i++) {
tmp[i] = _start[i]; // 拷贝可能抛出异常
}
} catch (...) {
delete[] tmp; // 发生异常时释放临时内存
throw;
}
delete[] _start;
_start = tmp;
_finish = _start + size();
_end_of_storage = _start + new_capacity;
}
*_finish = x; // 拷贝赋值可能抛出异常
++_finish;
}
关键点：在修改内部状态前完成所有可能抛出异常的操作，确保异常发生时对象仍处于有效状态。
5. 完整实现与测试
5.1 完整vector类模板
结合上述讨论，下面是简化版的完整vector实现：
cpp复制template <typename T>
class vector {
public:
using iterator = T*;
using const_iterator = const T*;
// 构造与析构
vector() = default;
~vector() { clear(); delete[] _start; }
// 迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
// 容量
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 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);
void pop_back() { assert(!empty()); --_finish; }
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
void clear() { _finish = _start; }
// 容量管理
void reserve(size_t n);
void resize(size_t n, const T& val = T());
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
5.2 综合测试用例
cpp复制void test_vector() {
vector<int> v;
// 测试push_back和扩容
for (int i = 0; i < 10; ++i) {
v.push_back(i);
cout << "size: " << v.size()
<< ", capacity: " << v.capacity() << endl;
}
// 测试迭代器
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 测试insert
v.insert(v.begin() + 5, 99);
// 测试erase
auto it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) {
it = v.erase(it);
} else {
++it;
}
}
// 测试resize
v.resize(20, -1);
cout << "After resize: ";
for (int num : v) {
cout << num << " ";
}
cout << endl;
}
6. 性能优化与进阶话题
6.1 移动语义支持
现代C++中，应该为vector添加移动构造函数和移动赋值运算符：
cpp复制vector(vector&& other) noexcept
: _start(other._start)
, _finish(other._finish)
, _end_of_storage(other._end_of_storage)
{
other._start = other._finish = other._end_of_storage = nullptr;
}
vector& operator=(vector&& other) noexcept {
if (this != &other) {
clear();
delete[] _start;
_start = other._start;
_finish = other._finish;
_end_of_storage = other._end_of_storage;
other._start = other._finish = other._end_of_storage = nullptr;
}
return *this;
}
6.2 emplace_back优化
C++11引入了emplace_back，可以直接在容器内构造元素，避免临时对象的创建和拷贝：
cpp复制template <typename... Args>
void emplace_back(Args&&... args) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
new (_finish) T(std::forward<Args>(args)...); // 原地构造
++_finish;
}
6.3 小型缓冲区优化
一些实现（如MSVC的vector）会为小型vector使用栈缓冲区，避免堆分配的开销：
cpp复制template <typename T, size_t SmallSize = 16>
class small_vector {
union {
T* _heap_ptr;
T _stack_buffer[SmallSize];
};
// ... 其他成员
};
这种优化对小尺寸vector特别有效，但增加了实现的复杂性。
7. 实际项目中的经验分享
在多年使用和实现vector的过程中，我总结了以下几点经验：
-
预分配内存：如果知道大致元素数量，先用reserve预分配空间，可以避免多次扩容带来的性能损耗。
-
谨慎使用erase：在循环中删除元素时，一定要正确处理迭代器，使用erase的返回值更新迭代器。
-
考虑使用emplace：对于复杂类型，emplace_back比push_back更高效，因为它避免了临时对象的构造和拷贝。
-
避免在vector中存储大对象：vector适合存储小对象或指针，对于大对象，考虑存储unique_ptr或shared_ptr。
-
注意异常安全：自定义vector实现时，要确保在异常发生时不会泄漏资源或破坏数据一致性。
-
性能分析：在性能关键路径上，要注意vector的扩容行为，可以通过自定义分配器或调整扩容策略来优化。
通过深入理解vector的底层实现，我们不仅能更有效地使用它，还能在需要时实现自己的变种，满足特定场景的需求。