1. 项目概述
在C++开发中,vector是最常用的容器之一,它提供了动态数组的功能,能够自动管理内存并支持高效的随机访问。但很多开发者只是停留在使用层面,对其底层实现机制并不了解。本文将带你从零开始实现一个简化版的vector容器,重点模拟其增删查改的核心功能。
通过这个项目,你将深入理解:
- vector如何动态管理内存
- 元素插入删除时的内存处理逻辑
- 迭代器失效的原理
- 模板编程在容器中的应用
这个实现虽然简化,但包含了vector最核心的机制,适合有一定C++基础(熟悉类、模板、指针等概念)的开发者学习。我在实际开发STL-like容器时积累的经验也会融入各个实现环节。
2. 核心数据结构设计
2.1 基础框架搭建
我们先定义类的基本框架:
cpp复制template <typename T>
class Vector {
public:
// 类型别名
using iterator = T*;
using const_iterator = const T*;
// 构造/析构函数
Vector();
explicit Vector(size_t n, const T& val = T());
~Vector();
// 容量相关
size_t size() const;
size_t capacity() const;
bool empty() const;
// 元素访问
T& operator[](size_t pos);
const T& operator[](size_t pos) const;
T& front();
T& back();
// 增删查改
void push_back(const T& val);
void pop_back();
iterator insert(iterator pos, const T& val);
iterator erase(iterator pos);
// 迭代器
iterator begin();
iterator end();
private:
T* _start; // 指向首元素
T* _finish; // 指向最后一个元素的下一个位置
T* _end_of_storage; // 指向存储空间末尾
};
这个设计采用了与STL vector类似的三个指针方案:
_start:指向动态数组的首元素_finish:指向最后一个有效元素的下一个位置_end_of_storage:指向已分配内存的末尾
这种设计可以高效地计算size(_finish - _start)和capacity(_end_of_storage - _start)。
2.2 内存管理策略
vector的核心在于其动态内存管理。当当前容量不足时,需要执行以下步骤:
- 分配新的更大的内存块(通常2倍扩容)
- 将原有元素移动/拷贝到新内存
- 释放旧内存
- 更新三个指针
这里的关键点:
- 移动语义:C++11后应优先使用std::move来转移元素
- 异常安全:在扩容过程中需要保证即使抛出异常也不会内存泄漏
- 迭代器失效:扩容会导致所有迭代器失效
3. 核心功能实现
3.1 构造函数实现
默认构造函数初始化空容器:
cpp复制Vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
带大小的构造函数:
cpp复制explicit Vector(size_t n, const T& val = T()) {
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
try {
std::uninitialized_fill(_start, _finish, val);
} catch (...) {
delete[] _start;
throw;
}
}
注意:这里使用了uninitialized_fill而不是简单的循环赋值,因为它能正确处理可能抛出异常的构造函数
3.2 push_back实现
push_back是vector最常用的操作:
cpp复制void push_back(const T& val) {
if (_finish == _end_of_storage) {
size_t new_cap = capacity() == 0 ? 1 : capacity() * 2;
reserve(new_cap);
}
*_finish = val;
++_finish;
}
配套的reserve实现:
cpp复制void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
T* new_start = new T[n];
try {
if constexpr (std::is_nothrow_move_constructible_v<T> ||
!std::is_copy_constructible_v<T>) {
std::uninitialized_move(_start, _finish, new_start);
} else {
std::uninitialized_copy(_start, _finish, new_start);
}
} catch (...) {
delete[] new_start;
throw;
}
delete[] _start;
_start = new_start;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
这里有几个关键点:
- 使用移动语义优先(如果类型支持)
- 异常安全处理
- 保持原有元素数量不变
3.3 insert和erase实现
insert在指定位置插入元素:
cpp复制iterator insert(iterator pos, const T& val) {
assert(pos >= begin() && pos <= end());
if (_finish == _end_of_storage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 1 : capacity() * 2);
pos = _start + len; // 解决迭代器失效
}
std::move_backward(pos, _finish, _finish + 1);
*pos = val;
++_finish;
return pos;
}
erase移除指定位置元素:
cpp复制iterator erase(iterator pos) {
assert(pos >= begin() && pos < end());
std::move(pos + 1, _finish, pos);
--_finish;
return pos;
}
重要提示:insert和erase都会导致从插入/删除点到end()的所有迭代器失效
3.4 元素访问实现
实现operator[]和边界检查:
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];
}
T& front() {
assert(!empty());
return *_start;
}
T& back() {
assert(!empty());
return *(_finish - 1);
}
4. 关键问题与优化
4.1 迭代器失效问题
vector的迭代器本质是指针,以下操作会导致迭代器失效:
- 任何可能导致扩容的操作(push_back、insert等)
- erase和insert操作点之后的迭代器
常见错误示例:
cpp复制Vector<int> vec{1,2,3};
auto it = vec.begin();
vec.push_back(4); // 可能导致扩容
*it = 5; // 危险!it可能已经失效
解决方案:
- 在可能扩容的操作后不要保留旧迭代器
- 使用返回值更新迭代器位置
4.2 异常安全保证
我们的实现需要提供基本的异常安全保证:
- 如果操作抛出异常,容器仍处于有效状态
- 不会发生内存泄漏
关键点:
- new分配内存后立即用try-catch保护
- 使用RAII管理资源
- 移动操作要判断是否可能抛出异常
4.3 性能优化技巧
- 移动语义优化:
cpp复制void push_back(T&& val) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 1 : capacity() * 2);
}
*_finish = std::move(val);
++_finish;
}
- 预留空间优化:
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;
}
- shrink_to_fit实现:
cpp复制void shrink_to_fit() {
if (size() < capacity()) {
Vector tmp(*this);
swap(tmp);
}
}
5. 测试与验证
5.1 基础功能测试
编写测试用例验证基本功能:
cpp复制void test_basic() {
Vector<int> vec;
assert(vec.empty());
vec.push_back(1);
assert(vec.size() == 1);
assert(vec[0] == 1);
vec.insert(vec.begin(), 0);
assert(vec.size() == 2);
assert(vec.front() == 0);
vec.pop_back();
assert(vec.size() == 1);
assert(vec.back() == 0);
}
5.2 边界条件测试
测试边界情况:
cpp复制void test_edge_cases() {
Vector<std::string> vec(5, "test");
assert(vec.size() == 5);
vec.reserve(100);
assert(vec.capacity() >= 100);
while (!vec.empty()) {
vec.pop_back();
}
assert(vec.empty());
Vector<NonCopyable> nc_vec;
nc_vec.push_back(NonCopyable{});
nc_vec.emplace_back();
}
5.3 性能测试
对比STL vector:
cpp复制void test_performance() {
const int N = 1000000;
// 测试我们的Vector
auto start1 = std::chrono::high_resolution_clock::now();
Vector<int> my_vec;
for (int i = 0; i < N; ++i) {
my_vec.push_back(i);
}
auto end1 = std::chrono::high_resolution_clock::now();
// 测试STL vector
auto start2 = std::chrono::high_resolution_clock::now();
std::vector<int> std_vec;
for (int i = 0; i < N; ++i) {
std_vec.push_back(i);
}
auto end2 = std::chrono::high_resolution_clock::now();
// 输出结果
auto my_dur = end1 - start1;
auto std_dur = end2 - start2;
std::cout << "Our Vector: " << my_dur.count() << "ns\n";
std::cout << "STL Vector: " << std_dur.count() << "ns\n";
}
6. 实际应用中的经验分享
6.1 避免频繁扩容
在实际项目中,如果知道大概的元素数量,应该提前reserve:
cpp复制// 不好的做法
Vector<Data> process_data() {
Vector<Data> result;
// 可能多次扩容
for (/*...*/) {
result.push_back(get_data());
}
return result;
}
// 好的做法
Vector<Data> process_data() {
Vector<Data> result;
result.reserve(estimated_size); // 预先分配
for (/*...*/) {
result.push_back(get_data());
}
return result;
}
6.2 处理复杂对象
当vector存储复杂对象时,需要注意:
- 对象的拷贝/移动构造函数
- 对象的异常安全性
- 析构函数的正确调用
示例:
cpp复制class ComplexObj {
public:
ComplexObj() { /*...*/ }
~ComplexObj() { /*...*/ }
ComplexObj(const ComplexObj&) { /*...*/ }
ComplexObj(ComplexObj&&) noexcept { /*...*/ }
// ...
};
Vector<ComplexObj> complex_vec;
complex_vec.push_back(ComplexObj{}); // 需要正确的拷贝/移动构造
6.3 自定义分配器支持
更高级的实现可以支持自定义分配器:
cpp复制template <typename T, typename Alloc = std::allocator<T>>
class Vector {
// 使用Alloc分配内存而不是直接new/delete
// ...
};
这允许用户控制内存分配方式,适用于特殊场景(如内存池、共享内存等)。
实现vector容器是理解C++内存管理、异常安全和模板编程的绝佳练习。虽然我们的实现相比STL vector简化了很多,但已经涵盖了最核心的机制。在实际项目中,建议直接使用标准库的vector,但了解其实现原理对写出高效、安全的代码至关重要。