21. list 与 deque：何时不用 vector

文章目录

• 引言
• 一、容器选择的三维决策模型
• 二、`std::list`：双向链表
• • 2.1 结构特征
  • 2.2 `list` 的杀手锏操作
  • 2.3 `list` 的迭代器极稳定
• 三、`std::deque`：双端队列
• • 3.1 结构特征
  • 3.2 `deque` 的基本用法
  • 3.3 `deque` 的迭代器稳定性
• 四、三容器对比表
• 五、决策逻辑
• • 5.1 默认使用 `vector`
  • 5.2 在什么情况下换 `deque`
  • 5.3 在什么情况下换 `list`
• 六、性能实测
• 七、容器选择的快速决策表
• 总结

本系列为《C++深度修炼：基础、STL源码与多线程实战》第21篇
前置条件：理解std::vector（第19篇），了解链表的基本概念

引言

第19篇我们详细拆解了std::vector——它是 C++ 中使用最频繁的容器。但"最频繁"不等于"永远正确"。在某些场景下，vector的操作复杂度会从 O(1) 退化为 O(n)，而list和deque恰好填补了这些场景。

本文不打算穷尽list和deque的每一个成员函数——那些用法和vector高度相似。本文聚焦于选择逻辑：在什么场景下，你应该放下vector，拿起list或deque？

---

一、容器选择的三维决策模型

选容器时，你需要在三个维度上做权衡：

维度	含义	典型问题
访问模式	你最频繁访问哪些位置？	随机访问？头/尾？遍历？
修改模式	你最频繁在哪些位置增删？	末尾？开头？中间？
内存特征	元素的存储布局和迭代器稳定性	是否连续？迭代器何时失效？

vector、list、deque刚好覆盖了这三个维度的不同折中。

---

二、std::list：双向链表

2.1 结构特征

#include<list>#include<iostream>intmain(){std::list<int>lst={1,2,3,4,5};// 基本操作和 vector 一样lst.push_back(6);// 末尾添加——O(1)lst.push_front(0);// 开头添加——O(1) ← vector 做不到！lst.pop_back();lst.pop_front();// 但是——没有 operator[]！不能 lst[2] = 10// 只能通过迭代器访问autoit=lst.begin();std::advance(it,2);// 前进 2 步——这是 O(n)std::cout<<*it<<'\n';// 3}

std::list是一个双向链表。每个节点存储一个元素 + 两个指针（前驱和后继）。

内存布局（概念）： [head] ↔ [1|prev|next] ↔ [2|prev|next] ↔ [3|prev|next] ↔ [tail]

2.2list的杀手锏操作

#include<list>#include<iostream>intmain(){std::list<int>lst1={1,2,3};std::list<int>lst2={10,20,30};// splice：O(1) 将整个 list2 移动到 lst1 的指定位置autoit=lst1.begin();std::advance(it,1);// 指向 2lst1.splice(it,lst2);// lst2 的全部元素插入到 2 之前// lst1: 1, 10, 20, 30, 2, 3// lst2: (空)for(autox:lst1)std::cout<<x<<' ';// 1 10 20 30 2 3std::cout<<'\n';std::cout<<"lst2.size() = "<<lst2.size()<<'\n';// 0}

splice是 O(1) 操作——它只修改几个指针，不拷贝任何元素。这是vector永远无法做到的（vector的插入/移动需要拷贝或移动元素本身）。

2.3list的迭代器极稳定

std::list<int>lst={1,2,3,4,5};autoit=std::next(lst.begin(),2);// 指向 3lst.push_front(0);// 开头插入lst.push_back(6);// 末尾插入lst.erase(lst.begin());// 删除开头// it 仍然有效，仍然指向 3std::cout<<*it<<'\n';// 3

在vector中，任何插入/删除都可能使所有迭代器失效（因为可能触发扩容/搬迁）。在list中，只有被删除的节点的迭代器才失效——其他迭代器全部保持有效。

---

三、std::deque：双端队列

3.1 结构特征

deque（“deck”）常被误解为"双端 vector"。更准确的理解是：deque 是分块连续存储的序列容器。

deque 的内部结构（概念）： 中控器（指针数组）： [ptr0] [ptr1] [ptr2] [ptr3] ... ↓ ↓ ↓ ↓ [块0] [块1] [块2] [块3] ← 每个块是固定大小的连续数组 1 2 3 4 5 6 7 8 9 10 11 12

实现细节在第50篇深入，现在只需要知道效果：

