Chapter 10: Vector
核心问题与阅读主线
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 状态,依次核对三步:
- 生命周期:目标槽位是否落在
[begin, end)。 - 存储归属:
begin与cap是否整体换块(仅end移动时旧块保留)。 - 地址有效:旧 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) | 调整有效元素数 | 变为 n | n > 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"); // 复用已有容量
边界与误区
修改操作两个高频失误:
- 丢弃
erase(it)返回值:继续解引用或递增失效旧it属未定义行为。 - 误以为
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;
}
关键事实
异常回收两道边界:
allocate仅得原始存储,生命周期自construct成功开始。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 返回 | 迁移路径 | 迁移中途抛异常时旧存储状态 |
|---|---|---|---|
移动构造为 noexcept | T&& | 移动构造 | 迁移不抛异常,保住 strong guarantee |
移动可能抛出且可拷贝(RiskyMove) | const T& | 拷贝构造 | 旧元素未被改写,清理新块后保留旧态 |
| 仅可移动且移动可能抛出 | T&& | 移动构造 | 部分旧元素进入 moved-from 状态,强保证退化 |
提交点是强异常安全的分界:提交前仅回滚新缓冲,三指针原子切换至新块后才销毁旧元素并释放旧块:
排查顺序
在 libstdc++ / libc++ 中阅读 reserve、emplace_back 与 insert 时,按四信号追踪提交点:
- 原始分配:
allocate申请新块,旧块仍有效。 - 未初始化构造:
uninitialized/construct依次构造前缀、新元素与后缀。 - 清理 guard:异常时仅按已构造进度
destroy并deallocate新块。 - 指针提交:旧元素析构与旧块释放位于三指针切换之后。
10.5 iterator 失效、cache locality 与性能陷阱
vector 的 iterator、pointer 与 reference 失效仅源自底层换块或同块内元素位移:
| 操作 | 未重分配时失效范围 | 触发重分配时失效范围 |
|---|---|---|
只读操作([]、at、data) | 无失效 | 不触发重分配 |
reserve / shrink_to_fit | capacity() 未变则全部有效 | 旧块全部位置失效 |
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> 三类高频踩坑:
auto& r = flags[0]无法绑定代理右值,部分要求真实T&迭代器的泛型算法会受限或报错。- 同一 word 内多 bit 共享内存字,并发写相邻下标可能引起数据竞争。
- 省位空间可选
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。