Skip to main content

Chapter 10: Vector

核心问题与阅读主线

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

std::vector 在运行期动态扩缩容时维持连续数组布局:常数时间下标访问与摊还常数时间尾部追加。工程分析每次操作,核心在于追踪底层换块、对象生命周期、iterator / pointer / reference 失效与异常保护。

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

贯穿材料核心代码

本章以批量收集日志记录作贯穿场景:写入期尾部追加、偶发按时间戳中间插入、末尾交付连续内存给 C 接口写出,串联 size()、capacity() 与 data() 的状态变化。

#include <string>
#include <vector>

struct LogRecord {
LogRecord(long long ts, std::string msg)
: timestamp(ts), message(std::move(msg)) {}

long long timestamp;
std::string message;
};

void collect_logs(std::vector<LogRecord>& records) {
records.reserve(1024);
records.emplace_back(1001, "start");
records.emplace_back(1002, "connect");
records.insert(records.begin() + 1, LogRecord{10015, "late record"});
}

按 cppreference 的 std::vector 页面,普通 std::vector<T> 须连续存储;各 STL 实现虽在字段命名、压缩 pair 或 allocator 基类优化上不同,均可抽象为 begin、end、cap 三段边界。

10.1 vector 的连续存储模型与三指针状态​

vector 用三个边界指针划分“已构造对象”与“原始存储”两段区间:

// 教学简化结构,用于解释状态关系,非任何标准库真实源码。
template<class T, class Alloc>
struct vector_storage_shape {
T* begin; // 已分配存储起点,也是第一个已构造元素的位置
T* end; // 已构造元素末尾
T* cap; // 已分配存储末尾
Alloc alloc;
};
边界 / 接口状态表达式生命周期与访问约束
[begin, end)已构造区,size() == end - begin槽位内含合法 T,可用 []、iterator 或 data() 访问
[end, cap)未构造区,capacity() == cap - begin仅由 allocator 持有原始空间,严禁按 T 读写
empty()begin == end仅判有效元素数为 0,不代表未分配容量
data()返回 begin空容器可能返回 nullptr 或哨兵地址,仅 size() > 0 时可解引用

因元素连续存放,日志写出可直接交付 records.data() 与 records.size() 给 C 接口:

void write_records(const LogRecord* first, std::size_t count);

void flush(const std::vector<LogRecord>& records) {
if (!records.empty()) {
write_records(records.data(), records.size());
}
}

边界与误区

注意

data() 指针不自动保活:write_records 期间,records 须存活且禁止并发触发改变 capacity() 的操作(追加、插入、reserve、shrink_to_fit、扩容 resize),否则换块即悬垂。

三指针状态迁移:

核心判断

分析任一操作后的 vector 状态,依次核对三步:

  1. 生命周期:目标槽位是否落在 [begin, end)。
  2. 存储归属:begin 与 cap 是否整体换块(仅 end 移动时旧块保留)。
  3. 地址有效:旧 pointer / iterator 是否仍落在新块 [begin, end) 内。

10.2 reserve、resize 与 shrink_to_fit 的状态改变​

API核心目的size()capacity()生命周期动作失效条件
reserve(n)预留至少 n 槽位不变n > capacity() 时增长不构造新元素;扩容时迁移旧元素capacity() 增长时全失效
resize(n) / resize(n, v)调整有效元素数变为 nn > capacity() 时重分配;缩小常不变扩大构造新元素;缩小析构尾部仅重分配时全失效
shrink_to_fit()请求释放多余容量不变非强制请求,由实现决定若重分配则迁移旧元素仅 capacity() 实际变化时全失效

reserve 只扩展原始存储而不创建 LogRecord,未超当前 capacity() 时原地址不变:

std::vector<LogRecord> records;
records.reserve(1024); // size == 0, capacity >= 1024
records.emplace_back(1, "a");
records.emplace_back(2, "b");

const LogRecord* first = records.data();
records.reserve(1024); // capacity 未增长时,first 仍指向同一块存储
records.reserve(2048); // capacity 增长时,first 指向的旧存储失效

