Skip to main content

Chapter 50: Mini Vector

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

实现 mini::vector<T, Alloc> 的核心工程问题是将“原始存储管理”与“元素对象生命周期”彻底解耦,并在扩容迁移、中间删改与拷贝移动中维持指针不变量和异常安全边界。本章构建一个可逐行追踪这两层边界的最小连续容器模型。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

本章贯穿材料是三指针状态模型:first_ 指向已分配存储起点,last_ 指向已构造区间末尾,cap_ 指向存储末尾(简化骨架省略头文件、比较运算符与 max_size() 检查)。

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_; }
};

骨架直接采用原生指针 T* 作为随机访问 iterator:[begin(), end()) 天然对应连续半开区间,一旦扩容迁移改变了 first_ 的指向,旧指针失效即可通过地址变化直接观测。

标准库基线约束了上述实现边界:

  • std::vector::reserve 的说明:扩容不改变 size(),重分配使旧 iterator 与引用全部失效,异常时保留原对象状态。
  • std::allocator_traits::construct:须经由 allocator traits(必要时落到 placement new 或 std::construct_at)在未初始化存储上启动元素生命周期。

50.1 三指针模型与对象状态​

mini::vector 的状态约束归结为三指针关系:空缓冲时三指针全为 nullptr,非空时恒满足 first_ <= last_ <= cap_。size() 与 capacity() 均由同一块存储上的指针差导出,内存管理与对象生命周期按区间严格分离:

指针区间 / 状态语义划分允许操作析构与回滚责任
first_ == last_ == cap_ == nullptr未分配空状态(默认构造或移动后)仅可安全析构或重新分配无构造对象,无需 deallocate
first_ == last_ 且 cap_ > first_已分配闲置缓冲(如 clear() 后)复用既有 capacity() 插入元素无构造对象,销毁阶段仅释放存储
[first_, last_)已构造元素区间(长度即 size())读写、移动、拷贝与合法解引用释放存储前必须逆序 destroy
[last_, cap_)未初始化原始存储([first_, cap_) 总长即 capacity())仅作 construct 目标地址禁止解引用或调用 destroy

核心判断

扩容迁移必须等新缓冲区全部构造成功后,再销毁旧元素、释放旧存储并提交新三指针。只要新缓冲区构造中途抛异常,旧 first_、last_、cap_ 仍指向完好原对象,从而维持 strong exception guarantee。

状态关系可通过如下调用序列观测:

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() 范围内的闲置槽位只是原始存储,读取它没有对象语义。实现尾插时必须先在 last_ 完成 construct() 再递增 last_;若先推进指针再构造,构造函数一旦抛异常,clear() 会对未初始化内存误调析构。

为让修改路径共用同一套状态清理边界,先补齐私有清理工具与 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() 从尾指针向起点回退销毁,与扩容回滚已构造前段 [new_first, new_last) 的游标方向一致。
  • 统一空态:release_storage() 释放内存后将三指针统一清零,使析构路径与 moved-from 对象复用同一空状态不变量。

50.2 reserve、push_back、emplace_back 与 reallocate​

reserve() 的核心取舍在迁移性能与异常安全之间:借助 std::move_if_noexcept,当 T 具备不抛异常的移动构造时优先移动,若移动可能抛异常且拷贝构造可用则回退拷贝,确保失败时旧元素不被破坏。

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;
}

关键事实

reserve() 中三条顺序约束不可颠倒:

  1. new_last 仅在元素构造成功后递增,使 catch (...) 精确回滚 [new_first, new_last);
  2. 旧元素销毁与旧存储释放后置到迁移循环成功之后,失败时原三指针完整保留;
  3. 用当前 capacity() 释放旧存储并暂存 old_size 须早于覆写三指针,防止 deallocate() 误传新容量。

emplace_back() 先确保空间充足,再于 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));
}

扩容与尾插在不同分支上的异常保证及迭代器失效边界如下:

执行路径失败时 size() 与元素状态capacity() 变化旧 iterator / 引用有效性
reserve(n) 且 n <= capacity()不变(直接返回)不变全部有效
reserve(n) 迁移阶段构造抛异常保留原元素与 size()(新缓冲区已回滚释放)不变全部有效(未切换指针)
reserve(n) 重分配提交成功size() 不变,元素位于新地址增至 n全部失效(旧存储已释放)
emplace_back() 容量充足时构造失败size() 不变(last_ 未推进)不变全部有效
emplace_back() 扩容成功但新元素构造失败size() 不变已按 next_capacity() 增大全部失效(已触发重分配)

next_capacity() 采用倍增策略以保证多次尾插具有摊还常数复杂度;若频繁按 size() + 1 调用 reserve(),容量退化为线性增长并引发反复迁移。

50.3 erase、clear 与 destructor​

erase() 处理连续存储中的元素删除:将被删区间之后的元素逐一前移覆盖,再销毁末尾多出的旧元素并收缩 last_。std::vector::erase 规定删除点及其后的 iterator 与引用全部失效,并返回指向原后继元素新位置的 iterator。

单元素 erase() 要求 T 支持移动赋值;若移动赋值途中抛异常,本实现只提供 basic guarantee(容器仍可安全析构,但元素可能已被部分移动赋值):

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;
}

范围删除沿用相同思路,将 [last, end) 搬移到 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;
}

删除、清空与析构操作的状态差异汇总如下:

操作移动与销毁行为size() 与 capacity() 变化异常保证iterator / 引用失效范围
erase(pos)[pos + 1, last_) 前移覆盖,销毁旧尾元素size() 减 1,capacity() 不变Basic guaranteepos 及之后全部失效,[first_, pos) 仍有效
erase(first, last)[last, last_) 前移至 first,销毁尾部多余段size() 减 last - first,capacity() 不变Basic guaranteefirst 及之后全部失效,[first_, first) 仍有效
clear()destroy_range(first_, last_) 销毁全部元素size() 归 0,capacity() 保持noexcept(默认析构不抛)全部失效(地址未变但对象已销毁)
~vector()先 clear(),再按 capacity() 释放原始存储并置空对象生命周期结束noexcept不再存在可访问对象

边界与误区

注意

clear() 后存储地址虽未改变,但 [first_, last_) 内对象生命周期已结束,旧 iterator 依然失去解引用语义——地址未变不等同于对象存活。此外,traits::deallocate(alloc_, p, n) 的 n 必须严格匹配分配时的 capacity()。

50.4 copy / move constructor 与 assignment​

拷贝构造函数的目标是深拷贝:通过 traits::select_on_container_copy_construction 获取 allocator 并分配独立存储,逐个拷贝构造元素,失败时回滚销毁新对象并释放新存储。

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-and-swap 提供 strong exception guarantee:将失败点全部集中在构造临时副本 temp 阶段,成功后再交换内部状态并由 temp 析构释放旧资源(教学版 swap() 直接交换 alloc_,完整标准库还需遵循 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_);
}

移动构造函数直接偷取 other 的三指针并移动 alloc_,同时把 other 三指针置空以维持可析构、可再赋值的有效空态:

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;
}

移动赋值先调用 clear() 与 release_storage() 清理左侧已有资源,再接管右侧指针与 alloc_(教学版默认一起移动 allocator 且元素析构不抛异常;完整标准库还需判断 allocator propagation 与 allocator equality 以决定能否直接偷取缓冲区):

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;
}

四个特殊成员函数的核心差异对照如下:

成员函数存储所有权策略左侧旧资源处理异常安全 / noexcept 条件other 结束状态
vector(const vector&)分配独立缓冲并逐个拷贝构造无(新构造对象)失败时销毁已构造前缀并释放新缓冲保持不变
operator=(const vector&)构造临时副本后 swap()随临时对象 temp 析构释放Strong guarantee(失败于 temp 构造)保持不变
vector(vector&&)转移三指针与 alloc_无(新构造对象)noexcept(std::is_nothrow_move_constructible_v<Alloc>)三指针归零(可析构、可再赋值)
operator=(vector&&)偷取三指针并移动 alloc_先 clear() 再 release_storage()noexcept(std::is_nothrow_move_assignable_v<Alloc>)三指针归零(可析构、可再赋值)

