上篇把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::list<int> tasks = {1, 2, 3, 4, 5}; auto it = tasks.begin(); std::advance(it, 2); // 移动到第3个元素 tasks.insert(it, 99); // 在2和3之间插入99，O(1) tasks.erase(it); // 删除3，O(1)list在机器人开发里的应用
说实话，list在实际机器人项目里用得不多。为什么？因为现代CPU对连续内存访问有缓存优化，list的节点散落在堆上，缓存命中率低，遍历起来反而比vector慢。
但有个场景list确实好用：任务队列里需要频繁在中间插入或删除。
比如机器人有个任务调度器，任务按优先级排列。新来的任务要插到合适的位置，完成的任务要删掉。这种场景下list的O(1)插入删除就有优势了。
std::list<Task> 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::list<int> 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的底层结构
deque（double-ended queue）的底层结构比较特殊。它不是完全连续的内存，而是分段连续的。
deque<int> 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::deque<std::vector<double>> scan_window; const int WINDOW_SIZE = 10; void processScan(const std::vector<double>& 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哈希表
有任何问题欢迎评论区留言，我会尽量回复。
与typedef的实战应用与内存解析)
