Chapter 50: Mini Vector

本章实现一个教学版 mini::vector<T, Alloc>，目标是把连续存储、元素生命周期、allocator 调用、扩容迁移、迭代器失效和异常安全连成一条可检查的实现路径。读完本章后，读者应能定位一个 vector 对象当前拥有哪些原始存储、哪些位置已经构造了元素、下一次插入是否触发 reallocate，以及失败路径上需要销毁哪些对象、释放哪块存储。

本章贯穿材料是一组最小状态：first_ 指向已分配存储起点，last_ 指向已构造区间末尾，cap_ 指向存储末尾。这个三指针模型足以支撑 size()、capacity()、随机访问 iterator、reserve()、emplace_back()、erase()、析构、拷贝和移动。标准库 std::vector 的公开语义比本章代码更完整，例如 allocator propagation、range insert、C++20 constexpr 支持和实现细节差异；本章只实现能解释核心对象状态的最小版本。

std::vector::reserve 的公开语义规定：扩容成功后 capacity 至少达到请求值，size 保持不变，发生 reallocation 时 iterator 和 reference 全部失效；异常路径上通常要求旧对象保持原状态。这个判断可从 std::vector::reserve 的说明 回溯。std::allocator_traits::construct 说明容器在未初始化存储上创建元素时应经由 allocator traits，必要时落到 placement new 或 std::construct_at；这个边界可从 std::allocator_traits::construct 回溯。正文会把这些公开语义转成 mini vector 的具体代码责任。

下面是本章用到的最小骨架。代码是教学简化代码，省略了完整 include、比较运算、range insert、max_size() 检查和 allocator propagation 细节；保留的部分覆盖对象状态和生命周期主路径。

template<class T, class Alloc = std::allocator<T>>
class vector {
public:
    using value_type = T;
    using allocator_type = Alloc;
    using size_type = std::size_t;
    using iterator = T*;
    using const_iterator = const T*;

private:
    using traits = std::allocator_traits<Alloc>;

    T* first_ = nullptr;
    T* last_ = nullptr;
    T* cap_ = nullptr;
    [[no_unique_address]] Alloc alloc_{};

public:
    vector() = default;
    explicit vector(const Alloc& alloc) : alloc_(alloc) {}

    ~vector() {
        clear();
        release_storage();
    }

    size_type size() const noexcept {
        return first_ == nullptr ? 0 : static_cast<size_type>(last_ - first_);
    }

    size_type capacity() const noexcept {
        return first_ == nullptr ? 0 : static_cast<size_type>(cap_ - first_);
    }

    bool empty() const noexcept {
        return first_ == last_;
    }

    iterator begin() noexcept { return first_; }
    iterator end() noexcept { return last_; }
    const_iterator begin() const noexcept { return first_; }
    const_iterator end() const noexcept { return last_; }
};

这段骨架先给出一个核心取舍：iterator 直接使用 T*。这个选择使 mini vector 保持连续存储语义，begin() 到 end() 是半开区间，算法能按 random access iterator 的方式执行差值、加法和比较。它同时让 iterator 失效变得可观察：只要 reallocate 改变 first_ 所指向的存储，旧 T* 就指向旧缓冲区，旧位置对象失去语义。

50.1 三指针模型与对象状态

mini vector 的主不变量来自三个指针之间的顺序关系：非空存储状态满足 first_ <= last_ <= cap_，空状态满足三个指针全为空。其中 [first_, last_) 是已经构造的元素区间，[last_, cap_) 是已经分配但尚未构造对象的原始存储区间。size() 来自已构造元素数量，capacity() 来自已分配槽位数量；这两个值来自同一块存储上的指针差，说明 size 和 capacity 是对象状态的投影。

空对象有两种常见表示。第一种是 first_ == last_ == cap_ == nullptr，表示没有分配存储。第二种是 first_ == last_ 且 cap_ > first_，表示有空闲存储但没有构造元素。mini vector 需要同时接受这两种状态，因为 clear() 会销毁元素并保留 capacity，默认构造对象则没有存储。

