上篇把vector扒了个底朝天今天看它的两个兄弟——list和deque。面试里经常这样问vector和list有什么区别什么时候用哪个这个问题看起来基础但真能答好的人不多。很多人背了一句vector随机访问快list插入删除快就完事了其实远没有这么简单。list的底层结构list的底层是双向链表。每个节点包含三个部分前驱指针、数据、后继指针。┌──────┐ ┌──────┐ ┌──────┐ │ prev │←───│ prev │←───│ prev │ │ data │ │ data │ │ data │ │ next │───→│ next │───→│ next │ └──────┘ └──────┘ └──────┘这意味着list不支持随机访问——你不能list[5]要访问第5个元素必须从头遍历过去时间复杂度O(N)。但list的优势在于插入和删除。只要你有指向那个位置的迭代器插入和删除都是O(1)——改几个指针就完事了。std::listint tasks {1, 2, 3, 4, 5}; auto it tasks.begin(); std::advance(it, 2); // 移动到第3个元素 tasks.insert(it, 99); // 在2和3之间插入99O(1) tasks.erase(it); // 删除3O(1)list在机器人开发里的应用说实话list在实际机器人项目里用得不多。为什么因为现代CPU对连续内存访问有缓存优化list的节点散落在堆上缓存命中率低遍历起来反而比vector慢。但有个场景list确实好用任务队列里需要频繁在中间插入或删除。比如机器人有个任务调度器任务按优先级排列。新来的任务要插到合适的位置完成的任务要删掉。这种场景下list的O(1)插入删除就有优势了。std::listTask task_queue; // 按优先级插入 auto it std::find_if(task_queue.begin(), task_queue.end(), [](const Task t) { return t.priority new_task.priority; }); task_queue.insert(it, new_task); // 删除已完成的任务 task_queue.remove_if([](const Task t) { return t.status DONE; });list还有个独特的能力splice——O(1)时间把一段元素从一个list移到另一个list。这个操作其他容器都做不到。std::listint high_priority, low_priority; // 把low_priority的前3个元素移到high_priority末尾 high_priority.splice(high_priority.end(), low_priority, low_priority.begin(), std::next(low_priority.begin(), 3));deque的底层结构dequedouble-ended queue的底层结构比较特殊。它不是完全连续的内存而是分段连续的。dequeint d {1, 2, 3, 4, 5, 6, 7, 8}; 内部结构 buffer map指针数组 │ ├──→ [block1: 1 2 3 4] ├──→ [block2: 5 6 7 8] └──→ [block3: ...]deque维护一个中控map不是map容器是个指针数组每个元素指向一个固定大小的buffer通常是512字节或4KB。每个buffer里存一段连续的元素。这种设计让deque支持两端O(1)的push_back和push_front。当一端的buffer满了就在中控map里分配一个新buffer不影响已有的数据。同时deque也支持随机访问。虽然不像vector那样直接指针偏移但通过中控map定位到对应的buffer再在buffer内偏移也是O(1)。deque vs vector vs list面试里经常让你比较这三个容器。核心区别vector连续内存尾部O(1)插入随机访问O(1)头部/中间插入O(N)。缓存友好。deque分段连续两端O(1)插入随机访问O(1)中间插入O(N)。缓存不如vector友好。list双向链表任意位置O(1)插入有迭代器的前提下不支持随机访问缓存不友好。一个常见的误解是需要频繁插入删除就用list。实际上如果你是在尾部插入vector的均摊O(1)比list的O(1)更快因为vector的缓存友好性。如果你是在头部插入用deque而不是list。list真正有优势的场景是你已经有指向中间某个位置的迭代器需要在它前后插入或删除。这种场景在实际开发中其实不多。迭代器失效的区别面试还有个爱考的点三种容器的迭代器失效规则不同。vector插入可能导致所有迭代器失效扩容时。删除被删元素之后的迭代器全部失效。deque插入在尾部不会使已有迭代器失效但不包括end()在头部或其他位置会使所有迭代器失效。删除只有被删元素的迭代器失效。list插入不会使任何迭代器失效。删除只让被删元素的迭代器失效其他都不受影响。这就是list真正的优势所在——迭代器稳定性最好。deque在机器人开发里的实际应用deque在机器人开发里有个很典型的应用场景滑动窗口滤波。比如你需要对最近10帧的激光雷达数据做滑动平均deque就是最自然的选择std::dequestd::vectordouble scan_window; const int WINDOW_SIZE 10; void processScan(const std::vectordouble new_scan) { scan_window.push_back(new_scan); if (scan_window.size() WINDOW_SIZE) { scan_window.pop_front(); // 头部删除O(1) } // 对window内的数据做平均 auto avg computeAverage(scan_window); }vector也能做但头部删除是O(N)每帧都要搬移数据。deque的头部删除是O(1)更适合这种高频操作。我之前做IMU数据融合的时候就是用deque维护一个固定大小的历史数据窗口。100Hz的采样率窗口大小200跑起来很流畅。面试中还有一个容易踩坑的追问list的splice操作是什么splice可以在O(1)时间内把一个list中的元素移动到另一个list的指定位置不涉及任何内存分配或拷贝只是修改指针指向。这个操作在实现任务队列优先级调整时非常有用——比如机器人任务调度器里某个任务突然需要提升优先级用splice把它从低优先级队列移到高优先级队列头部常数时间搞定。另外面试时经常被问到的还有deque的迭代器会不会失效——答案是deque在头部或尾部插入元素时中间元素的迭代器不会失效这和vector不同但在中间插入会导致所有迭代器失效。理解这些细节能帮你在面试中回答得更精准。给正在准备面试的你一点建议容器选型在面试里是送分题但很多人答不全。记住这个决策树需要随机访问且大部分操作在尾部→vector。需要两端操作→deque。需要在中间频繁插入删除且已有迭代器→list。如果拿不准选vector。在绝大多数场景下vector的性能都是最好的因为连续内存对CPU缓存最友好。实际项目中我遇到的情况九成以上vector都是最优解。下篇讲map和unordered_map——底层红黑树vs哈希表面试考得非常多。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第30篇 STL之vector深度解析——为什么机器人代码里到处都是它 下一篇预告第32篇 STL之map与unordered_map——底层红黑树vs哈希表有任何问题欢迎评论区留言我会尽量回复。