reserve 后槽位仍在未构造区 [end, cap),直接下标赋值属越界写入:

std::vector<int> values;
values.reserve(10);

// values[0] = 42; // 错误路径:size 仍为 0,位置 0 尚无有效 int 对象。
values.push_back(42); // 正确路径:先构造元素,再进入 [begin, end)。

边界与误区

注意

reserve 不构造对象:reserve(n) 后 size() 不变,须经 push_back、emplace_back、insert 或增大 resize 构造对象后方可读写。

resize(n) 对元素生命周期与类型约束有明确分界:

  • 缩容:从尾部逆序析构多余元素(如销毁 LogRecord 及其 std::string 成员)并通常保留容量。
  • 扩容:resize(n) 要求元素可值初始化,resize(n, v) 要求可拷贝构造;仅支持移动且无默认构造的类型无法调用扩大版 resize。
std::vector<std::string> names;
names.reserve(3);
names.push_back("alpha");
names.resize(3); // 构造两个空 string,size 变成 3
names.resize(1); // 销毁索引 1 和 2 的 string,capacity 通常仍为 3

struct Token {
Token(int id) : id(id) {}
Token(const Token&) = delete;
Token(Token&&) noexcept = default;
int id;
};

std::vector<Token> tokens;
tokens.emplace_back(1);
// tokens.resize(2); // Token 没有默认构造函数,扩大 resize 不满足构造条件。
tokens.emplace_back(2);

核心判断

容量管理顺序:先 reserve 已知上限(如 1024 条日志)合并分配,用 resize 改元素数,峰值回落后需减容再调 shrink_to_fit(),并以 capacity() 是否变化判断是否重取旧地址。

10.3 push_back、emplace_back、insert、erase 与 clear​

操作位置容量足够时行为容量不足时行为定位与复杂度
push_back(v)尾部从 v 拷贝/移动构造,end 后移重分配并迁移旧元素摊还 O(1)
emplace_back(args...)尾部在 end 原地构造,end 后移重分配并迁移旧元素摊还 O(1),省临时对象
insert(pos, v)中间后缀后移,构造/赋值新值,end 后移分配新块构造前缀、新值、后缀并提交线性 O(N),越靠前越慢
erase(pos) / erase(first, last)区间销毁区间,后缀前移,end 前移不重分配,capacity() 保持线性 O(N),返回新定位点
clear()全表销毁 [begin, end) 全部对象,end 归零不重分配,capacity() 常保持线性 O(N),容量可复用

emplace_back 虽省临时对象,但工程上先看容量:一旦触发重分配,迁移旧元素的开销远超单次构造差异:

std::vector<LogRecord> records;
records.reserve(2);

LogRecord first{1001, "start"};
records.push_back(first); // 从 first 拷贝构造末尾元素
records.emplace_back(1002, "connect"); // 用参数直接构造末尾元素

中间插入为保持下标连续,须将插入点之后的全部元素后移(如下例的 connect 与 done):

std::vector<LogRecord> records;
records.reserve(4);
records.emplace_back(1001, "start");
records.emplace_back(1002, "connect");
records.emplace_back(1003, "done");

records.insert(records.begin() + 1, LogRecord{10015, "late record"});

erase 与 clear 结束对象生命周期但保留底层容量;遍历删除须接收 erase 返回的新迭代器,而 clear() 后追加可直接复用容量:

std::vector<LogRecord> records = {
{1001, "start"},
{1002, "connect"},
{1003, "done"}
};

for (auto it = records.begin(); it != records.end(); ) {
if (it->message == "connect") {
it = records.erase(it); // 返回删除位置之后的新位置
} else {
++it;
}
}

std::vector<std::string> buffer;
buffer.reserve(1000);
buffer.push_back("one batch");
buffer.clear(); // size == 0,字符串对象已销毁
buffer.push_back("next batch"); // 复用已有容量

边界与误区

注意