三指针模型把内存分成两层责任。allocator 负责 [first_, cap_) 这块原始存储的申请与释放；元素构造和析构只覆盖 [first_, last_)。这两个范围在实现中必须分开维护：释放存储前必须先销毁已经构造的元素，构造新元素失败时只能销毁已经构造成功的那一段。

下面的图描述 mini vector 在扩容前后的状态边界。图中 raw storage 表示已经分配但没有对象生命周期的槽位。

这条路径的核心是提交顺序。reallocate 在新缓冲区中构造成功前，旧 first_、last_、cap_ 仍代表当前对象的有效状态；新缓冲区准备完成后，旧元素才能销毁，旧存储才能释放，然后三指针切换到新存储。这个顺序支撑 strong exception guarantee 的基本形状：失败发生在新缓冲区准备阶段时，旧 vector 仍保持原状态。

对象状态可以用一个短例子验证。下面代码是简化代码，假设 vector<int> 已经实现 reserve() 和 emplace_back()。

mini::vector<int> values;
values.reserve(4);
values.emplace_back(10);
values.emplace_back(20);

// 状态应满足：size == 2，capacity >= 4。
// [begin, end) 中有 10、20 两个 int 对象。
// [end, begin + capacity) 是原始存储，解引用没有 int 对象语义。

这段代码说明一个常见实现边界：capacity 范围内的空位属于原始存储，读取它们没有对象语义。mini vector 的实现必须只在 last_ 位置调用 construct，构造成功后再推进 last_。如果先推进 last_ 再构造，构造函数抛异常时，clear() 会把一个尚未进入生命周期的位置当作对象销毁。

为了让每个修改函数都能复用同一套状态判断，可以先补齐私有工具函数。

private:
    void destroy_range(T* first, T* last) noexcept {
        while (last != first) {
            --last;
            traits::destroy(alloc_, last);
        }
    }

    void release_storage() noexcept {
        if (first_ != nullptr) {
            traits::deallocate(alloc_, first_, capacity());
        }
        first_ = nullptr;
        last_ = nullptr;
        cap_ = nullptr;
    }

public:
    void clear() noexcept {
        destroy_range(first_, last_);
        last_ = first_;
    }

destroy_range() 从尾部向前销毁。尾部销毁适合扩容回滚，因为新缓冲区中已构造数量通常由一个尾指针推进；回滚时只需要把这个尾指针倒退到起点。release_storage() 只释放原始存储，并把三个指针统一恢复到空对象状态。这个恢复动作使 moved-from 对象和析构后的内部清理路径都能复用同一组不变量。

50.2 reserve、push_back、emplace_back 与 reallocate

reserve() 的核心问题是扩容时如何把旧元素迁移到新存储，并在失败时保留旧 vector 的状态。mini vector 的实现顺序应固定为：申请新原始存储，逐个构造新元素，失败时销毁新存储中已经构造的元素并释放新存储，成功后销毁旧元素并释放旧存储，最后提交新三指针。

下面是一个简化版 reserve()。它使用 std::move_if_noexcept，使可抛异常的移动构造在有拷贝构造可用时优先走拷贝路径。这个选择对应标准库常见实现形状：扩容迁移需要在性能和异常安全之间做取舍。

public:
    void reserve(size_type new_capacity) {
        if (new_capacity <= capacity()) {
            return;
        }

        T* new_first = traits::allocate(alloc_, new_capacity);
        T* new_last = new_first;

        try {
            for (T* cur = first_; cur != last_; ++cur, ++new_last) {
                traits::construct(
                    alloc_,
                    new_last,
                    std::move_if_noexcept(*cur)
                );
            }
        } catch (...) {
            destroy_range(new_first, new_last);
            traits::deallocate(alloc_, new_first, new_capacity);
            throw;
        }

        destroy_range(first_, last_);
        if (first_ != nullptr) {
            traits::deallocate(alloc_, first_, capacity());
        }

        const size_type old_size = static_cast<size_type>(new_last - new_first);
        first_ = new_first;
        last_ = new_first + old_size;
        cap_ = new_first + new_capacity;
    }

