【C 面试真题】聊聊 C 的序列容器序列容器是标准库的开胃菜也是工程里用得最多的一族。背得出vector 是动态数组只是及格真考你的是string 怎么和 C 字符串打交道、vector 扩容为什么倍增、reserve 和 resize 差在哪、list 的插删 O(1) 有什么猫腻、deque 凭什么两端 O(1)、stack/queue 算不算容器。本文按 string → vector → list → deque → 适配器的顺序把底层和选型一次讲清。一、开场序列容器有哪些❓ 介绍一下标准库的序列容器✅ 标准库容器分四大类序列容器按插入顺序排、关联容器按 key 有序、无序关联容器哈希、容器适配器包装改造。序列家族一张表容器底层强项弱项string字符数组文本处理、C 互操作同 vectorvector动态数组随机访问 O(1)中间插删 O(n)array[C11]定长数组零堆分配长度编译期定死deque分段连续两端插删 O(1)中间插删 O(n)list双向链表持迭代器插删 O(1)随机访问 O(n)forward_list[C11]单向链表比 list 省一个指针不能回退、无 sizestack/queue适配器限定 LIFO/FIFO 语义接口受限回答思路按连续内存string/vector/array→ 分段deque→ 链表list/forward_list→ 适配器报一遍每类点出底层和强项——面试官就知道你心里有张容器地图接下来多半会挑一个深入底层。怎么选按顺序问自己三个问题两端频繁进出→ deque滑窗、任务队列已持有迭代器、频繁中间插删、元素拷贝贵→ list其余一律vector——哪怕是中间插删。// 大多数场景的正确答案vectorWidgetwidgets;// 中间插删 O(n) 但搬的是字节// 连续内存下常比 list 跳节点更快反直觉但重要小元素场景vector 的O(n) 搬移经常跑赢list 的O(1) 链表跳转——缓存一次搬几十个字节比追一次指针便宜。别只看复杂度选容器要看访存模式。这也是默认 vector成为共识的原因。二、string与 C 字符串的互操作❓ string 和 C 字符串const char*怎么互操作✅ 两个方向各有一手C 串 → string构造和赋值直接吃遇\0停止string shello;// 直接构造s world;// 追加string → C 串c_str()/data()返回const char*保证以\0结尾可以喂给任何 C APIprintf(%s,s.c_str());FILE*ffopen(s.c_str(),r);⚠️三个坑①内嵌\0会截断——string s(a\0b)长度只有 1要指定长度string(a\0b, 3)②c_str() 的指针会失效——string 一旦扩容、修改、析构旧指针就悬空。别存下来复用每次要用现取③string_view 不保证\0结尾[C17]——sv.data()只是无主视图喂 C API 前老老实实调c_str()。❓string s NULL;会发生什么✅ 编译能过运行崩。NULL或0隐式转成const char*空指针匹配string(const char*)构造——它从指针逐字符读到\0对空指针就是解引用 0 地址未定义行为典型表现是段错误。string s1NULL;// 编译过运行崩string s20;// 同样崩// 想要空字符串string s3;// ✅ 默认就是空 根因该构造的契约是指针指向合法\0结尾串传 nullptr 违反前置条件直接 UB。[C23]堵了半个口子string s nullptr;编译报错构造被 deleteNULL展开为 0 时仍走老路。实战守则变量可能为空就先判空——string s p ? p : ;别让空指针有机会溜进构造函数。❓ string 和 vectorchar 底层一样吗✅ 骨架都是连续字符数组但 string 多了C 字符串互操作语义\0结尾和SSO小字符串优化短串直接存对象内部、不碰堆——而短串是绝对主流。加分点SSO 是实现细节不是标准规定——不同标准库的容量和对象大小都不一样标准库sizeof(string)SSO 容量libstdcGCC32 字节15 字符libcClang24 字节22 字符MSVC STL32 字节15 字符64 位平台常见值以具体实现为准。面试聊 SSO 的正确姿势短串存对象内、免堆分配阈值因实现而异——知道平台差异比背一个数字更加分。三、vector连续内存与高频考点❓ vector 的底层结构是什么✅一块连续内存 三根指针示意// vector 内部示意T*start;// 数据起点T*finish;// 已用末尾T*end_stg;// 存储末尾// size finish - start// capacity end_stg - startsize是已有元素数capacity是已开好的总容量。push_back时若两者相等满了触发扩容开一块更大的内存约 2 倍或 1.5 倍实现相关把旧元素搬过去——C11 后优先移动而非拷贝——再释放旧内存。为什么倍增摊还分析的经典结论n 次push_back的总搬运量是 O(n)124…n摊到每次是 O(1)。若每次只加固定 k 个总代价 O(n²)push 越多越亏。搬运靠移动扩容搬旧元素优先用移动构造——前提是它标了noexcept否则 vector 为保异常安全只能退回拷贝。这也是移动构造要 noexcept最直接的兑现场景。❓ reserve 和 resize 有什么区别迭代器什么时候失效✅reserve 只开容量resize 真造对象vectorintv;v.reserve(1000);// capacity1000size0// 没有元素被构造v.resize(1000);// size1000// 1000 个元素被值初始化迭代器失效必考扩容旧内存整块释放所有迭代器、指针、引用全部失效insert/erase插删点之后的迭代器失效元素被搬动。vectorintv{1,2,3,4};autoitv.begin();v.push_back(5);// 可能扩容// *it; // ❌ it 可能已悬空⚠️ 典型翻车循环里边push_back边持旧迭代器扩容即悬空。先reserve够大或改用新迭代器。边遍历边删erase返回被删元素之后的新迭代器接住它继续走// ✅ 正确用 erase 的返回值for(autoitv.begin();it!v.end();)if(*it%2)itv.erase(it);elseit;// ❌ 错误erase 后还 it悬空❓ 如何删除元素如何释放内存✅删元素erase删单个或区间、pop_back尾删、clear清空按条件批量删交给 erase-remove 惯用法。释放内存是另一回事——clear只析构元素容量原封不动vectorintv;v.reserve(1000);v.clear();// size0capacity 仍 1000// [C11] 请求收缩非强制v.shrink_to_fit();// 经典强制释放和空对象交换vectorint().swap(v); vector 的容量只增不减除非换内存clear 也不缩——容量是以防万一的蓄水池缩了下次又得重新分配。shrink_to_fit是请求不是命令实现可以拒绝swap 技巧靠临时对象析构释放是强制手段。四、list插删 O(1) 的真相❓ list 随处插删 O(1)为什么还常被 vector 打败✅ 因为O(1) 的前提是已经拿到迭代器——找位置本身就是 O(n)。// 节点示意structNode{Node*prev;Node*next;T data;};list 的真实代价账单没有 operator[]随机访问只能从头走O(n)每个元素多两个指针的内存开销节点散落堆上缓存不友好——跳一个节点就是一次潜在 cache miss插删本身 O(1)但先得 O(n) 找到位置。所以 list 只在已持有迭代器 频繁中间插删 元素大拷贝贵时才真正划算。它也有独门绝技splice——把另一个 list 的整段节点直接摘下来接上不拷贝、不分配真 O(1)listinta{1,2},b{3,4};// 把 b 整段接到 a 末尾O(1)a.splice(a.end(),b);五、deque分段连续两端 O(1)❓ deque 凭什么头尾插删都是 O(1)✅ 因为它不是一整块内存而是一串固定大小的缓冲区由一个中控数组索引中控 map: [p0, p1, p2, ...] ↓ ↓ ↓ [buf][buf][buf] ...头部插删只动最前面的 buf满了就在另一端挂一块新 bufO(1)随机访问两级寻址先算第几块 buf再算块内偏移仍是 O(1)但常数比 vector 大中间插删仍要搬元素O(n)。失效更宽松头尾插删只失效指向被插删元素的迭代器其余不动不像 vector 扩容全失效。代价是结构复杂、缓存局部性不如 vector。六、stack 与 queue容器适配器❓ stack、queue 算容器吗✅ 严格说是容器适配器——不自己管数据包装一个底层容器、只暴露对应接口适配器语义默认底层核心接口stackLIFOdequepush / pop / topqueueFIFOdequepush / pop / front / backpriority_queue大顶堆vectorpush / pop / topstackints;// 默认 deque 打底s.push(1);s.pop();// 也可以指定底层容器stackint,vectorints2; 标准库自己面对两头进出stack/queue也是拿 deque 打底——deque 两端 O(1) 的直接背书。适配器的价值在于收窄接口、限定语义stack 就不该有中间插入类型系统直接禁掉误用进不了编译。七、面试高频追问❓ Q1vector 为什么倍增扩容而不是每次加固定个数✅ 摊还分析。倍增时 n 次插入总搬运 O(n)摊还每次 O(1)固定增量则是 O(n²)。1.5 倍和 2 倍各有取舍2 倍浪费更多实现自选。❓ Q2vector 和 array 什么区别✅array是编译期定长的裸数组包装无堆分配、无扩容、无容量概念。长度固定且小用 array 更省。❓ Q3forward_list 和 list 呢✅ forward_list 是单向链表每个节点省一个 prev 指针只能前向遍历连size()都没有为了不存计数。是更省内存的极致版 list。❓ Q4push_back 什么时候使迭代器失效✅ 仅在触发扩容时——旧内存整块搬家全部失效容量足够时 push_back 不失效任何迭代器。❓ Q5deque 为什么随机访问也是 O(1)✅ 中控数组记录每块 buf 的地址给下标 n 可直接算出第几块 buf 块内偏移两级乘加寻址常数大于 vector 但量级 O(1)。❓ Q6emplace_back 和 push_back 的区别✅emplace_back(args...)在尾部原地构造省去临时对象和一次移动push_back(x)先有 x 再搬进去。能 emplace 就 emplace。❓ Q7vectorbool 是怎么回事✅ 它是特化版本不真存 bool 数组而是按位压缩1 个 bool 只占 1 bit。代价是operator[]返回代理对象而非真正的引用也没法取元素地址。要正常的 bool 数组用vectorchar或bitset。八、总结速查表考点一句话结论选型三问两端进出→deque持迭代器插删→list默认 vectorstring ↔ C 串c_str() 现取现用防悬空string SSO实现细节阈值随标准库而异vector 底层连续内存 三指针扩容策略倍增2x/1.5x摊还 O(1)reserve/resize只开容量 / 真造对象vector 失效扩容全失效插删点之后失效clear 与内存只清元素不清容量swap 真释放list插删 O(1) 需先有迭代器无 []deque分段连续 中控两端 O(1)stack/queue适配器默认 deque 打底一句话回顾string 先过 C 互操作关c_str 现取现用、防\0截断vector 是连续数组倍增扩容摊还 O(1)扩容即全失效、clear 不缩容list 是链表插删 O(1) 但先得 O(n) 找位置deque 分段连续两端 O(1)stack/queue 是适配器deque 打底。默认 vector——小元素时它连中间插删都常赢 list。如果您觉得本篇内容对你有帮助欢迎点赞 、收藏 ⭐、转发 。下期我们继续标准库篇聊关联容器——map/set 的红黑树和 unordered_map 的哈希表到底差在哪、怎么选敬请关注