一个清理任务,遍历 vector<Item>,把超过七天没访问的条目删掉。写的人用迭代器跑循环,命中就 erase。测试环境跑了几十次都正常,上线后每天偶尔崩一次,退出码 -1073741819,日志里一个字都没有。把线上数据导回本地,又复现不了。
同一个项目里还有一处:为了少拷贝,某个模块保存了容器里一个元素的 const 引用。后来队列又 push_back 了几条,再拿那个引用去读,得到一个空字符串。没崩,只是数据不对。
两件事的共同点:容器在背后重新安排了内存,代码手里还攥着旧位置。这篇讲清容器怎么选、迭代器什么时候失效、比较器怎么写才不炸,以及 remove 之后为什么没删掉。
现象:删元素删出了错
先把那段清理逻辑缩成最小例子:把 vector 里所有的 2 删掉。
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 2, 3, 2, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it == 2) v.erase(it); // 这里已经出事了
}
for (int x : v) std::cout << x << ' ';
std::cout << "\n";
}
编译运行(本机实测):
g++ -std=c++20 -Wall -Wextra erase_demo.cpp -o erase_demo.exe
.\erase_demo.exe
1 2 3 4
结果还留着一个 2,3 后面那个 2 也没了。它没崩,退出码还是 0,测试很容易放过。原因是 erase 把被删位置之后的元素整体前移一格,返回下一个位置;传进去的 it 此刻已经失效,它指向的格子是原来下一个元素,循环末尾再 ++it,又跳过了一个。紧挨着的重复值就这么漏掉了。
从第一次 erase 起,这段代码就是未定义行为(UB):标准不再规定发生什么,可能少删、多删、读到已释放的内存,也可能看起来完全正常。所以别拿「本机输出是 1 2 3 4」当结论,那只是一次巧合。
正确写法是把返回值接回来,没删的时候才前进:
for (auto it = v.begin(); it != v.end();) {
if (*it == 2) it = v.erase(it); // erase 返回下一个有效位置
else ++it;
}
批量删除推荐用后文的 remove-erase。先记住一条规则:遍历中改动容器结构,必须重新拿迭代器。list 的 erase 也返回下一个位置,区别是只让被删的那个失效,其他元素不受影响。
容器怎么选:先看内存怎么摆
选容器先想三件事:数据量多大、是随机读还是顺序扫、插入删除发生在哪。复杂度只描述增长趋势,缓存命中率和常数才决定实际快慢。
「连续」比复杂度更重要。vector 的相邻元素挨在一起,顺序遍历几乎每次都能命中缓存;list 的节点是逐个 new 出来的,地址东一块西一块,每跳都可能缓存缺失。所以元素不大、几万条以内时,哪怕要在中间插入,vector 的整体表现也常不输 list:搬移是连续内存的 memmove,比链表逐个分配节点快。别凭直觉,拿真实数据测。
| 容器 | 内存与随机访问 | 插入删除 | 查找 | 适合的场景 |
|---|---|---|---|---|
vector | 连续内存,下标 O(1) | 尾部均摊 O(1),中间 O(n) | 无序,线性 O(n) | 默认选择 |
deque | 分段连续,下标 O(1) | 两头 O(1),中间 O(n) | 线性 O(n) | 两头频繁进出 |
list | 节点散落,只能顺序走 | 已知位置 O(1),定位 O(n) | 线性 O(n) | 迭代器要长期稳定、频繁 splice |
map / set | 红黑树,按 key 有序 | O(log n) | O(log n),可查区间 | 有序遍历、范围查询 |
unordered_map | 哈希桶加节点,无序 | 平均 O(1) | 平均 O(1),最坏 O(n) | 只按 key 存取 |
选择顺序:默认 vector;两头进出用 deque;只按 key 取用用 unordered_map;要范围查询用 map/set;只有「元素地址必须稳定」是硬需求时才用 list。
unordered_map 最坏是 O(n),哈希差或被构造碰撞会退化成链表;map 的常数不小,几万条以内有时不如排序 vector 加二分。「O(1) 一定比 O(log n) 快」是错的。
capacity 与 reserve:扩容到底发生了什么
size() 是现在装了几个元素,capacity() 是不重新分配的情况下最多能装几个。两者之间那段空间已经分配但还没构造元素,不能直接访问。撞上容量上限时,容器会申请更大的内存、把元素搬过去、释放旧块;指向旧元素的指针、引用、迭代器全部失效——这正解释了开头「引用读出空串」的现象。
扩容一般不是每次加一个,否则每次 push_back 都要搬。本机 libstdc++ 实测的容量序列:
size=0 cap=0
size=1 cap=1
size=2 cap=2
size=3 cap=4
size=5 cap=8
size=9 cap=16
size=17 cap=32
size=33 cap=64
翻倍让「n 次 push_back 的总搬移量」摊到每次是常数,这就是均摊 O(1) 的来源。代价是峰值内存可能接近用量一倍,扩容那一下有明显停顿,延迟敏感的线程要单独处理。
大概知道要装多少条,可以用 reserve(n) 一次性留够,省掉中间几次搬移:
std::vector<LogLine> lines;
lines.reserve(100000); // 只改 capacity,不改 size
for (...) lines.push_back(...);
几个必须记住的细节:reserve 只增不减,传比当前容量小的值什么都不会发生;shrink_to_fit() 只是「请求」释放多余容量,标准不保证实现照做;reserve 不构造元素,lines[0] 依然越界;resize(n) 才真的构造出 n 个元素。两者别混。
reserve 不是越多越好。预留 100 万、实际只用 10 条,那块内存会一直占着,RSS 不会因为你只用了 10 条就下降。另外 unordered_map::reserve 的单位是桶数,作用是把 rehash 提前做掉,和 vector 的容量不是一回事。迭代器是什么,什么时候失效
迭代器是「容器里某个位置」的抽象,不是指针的别名。begin() 指第一个元素,end() 指最后一个元素的再后面,所以 end 不能解引用。
能力分四档:输入、前向、双向、随机访问。vector 和 deque 是随机访问,list、map、set 是双向,unordered_map 是前向。std::sort 要求随机访问,list 得用成员 sort();std::find 只要求前向,但对 map 是白瞎树结构。
| 操作 | 谁失效 | 说明 |
|---|---|---|
vector 的 push_back 触发扩容 | 全部迭代器、指针、引用 | 元素被搬到新内存,旧地址整体作废 |
vector 的 reserve、resize 导致扩容 | 全部迭代器、指针、引用 | 只改 size 不扩容时不失效 |
vector 的 erase(p) | p 及其后的所有迭代器 | 后面的元素整体前移,end 也变了 |
vector 的 insert(p, x) | p 及其后;若扩容则全部 | 插入点之后的元素位置都变了 |
deque 的两端插入 | 全部迭代器 | 元素的指针和引用仍有效,这点和 vector 不同 |
list / map / set 的 erase(p) | 只有 p | 其他节点地址不变,这是节点式容器的价值 |
unordered_map 插入触发 rehash | 全部迭代器 | 元素指针和引用仍有效,桶的顺序变了 |
第二列写的是「迭代器、指针、引用」,不只是迭代器。很多人知道迭代器会失效,却忘了自己存的是 const Item& 或 Item*。判断很简单:只要容器可能重新分配内存,任何指向元素的地址型句柄都不能跨过这次操作。
失效不等于立刻崩:可能读到旧值、空串,也可能访问违例。这类 bug 在测试环境很难复现,只能靠规则提前避免。
完整走查:从一堆访问日志到 Top 3
把上面这些拼成一个能跑的小工具。需求:每行格式为 METHOD PATH MS,输出总耗时,以及总耗时最高的三个接口各自的调用次数和平均耗时;调用次数少于两次的接口不展示。
#include <algorithm>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <string_view>
#include <unordered_map>
#include <vector>
struct LogLine {
std::string path;
int ms;
};
struct Stat {
std::string path;
int calls = 0;
long long total_ms = 0;
};
std::vector<LogLine> readLines(std::istream& in) {
std::vector<LogLine> out;
std::string line;
while (std::getline(in, line)) {
std::istringstream iss(line);
std::string method, path;
int ms = 0;
if (!(iss >> method >> path >> ms)) continue;
out.push_back(LogLine{path, ms});
}
return out;
}
int main() {
auto lines = readLines(std::cin);
std::unordered_map<std::string, Stat> agg;
agg.reserve(lines.size() / 2);
for (const auto& l : lines) {
auto& s = agg[l.path];
if (s.path.empty()) s.path = l.path;
s.calls += 1;
s.total_ms += l.ms;
}
std::vector<Stat> rows;
rows.reserve(agg.size());
for (const auto& [k, v] : agg) rows.push_back(v);
rows.erase(std::remove_if(rows.begin(), rows.end(),
[](const Stat& s) { return s.calls < 2; }),
rows.end());
std::sort(rows.begin(), rows.end(), [](const Stat& a, const Stat& b) {
if (a.total_ms != b.total_ms) return a.total_ms > b.total_ms;
return a.path < b.path;
});
long long all_ms = std::accumulate(
lines.begin(), lines.end(), 0LL,
[](long long acc, const LogLine& l) { return acc + l.ms; });
std::cout << "lines=" << lines.size() << " total_ms=" << all_ms << "\n";
int shown = 0;
for (const auto& r : rows) {
if (shown++ == 3) break;
std::cout << r.path << " calls=" << r.calls
<< " total=" << r.total_ms
<< " avg=" << (r.total_ms / r.calls) << "\n";
}
}
输入文件 input.txt 的内容:
GET /api/users 12
GET /api/users 30
GET /api/orders 45
POST /api/orders 80
GET /api/users 6
GET /health 1
GET /api/orders 20
POST /api/orders 55
GET /metrics 3
GET /api/users 9
GET /health 2
编译并运行(Windows PowerShell,本机实测):
g++ -std=c++20 -Wall -Wextra stl_demo.cpp -o stl_demo.exe
Get-Content input.txt | .\stl_demo.exe
lines=11 total_ms=263
/api/orders calls=4 total=200 avg=50
/api/users calls=4 total=57 avg=14
/health calls=2 total=3 avg=1
几个关键决定:
readLines返回vector,因为后面要整体遍历两次,连续内存最省事;返回时是移动。- 聚合用
unordered_map,只按 path 取值、不需要顺序;reserve按「接口数少于日志行数一半」估,估不准最多多一次 rehash。 - 哈希容器不能直接按值排序,先搬进
vector<Stat>再排,搬之前reserve。 remove_if过滤低频接口,配合erase缩短容器。sort先比总耗时再比 path,让相等行有确定顺序,方便回归测试。accumulate初始值写0LL而不是0。0是int,几十万条日志的毫秒数很容易溢出。
输出 total_ms=263 是 11 行相加;/metrics 一次调用被过滤;/health 两次 3 毫秒排第三。平均用整数除法,3/2 得 1,要小数换 double。
算法与 lambda:把循环写成意图
<algorithm> 里的算法只认迭代器区间,不认具体容器。同一段 find_if 能作用在 vector、list、deque 上,只要迭代器类别够用。
std::find是线性查找,返回迭代器,找不到返回e。对map/set/unordered_map要用成员find(key),否则把 O(log n) 或 O(1) 变成 O(n)。find_if按条件找第一个,count_if数个数,any_of找到就能提前退出。sort要求随机访问,不稳定;需要保持相等元素的顺序用stable_sort,代价是额外内存。accumulate的初始值类型决定结果类型,前面已经踩过一次。
lambda 是这些算法的胶水。它本质是匿名的函数对象,[] 是捕获列表:[&] 按引用捕获用到的变量,[=] 按值捕获,[x] 只捕获 x。无捕获的 lambda 可以退化成普通函数指针,不占额外空间,排序比较器一般就这么写。捕获引用要小心:lambda 被存起来、过一会儿再调用,而局部变量已经出了作用域,那就是悬垂引用,下一篇专门讲。
自定义比较器:严格弱序不是学术名词
sort 不要求你给出完整顺序,只要求比较器描述一个严格弱序。翻成大白话三条:comp(a, a) 必须返回 false;comp(a, b) 和 comp(b, a) 不能同时为真;比较关系要能传递。
写成 return a.ms <= b.ms; 就违反了第一条:两个耗时相同的任务互相比较都返回 true,排序内部会认为「a 在 b 前」同时「b 在 a 前」,分区逻辑自相矛盾,接下来发生什么标准不管。
本机实测两种情况:64 条数据时程序正常退出,输出 sorted, first=0 last=22 size=64,看起来一切正常;加到 20 万条,同一个比较器直接以 -1073741819(0xC0000005,访问违例)结束,屏幕上没有任何输出。
正确写法是给出真正的全序,至少加一个唯一的 tie-break:
std::sort(rows.begin(), rows.end(), [](const Stat& a, const Stat& b) {
if (a.total_ms != b.total_ms) return a.total_ms > b.total_ms;
return a.path < b.path; // 相等时按 path 定序
});
其他常见错误:用 return a.ms - b.ms; 当布尔值,大数相减会溢出,符号一变顺序就乱;浮点里有 NaN 时任何比较都返回 false,等价关系不传递;比较器里读外部可变状态,每次调用结果不同,排序直接失去依据。
std::is_sorted 只能检查结果有没有序,检查不了比较器本身——错误的比较器也可能碰巧排出有序结果。MSVC 的 debug 版会直接报 invalid comparator,本机 MinGW 没有这个断言,未实测。
remove-erase:为什么 remove 之后没删掉
先看一段会让人误会的代码:
std::vector<int> v{2, 7, 2, 9, 2, 5};
auto newEnd = std::remove(v.begin(), v.end(), 2);
std::cout << "after remove: size=" << v.size()
<< " live=" << (newEnd - v.begin()) << " bytes=";
for (int x : v) std::cout << x << ' ';
std::cout << "\n";
v.erase(newEnd, v.end());
std::cout << "after erase: size=" << v.size() << " bytes=";
for (int x : v) std::cout << x << ' ';
std::cout << "\n";
std::vector<int> w{2, 7, 2, 9, 2, 5};
std::size_t n = std::erase(w, 2);
std::cout << "std::erase removes " << n << ", size=" << w.size() << "\n";
本机输出:
after remove: size=6 live=3 bytes=7 9 5 9 2 5
after erase: size=3 bytes=7 9 5
std::erase removes 3, size=3
remove 只做一件事:把要保留的元素依次往前挪,返回新的逻辑结尾。它拿不到容器本身,所以既不能改 size,也不能释放内存。执行完前三个位置是 7 9 5,后面三个是搬移留下的残值 9 2 5,仍然是被构造过的对象。所以只调 remove 不调 erase,等于没删。
erase(newEnd, v.end()) 才真正析构尾部、把 size 改成 3。C++20 给了更省事的 std::erase(v, value) 和 std::erase_if(v, pred),一步完成「挪 + 删」,还返回删除个数;本机实测 std::erase(w, 2) 返回 3。
性能上 remove_if 对每个保留元素做一次移动赋值,整体 O(n),并不比手写循环差,而且不容易写错失效逻辑。限制也要知道:list 应该用成员 remove/remove_if,它只摘链节点;map/set 没有这套,按 key 或迭代器删。
string_view 与 ranges:省一次拷贝,换一份责任
std::string_view 是「指针加长度」的只读视图,不拥有字符内存。它最大的价值在函数参数上:
void logIt(std::string_view sv); // 字面量、std::string、char* 都不拷贝
参数写成 const std::string&,传字面量会临时构造 std::string,多一次分配;写成 std::string 更是整份拷贝。string_view 没这些开销,size()、substr()、遍历照常可用。
代价是它不延长被看那块内存的寿命。函数内部用完就扔没问题;一旦存进成员、塞进容器、或者从函数返回,就必须确认底层字符串还活着。build() 返回一个临时 std::string,用它的内容构造 view,函数返回后临时对象销毁,view 就悬空了。本机实测这段代码打印出 view size=45 first=x——长度和首字符都还「正常」,因为内存还没被覆盖。下一次内存被复用就是乱码或崩溃。
实用规则:参数用 string_view,只在函数执行期间使用;要保存就在入口转成 std::string;别假定 data() 以 '\0' 结尾;substr 返回的仍是 view,底层 buffer 照样要盯着。
C++20 的 ranges 把「容器 + 算法」换成「范围 + 视图」:
auto out = nums | std::views::filter([](int n) { return n % 2 == 0; })
| std::views::transform([](int n) { return n * n; });
for (int n : out) std::cout << n << ' ';
本机 GCC 16.2.0 实测可编译运行,输入 {3, 8, 1, 6, 9, 2} 输出 64 36 4。更复杂的 ranges 设施没有逐项验证,标为待确认。要注意视图是惰性的,不复制数据,所以底层容器必须活得比视图长;返回一个指向局部容器的 view,和返回悬垂 string_view 是同一类错误。
现象、真实原因、第一步查什么
STL 的问题大多不带明确报错,靠猜很费时间。下面这张表按「看到什么」反推,先把方向定下来再动代码。
| 你看到的现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 遍历时删元素,结果少删或多删,偶尔崩 | erase/insert 让迭代器失效,循环还在用它 | 看循环里有没有改结构;改成 it = v.erase(it),或用 remove-erase |
| 扩容后,之前保存的指针或引用读出空串、乱码 | 元素被搬到新内存,旧地址作废 | 搜 push_back 之前保存的 T*、T&;换下标或不要跨扩容使用 |
sort 偶发崩溃,或排完顺序仍然不对 | 比较器不满足严格弱序 | 查是否用了 <=、减法、对 NaN 或外部状态做比较;补 tie-break |
map 查找慢得离谱 | 用了 std::find 而不是成员 find | 搜落在 map/set 上的 std::find( 调用 |
只调了 remove,容器 size() 没变 | remove 只挪元素,不删元素 | 补 erase(newEnd, end()),或改用 C++20 的 std::erase |
string_view 内容为空、乱码或指向已释放内存 | 底层字符串生命周期结束,view 悬垂 | 查来源是不是临时对象;要存就转成 std::string |
表里第一条最值得先看,它的现场最像「代码没问题」:没有报错、输出大部分正确、退出码还可能是 0。凡是「遍历中改容器」的代码,都值得停一下,确认自己接住了返回的迭代器。
边界与代价:STL 管住了什么,没管住什么
STL 把数据结构和算法标准化了,写出来的代码别人看得懂,不用自己维护链表和红黑树。但它不是免费,也不是万能的。
- 抽象有成本。
vector扩容要搬移全部元素,一次插入的停顿可能到毫秒级;unordered_maprehash 要重建整张桶表,延迟敏感的服务得提前reserve。 - 内存开销不只看元素大小。
list每个节点两个指针,加上分配器元数据;map的红黑树节点同样如此;unordered_map的桶数组可能比元素本身还大。同样一万条数据,不同容器差几倍内存很正常。 - 迭代器规则多,失效后的表现不可预测。记不住就保守:只要改了结构,就重新
begin(),不要复用旧迭代器或旧引用。 - 模板的编译期代价。每个组合实例化一份代码,编译变慢、报错变长;一个类型写错,可能吐出上百行展开,有用的往往是最前面那行。
- 容器本身不是线程安全的。多线程同时读没事,只要有一个在写就得自己加锁;标准库没有并发容器。
这些代价换来的是「不用自己写数据结构」和「别人一眼看懂」。真正要避免的不是用 STL,而是用错了怪语言。
当天能验证的练习
下面几条都能在本机直接跑。
- 编译运行第一段错误删除程序,确认输出
1 2 3 4;改成it = v.erase(it)对比。再换成{2, 2, 2, 2},看错误版本输出变不变——会变,这就是 UB 不可依赖的证据。 - 循环
push_back到 33 个元素,打印每次capacity变化;再在开头加reserve(33),观察容量序列。 - 用
<=写比较器,分别用 64 条和 20 万条数据排序,记录退出码。本机 64 条正常结束,20 万条以-1073741819退出且没有输出;改回严格弱序再跑一遍。 - 跑
remove示例,先只调remove打印size和内容,确认尾部有残值;再补erase,然后用std::erase重写。 - 把 Top 3 程序改成从命令行参数读文件名,用
string_view做参数;再写一个返回string_view的函数指向局部std::string,观察输出。记住「看起来正常」不代表正确。
小结
记住三件事:默认用 vector,需要有序 key 用 map/set,需要平均 O(1) 查找用 unordered_map;只要容器可能重新分配内存,任何指向元素的迭代器、指针、引用都不能跨过这次操作;sort 的比较器必须满足严格弱序,写 <= 是在赌数据量。
容器把元素放在一起,也把「谁在什么时候释放」推给下一层:vector 析构时释放自己的内存,元素内部的堆资源则要靠元素自己的析构函数收尾。下一篇讲这层:栈、堆、静态存储的区别,为什么默认用 unique_ptr,shared_ptr 的引用计数为什么停在 2,以及智能指针也解决不了的悬垂引用。