这段代码有三个细节需要单独检查。第一，new_last 只在一个元素构造成功后推进，因此 catch 分支能准确销毁 [new_first, new_last)。第二，旧元素销毁和旧存储释放发生在所有新元素构造成功之后，因此构造失败时旧 vector 的三指针仍指向旧状态。第三，old_size 在提交前从新指针计算出来，提交后 capacity() 才会换成新存储容量；这能防止释放旧存储时误用新 capacity。

emplace_back() 是插入路径的最小入口。它需要先保证有空间，然后在 last_ 所指位置构造对象，构造成功后再推进 last_。push_back() 可以复用 emplace_back()，分别传入左值和右值。

private:
    size_type next_capacity() const {
        const size_type old_capacity = capacity();
        return old_capacity == 0 ? 1 : old_capacity * 2;
    }

public:
    template<class... Args>
    T& emplace_back(Args&&... args) {
        if (last_ == cap_) {
            reserve(next_capacity());
        }

        traits::construct(
            alloc_,
            last_,
            std::forward<Args>(args)...
        );
        ++last_;
        return *(last_ - 1);
    }

    void push_back(const T& value) {
        emplace_back(value);
    }

    void push_back(T&& value) {
        emplace_back(std::move(value));
    }

emplace_back() 的异常边界比 reserve() 更小。空间足够时，失败点集中在一次元素构造；因为 last_ 尚未推进，失败后 [first_, last_) 仍覆盖原有元素。空间不足时，先进入 reserve()，扩容完成后再构造新元素；如果扩容失败，旧状态保留；如果新元素构造失败，扩容已经提交，size 仍是旧值，capacity 可能已经变大。这是许多容器操作中常见的状态区分：元素数量和容量变化属于不同承诺。

next_capacity() 使用倍增策略，使多次尾插的摊还复杂度保持常数级。每次都按 size() + 1 调用 reserve() 会让容量线性增长，长期插入会触发更多次迁移。标准库公开说明中也提醒过度使用 reserve() 可能改变增长行为；mini vector 用一个固定增长函数把这个策略集中到一处。

扩容会使旧 iterator、pointer 和 reference 失效。mini vector 的 iterator 是 T*，因此失效判断可以直接从地址变化推出：reserve() 如果分配新缓冲区，旧 begin() 返回的地址属于旧存储；旧存储释放后，继续解引用旧地址会进入未定义行为。reserve() 如果没有扩容，旧地址保持有效。这个判断顺序也适用于 emplace_back()：先看是否触发 reallocate，再判断旧 iterator 是否仍能使用。

50.3 erase、clear 与 destructor

erase() 处理的是连续存储中间删除。删除位置之后的元素必须向前覆盖空洞，最后一个旧元素需要析构，last_ 向前收缩。std::vector::erase 的公开语义规定，删除点及其后的 iterator 和 reference 失效，返回被删除区间之后的新 iterator；这个边界可从 std::vector::erase 回溯。

单元素 erase() 可以写成如下形式。代码是教学简化代码，要求 T 支持 move assignment；如果 move assignment 抛异常，本函数只提供 basic guarantee，即 vector 仍能析构和继续使用，但元素值可能已经被部分移动赋值过。

public:
    iterator erase(iterator pos) {
        for (T* cur = pos; cur + 1 != last_; ++cur) {
            *cur = std::move(*(cur + 1));
        }

        --last_;
        traits::destroy(alloc_, last_);
        return pos;
    }

这段代码体现了连续存储删除的成本来源。删除第一个元素时，需要移动赋值后面全部元素；删除最后一个元素时，循环不执行，只销毁尾元素。复杂度由删除点之后的元素数量决定，容器仍保持连续存储和原始 capacity。删除动作不会释放存储，因此 capacity() 保持不变。

范围删除使用同一条思路：把 [last, end) 移动到 first 起始的位置，然后销毁尾部多余元素。返回值是新位置 first，也就是旧区间后继元素搬移后的地址。

public:
    iterator erase(iterator first, iterator last) {
        if (first == last) {
            return first;
        }

        T* write = first;
        T* read = last;
        while (read != last_) {
            *write = std::move(*read);
            ++write;
            ++read;
        }

        destroy_range(write, last_);
        last_ = write;
        return first;
    }

