1. 项目概述
"手撕vector"这个标题在C++开发者社区中有着特殊的含义——它指的是不依赖标准库，从零开始实现一个完整的vector容器。这就像厨师不用现成的调料包，而是亲自调配每一味香料。作为C++中最基础也最常用的容器之一，vector的实现涉及内存管理、迭代器设计、异常安全等核心概念，是检验开发者对C++底层理解的最佳试金石。
我曾在多个高性能计算项目中遇到过标准库vector无法满足特殊需求的情况，比如需要定制内存分配策略或实现特殊迭代逻辑。这时候"手撕"一个定制版vector就成了必选项。本文将带你从内存布局设计开始，逐步实现插入删除、迭代器、异常安全等完整功能，最后还会分享几个性能优化的小技巧。
2. 核心设计思路
2.1 内存管理模型
标准vector的核心是一个三段式内存结构：
cpp复制template <typename T>
class Vector {
T* _begin; // 有效元素起始位置
T* _end; // 最后一个有效元素的下一个位置
T* _cap; // 分配内存的末尾位置
};
这种设计使得size()和capacity()的计算变得极其高效：
cpp复制size_t size() const { return _end - _begin; }
size_t capacity() const { return _cap - _begin; }
内存增长策略通常采用2倍扩容法，这是空间和时间效率的平衡点。实测显示，当扩容因子在1.5-2之间时，均摊时间复杂度接近O(1)。以下是扩容的典型实现：
cpp复制void reserve(size_t new_cap) {
if (new_cap <= capacity()) return;
T* new_begin = allocator.allocate(new_cap);
try {
std::uninitialized_move(_begin, _end, new_begin);
} catch (...) {
allocator.deallocate(new_begin, new_cap);
throw;
}
destroy_elements();
allocator.deallocate(_begin, capacity());
_end = new_begin + size();
_begin = new_begin;
_cap = new_begin + new_cap;
}
2.2 异常安全保证
一个工业级的vector需要满足强异常安全保证——要么操作成功，要么保持原状。这在插入元素时尤为关键。我们采用RAII技术管理资源：
cpp复制template <typename... Args>
void emplace_back(Args&&... args) {
if (_end == _cap) {
reserve(capacity() ? capacity() * 2 : 1);
}
new (_end) T(std::forward<Args>(args)...); // 就地构造
++_end;
}
当构造可能抛出异常时，需要先分配内存再构造元素：
cpp复制void push_back(const T& value) {
if (_end == _cap) {
size_t new_cap = capacity() ? capacity() * 2 : 1;
T* new_begin = allocator.allocate(new_cap);
T* new_end = new_begin;
try {
new_end = std::uninitialized_copy(_begin, _end, new_begin);
new (new_end) T(value); // 在已分配内存上构造
++new_end;
} catch (...) {
while (new_end != new_begin) {
(--new_end)->~T();
}
allocator.deallocate(new_begin, new_cap);
throw;
}
destroy_elements();
allocator.deallocate(_begin, capacity());
_begin = new_begin;
_end = new_end;
_cap = new_begin + new_cap;
} else {
new (_end) T(value);
++_end;
}
}
3. 关键实现细节
3.1 迭代器设计
vector的迭代器本质就是指针的包装：
cpp复制template <typename T>
class VectorIterator {
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
VectorIterator(pointer ptr) : _ptr(ptr) {}
reference operator*() const { return *_ptr; }
pointer operator->() const { return _ptr; }
VectorIterator& operator++() { ++_ptr; return *this; }
VectorIterator operator++(int) { VectorIterator tmp = *this; ++_ptr; return tmp; }
// 其他随机访问迭代器操作...
private:
pointer _ptr;
};
3.2 移动语义支持
现代C++必须支持移动语义以提高效率：
cpp复制void push_back(T&& value) {
if (_end == _cap) {
reserve(capacity() ? capacity() * 2 : 1);
}
new (_end) T(std::move(value));
++_end;
}
Vector(Vector&& other) noexcept
: _begin(other._begin), _end(other._end), _cap(other._cap) {
other._begin = other._end = other._cap = nullptr;
}
Vector& operator=(Vector&& other) noexcept {
if (this != &other) {
clear();
allocator.deallocate(_begin, capacity());
_begin = other._begin;
_end = other._end;
_cap = other._cap;
other._begin = other._end = other._cap = nullptr;
}
return *this;
}
4. 性能优化技巧
4.1 小对象优化
对于小型vector，可以像std::string那样实现SSO(Small Size Optimization)：
cpp复制template <typename T, size_t SmallSize = 16>
class SmallVector {
union {
T* _dynamic;
T _static[SmallSize];
};
size_t _size;
bool _is_dynamic;
// 其他实现...
};
4.2 批量操作优化
insert和erase的批量版本可以大幅减少内存操作：
cpp复制iterator insert(const_iterator pos, size_t count, const T& value) {
size_t offset = pos - begin();
if (size() + count > capacity()) {
reserve(calculate_new_capacity(size() + count));
}
iterator insert_pos = begin() + offset;
if (insert_pos != end()) {
std::move_backward(insert_pos, end(), end() + count);
}
std::uninitialized_fill_n(insert_pos, count, value);
_end += count;
return insert_pos;
}
5. 常见问题与解决方案
5.1 迭代器失效问题
vector在以下操作后迭代器会失效：
- 插入导致扩容：所有迭代器失效
- 插入未导致扩容：插入点之后的迭代器失效
- 删除元素：删除点之后的迭代器失效
解决方案是尽量在修改操作后重新获取迭代器，或使用索引代替迭代器。
5.2 内存泄漏排查
当vector析构时出现内存泄漏，通常是因为：
- 没有正确调用元素的析构函数
- 忘记释放内存块
- 异常安全处理不完善
可以使用valgrind或AddressSanitizer工具检测，确保每个new都有对应的delete，每个构造都有对应的析构。
6. 测试用例设计
完整的vector实现需要覆盖以下测试场景：
cpp复制TEST(VectorTest, BasicOperations) {
Vector<int> v;
ASSERT_TRUE(v.empty());
v.push_back(1);
ASSERT_EQ(v.size(), 1);
ASSERT_EQ(v[0], 1);
v.reserve(100);
ASSERT_GE(v.capacity(), 100);
Vector<int> v2 = v;
ASSERT_EQ(v2.size(), 1);
v2.emplace_back(2);
ASSERT_EQ(v2.back(), 2);
v2.pop_back();
ASSERT_EQ(v2.size(), 1);
v2.clear();
ASSERT_TRUE(v2.empty());
}
TEST(VectorTest, ExceptionSafety) {
struct ThrowOnCopy {
ThrowOnCopy() = default;
ThrowOnCopy(const ThrowOnCopy&) { throw std::runtime_error("copy failed"); }
};
Vector<ThrowOnCopy> v(10);
ASSERT_THROW(v.push_back(ThrowOnCopy{}), std::runtime_error);
ASSERT_EQ(v.size(), 10); // 状态应保持不变
}
实现一个完整的vector容器远不止这些内容，还包括allocator支持、constexpr支持、三路比较操作符等现代C++特性。但掌握了这些核心要点，你已经能够应对大多数应用场景了。