C++
手写 std::vector
从原始存储、几何扩容和异常回滚出发，实现支持复制移动、迭代器与主要修改操作的动态数组。
发布于 2026年7月23日
手写 std::vector
从原始存储、几何扩容和异常回滚出发，实现支持复制移动、迭代器与主要修改操作的动态数组。
本系列代码使用 C++20 和
oc::handmade命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。
一、学习目标
- 实现 size/capacity 双边界
- 理解几何扩容带来的摊还 O(1)
- 处理自引用插入与搬迁异常
二、前置条件
掌握 allocator_traits、移动语义和强异常保证。
Linux/macOS：
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure
Windows PowerShell：
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure
三、问题与设计选择
保存 data_、size_、capacity_ 和 allocator。扩容先在新缓冲区构造全部对象，成功后一次提交；优先使用 nothrow move，否则复制。
这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。
四、内存布局与核心不变量
data_ 要么为空，要么指向 capacity 个 T 的原始存储；其中前 size 个对象已经构造。
每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。
五、核心实现
void grow_for_one() {
const size_type next = capacity_ ? capacity_ * 2 : 1;
pointer fresh = traits::allocate(alloc_, next);
size_type built = 0;
try {
for (; built < size_; ++built)
traits::construct(alloc_, fresh + built,
std::move_if_noexcept(data_[built]));
} catch (...) {
while (built) traits::destroy(alloc_, fresh + --built);
traits::deallocate(alloc_, fresh, next);
throw;
}
destroy_and_deallocate();
data_ = fresh;
capacity_ = next;
size_ = built;
}
上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。
六、完整教学实现
下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。
namespace oc::handmade {
template<class T, class Allocator = std::allocator<T>>
class vector {
using traits = std::allocator_traits<Allocator>;
Allocator allocator_{};
T* data_{};
std::size_t size_{};
std::size_t capacity_{};
void destroy_elements() noexcept {
while (size_ != 0) traits::destroy(allocator_, data_ + --size_);
}
void release() noexcept {
destroy_elements();
if (data_) traits::deallocate(allocator_, data_, capacity_);
data_ = nullptr;
capacity_ = 0;
}
bool refers_to_storage(const T* value) const noexcept {
return data_ && value >= data_ && value < data_ + size_;
}
public:
using value_type = T;
using size_type = std::size_t;
using iterator = T*;
using const_iterator = const T*;
vector() = default;
explicit vector(const Allocator& allocator) : allocator_(allocator) {}
vector(const vector& other)
: allocator_(traits::select_on_container_copy_construction(other.allocator_)) {
reserve(other.size_);
try {
for (const T& item : other) emplace_back(item);
} catch (...) {
release();
throw;
}
}
vector(vector&& other) noexcept
: allocator_(std::move(other.allocator_)),
data_(std::exchange(other.data_, nullptr)),
size_(std::exchange(other.size_, 0)),
capacity_(std::exchange(other.capacity_, 0)) {}
vector& operator=(const vector& other) {
if (this == &other) return *this;
vector copy(other);
swap(copy);
return *this;
}
vector& operator=(vector&& other) noexcept {
if (this == &other) return *this;
release();
allocator_ = std::move(other.allocator_);
data_ = std::exchange(other.data_, nullptr);
size_ = std::exchange(other.size_, 0);
capacity_ = std::exchange(other.capacity_, 0);
return *this;
}
~vector() { release(); }
void swap(vector& other) noexcept {
using std::swap;
swap(allocator_, other.allocator_);
swap(data_, other.data_);
swap(size_, other.size_);
swap(capacity_, other.capacity_);
}
iterator begin() noexcept { return data_; }
const_iterator begin() const noexcept { return data_; }
iterator end() noexcept { return data_ ? data_ + size_ : nullptr; }
const_iterator end() const noexcept { return data_ ? data_ + size_ : nullptr; }
T* data() noexcept { return data_; }
const T* data() const noexcept { return data_; }
bool empty() const noexcept { return size_ == 0; }
size_type size() const noexcept { return size_; }
size_type capacity() const noexcept { return capacity_; }
T& operator[](size_type index) noexcept { return data_[index]; }
const T& operator[](size_type index) const noexcept { return data_[index]; }
T& at(size_type index) {
if (index >= size_) throw std::out_of_range("oc::handmade::vector::at");
return data_[index];
}
const T& at(size_type index) const {
if (index >= size_) throw std::out_of_range("oc::handmade::vector::at");
return data_[index];
}
T& front() noexcept { return data_[0]; }
const T& front() const noexcept { return data_[0]; }
T& back() noexcept { return data_[size_ - 1]; }
const T& back() const noexcept { return data_[size_ - 1]; }
void reserve(size_type requested) {
if (requested <= capacity_) return;
T* fresh = traits::allocate(allocator_, requested);
size_type built = 0;
try {
for (; built < size_; ++built) {
traits::construct(
allocator_,
fresh + built,
std::move_if_noexcept(data_[built])
);
}
} catch (...) {
while (built) traits::destroy(allocator_, fresh + --built);
traits::deallocate(allocator_, fresh, requested);
throw;
}
const size_type old_size = size_;
destroy_elements();
if (data_) traits::deallocate(allocator_, data_, capacity_);
data_ = fresh;
size_ = old_size;
capacity_ = requested;
}
template<class... Args>
T& emplace_back(Args&&... args) {
if (size_ == capacity_) {
T temporary(std::forward<Args>(args)...);
reserve(capacity_ == 0 ? 1 : capacity_ * 2);
traits::construct(allocator_, data_ + size_, std::move(temporary));
} else {
traits::construct(
allocator_,
data_ + size_,
std::forward<Args>(args)...
);
}
return data_[size_++];
}
void push_back(const T& value) {
if (size_ == capacity_ && refers_to_storage(std::addressof(value))) {
T copy(value);
emplace_back(std::move(copy));
} else {
emplace_back(value);
}
}
void push_back(T&& value) {
if (size_ == capacity_ && refers_to_storage(std::addressof(value))) {
T temporary(std::move(value));
emplace_back(std::move(temporary));
} else {
emplace_back(std::move(value));
}
}
void pop_back() noexcept {
assert(size_ != 0);
traits::destroy(allocator_, data_ + --size_);
}
iterator erase(iterator position) {
assert(position >= begin() && position < end());
for (iterator current = position; current + 1 != end(); ++current)
*current = std::move(*(current + 1));
pop_back();
return position;
}
void clear() noexcept { destroy_elements(); }
};
} // namespace oc::handmade
生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。
七、使用示例与输出
预期输出或状态：
依次插入 1、2、3 时容量示例为 1、2、4；元素顺序保持 1 2 3。
示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。
八、复杂度与失效规则
| 操作 | 复杂度 | 说明 |
|---|---|---|
| operator[]/back | O(1) | 不检查边界 |
| push_back | 摊还 O(1) | 扩容时 O(n) |
| insert/erase | O(n) | 移动尾部 |
| reserve | O(n) | 所有迭代器失效 |
复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。
九、异常安全与资源管理
- 获取资源后立即交给 RAII 对象或明确记录已构造数量。
- 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
- 只有在所有后续步骤不会失败时才修改不可回滚的链接。
- 析构、释放和关闭路径不得抛异常。
- 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。
十、常见错误
1. 扩容成功前就覆盖旧指针
扩容成功前就覆盖旧指针会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
2. 传入 v[0] 再扩容导致参数引用悬空
传入 v[0] 再扩容导致参数引用悬空会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
3. 用 memcpy 搬运任意 T
用 memcpy 搬运任意 T会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
十一、面试追问
- 为什么扩容倍数通常大于 1？
push_back在什么情况下不能提供强保证？reserve与resize的区别是什么？
回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。
十二、练习与自测
- 实现
emplace_back - 处理自引用 push_back
- 统计不同增长因子的搬迁次数
自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。
十三、官方资料与延伸阅读
上一篇：手写 std::array ｜ 下一篇：手写 std::string