clear() 的语义更直接：销毁所有已构造元素，把 last_ 恢复到 first_，保留原始存储。这个行为使后续 emplace_back() 可以复用已有 capacity。destructor 则在 clear() 之后调用 release_storage()，把元素生命周期结束和原始存储释放串成完整闭环。

析构路径需要满足两个条件。第一，析构只覆盖已经构造的 [first_, last_)，因此默认构造后的空 vector、clear() 后的空 vector、移动后的空 vector 都能安全析构。第二，释放存储时必须使用分配时传入的元素数量，也就是旧 capacity()。allocator 的 deallocate(p, n) 对 n 有匹配要求，mini vector 必须在更新指针前完成旧存储释放，或提前保存旧容量。

erase() 和 clear() 的 iterator 失效规则来自状态变化。clear() 后，所有指向旧元素的 iterator 都失效，因为旧元素生命周期已经结束；即使地址仍在同一块存储中，也没有可解引用的对象。erase() 后，删除点之前的元素对象仍在原地址，删除点及其后的元素经历移动覆盖或析构，因此这些位置的旧 iterator 失效。这个判断比单纯看地址更精确，因为对象生命周期和地址复用属于两层事实。

50.4 copy / move constructor 与 assignment

copy constructor 的目标是深拷贝：新 vector 分配独立存储，并在新存储中逐个拷贝构造元素。旧 vector 和新 vector 之间没有元素所有权共享，因此任意一方析构、扩容或修改都不会影响另一方的存储所有权。

下面是简化版 copy constructor。它在构造过程中使用局部指针记录已构造区间，失败时销毁新对象并释放新存储。

public:
    vector(const vector& other)
        : alloc_(traits::select_on_container_copy_construction(other.alloc_)) {
        const size_type n = other.size();
        if (n == 0) {
            return;
        }

        first_ = traits::allocate(alloc_, n);
        last_ = first_;
        cap_ = first_ + n;

        try {
            for (T* cur = other.first_; cur != other.last_; ++cur, ++last_) {
                traits::construct(alloc_, last_, *cur);
            }
        } catch (...) {
            destroy_range(first_, last_);
            traits::deallocate(alloc_, first_, n);
            first_ = nullptr;
            last_ = nullptr;
            cap_ = nullptr;
            throw;
        }
    }

copy assignment 可以用 copy-and-swap 表达 strong exception guarantee。先构造临时副本；临时副本构造成功后再交换当前对象和临时对象。临时对象离开作用域时析构旧资源。这个方法把失败点集中在临时对象构造阶段，当前对象在失败时保持原状态。教学版 swap() 同时交换 allocator，真实标准库会受 allocator propagation 规则约束。

public:
    vector& operator=(const vector& other) {
        if (this == &other) {
            return *this;
        }

        vector temp(other);
        swap(temp);
        return *this;
    }

    void swap(vector& other) noexcept(std::is_nothrow_swappable_v<Alloc>) {
        using std::swap;
        swap(first_, other.first_);
        swap(last_, other.last_);
        swap(cap_, other.cap_);
        swap(alloc_, other.alloc_);
    }

move constructor 的目标是资源转移。mini vector 可以直接偷取 other 的三指针和 allocator，然后把 other 恢复成可析构的空状态。这个 moved-from 状态需要满足对象不变量：other.size() == 0、other.capacity() == 0、析构安全、可以再次赋值。

public:
    vector(vector&& other) noexcept(std::is_nothrow_move_constructible_v<Alloc>)
        : first_(other.first_),
          last_(other.last_),
          cap_(other.cap_),
          alloc_(std::move(other.alloc_)) {
        other.first_ = nullptr;
        other.last_ = nullptr;
        other.cap_ = nullptr;
    }

move assignment 需要先释放当前对象已有资源，再接管右侧对象资源。教学版采用“allocator 一起移动并允许偷取存储”的策略，因此代码短；标准库 std::vector 还需要处理 allocator propagation 和 allocator equality，这会影响能否直接偷取缓冲区。代码中的 noexcept 条件只覆盖 allocator 移动赋值，本章默认元素析构不抛异常。