• 支持operator[]随机访问——O(1)，但比vector多一次间接跳转（先找块，再在块内偏移）
• 在两端插入/删除是 O(1)——不会像vector那样触发大规模元素搬迁
• 在中间插入/删除仍然是 O(n)——需要移动该块及后续块中的元素
• 元素不保证完全连续——不能直接把deque.data()传给 C API

3.2deque的基本用法

#include<deque>#include<iostream>intmain(){std::deque<int>dq={1,2,3,4,5};dq.push_back(6);// O(1)dq.push_front(0);// O(1) ← vector 没有这个dq.pop_back();dq.pop_front();// 支持随机访问dq[2]=99;std::cout<<dq[2]<<'\n';// 99std::cout<<dq.at(3)<<'\n';// 4（带边界检查）// 但是 dq.data() 返回什么？// deque 不保证元素完全连续——没有 data() 方法}

3.3deque的迭代器稳定性

deque的迭代器稳定性介于vector和list之间：

• 在两端插入：所有迭代器有效（push_front/push_back不会搬迁已有元素）
• 在中间插入/删除：所有迭代器可能失效
• 被删除元素的迭代器：一定失效

---

四、三容器对比表

维度	std::vector	std::deque	std::list
内存布局	单块连续	分块连续	链表节点（不连续）
随机访问[]	O(1) 最快	O(1) 稍慢（一次间接）	不支持
末尾插入	O(1) 均摊	O(1)	O(1)
末尾删除	O(1)	O(1)	O(1)
开头插入	O(n)	O(1)	O(1)
开头删除	O(n)	O(1)	O(1)
中间插入	O(n)	O(n)	O(1)*
中间删除	O(n)	O(n)	O(1)*
.data()	有（连续）	无（分块）	无
遍历速度	极快（缓存友好）	中等	慢（指针跳跃，缓存不友好）
内存开销	极小（纯数据）	小（中控器 + 块）	大（每个元素 2 个指针）
迭代器失效	扩容时全部失效	中间插入/删除时全部失效	仅被删除的节点失效
元素大小影响	小	小	大——大元素导致更多缓存缺失

*list的中间插入/删除是 O(1) 的前提是你已经有了指向该位置的迭代器。找到这个位置仍然需要 O(n) 的遍历。

---

五、决策逻辑

5.1 默认使用vector

vector是 C++ 中性能最好的通用容器——连续内存带来的缓存友好性在绝大多数场景下碾压其他容器。除非你有明确的理由选别的，否则用vector。

5.2 在什么情况下换deque

两个明确信号：

1. 需要频繁在开头插入/删除：vector在开头插入是 O(n)，deque是 O(1)。如果你要实现一个队列（FIFO），deque是std::queue的默认底层容器。

2. 元素很大，且扩容搬迁的代价很高：deque扩容时不需要搬迁已有的元素（它只是分配一个新块）。如果你的元素是 100+ 字节的大对象，deque的插入比vector更稳定——不会出现某次push_back突然触发 O(n) 搬迁的"卡顿"。

// 信号 1：生产者-消费者队列std::deque<Message>message_queue;voidproduce(constMessage&msg){message_queue.push_back(msg);// 生产者追加到末尾}Messageconsume(){automsg=std::move(message_queue.front());message_queue.pop_front();// 消费者从开头取——O(1)returnmsg;}

5.3 在什么情况下换list

三个明确信号：

1. 需要在中间频繁插入/删除（而且你已经有了迭代器）：比如实现 LRU Cache——每次访问一个元素时要把它移到列表头。

2. 需要 splice 级别的操作：把一个列表的整段迁移到另一个列表——list::splice是 O(1)，而用vector模拟需要 O(n) 拷贝。

3. 迭代器绝对不能失效：你持有指向元素的迭代器作为"句柄"，希望在任意其他修改操作后仍然能用这个句柄访问元素。

// 信号 1 + 信号 3：LRU Cache 的简化骨架#include<list>#include<unordered_map>#include<string>template<typenameK,typenameV>classLRUCache{public:explicitLRUCache(size_t cap):capacity_(cap){}V*get(constK&key){autoit=map_.find(key);if(it==map_.end())returnnullptr;// 移到最前面——O(1) spliceitems_.splice(items_.begin(),items_,it->second);return&it->second->second;}voidput(constK&key,constV&value){autoit=map_.find(key);if(it!=map_.end()){it->second->second=value;items_.splice(items_.begin(),items_,it->second);return;}if(items_.size()>=capacity_){map_.erase(items_.back().first);items_.pop_back();}items_.emplace_front(key,value);map_[key]=items_.begin();}private:size_t capacity_;std::list<std::pair<K,V>>items_;std::unordered_map<K,typenamedecltype(items_)::iterator>map_;};