修改操作两个高频失误:

  1. 丢弃 erase(it) 返回值:继续解引用或递增失效旧 it 属未定义行为。
  2. 误以为 clear() 归还内存:clear() 与 erase() 仅缩短 [begin, end),峰值 capacity() 仍驻留在容器中。

10.4 reallocate 路径:allocator、placement new、move / copy 与 move_if_noexcept​

重分配须用 std::allocator_traits<Alloc>::allocate 取得新存储、在新块构造等价元素,并在异常中途无损保留旧三指针:

// 教学简化代码,用于解释 reallocate 的阶段,省略增长策略和边界细节。
template<class T, class Alloc>
T* relocate_range(Alloc& alloc, T* old_begin, T* old_end, std::size_t new_capacity) {
T* new_begin = std::allocator_traits<Alloc>::allocate(alloc, new_capacity);
T* new_end = new_begin;

try {
for (T* p = old_begin; p != old_end; ++p, ++new_end) {
std::allocator_traits<Alloc>::construct(
alloc,
new_end,
std::move_if_noexcept(*p)
);
}
} catch (...) {
for (T* p = new_begin; p != new_end; ++p) {
std::allocator_traits<Alloc>::destroy(alloc, p);
}
std::allocator_traits<Alloc>::deallocate(alloc, new_begin, new_capacity);
throw;
}

return new_begin;
}

关键事实

异常回收两道边界:

  1. allocate 仅得原始存储,生命周期自 construct 成功开始。
  2. catch 只销毁新前缀 [new_begin, new_end) 并释放新块,旧存储完好无损。

cppreference 的 std::move_if_noexcept 页面 决定迁移择路:当移动可能抛出而类型可拷贝(如 RiskyMove)时退回拷贝,避免旧对象被部分掏空:

#include <type_traits>
#include <utility>
#include <vector>

struct RiskyMove {
RiskyMove() = default;
RiskyMove(const RiskyMove&) = default;
RiskyMove(RiskyMove&&) noexcept(false) {}
};

static_assert(std::is_copy_constructible_v<RiskyMove>);
static_assert(!std::is_nothrow_move_constructible_v<RiskyMove>);
元素移动与拷贝特征move_if_noexcept 返回迁移路径迁移中途抛异常时旧存储状态
移动构造为 noexceptT&&移动构造迁移不抛异常,保住 strong guarantee
移动可能抛出且可拷贝(RiskyMove)const T&拷贝构造旧元素未被改写,清理新块后保留旧态
仅可移动且移动可能抛出T&&移动构造部分旧元素进入 moved-from 状态,强保证退化

提交点是强异常安全的分界:提交前仅回滚新缓冲,三指针原子切换至新块后才销毁旧元素并释放旧块:

排查顺序

在 libstdc++ / libc++ 中阅读 reserve、emplace_back 与 insert 时,按四信号追踪提交点:

  1. 原始分配:allocate 申请新块,旧块仍有效。
  2. 未初始化构造:uninitialized / construct 依次构造前缀、新元素与后缀。
  3. 清理 guard:异常时仅按已构造进度 destroy 并 deallocate 新块。
  4. 指针提交:旧元素析构与旧块释放位于三指针切换之后。

10.5 iterator 失效、cache locality 与性能陷阱​

vector 的 iterator、pointer 与 reference 失效仅源自底层换块或同块内元素位移:

操作未重分配时失效范围触发重分配时失效范围
只读操作([]、at、data)无失效不触发重分配
reserve / shrink_to_fitcapacity() 未变则全部有效旧块全部位置失效
push_back / emplace_back旧元素有效;旧 end() 失效旧块全部位置失效
insert插入点及之后(含 end())失效旧块全部位置失效
erase被删位置及之后(含 end())失效不触发重分配
clear全部元素与 end() 失效不触发重分配

容量足够时尾部追加保住旧地址,但前部插入会改变原有元素的逻辑位置:

std::vector<int> values;
values.reserve(4);
values.push_back(1);
values.push_back(2);
values.push_back(3);