public:
    vector& operator=(vector&& other) noexcept(std::is_nothrow_move_assignable_v<Alloc>) {
        if (this == &other) {
            return *this;
        }

        clear();
        release_storage();

        first_ = other.first_;
        last_ = other.last_;
        cap_ = other.cap_;
        alloc_ = std::move(other.alloc_);

        other.first_ = nullptr;
        other.last_ = nullptr;
        other.cap_ = nullptr;
        return *this;
    }

这组 special member functions 的判断顺序是：先看资源所有权是否共享，再看失败发生在新资源准备前还是提交后，再看 moved-from 对象是否仍满足析构安全和可赋值状态。copy 必须建立独立存储，move 可以转移存储所有权；assignment 必须处理当前对象已有资源，因此比 constructor 多一个释放旧状态的步骤。

自赋值和自移动都需要有明确处理。operator=(const vector&) 中的 this == &other 检查可以减少无意义工作。move assignment 中同样保留这个检查，因为 v = std::move(v) 在泛型代码中可能出现；直接 clear() 再偷取自身指针会把对象清空并破坏预期。教学版用显式检查保持对象状态稳定。

50.5 mini vector 验收检查点

mini vector 的验收应从对象状态开始。任意 public 成员函数返回后，非空存储状态都应满足 first_ <= last_ <= cap_，空状态都应满足三个指针全为空。size() 只计算 [first_, last_) 的长度，capacity() 只计算 [first_, cap_) 的长度。clear() 后 size 为 0，capacity 保持；析构后内部不再被观察，但释放路径必须先销毁元素再释放存储。

第二个检查点是 allocator 与对象生命周期分离。allocate() 只得到原始存储，construct() 才让某个槽位进入 T 的生命周期，destroy() 结束对象生命周期，deallocate() 释放整块原始存储。测试时可以使用带日志的元素类型统计构造、拷贝、移动、析构次数；构造失败后，已经构造成功的元素数量应和析构数量匹配。

第三个检查点是 reallocate 的提交边界。reserve() 在新缓冲区准备完成前应保持当前三指针不变；迁移失败时，旧元素仍可遍历，旧 size 和 capacity 保持原值。迁移成功后，旧 iterator 全部失效，新 iterator 指向新缓冲区。这个检查需要同时观察值序列和地址变化。

第四个检查点是 insertion 的 last_ 推进顺序。emplace_back() 应在构造成功后推进 last_；构造函数抛异常时，size 保持不变。空间不足时，扩容和新元素构造是两个阶段：扩容成功会改变 capacity，新元素构造失败不会增加 size。

第五个检查点是 erase 的覆盖和销毁顺序。单点删除会移动赋值后续元素并销毁尾部旧元素；范围删除会移动保留后缀并销毁尾部多余元素。删除点之前的 iterator 仍对应原对象；删除点及其后的 iterator 失效。capacity 保持原值。

第六个检查点是 copy 与 move 的资源边界。copy 后两个 vector 应拥有不同的 begin() 地址；修改一个对象不会改变另一个对象的元素序列。move 后目标对象接管原地址，源对象进入可析构、可赋值的空状态。move assignment 还要确认左侧旧资源已经销毁和释放。

下面是一组最小测试片段。它们承担验收顺序表达，完整测试框架还应补充异常注入、allocator 日志和边界值。

struct Trace {
    static inline int alive = 0;
    int value = 0;

    explicit Trace(int v) : value(v) { ++alive; }
    Trace(const Trace& other) : value(other.value) { ++alive; }
    Trace(Trace&& other) noexcept : value(other.value) {
        other.value = -1;
        ++alive;
    }
    Trace& operator=(Trace&& other) noexcept {
        value = other.value;
        other.value = -1;
        return *this;
    }
    ~Trace() { --alive; }
};

void smoke_test() {
    mini::vector<Trace> values;
    values.reserve(2);
    auto* old_begin = values.begin();

    values.emplace_back(1);
    values.emplace_back(2);
    assert(values.size() == 2);
    assert(values.capacity() >= 2);

    values.emplace_back(3);
    assert(values.size() == 3);
    assert(values.begin() != old_begin);

    values.erase(values.begin() + 1);
    assert(values.size() == 2);
    assert(values.begin()[0].value == 1);
    assert(values.begin()[1].value == 3);

    mini::vector<Trace> copy = values;
    assert(copy.begin() != values.begin());

    mini::vector<Trace> moved = std::move(values);
    assert(moved.size() == 2);
    assert(values.size() == 0);
}

