std::vector 性能与容器失效规则
std::vector 是 C++ 里使用频率最高的容器，也是最容易被"随手用错"的容器。它的行为规则非常确定：连续内存、按系数扩容、扩容即失效。理解这三条，性能问题就解决大半。
一、内存布局与扩容机制
vector 内部三个指针：begin、end（已用末尾）、cap（容量末尾）。size() 与 capacity() 分离是它所有性能特性的来源。
扩容时（push_back 超出容量）：
- 申请一块更大的连续内存（常见实现为 1.5 倍或 2 倍）；
- 把旧元素移动或拷贝到新内存；
- 销毁旧元素、释放旧内存。
因此"多次 push_back 到 n 个元素"的总拷贝量是 O(n)，均摊 O(1) 每次。但若元素移动构造不是 noexcept，扩容会退化为拷贝——这是自定义类型必须标 noexcept 的直接原因。
二、reserve 的正确用法
std::vector<int> v;
v.reserve(1000); // 只改容量，不改 size
for (int i = 0; i < 1000; ++i) v.push_back(i);
注意区别：
| 操作 | 影响 size | 影响 capacity | 说明 |
|---|---|---|---|
reserve(n) | 不变 | 至少 n | 只预留，元素未构造 |
resize(n) | 变为 n | 至少 n | 构造/销毁元素 |
shrink_to_fit() | 不变 | 收缩到 size | 请求式，不保证 |
clear() | 变 0 | 不变 | 元素析构，容量保留 |
常见误用：用 resize 代替 reserve 再下标赋值，会多一次默认构造。除非确实需要默认值，否则 reserve + push_back/emplace_back 更清晰。
三、迭代器与引用失效规则
| 操作 | 失效范围 |
|---|---|
push_back 未扩容 | 仅 end() 失效 |
push_back 触发扩容 | 全部迭代器、指针、引用失效 |
insert 中间位置 | 插入点之后全部失效 |
erase 中间位置 | 删除点之后全部失效 |
reserve / shrink_to_fit | 可能全部失效 |
clear | 全部失效 |
典型崩溃：
std::vector<int> v{1,2,3};
int& r = v[0];
v.push_back(4); // 可能扩容
r = 10; // ❌ r 可能指向已释放内存
安全写法：扩容之后再取引用，或者提前 reserve 足够容量。
四、删除元素的正确姿势
技巧 1：swap-and-pop（不保序，O(1)）
std::size_t i = 3;
v[i] = std::move(v.back());
v.pop_back();
适合元素顺序不重要的场景，是大容器删除单个元素的性能首选。
技巧 2：remove-erase 惯用法（保序）
v.erase(std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; }),
v.end());
std::remove_if 并不删除，只是把保留元素前移并返回新逻辑末尾，erase 才真正缩短 size。
C++20 可以直接 std::erase_if(v, pred)。
五、减少拷贝与临时对象
// ❌ 临时对象 + 拷贝
v.push_back(std::string("hello"));
// ✅ 就地构造
v.emplace_back("hello");
// ❌ 构造后拷贝
std::vector<Foo> foos;
Foo f(1, 2);
foos.push_back(f);
// ✅ 移动
foos.push_back(std::move(f));
注意 emplace_back 并非永远更好：它接受任意参数并做重载决议，传入已有对象时可能选中 explicit 构造造成意外。传已有对象时优先 push_back。
六、批量插入与拼接
std::vector<int> a{1,2,3}, b{4,5,6};
a.insert(a.end(), b.begin(), b.end()); // 一次性插入，比循环 push_back 快
// 避免重复扩容
a.reserve(a.size() + b.size());
七、vector<bool> 的特殊性
std::vector<bool> 是标准里唯一被特化的容器：元素按位打包，operator[] 返回代理对象而非 bool&。
std::vector<bool> vb(8, true);
bool& r = vb[0]; // ❌ 编译失败，不能绑定代理到 bool&
auto v = vb[0]; // 得到代理对象，不是 bool
替代方案：
- 需要真实引用：
std::vector<char>或std::deque<bool>； - 需要位级压缩：保留
vector<bool>，但取元素时显式转bool； - C++20 可用
std::bitset（定长）或第三方dynamic_bitset。
八、容量控制与内存释放
std::vector<Foo> v(10000);
// ... 使用后只剩少量数据
v.shrink_to_fit(); // 请求收缩（不保证）
std::vector<Foo>().swap(v); // C++98 惯用法，强制释放
反复"清空再填满"的场景不要每次都释放容量，保留容量反而更好；只有大批量数据用完、容器长期空闲时才收缩。
九、性能检查清单
- 循环
push_back前是否reserve？ - 元素类型是否小于等于两个指针宽？按值传递可能更快。
- 是否在循环里用
v.size()反复判断（多数编译器会优化，但用const std::size_t n = v.size()更明确）？ - 自定义类型是否定义了
noexcept移动构造？ - 是否在内层循环里创建临时
vector（考虑移到外层 +clear()复用）？ - 是否使用了
vector<vector<T>>存储稀疏二维数据（考虑扁平化到一维）？
vector 的规则很简单，难的是把规则变成手感：能 reserve 就 reserve，扩容后不摸旧引用，删除大容器元素考虑 swap-and-pop。