int* p0 = values.data();
auto it1 = values.begin() + 1;

values.push_back(4); // 容量足够,p0 仍指向同一块存储,it1 仍指向值 2
values.insert(values.begin(), 0); // 可能触发重分配;即使容量足够,it1 也不再代表原位置

前部修改后需追踪目标时,保存逻辑索引并显式修正比持 iterator 更稳;若需长期稳定引用,应配稳定 ID、外部索引表或节点容器:

std::vector<LogRecord> records = {
{1001, "start"},
{1002, "connect"},
{1003, "done"}
};

std::size_t index = 1;
records.insert(records.begin(), LogRecord{1000, "boot"});

LogRecord& original_connect = records[index + 1];

连续存储兼有性能收益与陷阱:

  • cache locality 收益:无链表指针与单元素分配元数据,利好 CPU 预取、顺序扫描、排序、二分与批量写出。
  • 线性移动与重复扩容陷阱:中间高频增删会搬移后缀;未提前 reserve 的持续追加会触发多次全量迁移。

“先收集、后读取”场景下,按 expected_count 一次 reserve 可将增长收敛为单次分配:

std::vector<LogRecord> build_records(std::size_t expected_count) {
std::vector<LogRecord> records;
records.reserve(expected_count);

for (std::size_t i = 0; i != expected_count; ++i) {
records.emplace_back(static_cast<long long>(i), "record");
}
return records;
}

关键事实

expected_count 显著高估会闲置 [end, cap) 内存,显著低估仍会退回增长重分配;选型须权衡数据规模、峰值内存与插入位置分布。

10.6 vector<bool> Specialization Boundary and Mini Vector Checkpoint​

cppreference 的 std::vector<bool> 页面 指明该特化常采用 bit-level 压缩(1 bit/元素,实现定义),在存储布局与引用语义上与普通 std::vector<T> 截然不同:

对比维度普通 std::vector<T>std::vector<bool> 特化std::vector<std::uint8_t> / unsigned char
底层表示连续 T 对象数组按 bit 压缩打包进 word连续单字节元素数组
operator[]返回真实 T&返回代理对象(如 reference)返回真实字节左值引用
C 接口交付data() 交付 T*无 bool* 连续数组表示data() 直接交付字节指针
适用场景通用连续对象容器动态 bitset 风格空间压缩需真实引用、元素并发或 C 互操作

下标访问 std::vector<bool> 返回持有 word 与 bit mask 的代理对象,而非 bool&:

std::vector<bool> flags = {true, false, true};
auto ref = flags[0]; // 通常是代理对象,表示某个 word 中的一位
ref = false;

bool value = flags[1]; // 转换成普通 bool 值

边界与误区

注意

vector<bool> 三类高频踩坑:

  1. auto& r = flags[0] 无法绑定代理右值,部分要求真实 T& 迭代器的泛型算法会受限或报错。
  2. 同一 word 内多 bit 共享内存字,并发写相邻下标可能引起数据竞争。
  3. 省位空间可选 vector<bool>、std::bitset 或第三方 dynamic bitset;需 bool* 布局或真实引用时应改用 std::vector<unsigned char>、std::vector<std::uint8_t> 或枚举字节存储。

教学版 mini_vector<T> 收敛了本章五项核心不变量:三指针一致、allocator 管原始存储、construct/destroy 管对象生命周期、重分配先构造再提交、修改维护有效定位:

