前言vector、stack、queue是 C 标准库中最常用的三个容器名字但它们的身份并不相同。std::vector是序列容器sequence container自己管理一段连续内存std::stack和std::queue是容器适配器container adaptor本身不存储元素而是包装另一个容器只对外暴露受限的接口。理解这一点很多「为什么 stack 没有迭代器」「为什么 queue 不能遍历」的疑问就自然解开了。常见的误解有五个。第一把stack/queue当成独立容器试图用begin()遍历实际上适配器刻意不提供迭代器。第二认为vector的size()和capacity()是一回事实际上前者是元素个数后者是当前缓冲区能容纳的个数。第三认为push_back永远不会让迭代器失效实际上扩容时全部失效。第四认为queue::pop()会返回队首元素实际上它返回void元素在调用前就已经被销毁。第五对vectorbool使用bool*或data() unaware 它是按位存储的特化版本。本文按「序列容器 → 适配器」的顺序讲三者示例以 C17 为基准。所有行为均按标准语义描述具体实现例如扩容倍数、deque的块大小由标准库决定不应依赖。一、vector连续存储的动态数组std::vectorT保证元素在内存中连续存放因此可以用指针算术访问也可以把data()的结果传给需要连续数组的 C 接口C11 起提供data()。连续存储带来两点好处随机访问是 O(1)缓存局部性好代价是中间插入或删除需要搬移元素复杂度 O(n)。vector有两个容易混淆的尺寸概念接口含义是否改变元素size()当前元素个数否capacity()不重新分配的前提下最多能存多少否reserve(n)把容量增加到至少 n否只改容量resize(n)把元素个数改为 n是多出的默认构造少的析构shrink_to_fit()请求把容量降到 size否非强制push_back的均摊复杂度是 O(1)容量足够时直接构造容量不足时按某个增长策略重新分配常见实现按几何倍数增长具体倍数由实现决定把旧元素移动或拷贝到新缓冲区再释放旧缓冲区。这也是迭代器失效的根源。// 适用于 C17#include algorithm#include iostream#include vectorint main() {std::vectorint v{5, 1, 4, 2, 3};v.reserve(16); // 预分配容量避免后续多次扩容v.push_back(6); // size 6capacity 16std::sort(v.begin(), v.end());// erase-remove 惯用法先移动要保留的元素再一次性截断v.erase(std::remove_if(v.begin(), v.end(),[](int x) { return x % 2 0; }),v.end());for (int x : v) {std::cout x ;}std::cout \n;std::cout size v.size() capacity v.capacity() \n;return 0;}推演一下初始列表有 5 个元素reserve(16)只改容量push_back(6)在容量内完成不触发重新分配sort把元素排成 1 到 6remove_if把偶数移到末尾并返回新逻辑终点erase删除[新终点, end)区间结果是 1、3、5。size()为 3capacity()至少为 16具体值取决于实现。迭代器失效规则要记牢发生重新分配时所有迭代器、指针、引用全部失效。没有重新分配时push_back/emplace_back只使end()失效insert/erase使插入或删除位置之后的迭代器失效。reserve如果扩大了容量同样会使全部迭代器失效。operator[]不做边界检查越界是未定义行为undefined behavior, UBat()会检查并抛出std::out_of_range。另外std::vectorbool是标准库对bool的特化元素按位打包存储。它的operator[]返回一个代理对象而不是bool因此bool* p v[0];无法编译也不能假定相邻元素在内存中连续。需要真正的布尔数组时可以用std::vectorchar或std::dequebool。二、stack后进先出的容器适配器std::stack的默认底层容器是std::deque也可以显式指定std::vector或std::list。适配器只要求底层容器支持back()、push_back()、pop_back()因此这三种容器都能用std::forward_list不支持尾部操作不能作为底层。// 适用于 C17#include iostream#include stack#include stringbool balanced(const std::string s) {std::stackchar st;for (char c : s) {if (c ( || c [ || c {) {st.push(c);} else if (c ) || c ] || c }) {if (st.empty()) {return false; // 右括号多余}const char open st.top();st.pop();if ((c ) open ! () ||(c ] open ! [) ||(c } open ! {)) {return false; // 括号不匹配}}}return st.empty(); // 左括号是否全部闭合}int main() {std::cout std::boolalpha;std::cout balanced({[()]}) \n; // truestd::cout balanced(([)]) \n; // falsestd::cout balanced((() \n; // falsereturn 0;}stack的接口只有push、pop、top、empty、size以及 C11 起的emplace和swap。没有begin()/end()也没有下标访问这不是遗漏而是适配器故意收窄接口保证「只能从一端进出」的语义。也因此遍历一个stack的唯一办法是不断top()再pop()而且这会破坏原栈需要保留内容时先拷贝一份。pop()返回void元素在调用时被销毁。如果要取栈顶值再弹出必须分两步// 适用于 C17int value st.top();st.pop();不能写成int value st.pop();也不能在pop()之后再访问top()。top()返回的是引用在空栈上调用是 UB调用前必须用empty()判断。stack没有clear()。清空的常用写法是与一个空栈交换或直接赋值为空栈// 适用于 C17std::stackint empty;st.swap(empty); // 之后 empty 持有原内容退出作用域时销毁指定底层容器时模板参数顺序是std::stackT, Container// 适用于 C17#include stack#include vectorstd::stackint, std::vectorint st;这样写不会改变接口只是把存储换成vector。在元素数量可预估时先reserve可以避免deque的块分配开销但stack本身不暴露底层容器的reserve只能先构造容器再适配或者直接使用vector模拟栈。三、queue先进先出与优先队列std::queue同样是适配器默认底层是std::deque。它要求底层容器支持front()、back()、push_back()、pop_front()因此std::deque和std::list可以用std::vector不行因为vector没有pop_front()。queue的接口是push、pop、front、back、empty、size。与stack一样pop()返回void取队首要先front()再pop()同样没有迭代器不能遍历。front()与back()在空队列上调用都是 UB。// 适用于 C17#include iostream#include queue#include utility#include vector// 网格中从左上到右下的最短步数0 可走1 为障碍// 前提grid 非空且每行长度相同int shortest_path(const std::vectorstd::vectorint grid) {const int n static_castint(grid.size());const int m static_castint(grid[0].size());std::vectorstd::vectorint dist(n, std::vectorint(m, -1));std::queuestd::pairint, int q;dist[0][0] 0;q.push({0, 0});const int dx[4] {1, -1, 0, 0};const int dy[4] {0, 0, 1, -1};while (!q.empty()) {const auto [x, y] q.front(); // C17 结构化绑定q.pop();if (x n - 1 y m - 1) {return dist[x][y];}for (int k 0; k 4; k) {const int nx x dx[k];const int ny y dy[k];if (nx 0 || ny 0 || nx n || ny m) continue;if (grid[nx][ny] 1 || dist[nx][ny] ! -1) continue;dist[nx][ny] dist[x][y] 1;q.push({nx, ny});}}return -1; // 不可达}int main() {const std::vectorstd::vectorint grid{{0, 0, 0},{1, 1, 0},{0, 0, 0},};std::cout shortest_path(grid) \n; // 4return 0;}推演起点(0,0)距离 0 入队。第一层扩展到(0,1)与(1,0)但(1,0)是障碍只有(0,1)距离 1。之后(0,2)距离 2、(1,2)距离 3、(2,2)距离 4到达终点返回 4。每个格子最多入队一次复杂度 O(n·m)。queue还有两个细节。第一front()返回引用若在pop()之后继续使用这个引用就是访问已销毁的对象需要保留值时先拷贝。第二queue没有clear()清空同样用swap或赋值空队列。如果需要的不是先进先出而是「每次取最大/最小」应当使用std::priority_queue。它默认基于std::vector和堆算法top()是最大元素默认std::lessT要取最小元素传入std::greaterT// 适用于 C17#include functional#include queue#include vectorstd::priority_queueint max_heap; // 大顶堆std::priority_queueint, std::vectorint, std::greaterint min_heap; // 小顶堆priority_queue的push/pop是 O(log n)top是 O(1)。它同样不支持遍历也不能修改堆内元素的键值需要「修改优先级」时通常要重新插入或使用更专门的数据结构。容器底层默认访问端迭代器典型操作复杂度vector连续数组任意下标随机访问尾部插入均摊 O(1)中间 O(n)stackdeque栈顶无push/popO(1)queuedeque队首/队尾无push/popO(1)priority_queuevector堆顶无push/popO(log n)常见坑点坑点一把size()当容量频繁push_back触发扩容。❌std::vectorint v; for (...) v.push_back(x);不知道会扩容几次迭代器多次失效。✅ 数量可预估时先v.reserve(n)注意reserve只改容量元素个数仍是size()。坑点二扩容后继续使用旧迭代器。❌auto it v.begin(); v.push_back(1); *it 2;若发生重新分配it已悬垂。✅ 修改后重新获取迭代器循环中需要下标就每轮用v[i]或v.begin() i。坑点三vector用operator[]越界。❌v[v.size()]不检查属于 UB可能读到垃圾值也可能崩溃。✅ 确定下标合法再用[]不确定时用v.at(i)或先判断i v.size()。坑点四以为stack/queue能遍历。❌for (auto x : st)无法编译适配器不提供begin()/end()。✅ 需要遍历就换用vector/deque确实要读栈内容时拷贝一份再逐个top()/pop()。坑点五写int x q.pop();。❌pop()返回void编译失败即使某些实现有返回值也不是标准接口。✅ 先int x q.front();再q.pop();。坑点六在空容器上调用top()/front()/back()。❌std::stackint s; s.top();空栈取顶是 UB。✅ 先if (!s.empty())循环条件用while (!q.empty())。坑点七pop()之后继续使用之前取得的引用。❌const auto x q.front(); q.pop(); use(x);引用指向已销毁的元素。✅ 先拷贝值再pop()需要引用语义时确认元素在pop()后仍然存在。坑点八把vectorbool当普通bool数组。❌bool* p v.data();或bool r v[0];在vectorbool上无法成立它是按位存储的特化。✅ 需要连续bool存储时用std::vectorchar只做逻辑位集合时明确接受代理对象的行为。总结项目vectorstackqueue身份序列容器容器适配器容器适配器默认底层自身连续数组dequedeque元素访问下标、迭代器、data()仅top()仅front()/back()插入删除任意位置中间 O(n)仅栈顶仅队尾进、队首出迭代器随机访问不提供不提供失效扩容全失效否则局部无迭代器可失效无迭代器可失效典型用途批量数据、需要遍历括号匹配、回溯、表达式求值BFS、任务排队vector是「可遍历、可随机访问的连续数组」用它的关键是理解size与capacity的分离以及扩容带来的迭代器失效。stack和queue是「只允许从固定端口进出的适配器」用它们的关键是接受接口的收窄没有迭代器、pop()不返回值、空容器上取元素是 UB。三者都建立在 RAII 之上不需要手动释放内存真正需要小心的是失效规则与空容器检查这两类错误在标准里都是未定义行为不会给出友好的报错。