1. 为什么需要自己实现vector
在C++标准库中，vector是最常用的容器之一，它提供了动态数组的功能。但很多开发者只是停留在使用层面，对其内部实现原理并不了解。通过手动实现一个简化版的vector，我们可以深入理解以下几个关键点：
首先，动态内存管理是vector的核心。与普通数组不同，vector能够根据需要自动扩容，这背后是malloc/free或new/delete的灵活运用。理解这一点对掌握C++内存管理至关重要。
其次，迭代器失效问题是实际开发中常见的坑。当我们自己实现vector时，可以清楚地看到在什么操作下迭代器会失效，以及为什么失效。这种理解能帮助我们在实际项目中避免很多bug。
再者，模板编程是C++的重要特性。通过实现一个模板化的vector，我们可以学习如何编写通用的、类型安全的容器类。这对提升C++编程能力有很大帮助。
最后，异常安全是高质量代码的重要指标。在实现vector的过程中，我们需要考虑各种操作（如push_back、insert等）的异常安全性，这能培养我们编写健壮代码的习惯。
2. 基础结构设计
2.1 类模板定义
我们首先定义一个类模板，这是现代C++容器的基础形式：
cpp复制template <typename T>
class Vector {
public:
// 类型别名，符合STL惯例
using value_type = T;
using pointer = T*;
using reference = T&;
using const_reference = const T&;
using size_type = size_t;
using difference_type = ptrdiff_t;
private:
pointer m_data; // 指向动态数组的指针
size_type m_size; // 当前元素数量
size_type m_capacity; // 当前容量
};
这里使用了STL中常见的类型别名约定，这能让我们的vector与标准库保持一致的接口风格。m_data指向动态分配的数组，m_size记录当前元素数量，m_capacity记录当前容量。
2.2 构造函数与析构函数
构造函数需要考虑多种情况：
cpp复制// 默认构造函数
Vector() : m_data(nullptr), m_size(0), m_capacity(0) {}
// 带初始容量参数的构造函数
explicit Vector(size_type count)
: m_data(static_cast<pointer>(::operator new(count * sizeof(T)))),
m_size(count),
m_capacity(count)
{
// 对每个元素进行默认构造
for (size_type i = 0; i < m_size; ++i) {
new (&m_data[i]) T();
}
}
// 拷贝构造函数
Vector(const Vector& other)
: m_data(static_cast<pointer>(::operator new(other.m_capacity * sizeof(T)))),
m_size(other.m_size),
m_capacity(other.m_capacity)
{
for (size_type i = 0; i < m_size; ++i) {
new (&m_data[i]) T(other.m_data[i]);
}
}
// 析构函数
~Vector() {
clear();
::operator delete(m_data);
}
这里有几个关键点需要注意：
- 使用了placement new来构造对象，这是为了将内存分配和对象构造分离
- 拷贝构造函数需要进行深拷贝
- 析构函数需要先销毁所有元素，再释放内存
3. 核心功能实现
3.1 内存管理
动态扩容是vector最核心的特性：
cpp复制void reserve(size_type new_capacity) {
if (new_capacity <= m_capacity) return;
pointer new_data = static_cast<pointer>(::operator new(new_capacity * sizeof(T)));
// 移动现有元素到新内存
for (size_type i = 0; i < m_size; ++i) {
new (&new_data[i]) T(std::move(m_data[i]));
m_data[i].~T(); // 销毁原对象
}
::operator delete(m_data);
m_data = new_data;
m_capacity = new_capacity;
}
扩容策略通常采用几何增长（如每次扩容为原来的2倍），这样可以保证多次插入操作的平均时间复杂度为O(1)：
cpp复制void push_back(const T& value) {
if (m_size >= m_capacity) {
reserve(m_capacity == 0 ? 1 : m_capacity * 2);
}
new (&m_data[m_size]) T(value);
++m_size;
}
3.2 元素访问
实现安全的元素访问操作：
cpp复制reference operator[](size_type pos) {
return m_data[pos];
}
const_reference operator[](size_type pos) const {
return m_data[pos];
}
reference at(size_type pos) {
if (pos >= m_size) {
throw std::out_of_range("Vector index out of range");
}
return m_data[pos];
}
at()函数提供了边界检查，这是与operator[]的主要区别。
3.3 迭代器支持
为了使我们的vector能够与标准算法配合使用，需要提供迭代器支持：
cpp复制class iterator {
pointer ptr;
public:
explicit iterator(pointer p) : ptr(p) {}
reference operator*() { return *ptr; }
pointer operator->() { return ptr; }
iterator& operator++() { ++ptr; return *this; }
// 其他迭代器操作...
};
iterator begin() { return iterator(m_data); }
iterator end() { return iterator(m_data + m_size); }
同样需要实现const_iterator版本，以支持const Vector的迭代。
4. 高级功能实现
4.1 移动语义支持
现代C++中，移动语义可以显著提高性能：
cpp复制// 移动构造函数
Vector(Vector&& other) noexcept
: m_data(other.m_data),
m_size(other.m_size),
m_capacity(other.m_capacity)
{
other.m_data = nullptr;
other.m_size = 0;
other.m_capacity = 0;
}
// 移动赋值运算符
Vector& operator=(Vector&& other) noexcept {
if (this != &other) {
clear();
::operator delete(m_data);
m_data = other.m_data;
m_size = other.m_size;
m_capacity = other.m_capacity;
other.m_data = nullptr;
other.m_size = 0;
other.m_capacity = 0;
}
return *this;
}
4.2 异常安全保证
在实现各种操作时，需要考虑异常安全：
cpp复制void push_back(const T& value) {
if (m_size >= m_capacity) {
size_type new_capacity = m_capacity == 0 ? 1 : m_capacity * 2;
pointer new_data = static_cast<pointer>(::operator new(new_capacity * sizeof(T)));
size_type i = 0;
try {
for (; i < m_size; ++i) {
new (&new_data[i]) T(std::move(m_data[i]));
}
new (&new_data[m_size]) T(value); // 可能抛出异常
} catch (...) {
// 发生异常时回滚
for (size_type j = 0; j < i; ++j) {
new_data[j].~T();
}
::operator delete(new_data);
throw;
}
// 销毁原对象并更新指针
for (i = 0; i < m_size; ++i) {
m_data[i].~T();
}
::operator delete(m_data);
m_data = new_data;
m_capacity = new_capacity;
} else {
new (&m_data[m_size]) T(value); // 可能抛出异常
}
++m_size;
}
这种实现保证了即使在构造元素时抛出异常，vector也能保持一致性。
5. 性能优化与测试
5.1 优化策略
- 小对象优化：对于小型vector，可以使用栈空间避免堆分配
- 分配器支持：允许用户自定义内存分配方式
- SSO（Small String Optimization）：类似字符串的优化策略
5.2 测试要点
完整的测试应该包括：
cpp复制void test_vector() {
// 基本功能测试
Vector<int> v;
assert(v.size() == 0);
v.push_back(1);
assert(v.size() == 1);
assert(v[0] == 1);
// 扩容测试
for (int i = 2; i <= 100; ++i) {
v.push_back(i);
}
assert(v.size() == 100);
assert(v[99] == 100);
// 拷贝测试
Vector<int> v2 = v;
assert(v2.size() == v.size());
// 移动测试
Vector<int> v3 = std::move(v);
assert(v3.size() == 100);
assert(v.size() == 0); // NOLINT
// 异常安全测试
struct ThrowOnCopy {
ThrowOnCopy() = default;
ThrowOnCopy(const ThrowOnCopy&) { throw std::runtime_error("copy failed"); }
};
Vector<ThrowOnCopy> v4;
v4.reserve(10);
try {
v4.push_back(ThrowOnCopy());
} catch (...) {
assert(v4.size() == 0); // 保证在异常后状态一致
}
}
6. 实际应用中的注意事项
-
迭代器失效：以下操作会使所有迭代器失效：
- 任何可能导致扩容的操作（push_back、resize等）
- insert和erase操作
-
异常安全：不同操作提供不同级别的异常安全保证：
- push_back：强异常安全保证
- pop_back：不抛出异常
- insert：基本异常安全保证
-
性能考虑：
- 频繁插入时，预先reserve可以避免多次扩容
- 移动语义可以显著提高大对象容器的性能
-
与std::vector的差异：
- 我们的实现省略了分配器支持
- 异常安全保证可能不完全一致
- 没有实现全部的STL容器接口
-
调试技巧：
- 在调试版本中可以添加边界检查
- 可以记录分配/释放操作帮助调试内存问题
通过这个简单的vector实现，我们深入理解了动态数组容器的内部工作原理。虽然它没有标准库vector那么完善，但涵盖了最核心的概念和实现技术。在实际项目中，除非有特殊需求，否则应该优先使用标准库的实现。但这种实现练习对于深入理解C++内存管理、异常安全和模板编程非常有价值。