// 教学简化代码,只展示不变量和关键动作,省略 allocator propagation 等完整标准库细节。
template<class T, class Alloc = std::allocator<T>>
class mini_vector {
public:
mini_vector() = default;

~mini_vector() {
destroy_range(begin_, end_);
if (begin_) {
std::allocator_traits<Alloc>::deallocate(alloc_, begin_, capacity());
}
}

std::size_t size() const { return static_cast<std::size_t>(end_ - begin_); }
std::size_t capacity() const { return static_cast<std::size_t>(cap_ - begin_); }
T* data() { return begin_; }
const T* data() const { return begin_; }

template<class... Args>
T& emplace_back(Args&&... args) {
if (end_ == cap_) {
grow_for_one_more();
}
std::allocator_traits<Alloc>::construct(
alloc_,
end_,
std::forward<Args>(args)...
);
++end_;
return *(end_ - 1);
}

private:
void destroy_range(T* first, T* last) {
while (last != first) {
--last;
std::allocator_traits<Alloc>::destroy(alloc_, last);
}
}

void grow_for_one_more() {
std::size_t old_size = size();
std::size_t old_capacity = capacity();
std::size_t new_capacity = old_capacity == 0 ? 1 : old_capacity * 2;
T* new_begin = std::allocator_traits<Alloc>::allocate(alloc_, new_capacity);
T* new_end = new_begin;

try {
for (T* p = begin_; p != end_; ++p, ++new_end) {
std::allocator_traits<Alloc>::construct(
alloc_,
new_end,
std::move_if_noexcept(*p)
);
}
} catch (...) {
destroy_range(new_begin, new_end);
std::allocator_traits<Alloc>::deallocate(alloc_, new_begin, new_capacity);
throw;
}

destroy_range(begin_, end_);
if (begin_) {
std::allocator_traits<Alloc>::deallocate(alloc_, begin_, old_capacity);
}
begin_ = new_begin;
end_ = new_begin + old_size;
cap_ = new_begin + new_capacity;
}

Alloc alloc_{};
T* begin_ = nullptr;
T* end_ = nullptr;
T* cap_ = nullptr;
};

关键事实

mini_vector 演示了扩容三锚点:allocate 仅配 construct 激活对象、失败只清理新前缀不伤旧态、提交三指针后再回收旧块;完整 STL 另含 allocator propagation、异常规格、范围插入、erase、swap、constexpr 与调试 iterator。

最小自检任务​

动手自检先独立判断

判断各注释点之后的 size()、capacity()、对象生命周期与迭代器状态(假设 reserve(3) 后容量正好为 3,插入第 4 个元素时触发重分配):

#include <string>
#include <vector>

struct Item {
std::string name;
};

int main() {
std::vector<Item> items;
items.reserve(3); // A
items.emplace_back(Item{"one"}); // B
items.emplace_back(Item{"two"}); // C

auto first = items.begin();
auto second = items.begin() + 1;

items.insert(items.begin() + 1, Item{"middle"}); // D
items.emplace_back(Item{"four"}); // E
items.erase(items.begin()); // F
items.clear(); // G
}

本章知识点总结​

  • 三指针连续模型

    普通 std::vector<T> 以 [begin, end) 存有效对象、以 [end, cap) 持原始存储,size()、capacity() 与 data() 均由此导出。

  • 容量控制三分法

    reserve 仅保最小原始容量;resize 同步改 size() 与对象生命周期;shrink_to_fit 为非强制请求,按 capacity() 实际变化判失效。

  • 修改与定位更新

    push_back / emplace_back 容量足时只移 end;insert / erase 移动后缀并使操作点及之后失效;clear 销毁对象但保留容量。

  • 重分配与异常提交点

    先 allocate 新块并用 std::move_if_noexcept(noexcept 移动或不可拷贝时移动,否则拷贝)迁移,失败按已构造前缀回滚,提交三指针后再回收旧块。

  • iterator 失效边界

    换块使旧块全部位置失效;同块增删使操作点及之后失效,跨修改追踪宜改用逻辑索引或稳定 ID。

  • 局部性与性能权衡

    连续存储兼有优异 cache locality 与 O(1) 随机访问,但中间高频增删与未 reserve 的反复扩容会放大线性迁移开销。

  • vector<bool> 特化边界

    std::vector<bool> 常以 bit 压缩存储并返回代理 reference,无 bool* 连续数组模型;需真实引用、元素并发或 C 交付时应改用 std::vector<std::uint8_t> / unsigned char。