一个清理任务,遍历 vector<Item>,把超过七天没访问的条目删掉。写的人用迭代器跑循环,命中就 erase。测试环境跑了几十次都正常,上线后每天偶尔崩一次,退出码 -1073741819,日志里一个字都没有。把线上数据导回本地,又复现不了。

同一个项目里还有一处:为了少拷贝,某个模块保存了容器里一个元素的 const 引用。后来队列又 push_back 了几条,再拿那个引用去读,得到一个空字符串。没崩,只是数据不对。

两件事的共同点:容器在背后重新安排了内存,代码手里还攥着旧位置。这篇讲清容器怎么选、迭代器什么时候失效、比较器怎么写才不炸,以及 remove 之后为什么没删掉。

本文按 C++20 写。示例在本机 Windows + MinGW g++ 16.2.0 上实际编译运行过,命令和输出照抄可用。未验证的部分会单独标注。

现象:删元素删出了错

先把那段清理逻辑缩成最小例子:把 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:一整块连续内存,装满了就另找一块更大的,把元素搬过去
deque:分段连续,若干固定大小的块加一张索引表,两头都能长
list:每个元素一个节点,前后各一个指针,节点散落在堆上
map / set:红黑树,每个元素一个节点,按 key 排好序
unordered_map:哈希桶加节点,按哈希值分散,桶不够就整体 rehash

「连续」比复杂度更重要。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_map rehash 要重建整张桶表,延迟敏感的服务得提前 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,以及智能指针也解决不了的悬垂引用。