2. deque与list容器：双端队列与链表的实战选择

大家好，欢迎来到第二章。今天我们来聊聊deque和list这两个容器。说实话，我在刚接触STL时，总觉得它们就是vector的“变种”。直到我在一个实时数据采集项目中，被vector的头部插入性能坑了一把，才真正开始重视它们。

这一章，我会结合自己的踩坑经历，带你彻底搞懂deque和list。嗯，咱们直接开始。

2.1 deque：双端队列的“左右逢源”

deque，全称double-ended queue。说白了，就是两端都能高效插入删除的队列。它的内部结构很有意思——不是一块连续内存，而是一段段连续内存块组成的“分段连续”结构。

我画了一张deque的内部结构图，你看一眼就明白了：

看到没？deque不像vector那样把所有元素挤在一块连续内存里。它把数据分散到多个固定大小的块中，再用一个中控数组来管理这些块。这样设计的好处很明显——头尾插入时，只需要分配一个新块就行，不用像vector那样搬动所有元素。

2.2 deque vs vector：谁更适合你？

很多新手会问：deque和vector到底选哪个？我直接给你一张对比表，看完就明白了：

操作	vector	deque
尾部插入	O(1) 均摊	O(1)
头部插入	O(n) ❌	O(1) ✅
随机访问	O(1) 极快	O(1) 稍慢
内存连续性	完全连续	分段连续
中间插入	O(n)	O(n)
内存占用	紧凑	略高（中控数组开销）

你看，vector在头部插入是O(n)，因为要移动所有元素。deque则是O(1)。但deque的随机访问比vector慢一点，因为需要先查中控数组，再定位到具体块。

2.3 list：链表的“插入删除之王”

list是双向链表。它的最大优势是：只要你知道位置（迭代器），插入和删除就是O(1)。

但代价是什么？

• 不支持随机访问（不能list[3]这样用）
• 每个元素额外存储两个指针（前驱和后继）
• 内存碎片化，缓存不友好

来看一个简单的list操作示例：

#include <list>
#include <iostream>

int main() {
    std::list<int> tasks = {1, 2, 3, 4, 5};
    
    // 在头部插入
    tasks.push_front(0);
    
    // 在尾部插入
    tasks.push_back(6);
    
    // 在中间插入（需要先找到位置）
    auto it = tasks.begin();
    std::advance(it, 3);  // 移动到第3个位置
    tasks.insert(it, 99);
    
    // 删除元素
    tasks.remove(3);  // 删除所有值为3的元素
    
    for (int v : tasks) {
        std::cout << v << " ";
    }
    // 输出: 0 1 2 99 4 5 6
    return 0;
}

注意看，list的insert和erase操作，一旦你拿到了迭代器，就是O(1)。但问题在于——你怎么拿到那个迭代器？如果你要从头遍历去找，那查找本身已经是O(n)了。

2.4 list的插入删除性能分析

我直接说结论：list的插入删除性能，在“已知位置”的情况下是无敌的。但实际项目中，这个“已知位置”往往是个大坑。

举个例子，我在做一个任务调度系统时，需要频繁在任务列表中间插入新任务。一开始我用vector，每次插入都要移动后面所有任务，性能惨不忍睹。换成list后，插入本身很快，但每次都要先遍历找到插入点，整体性能反而更差了。

后来怎么解决的？我用了一个“迭代器缓存”的技巧：

// 迭代器缓存示例
std::list<Task> taskList;
std::unordered_map<int, std::list<Task>::iterator> iterCache;

// 插入任务时，缓存迭代器
auto it = taskList.insert(pos, newTask);
iterCache[newTask.id] = it;

// 删除时，直接从缓存取迭代器
auto it = iterCache[taskId];
taskList.erase(it);
iterCache.erase(taskId);

这样一来，查找是O(1)，删除也是O(1)。这才是list的正确打开方式。

2.5 forward_list：单向链表的“轻量之选”

forward_list是C++11引入的单向链表。它比list更省内存——每个节点只存一个next指针。但代价是只能单向遍历。

它的接口也做了精简，没有push_back，只有push_front。为什么？因为单向链表找尾节点是O(n)，所以干脆不提供尾部操作。

#include <forward_list>

std::forward_list<int> flist = {3, 4, 5};
flist.push_front(2);  // 只能从头部插入
flist.push_front(1);  // 现在: 1 2 3 4 5

// 遍历
for (int v : flist) {
    std::cout << v << " ";
}

forward_list适合什么场景？我个人的经验是：当你只需要一个简单的“后进先出”结构，或者内存非常受限时，用它准没错。比如嵌入式系统中，每个字节都很宝贵，forward_list比list省一半的指针开销。

2.6 实战：任务调度队列

好了，理论说完了，咱们来点实战。假设我们要实现一个简单的任务调度队列，支持以下操作：

• 从尾部添加任务
• 从头部取出任务执行
• 支持紧急任务插队（插入到头部）
• 支持取消指定任务

你想想看，这个场景用什么容器最合适？

deque！因为：

• 尾部添加 → push_back，O(1)
• 头部取出 → pop_front，O(1)
• 紧急插队 → push_front，O(1)
• 取消任务 → 需要遍历查找，但deque支持随机访问，可以用二分查找优化

来看代码实现：

#include <deque>
#include <algorithm>
#include <functional>

struct Task {
    int id;
    int priority;
    std::function<void()> handler;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

class TaskScheduler {
    std::deque<Task> tasks_;
    
public:
    void addTask(Task task) {
        // 按优先级插入，保持队列有序
        auto pos = std::lower_bound(tasks_.begin(), tasks_.end(), task);
        tasks_.insert(pos, std::move(task));
    }
    
    void addUrgentTask(Task task) {
        tasks_.push_front(std::move(task));  // 紧急任务插队到头部
    }
    
    Task popTask() {
        if (tasks_.empty()) {
            throw std::runtime_error("No tasks available");
        }
        Task t = std::move(tasks_.front());
        tasks_.pop_front();
        return t;
    }
    
    bool cancelTask(int taskId) {
        auto it = std::find_if(tasks_.begin(), tasks_.end(),
            [taskId](const Task& t) { return t.id == taskId; });
        if (it != tasks_.end()) {
            tasks_.erase(it);
            return true;
        }
        return false;
    }
    
    size_t size() const { return tasks_.size(); }
};

这个调度器用deque实现，核心操作都是O(1)或O(log n)。addTask用了二分查找找到插入位置，然后insert。注意deque的中间插入是O(n)，但因为我们是按优先级有序插入，实际项目中任务数量通常不大，这个开销可以接受。

小结

这一章我们聊了deque和list的核心区别。deque适合“两端操作+偶尔随机访问”，list适合“已知位置频繁插入删除”。forward_list则是内存敏感场景的轻量选择。

选择容器时，我建议你问自己三个问题：

1. 我需要随机访问吗？→ 需要就选vector或deque
2. 我主要在两端操作还是中间？→ 两端用deque，中间用list
3. 内存是否紧张？→ 紧张就考虑forward_list

记住，没有银弹。每个容器都有自己的适用场景。理解它们的底层实现，才能做出正确的选择。

---

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