LRU Cache 是list+unordered_map的组合经典——list 提供 O(1) 的 splice/erase/push_front，unordered_map 提供 O(1) 的查找。

---

六、性能实测

#include<vector>#include<deque>#include<list>#include<iostream>#include<chrono>#include<random>constintN=100'000;template<typenameContainer>voidbenchmark(constchar*name,Container&c){// 在开头插入 N 个元素autostart=std::chrono::high_resolution_clock::now();for(inti=0;i<N;++i){c.insert(c.begin(),i);}autoend=std::chrono::high_resolution_clock::now();std::cout<<name<<": "<<std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()<<" ms\n";}intmain(){{std::vector<int>v;benchmark("vector 开头插入",v);}{std::deque<int>d;benchmark("deque 开头插入",d);}{std::list<int>l;benchmark("list 开头插入",l);}}

$ g++ -std=c++17 -O2 bench_containers.cpp && ./a.out vector 开头插入: 约 1200 ms ← O(n²) 在 100k 上的显现 deque 开头插入: 约 2 ms ← O(1) list 开头插入: 约 3 ms ← O(1)

再看遍历速度（同样是 100k 个int）：

vector 遍历: 约 0.3 ms ← 连续内存，缓存预取 deque 遍历: 约 3 ms ← 分块内存，预取受限 list 遍历: 约 15 ms ← 指针追逐，每次访问可能 cache miss

同一个数据规模，不同的操作模式，性能差异可达 1000 倍。这就是为什么容器选择是最重要的性能决策之一。

---

七、容器选择的快速决策表

按你需要的主操作查表：

你最频繁的操作	推荐容器	原因
push_back+pop_back+ 随机访问	vector	栈模式，vector 最优
push_back+pop_front（FIFO 队列）	deque	两端 O(1)
push_front+pop_back（FILO 栈）	vector或deque	都可以，vector 更简单
push_front+pop_front	deque或list	deque 更快（缓存友好）
中间 splice / 移动大段元素	list	splice 是 O(1)
纯遍历（读 + 改）	vector	缓存友好性碾压
持有长期有效的元素句柄	list	迭代器极稳
传给 C API（需要data()）	vector	唯一保证连续

---

总结

vector、deque、list的选择不是"哪个更好"——是**“哪个更适合你的访问和修改模式”**：

1. vector是默认选择：连续内存的缓存友好性在各种操作中都是巨大的隐性加速——末尾操作 O(1)，遍历极快，可以传给 C API
2. 当你需要开头 O(1) 插入/删除时考虑deque：它填补了"需要随机访问 + 需要头尾双端操作"这个 niche——比 list 更缓存友好，比 vector 在两端更快
3. 当（且仅当）你需要中间 O(1) 插入/删除或 splice 时，选list：前提是你已经有了迭代器，否则找到插入位置本身就需要 O(n) 遍历。大部分场景下vector+ 末尾操作 + 最后排序/反转是更好的替代
4. 一个 100k 个元素的数据集上，错误的容器选择可以导致 1000 倍的性能差异——容器选择是一行代码（声明类型）的决策，但影响贯穿整个程序
5. 如果你不确定，用vector——然后测量。如果 profile 显示瓶颈在容器操作上，再考虑换

下一篇——迭代器：统一的数据访问接口——我们将揭开迭代器的面纱。vector::iterator、list::iterator、deque::iterator是三个完全不同的类型，但它们共享一致的语法。正是这种"一致的不一致"让 STL 算法可以一次编写、对所有容器通用。

---

📝动手练习：

1. 对vector、deque、list分别测试：在开头插入 10 万个元素 vs 在末尾插入 10 万个元素，比较用时
2. 实现上文中的 LRU Cache 类，添加单元测试验证 get/put 行为和容量限制
3. 用list::splice把两个 list 交替合并（a1, b1, a2, b2, …），分析为什么 splice 不拷贝元素
4. 对比三个容器在遍历 100 万个 int 时的性能，用<chrono>精确测量
5. 测试deque的迭代器稳定性：在两端插入/删除后，检查中间元素的迭代器和引用是否仍然有效