当前位置：首页 > news >正文

STL之list与deque：不同场景下的容器选型，别再无脑用vector了

news 2026/7/15 4:57:08

上篇把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不同），但在中间插入会导致所有迭代器失效。理解这些细节能帮你在面试中回答得更精准。