边界与误区

注意

拷贝赋值与移动赋值都必须显式检查 this == &other。泛型代码中可能出现 v = std::move(v):若移动赋值省去自检直接调用 clear() 和 release_storage(),会把自身缓冲区销毁释放后再把已悬空或归零的指针赋回自己。

50.5 mini vector 验收检查点​

验收实现必须逐项验证以下六条可观测约束:

  1. 三指针状态不变量:任意 public 成员函数返回后,非空状态满足 first_ <= last_ <= cap_,空状态三指针全为 nullptr;clear() 后 size() == 0 且 capacity() 保持不变。
  2. 生命周期计数匹配:用带计数器的元素类型追踪 construct() 与 destroy() 次数;异常注入时,回滚销毁次数必须严格等于此前构造成功数。
  3. 扩容提交与失效边界:reserve() 迁移失败时,旧元素序列、size()、capacity() 与旧 iterator 全保留;迁移成功后 begin() 地址变更且旧 iterator 全部失效。
  4. 尾插两阶段边界:emplace_back() 必须在构造成功后才推进 last_;空间不足时若扩容已提交而新元素构造失败,允许 capacity() 增大且 size() 不变。
  5. 删除覆盖与容量保留:erase() 移动覆盖后缀并销毁末尾多余对象,删除点之前的 iterator 仍有效,删除点及其后失效,且 capacity() 保持原值。
  6. 拷贝独立与移动清源:拷贝后两对象 begin() 地址不同;移动后目标接管原地址、源对象进入三指针全空状态,且移动赋值需确认左侧旧资源已销毁并释放。

下面的最小测试同时覆盖状态(size()/capacity()/地址)、生命周期(Trace::alive)与元素语义三类证据:

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);
}

排查顺序

定位连续容器实现缺陷时按以下五步核对:

  1. 划出 [first_, last_) 已构造区间与 [last_, cap_) 原始存储区间;
  2. 确认当前操作是否申请新缓冲及提交指针的准确时机;
  3. 核对哪些槽位启动或结束了 T 的生命周期;
  4. 依据地址替换与对象销毁范围判定 iterator 失效集合;
  5. 检查异常分支是否成对执行 destroy 与匹配的 deallocate(p, old_cap)。

最小自检任务​

动手自检先独立判断

阅读下面代码,判断每一步之后 mini::vector<std::string> 的 size()、capacity() 关系、iterator 失效范围和对象生命周期变化(假设 reserve() 与 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();

本章知识点总结​

  • 三指针不变量

    非空状态下 first_ <= last_ <= cap_ 切分已构造区间 [first_, last_) 与原始存储 [last_, cap_),空状态则三指针归零或保持 first_ == last_ < cap_。

  • 生命周期分层

    allocate()/deallocate() 管理原始存储,construct()/destroy() 负责对象启停,释放存储前须逆序销毁元素并传入原 capacity()。

  • 扩容提交边界

    reserve() 借 std::move_if_noexcept 在新缓冲全量构造成功后,才销毁旧元素、释放旧存储并切换三指针以维持 strong exception guarantee。

  • 尾插与倍增策略

    emplace_back() 先在 last_ 构造成功再递增尾指针,扩容后新元素构造失败允许 capacity() 增长;倍增容量保证长期尾插的摊还常数复杂度。

  • 删除与清空边界

    erase() 移动赋值覆盖后缀并销毁末尾旧元素,clear() 销毁全部对象但保留缓冲,两者均保持 capacity() 不变。

  • 拷贝与移动语义

    拷贝通过独立分配和 copy-and-swap 隔离所有权;移动接管三指针并置空源对象,赋值操作须防 this == &other 并释放左侧旧资源。

  • 迭代器失效判定

    重分配使旧缓冲全部 iterator 失效;erase() 使删除点及其后失效;clear() 虽复用地址但因对象销毁而使全部旧 iterator 失效。