1. 为什么需要模拟实现vector
在C++标准库中，vector是最常用的容器之一，它提供了动态数组的功能。但很多初学者只是停留在使用层面，对底层实现原理一知半解。通过手动实现一个简化版的vector，可以深入理解以下几个关键点：
- 动态内存管理的机制
- 迭代器失效的场景
- 扩容策略对性能的影响
- 异常安全的保证
我在实际开发中遇到过不少因为不了解vector内部机制而导致的bug。比如在遍历时插入元素导致迭代器失效，或者频繁扩容引发性能问题。这些问题都可以通过理解底层实现来避免。
2. 基础框架搭建
2.1 类模板定义
我们先从最基本的类模板开始：
cpp复制template <typename T>
class Vector {
public:
// 类型别名
using value_type = T;
using iterator = T*;
using const_iterator = const T*;
private:
iterator _start; // 指向首元素
iterator _finish; // 指向最后一个元素的下一个位置
iterator _end_of_storage; // 指向存储空间末尾的下一个位置
};
这里使用了三个指针来管理内存：
_start指向数组首元素_finish指向最后一个元素的下一个位置_end_of_storage指向分配的内存末尾
这种设计是标准库vector的经典实现方式，可以高效地获取size和capacity：
cpp复制size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
2.2 构造函数实现
实现几个常用构造函数：
cpp复制// 默认构造
Vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
// 指定大小构造
explicit Vector(size_t n, const T& value = T()) {
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
std::fill(_start, _finish, value);
}
// 迭代器范围构造
template <typename InputIterator>
Vector(InputIterator first, InputIterator last) {
size_t n = std::distance(first, last);
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
std::copy(first, last, _start);
}
注意：迭代器范围构造使用了模板，可以接受任意类型的迭代器，这是标准库的通用做法。
3. 核心操作实现
3.1 插入操作
插入操作需要考虑扩容和元素移动：
cpp复制iterator insert(iterator pos, const T& value) {
if (pos < _start || pos > _finish) {
throw std::out_of_range("Vector::insert - invalid position");
}
// 检查是否需要扩容
if (_finish == _end_of_storage) {
size_t new_capacity = capacity() == 0 ? 1 : capacity() * 2;
reserve(new_capacity);
pos = _start + (pos - _start); // 扩容后pos可能失效，需要重新计算
}
// 移动元素
iterator end = _finish;
while (end > pos) {
*end = *(end - 1);
--end;
}
// 插入新元素
*pos = value;
++_finish;
return pos;
}
这里有几个关键点：
- 扩容策略采用常见的2倍扩容
- 扩容后需要重新计算pos，因为原内存可能被释放
- 元素移动是从后往前，避免覆盖
3.2 删除操作
删除操作需要考虑元素移动和析构：
cpp复制iterator erase(iterator pos) {
if (pos < _start || pos >= _finish) {
throw std::out_of_range("Vector::erase - invalid position");
}
// 移动元素
iterator next = pos;
while (next + 1 != _finish) {
*next = *(next + 1);
++next;
}
// 调用析构
--_finish;
_finish->~T();
return pos;
}
注意：删除元素后，所有指向被删除元素及其后的迭代器都会失效，这是vector的一个重要特性。
3.3 查找操作
虽然vector主要提供随机访问，但我们可以实现一个简单的查找：
cpp复制iterator find(const T& value) {
for (iterator it = _start; it != _finish; ++it) {
if (*it == value) {
return it;
}
}
return _finish;
}
对于有序vector，可以使用二分查找提高效率：
cpp复制iterator binary_find(const T& value) {
iterator first = _start;
iterator last = _finish;
while (first < last) {
iterator mid = first + (last - first) / 2;
if (*mid < value) {
first = mid + 1;
} else if (value < *mid) {
last = mid;
} else {
return mid;
}
}
return _finish;
}
4. 内存管理
4.1 扩容策略
vector最核心的特性就是动态扩容，我们来看reserve的实现：
cpp复制void reserve(size_t new_capacity) {
if (new_capacity <= capacity()) return;
// 分配新内存
T* new_start = new T[new_capacity];
// 转移元素
size_t old_size = size();
if (_start) {
std::copy(_start, _finish, new_start);
delete[] _start;
}
// 更新指针
_start = new_start;
_finish = _start + old_size;
_end_of_storage = _start + new_capacity;
}
扩容时需要注意：
- 只有当新容量大于当前容量时才处理
- 需要保留原有元素
- 需要释放旧内存
4.2 析构函数
正确的资源释放非常重要：
cpp复制~Vector() {
if (_start) {
// 调用每个元素的析构
for (iterator it = _start; it != _finish; ++it) {
it->~T();
}
delete[] _start;
}
}
5. 迭代器实现
vector的迭代器本质就是指针：
cpp复制iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
const_iterator cbegin() const { return _start; }
const_iterator cend() const { return _finish; }
但要注意迭代器失效的几种情况：
- 插入元素导致扩容，所有迭代器失效
- 删除元素导致被删除元素及其后的迭代器失效
6. 性能优化技巧
6.1 移动语义支持
现代C++应该支持移动语义：
cpp复制void push_back(T&& value) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 1 : capacity() * 2);
}
*_finish = std::move(value);
++_finish;
}
6.2 emplace_back优化
直接原地构造，避免临时对象：
cpp复制template <typename... Args>
void emplace_back(Args&&... args) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 1 : capacity() * 2);
}
new (_finish) T(std::forward<Args>(args)...);
++_finish;
}
6.3 shrink_to_fit
释放多余内存：
cpp复制void shrink_to_fit() {
if (size() == capacity()) return;
T* new_start = new T[size()];
std::copy(_start, _finish, new_start);
delete[] _start;
_start = new_start;
_finish = _start + size();
_end_of_storage = _finish;
}
7. 常见问题与解决方案
7.1 迭代器失效问题
cpp复制Vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 可能导致扩容
*it = 5; // 危险！it可能已经失效
解决方案：
- 插入/删除后不要使用旧的迭代器
- 使用索引代替迭代器
- 预先reserve足够空间
7.2 异常安全问题
考虑构造函数中发生异常的情况：
cpp复制Vector(size_t n, const T& value = T()) {
_start = new T[n];
try {
std::fill(_start, _start + n, value);
} catch (...) {
delete[] _start; // 发生异常时释放内存
throw;
}
_finish = _start + n;
_end_of_storage = _finish;
}
7.3 性能陷阱
频繁扩容会导致性能下降：
cpp复制// 不好的做法
Vector<int> v;
for (int i = 0; i < 1000000; ++i) {
v.push_back(i); // 多次扩容
}
// 好的做法
Vector<int> v;
v.reserve(1000000); // 预先分配足够空间
for (int i = 0; i < 1000000; ++i) {
v.push_back(i);
}
8. 完整实现与测试
最后给出一个完整的简化实现，并添加测试用例：
cpp复制// 测试代码
int main() {
Vector<int> v;
for (int i = 0; i < 10; ++i) {
v.push_back(i);
}
// 测试插入
v.insert(v.begin() + 5, 99);
// 测试删除
v.erase(v.begin() + 3);
// 测试查找
auto it = v.find(5);
if (it != v.end()) {
std::cout << "Found: " << *it << std::endl;
}
// 测试容量
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
// 测试缩容
v.shrink_to_fit();
std::cout << "After shrink: Size: " << v.size()
<< ", Capacity: " << v.capacity() << std::endl;
return 0;
}
在实际项目中，建议添加更多边界测试和异常测试，确保实现的健壮性。