C++ STL 容器:deque、list 与选择指南

std::vector 你肯定用熟了,但它有个软肋:在头部插入元素是 O(n),中间插入要搬动后面所有元素。那 deque 和 list 是来干什么的?什么时候该放弃 vector?本文从数据结构原理出发,把四个常用顺序容器放在一起对比,给你一份可落地的选择指南,以后选容器不再靠猜。

1. 回顾 vector:它强在哪、弱在哪

vector 底层是连续内存上的动态数组:下标访问 O(1),尾部插入均摊 O(1)。这也是它"快"的全部秘密——数据挨在一起,CPU 缓存命中率高,遍历速度是所有容器里最快的。但代价也来自"连续":头部或中间插入/删除,要整体搬移元素;容量不够时重新分配,还要把全部元素拷贝到新内存。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};
    // 头部插入:所有元素都要往后挪一位,O(n)
    v.insert(v.begin(), 0);
    // 中间插入:同样要搬移
    v.insert(v.begin() + 3, 99);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";   // 0 1 2 99 3 4 5
    return 0;
}

这还不是最痛的。最痛的是迭代器失效:vector 一旦扩容,所有迭代器、指针、引用全部失效;中间插入也会让插入点之后的迭代器失效。如果你的程序频繁在头部操作、又长时间持有迭代器,vector 就不是好选择了。另外提一句:如果元素个数在编译期就固定,用 std::array 比 vector 更省心,连堆分配都省了。

2. deque:双端队列

deque 是"双端队列",两端都能 O(1) 插入删除,同时保留了随机访问(下标 O(1))。实现上它由若干块连续内存拼接而成,扩容时只需要新增一块,不需要搬移已有元素,所以两端操作都是常数时间:

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d;
    d.push_back(30);    // 尾部
    d.push_front(20);   // 头部
    d.push_front(10);
    d.push_back(40);
    std::cout << "front=" << d.front() << ", back=" << d.back() << "\n";
    d.pop_front();      // 弹出头部
    d.pop_back();       // 弹出尾部
    for (int x : d) std::cout << x << " ";
    std::cout << "\n";   // 20 30
    return 0;
}

什么时候用 deque?典型场景是任务队列:一边往尾部追加任务,一边从头部取任务处理;或者实现"撤销/重做"这种两头都要操作的结构。它比 list 好在有随机访问,比 vector 好在头部操作是 O(1)。代价是:内部按块管理内存,不如 vector 紧凑,遍历速度略慢一点点。还有一个容易忽略的点:deque 在两端插入/删除时,迭代器不会失效(只有被删元素对应的迭代器失效),这比 vector 宽容得多。

3. list:双向链表

list 是双向链表:每个节点独立分配,通过指针串联。任意位置的插入/删除都是 O(1)——只要你有那个位置的迭代器。但它没有随机访问,找第 n 个元素只能从头走,下标是 O(n);每个元素还要多存两个指针,内存开销大:

#include <algorithm>
#include <iostream>
#include <list>

int main() {
    std::list<int> lst{10, 20, 30, 40};
    // 找到 20 所在位置,在其前面插入 15
    auto it = std::find(lst.begin(), lst.end(), 20);
    lst.insert(it, 15);
    // 删除 30
    auto it2 = std::find(lst.begin(), lst.end(), 30);
    lst.erase(it2);
    for (int x : lst) std::cout << x << " ";
    std::cout << "\n";   // 10 15 20 40
    return 0;
}

注意:list 的 insert/erase 是 O(1),但前面那句 std::find 是 O(n)——链表上"找到位置"本身要遍历。所以 list 的 O(1) 插入只在"你已经持有迭代器"时才成立。典型场景是"一边遍历一边删除":遍历时删除元素,只有被删节点的迭代器失效,其他迭代器安然无恙:

#include <iostream>
#include <list>

int main() {
    std::list<int> nums{1, 2, 3, 4, 5, 6, 7, 8};
    // 一边遍历一边删除偶数:erase 返回下一个有效迭代器
    for (auto it = nums.begin(); it != nums.end();) {
        if (*it % 2 == 0) {
            it = nums.erase(it);
        } else {
            ++it;
        }
    }
    for (int x : nums) std::cout << x << " ";
    std::cout << "\n";   // 1 3 5 7
    return 0;
}

这段代码换成 vector 就会出问题:erase 之后迭代器失效,++it 是未定义行为。所以"遍历中删除"首选 list;另一个典型场景是 LRU 缓存——哈希表存迭代器,链表负责调整访问顺序。反过来,如果你只是"随机插一下",list 未必划算,find 的 O(n) 可能比 vector 的整体搬移还慢。

4. list 的特殊成员函数

链表天生适合"整段搬移",所以 list 有一批专属操作:sort(链表自己的归并排序)、unique(去重)、merge(合并两个有序链表)、splice(把一段节点直接嫁接到另一个链表):

#include <iostream>
#include <list>