这组测试覆盖三类证据。状态证据检查 size、capacity 和地址；生命周期证据可通过 Trace::alive 或更完整的计数器观察；语义证据检查 erase 后的元素序列、copy 后的独立存储、move 后的源对象状态。mini vector 通过这些检查后，才算建立了连续存储容器的基本实现判断力。

本章的可迁移判断顺序可以固定为：先画出 [first_, last_) 和 [last_, cap_)；再定位当前操作是否申请新存储；接着判断哪些槽位进入或结束对象生命周期；然后确定 iterator 失效范围；最后检查失败路径是否有匹配的 destroy 和 deallocate。这个顺序也适用于阅读真实标准库实现，只是实际源码会把这些动作拆进 helper、guard、allocator traits 和类型分发中。

最小自检任务

阅读下面的简化代码，判断每一步之后 mini::vector<std::string> 的 size、capacity 关系、iterator 失效范围和对象生命周期变化。假设 reserve() 使用本章的 reallocate 策略，erase() 使用移动赋值覆盖后缀。

mini::vector<std::string> names;
names.reserve(3);
auto it0 = names.begin();

names.emplace_back("Ada");
names.emplace_back("Bjarne");
auto it1 = names.begin();

names.emplace_back("Grace");
names.emplace_back("Dennis");

auto erased = names.erase(names.begin() + 1);
names.clear();

答案要点

reserve(3) 后 size 为 0，capacity 至少为 3，it0 是空区间起点地址，当前没有已构造字符串对象。前两次 emplace_back() 在已有存储中构造对象，size 变为 2，capacity 保持至少 3，it1 指向第一个已构造对象，it0 和 it1 地址相同但 it0 在记录时没有可解引用对象语义。

第三次 emplace_back("Grace") 仍可在已有 capacity 内构造，size 变为 3。第四次 emplace_back("Dennis") 触发 reallocate，新缓冲区构造旧三个字符串，再构造新字符串；成功后旧存储释放，it1 以及此前所有指向旧元素的 iterator 和 reference 全部失效。erase(names.begin() + 1) 删除 Bjarne 位置，后缀元素向前移动，尾部旧元素析构，返回 iterator 指向删除后当前位置的元素，也就是 Grace。clear() 销毁全部已构造字符串，size 变为 0，capacity 保持不变，所有指向旧元素的 iterator 失去对象语义。

本章知识点总结

• 三指针不变量：非空存储状态下 first_ <= last_ <= cap_ 描述已构造区间和原始存储区间的边界。
• 空状态：默认空对象和清空后的对象都必须满足可析构、可赋值、可重新插入的状态条件。
• 生命周期分层：allocator 申请的是原始存储，construct() 和 destroy() 才改变元素对象生命周期。
• 扩容提交点：reallocate 应先准备新缓冲区，成功后再销毁旧元素、释放旧存储并提交新指针。
• 尾插顺序：emplace_back() 应先在 last_ 构造对象，构造成功后再推进 last_。
• 容量策略：倍增 capacity 能减少长期尾插中的迁移次数，并支撑摊还常数复杂度判断。
• 删除成本：erase() 需要移动覆盖删除点之后的元素，并销毁尾部多余对象。
• 清空边界：clear() 结束元素生命周期但保留原始存储，因此 size 归零而 capacity 保持。
• 拷贝语义：copy constructor 和 copy assignment 应建立独立存储，使两个 vector 的资源所有权分离。
• 移动语义：move constructor 和 move assignment 可以转移三指针所有权，并把源对象恢复成可析构空状态。
• 失效判断：reallocate 使旧缓冲区地址全部失效，erase 使删除点及其后的位置失去旧对象语义。
• 验收顺序：先检查三指针区间，再检查生命周期调用，再检查异常回滚、iterator 失效和 moved-from 状态。