1. 为什么需要自己实现vector
在C++标准库中，vector是最常用的容器之一，它提供了动态数组的功能。但作为一名C++开发者，理解vector的内部实现机制至关重要。自己动手实现一个简化版的vector，能够帮助我们：
- 深入理解动态内存管理的原理
- 掌握迭代器失效的边界条件
- 学习如何设计高效的容器接口
- 理解异常安全在容器设计中的重要性
我在实际工作中发现，很多看似简单的vector操作（比如reserve()和resize()的区别），只有亲手实现过才能真正理解其底层机制。这也是为什么各大厂的C++面试中，手写vector实现是经典考题。
2. 基础架构设计
2.1 核心成员变量
一个最基本的vector需要三个指针成员：
cpp复制template <typename T>
class Vector {
private:
T* m_data; // 指向动态分配的内存首地址
size_t m_size; // 当前元素数量
size_t m_capacity; // 当前分配的内存容量
};
这里的关键设计点在于：
- 使用模板支持任意类型
- 将size和capacity分开存储，避免频繁计算
- 采用指针而非数组，实现动态扩展
2.2 内存增长策略
vector最核心的特性是动态扩容。常见的增长策略有两种：
-
固定倍数增长（如2倍）
- 优点：均摊时间复杂度O(1)
- 缺点：可能浪费内存
-
固定增量增长（如每次+16）
- 优点：内存利用率高
- 缺点：时间复杂度退化到O(n)
标准库通常采用2倍增长策略。在我的实现中，初始容量设为16，之后每次扩容为当前容量的2倍：
cpp复制void reserve(size_t new_capacity) {
if (new_capacity <= m_capacity) return;
T* new_data = static_cast<T*>(::operator new(new_capacity * sizeof(T)));
// ... 元素搬移和旧内存释放
m_capacity = new_capacity;
}
注意：这里使用operator new而不是new[]，是为了与标准库实现保持一致，便于后续优化。
3. 关键接口实现
3.1 push_back的实现细节
看似简单的push_back实际上需要考虑多种情况：
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); // placement new
++m_size;
}
这里有几个技术要点：
- 使用placement new在已分配的内存上构造对象
- 处理初始容量为0的特殊情况
- 先检查容量再构造，保证异常安全
3.2 迭代器失效问题
vector的迭代器失效是常见陷阱。以下操作会导致迭代器失效：
- 任何可能引起扩容的操作（push_back等）
- insert/erase操作
在我的实现中，迭代器就是一个简单的指针包装：
cpp复制template <typename U>
class Iterator {
U* m_ptr;
public:
// ... 迭代器必要接口
};
使用时需要特别注意：
cpp复制Vector<int>::iterator it = vec.begin();
vec.push_back(42); // it可能失效！
4. 异常安全保证
4.1 基本异常安全
在容器操作中，我们需要保证：
- 不泄漏资源
- 保持容器一致性
以reserve为例的正确实现：
cpp复制void reserve(size_t new_capacity) {
if (new_capacity <= m_capacity) return;
T* new_data = static_cast<T*>(::operator new(new_capacity * sizeof(T)));
size_t i = 0;
try {
for (; i < m_size; ++i) {
new (new_data + i) T(std::move_if_noexcept(m_data[i]));
}
} catch (...) {
for (size_t j = 0; j < i; ++j) {
(new_data + j)->~T();
}
::operator delete(new_data);
throw;
}
// 销毁旧元素并释放内存
for (size_t i = 0; i < m_size; ++i) {
m_data[i].~T();
}
::operator delete(m_data);
m_data = new_data;
m_capacity = new_capacity;
}
4.2 强异常安全
对于某些操作如insert，我们可以通过"copy-and-swap"实现强异常安全：
cpp复制iterator insert(iterator pos, const T& value) {
size_t offset = pos - begin();
if (m_size >= m_capacity) {
Vector temp(*this);
temp.reserve(m_capacity == 0 ? 1 : m_capacity * 2);
swap(temp);
}
// ... 插入逻辑
}
5. 性能优化技巧
5.1 移动语义支持
现代C++中应该充分支持移动语义：
cpp复制void push_back(T&& value) {
if (m_size >= m_capacity) {
reserve(m_capacity == 0 ? 1 : m_capacity * 2);
}
new (m_data + m_size) T(std::move(value));
++m_size;
}
5.2 小型缓冲区优化
对于小型vector，可以避免频繁内存分配：
cpp复制template <typename T, size_t SmallSize = 16>
class SmallVector {
union {
T* m_data;
T m_small_buffer[SmallSize];
};
bool m_is_small;
// ...
};
5.3 内存池技术
频繁的push_back/pop_back操作可以考虑使用内存池：
cpp复制template <typename T>
class Vector {
private:
MemoryPool<T> m_pool;
// ...
};
void push_back(const T& value) {
if (m_size >= m_capacity) {
reserve(m_capacity == 0 ? 1 : m_capacity * 2);
}
m_pool.construct(m_data + m_size, value);
++m_size;
}
6. 完整实现示例
以下是简化版的完整实现框架：
cpp复制template <typename T>
class Vector {
public:
// 类型定义
using value_type = T;
using iterator = T*;
using const_iterator = const T*;
// 构造/析构
Vector() : m_data(nullptr), m_size(0), m_capacity(0) {}
~Vector() { clear(); ::operator delete(m_data); }
// 容量相关
size_t size() const { return m_size; }
size_t capacity() const { return m_capacity; }
bool empty() const { return m_size == 0; }
// 元素访问
T& operator[](size_t index) { return m_data[index]; }
const T& operator[](size_t index) const { return m_data[index]; }
// 迭代器
iterator begin() { return m_data; }
iterator end() { return m_data + m_size; }
// 修改操作
void push_back(const T& value);
void pop_back();
iterator insert(iterator pos, const T& value);
iterator erase(iterator pos);
void clear();
void reserve(size_t new_capacity);
void resize(size_t new_size, const T& value = T());
private:
T* m_data;
size_t m_size;
size_t m_capacity;
};
7. 测试与验证
7.1 基础功能测试
编写测试用例验证基本功能：
cpp复制void test_vector() {
Vector<int> vec;
assert(vec.empty());
vec.push_back(1);
assert(vec.size() == 1);
assert(vec[0] == 1);
vec.pop_back();
assert(vec.empty());
}
7.2 异常安全测试
模拟异常场景：
cpp复制struct ThrowOnCopy {
ThrowOnCopy() = default;
ThrowOnCopy(const ThrowOnCopy&) { throw std::runtime_error("copy failed"); }
};
void test_exception_safety() {
Vector<ThrowOnCopy> vec;
try {
vec.push_back(ThrowOnCopy{});
vec.push_back(ThrowOnCopy{}); // 触发扩容
} catch (...) {
assert(vec.size() == 1); // 保证一致性
}
}
7.3 性能测试
比较与std::vector的性能差异：
cpp复制void benchmark_push_back() {
const size_t count = 1000000;
auto start = std::chrono::high_resolution_clock::now();
Vector<int> my_vec;
for (int i = 0; i < count; ++i) {
my_vec.push_back(i);
}
auto end = std::chrono::high_resolution_clock::now();
// 同样测试std::vector...
}
8. 实际应用中的经验分享
在实现过程中，我总结了一些有价值的经验：
-
内存对齐问题：直接使用operator new分配的内存可能没有适当对齐。在实际项目中，应该使用aligned_alloc或者特定平台的API确保内存对齐。
-
类型萃取应用：对于trivially copyable类型，可以用memcpy优化元素搬移：
cpp复制if constexpr (std::is_trivially_copyable_v<T>) {
std::memcpy(new_data, m_data, m_size * sizeof(T));
} else {
// 正常逐个构造
}
- 调试支持：添加迭代器越界检查：
cpp复制T& operator[](size_t index) {
assert(index < m_size && "index out of range");
return m_data[index];
}
-
SSO优化：对于小型字符串等场景，可以实现类似std::string的SSO(Small String Optimization)优化。
-
多线程考量：标准容器通常不是线程安全的，但在实际项目中，可以考虑添加细粒度锁或版本号机制来支持并发访问。
实现一个完整的vector容器远比看起来复杂，但这个过程能让我们深入理解C++的许多核心概念：模板、内存管理、异常安全、迭代器等。这也是为什么它成为衡量C++开发者水平的重要标准。