35、STL容器（list与deque）：list双向链表、deque双端队列

说实话，很多C++初学者学完vector就觉得容器学得差不多了。但真到了项目里，你会发现vector并不是万能的。比如你需要在中间频繁插入删除，或者你需要在头部尾部同时操作——这时候vector就有点力不从心了。

今天我们就来聊聊list和deque。这两个容器，一个擅长任意位置的插入删除，一个擅长两端操作。我个人项目中经常把它们搭配着用，效果还不错。

一、list：双向链表

list底层是双向链表。每个节点都保存着前驱和后继的指针。这意味着什么？意味着插入和删除非常快——只要改几个指针就行，不需要像vector那样搬动大量元素。

基本操作示例

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30, 40};

    // 在头部插入
    lst.push_front(5);
    // 在尾部插入
    lst.push_back(50);

    // 在中间插入（迭代器指向第三个位置）
    auto it = lst.begin();
    std::advance(it, 2);  // 注意：list不支持 it += 2
    lst.insert(it, 25);

    // 遍历
    for (int v : lst) {
        std::cout << v << " ";
    }
    // 输出：5 10 25 20 30 40 50

    return 0;
}

这里有个坑，我刚开始用list时踩过。list的迭代器不支持随机访问，你不能直接写 it += 3，必须用 std::advance。为什么？因为链表节点在内存里不是连续存放的，没法通过偏移量直接跳到第N个节点。

list的排序

list自己带了一个 sort() 成员函数。注意，不能用标准库的 std::sort，因为那个要求随机访问迭代器。

lst.sort();  // 默认升序
lst.sort(std::greater<int>());  // 降序

二、deque：双端队列

deque这个名字有点怪，全称是double-ended queue。它结合了vector和list的部分优点。底层是一段一段连续内存拼起来的，所以既支持随机访问，又能在两端快速插入删除。

基本操作示例

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {100, 200, 300};

    // 两端操作
    dq.push_front(50);
    dq.push_back(400);

    // 随机访问
    std::cout << dq[2];  // 输出200

    // 遍历
    for (size_t i = 0; i < dq.size(); ++i) {
        std::cout << dq[i] << " ";
    }
    // 输出：50 100 200 300 400

    return 0;
}

我记得有一次做消息队列的缓存层，需要频繁从头部取数据、从尾部加数据。用vector的话，头部删除要搬动所有元素，性能扛不住。用list的话，又需要随机访问某个位置的消息。最后选了deque，两边都满足了。

三、list vs deque vs vector 对比

操作	vector	list	deque
随机访问	O(1)	O(n)	O(1)
头部插入/删除	O(n)	O(1)	O(1)
尾部插入/删除	O(1) 均摊	O(1)	O(1)
中间插入/删除	O(n)	O(1)	O(n)
内存连续性	连续	不连续	分段连续
迭代器失效	插入/删除后可能失效	只有被删的失效	头部/尾部操作不影响其他

四、实战场景：用deque实现滑动窗口

我项目中经常需要处理滑动窗口问题。比如计算一个数组里每个长度为k的子数组的最大值。用deque实现非常优雅。

#include <iostream>
#include <deque>
#include <vector>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::vector<int> result;
    std::deque<int> dq;  // 存储下标

    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口范围的元素
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 移除比当前元素小的元素（它们不可能成为最大值）
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // 窗口形成后，记录最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    auto res = maxSlidingWindow(nums, 3);
    for (int v : res) {
        std::cout << v << " ";
    }
    // 输出：3 3 5 5 6 7
    return 0;
}

这个算法的时间复杂度是O(n)。每个元素最多入队一次、出队一次。deque在这里发挥了关键作用——既要从头部移除过期元素，又要从尾部移除比当前小的元素。vector做不到，list又太慢。

五、选择建议

嗯，这里我总结一下我的选择原则：

• 需要随机访问，主要在尾部操作 → vector
• 需要频繁在中间插入删除 → list
• 需要两端操作，偶尔随机访问 → deque
• 需要稳定排序且频繁插入 → list
• 需要缓存友好（内存连续） → vector

六、知识体系结构图

下面这张图帮你理清list和deque的核心区别与适用场景：

七、避坑指南

我曾经在项目里用list存储大量小对象，结果内存占用比vector多了快3倍。每个节点多出来的两个指针，在数据量大的时候非常可观。后来我改用了vector+预留空间，性能反而更好。

还有一个坑：list的 size() 在C++11之前是O(n)的。虽然C++11之后保证了O(1)，但如果你在维护老代码，要注意这一点。

deque也有个问题：如果你在中间插入元素，虽然理论上是O(n)，但实际开销比vector小一些。不过别指望它能和list比。我见过有人用deque做中间插入，数据量一上来就卡死了。

好了，list和deque就聊到这里。这两个容器各有各的脾气，用对了地方就是利器，用错了就是坑。多写写代码，慢慢就有感觉了。

---

公众号:蓝海资料掘金营，微信deep3321