int main() {
    std::list<int> a{5, 1, 4};
    std::list<int> b{3, 2};
    a.sort();          // 链表自己的排序,不是 std::sort
    b.sort();
    a.merge(b);        // 把有序的 b 合并进有序的 a,b 变空
    a.unique();        // 去掉相邻重复的元素
    for (int x : a) std::cout << x << " ";
    std::cout << "\n"; // 1 2 3 4 5

    // splice:把 y 的节点整体搬到 x 头部,O(1) 完成
    std::list<int> x{100, 200}, y{1, 2, 3};
    x.splice(x.begin(), y);   // y 变空
    for (int v : x) std::cout << v << " ";
    std::cout << "\n";        // 1 2 3 100 200
    return 0;
}

注意 a.sort() 是成员函数,和 std::sort 不一样——std::sort 需要随机访问迭代器,链表用不了。splice 是 list 的招牌:把另一个链表的节点"搬"过来,不拷贝元素、O(1) 完成,这是 vector/deque 永远做不到的。这些操作都是链表数据结构特有的,写缓存、任务调度这类代码时非常有用。

5. forward_list:单链表

forward_list 是 C++11 引入的单向链表:只能从头往后走,没有 back(),插入只能"在当前位置之后"。它是最节省内存的链表(每节点只存一个指针),适合"只要顺序遍历"的场合:

#include <algorithm>
#include <forward_list>
#include <iostream>

int main() {
    std::forward_list<int> fl{3, 1, 4};
    fl.push_front(0);          // 单链表只能从头部插入
    // 在值为 1 的元素后面插入 2
    auto it = std::find(fl.begin(), fl.end(), 1);
    fl.insert_after(it, 2);
    fl.remove(3);              // 删除所有值为 3 的节点
    for (int x : fl) std::cout << x << " ";
    std::cout << "\n";         // 0 1 2 4
    return 0;
}

因为只能单向走,insert_after 和 erase_after 都是在"某个节点之后"操作,remove 直接按值批量删除。它还有 before_begin() 这个特殊迭代器,指向首元素之前,用于在头部插入。说实话,日常业务里 forward_list 用得不多——大部分"只需要单向遍历"的场景,vector 因为缓存友好反而更快;但面试常问,而且它是理解"为什么双向链表需要两个指针"的好教材。

6. 复杂度对比与选择指南

把四个容器放到一张表里看:

* list 的中间插入 O(1) 前提是已持有目标位置的迭代器,找位置本身还是 O(n)。选择建议:默认用 vector;需要两端操作又有下标访问需求,用 deque;需要频繁中间插入且能持有迭代器,或要"遍历中删除",用 list;追求最小内存且只单向遍历,用 forward_list。别忘了复杂度之外还有缓存友好性:元素少、操作简单时,vector 往往连 list 的"优势场景"都能打赢。

最后给一个"选择困难终结者"的实战:用 deque 实现一个双端任务队列,模拟"从两头同时处理任务":

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> tasks;
    tasks.push_back("写代码");
    tasks.push_back("写测试");
    tasks.push_back("写文档");
    tasks.push_front("紧急修复");   // 新来的紧急任务插队到队头

    while (!tasks.empty()) {
        // 交替从两头取任务,模拟两个处理者
        std::string job;
        if (tasks.size() % 2 == 0) { job = tasks.front(); tasks.pop_front(); }
        else                       { job = tasks.back();  tasks.pop_back();  }
        std::cout << "处理: " << job << "\n";
    }
    return 0;
}

这个例子里 push_front 让紧急任务 O(1) 插队,pop_front/pop_back 让两端取出都是 O(1)——换成 vector,insert(begin()) 会变成 O(n),数据量大时差距立刻显现。选容器的本质,就是看你的"热点操作"是哪些,让最频繁的操作复杂度最低;如果两个方案复杂度一样,就选更简单、更缓存友好的那个。

7. 总结与练习

一句话回顾:vector 是默认选择,连续内存、随机访问快;deque 是"两头都能动"的 vector;list 擅长"持有迭代器时的 O(1) 插入删除"和"遍历中删除";forward_list 是省内存的单链表。选择时先列热点操作,再查表对复杂度,而不是凭感觉。迭代器失效规则同样重要:vector 最脆弱,deque 两端操作安全,list 系列最宽容。

练习题:

• 用 deque 模拟一个"回文检查器":从两头同时 pop 字符比较,验证字符串是否回文。
• 给 list 写一个"每隔一个节点删除一个"的函数(提示:遍历时小心迭代器失效,先用 std::next(it) 保存后继)。
• 对比实验:向 vector 和 list 的头部各插入 10 万个元素,用 <chrono> 计时,亲眼看看 O(n) 和 O(1) 的差距。

💡 记住一条经验法则:只有当"测量或分析"证明 vector 不够用(或语义上必须用链表)时才换容器。过早优化是万恶之源,但选错容器的复杂度差异,往往是数量级的。