前言自己动手实现一个简化版std::vector是理解「动态数组」和「对象生命周期」的最好练习。标准库的vector要处理分配器、异常安全、迭代器、initializer_list、resize/insert/erase等大量细节本文只保留最核心的部分三个指针数据、大小、容量、扩容、push_back、pop_back、reserve、元素访问、拷贝与移动。常见的误解有三个。第一以为push_back每次都是 O(1)——单次可能是 O(n)扩容时搬移所有元素只有均摊复杂度是 O(1)。第二以为capacity()和size()总相等——容量是已分配空间能容纳的元素数大小是实际构造的元素数二者之间可能有未构造的原始内存。第三用new T[n]来分配容量这会默认构造全部n个元素既要求T可默认构造也无法表达「已分配但未构造」的状态。本文用std::allocator把「分配原始内存」和「构造对象」分开实现一个行为接近标准库的简化版本。代码以 C17 为基准。一、三个成员与不变量// 适用于 C17template typename Tclass Vector {private:T* data_ nullptr; // 指向已分配的原始内存std::size_t size_ 0; // 已构造的元素个数std::size_t cap_ 0; // 已分配内存能容纳的元素个数};不变量invariantsize_ cap_。data_指向cap_个T大小的原始内存前size_个位置是已构造的对象后面cap_ - size_个位置未构造。cap_ 0时data_ nullptr。data_ size_是「尾后位置」可以用于迭代器但不能解引用。这三个值决定了所有操作push_back在size_ cap_时扩容pop_back只析构最后一个元素、不释放内存clear析构所有元素但保留容量。二、为什么用 allocator 而不是 new T[n]new T[n]会做两件事分配n * sizeof(T)字节并对每个元素调用默认构造函数。这带来三个问题要求T可默认构造。vector应该能存放没有默认构造函数的类型只要通过push_back提供值。capacity大于size时多出来的位置也被构造了浪费构造/析构开销语义上也不对。delete[]会对所有n个元素调用析构即使其中只有前size个真正构造过。std::allocatorT把两件事拆开allocate(n)分配能容纳n个T的原始内存不构造对象。construct(p, args...)在p指向的原始内存上构造对象。destroy(p)调用析构函数不释放内存。deallocate(p, n)释放内存。C17 起std::allocatorT::construct和destroy已被弃用C20 移除应该通过std::allocator_traits调用// 适用于 C17using AllocTraits std::allocator_traitsstd::allocatorT;AllocTraits::construct(alloc_, ptr, args...);AllocTraits::destroy(alloc_, ptr);这样写也与自定义分配器兼容把std::allocatorT换成别的分配器allocator_traits会补上缺失的成员。三、扩容与异常安全扩容的步骤是分配一块更大的原始内存。把旧元素逐个搬到新内存std::move_if_noexcept。析构旧元素。释放旧内存。更新data_、cap_。std::move_if_noexcept的选择逻辑是如果T的移动构造是noexcept或者T不可拷贝就返回右值引用移动否则返回const拷贝。这样在「移动可能抛异常且拷贝可用」时宁可拷贝也要保证强异常安全扩容失败时原容器不变。扩容因子通常取 2 或 1.5。取 2 的好处是实现简单、均摊 O(1) 容易证明取 1.5 的好处是内存复用率更高释放的旧块可能被后续分配复用。标准没有规定因子本文用 2。异常安全的目标是「强保证」如果扩容过程中抛异常容器保持原状。实现方式是在新内存上构造全部成功后才动旧内存中途失败则销毁已构造的新元素、释放新内存然后重新抛出。四、完整实现// 适用于 C17#include cstddef#include memory#include stdexcept#include utilitytemplate typename Tclass Vector {public:using value_type T;using iterator T*;using const_iterator const T*;Vector() noexcept default;explicit Vector(std::size_t n) {if (n 0) return;data_ AllocTraits::allocate(alloc_, n);cap_ n;try {for (; size_ n; size_) {AllocTraits::construct(alloc_, data_ size_);}} catch (...) {clear();AllocTraits::deallocate(alloc_, data_, cap_);data_ nullptr;cap_ 0;throw;}}~Vector() {clear();deallocate();}Vector(const Vector other) {reserve(other.size_);try {for (std::size_t i 0; i other.size_; i) {push_back(other.data_[i]);}} catch (...) {clear();deallocate();throw;}}Vector operator(const Vector other) {if (this ! other) {Vector tmp(other);swap(tmp);}return *this;}Vector(Vector other) noexcept: data_(other.data_), size_(other.size_), cap_(other.cap_) {other.data_ nullptr;other.size_ 0;other.cap_ 0;}Vector operator(Vector other) noexcept {if (this ! other) {clear();deallocate();data_ other.data_;size_ other.size_;cap_ other.cap_;other.data_ nullptr;other.size_ 0;other.cap_ 0;}return *this;}void push_back(const T value) { emplace_back(value); }void push_back(T value) { emplace_back(std::move(value)); }template typename... ArgsT emplace_back(Args... args) {if (size_ cap_) {grow(cap_ 0 ? 1 : cap_ * 2);}AllocTraits::construct(alloc_, data_ size_, std::forwardArgs(args)...);size_;return data_[size_ - 1];}void pop_back() {if (size_ 0) {throw std::out_of_range(pop_back on empty Vector);}--size_;AllocTraits::destroy(alloc_, data_ size_);}void reserve(std::size_t n) {if (n cap_) grow(n);}void clear() noexcept {for (std::size_t i 0; i size_; i) {AllocTraits::destroy(alloc_, data_ i);}size_ 0;}T operator[](std::size_t i) { return data_[i]; }const T operator[](std::size_t i) const { return data_[i]; }T at(std::size_t i) {if (i size_) throw std::out_of_range(Vector::at);return data_[i];}const T at(std::size_t i) const {if (i size_) throw std::out_of_range(Vector::at);return data_[i];}T* data() noexcept { return data_; }const T* data() const noexcept { return data_; }std::size_t size() const noexcept { return size_; }std::size_t capacity() const noexcept { return cap_; }bool empty() const noexcept { return size_ 0; }iterator begin() noexcept { return data_; }iterator end() noexcept { return data_ size_; }const_iterator begin() const noexcept { return data_; }const_iterator end() const noexcept { return data_ size_; }void swap(Vector other) noexcept {std::swap(data_, other.data_);std::swap(size_, other.size_);std::swap(cap_, other.cap_);}private:using AllocTraits std::allocator_traitsstd::allocatorT;void deallocate() noexcept {if (data_ ! nullptr) {AllocTraits::deallocate(alloc_, data_, cap_);data_ nullptr;}cap_ 0;}void grow(std::size_t newCap) {T* newData AllocTraits::allocate(alloc_, newCap);std::size_t i 0;try {for (; i size_; i) {AllocTraits::construct(alloc_, newData i,std::move_if_noexcept(data_[i]));}} catch (...) {for (std::size_t j 0; j i; j) {AllocTraits::destroy(alloc_, newData j);}AllocTraits::deallocate(alloc_, newData, newCap);throw;}for (std::size_t j 0; j size_; j) {AllocTraits::destroy(alloc_, data_ j);}if (data_ ! nullptr) {AllocTraits::deallocate(alloc_, data_, cap_);}data_ newData;cap_ newCap;}std::allocatorT alloc_;T* data_ nullptr;std::size_t size_ 0;std::size_t cap_ 0;};几处设计说明构造函数explicit Vector(std::size_t n)构造n个值初始化的元素。标准库的vector(n)是值初始化vector(n, value)是拷贝值本文只实现前者的简化版。拷贝构造先用reserve分配足够空间再逐个push_back。push_back不会触发扩容容量已够每次只构造一个元素。拷贝赋值用拷贝并交换Vector tmp(other); swap(tmp);。tmp析构时释放原来的资源自赋值也安全。移动构造和移动赋值直接偷指针并把源对象置空。前提是分配器无状态std::allocator满足如果分配器带状态标准库需要按propagate_on_container_move_assignment决定是否交换分配器本文省略。pop_back在空容器上抛异常。标准std::vector::pop_back对空容器是未定义行为undefined behavior, UB这里为了教学改成抛std::out_of_range属于有意的行为差异使用时要清楚。grow用std::move_if_noexcept搬移中途失败会销毁已构造的新元素、释放新内存旧容器不受影响。begin()/end()返回裸指针。空容器时data_为nullptrend()也是nullptrbegin() end()成立。五、使用示例// 适用于 C17#include iostream#include stringint main() {Vectorint v;for (int i 0; i 5; i) {v.push_back(i * i);}std::cout v.size() v.capacity() \n;for (std::size_t i 0; i v.size(); i) {std::cout v[i] ;}std::cout \n;v.pop_back();std::cout v.size() \n;Vectorstd::string names;names.push_back(Alice);names.emplace_back(3, x); // 构造 xxxstd::cout names[1] \n;Vectorstd::string copy names;copy.clear();std::cout names.size() copy.size() \n;return 0;}emplace_back(3, x)把参数完美转发给std::string的构造函数string(size_type count, char ch)直接在容器的原始内存上构造不产生临时std::string。push_back(Alice)会先构造一个临时std::string再移动进容器两者语义略有差别emplace_back少一次移动。六、复杂度操作复杂度说明push_back/emplace_back均摊 O(1)单次最坏 O(n)扩容时搬移全部元素pop_backO(1)只析构最后一个operator[]/at/dataO(1)连续存储reserveO(n)可能搬移全部元素clearO(n)析构所有元素拷贝构造O(n)逐个拷贝移动构造O(1)偷指针「均摊 O(1)」的含义是连续n次push_back的总代价是 O(n)而不是每次都是常数。证明的关键是扩容因子大于 1每次扩容搬移的元素数按几何级数增长总和是 O(n)。常见坑点1. 用 new T[n] 分配容量❌data_ new T[cap];默认构造全部元素要求T可默认构造且无法区分「已构造」和「未构造」。✅ 用allocator::allocate分配原始内存allocator_traits::construct按需构造。2. 析构时只 delete[] 不逐个析构❌delete[] data_;与allocate不配对且会析构未构造的位置。✅ 先对前size_个元素调用destroy再deallocate(data_, cap_)。3. push_back 扩容后使用旧指针❌int* p v[0]; v.push_back(1); *p 2;—— 扩容后旧内存已释放p悬垂。✅ 扩容会使所有指针、引用、迭代器失效需要跨操作保存时用下标并重新获取地址。4. 扩容因子取 1 或接近 1❌grow(cap_ 1)每次只多一个位置n次push_back变成 O(n²)。✅ 按倍数增长2 或 1.5保证均摊 O(1)。5. 拷贝赋值没有处理自赋值❌ 先clear()再逐个拷贝other当this other时源数据已被清空。✅ 用拷贝并交换或先判断this ! other。6. 移动后不把源对象置空❌ 偷了指针但不修改other.data_源对象析构时重复释放。✅ 移动后把源对象的data_置nullptr、size_/cap_置 0。7. 在空容器上 pop_back❌ 不做检查直接--size_并析构data_[size_]无符号下溢或访问非法内存。✅ 检查empty()标准库对此是 UB自己实现时可以抛异常或断言。8. 扩容时用 std::move 而不是 move_if_noexcept❌ 对可能抛异常的移动构造直接用std::move扩容中途失败会丢失原元素。✅ 用std::move_if_noexcept在移动不保证noexcept时退回复制。总结组件作用data_原始内存起始地址size_已构造元素个数cap_已分配内存可容纳的元素个数allocate/deallocate管理原始内存construct/destroy管理对象生命周期grow按倍数扩容move_if_noexcept搬移拷贝并交换异常安全、自赋值安全的赋值实现vector的关键不是记住接口而是分清「内存」和「对象」这两件事allocate只给内存construct才开始对象的生命周期destroy结束生命周期deallocate归还内存。把这四步和size_/cap_的关系理清扩容、析构、拷贝、移动就都不会写错。
