2.7、讲讲deque实现原理

deque的底层数据结构

分段连续存储模型

• • 非连续内存结构：由多个**固定大小的缓冲区（buffer）**组成，每个缓冲区内部是连续内存块，缓冲区之间在物理内存中不连续
• • **中控器（map）**机制：
  • • 本质：指针数组（非STL的map容器），存储各缓冲区起始地址
  • • 特性：中控器自身是连续内存，通过指针数组实现逻辑连续的线性空间假象
• • 缓冲区大小策略：
  • • 动态适配元素大小：元素≤512字节时，缓冲区大小≈512/sizeof(T)；否则为1个元素大小
  • • 目标：平衡空间利用率与管理开销

随机访问实现原理

元素定位算法

索引i元素定位步骤：
1. 计算缓冲区编号：node_index = i / buffer_size
2. 计算缓冲区内偏移：offset = i % buffer_size
3. 通过map[node_index]获取缓冲区首地址，+offset得到元素指针

迭代器核心设计

• • 迭代器结构体关键成员：
  • • cur：当前元素指针
  • • first：当前缓冲区首地址
  • • last：当前缓冲区尾地址（未包含）
  • • node：当前缓冲区对应的map节点指针
• • 缓冲区切换函数：

void set_node(map_pointer new_node) {
  node = new_node;         // 更新map节点
  first = *new_node;       // 获取新缓冲区首地址
  last = first + buffer_size(); // 计算新缓冲区尾地址
}

插入与删除操作特性

双端操作优化

• • 头尾插入/删除：
  • • 均摊时间复杂度：O(1)
  • • 实现逻辑：空间不足时动态分配新缓冲区，更新map指针，避免整体元素搬移
• • 中间操作劣势：
  • • 时间复杂度：O(N)（需移动插入点至某一端的所有元素）
  • • 迭代器影响：操作后所有相关迭代器失效
  • • 优化策略：插入时选择移动较少元素的一侧（insert_aux算法）

扩容机制解析

缓冲区扩容

• • 触发条件：当前缓冲区空间不足
• • 操作：分配新缓冲区，插入到map对应位置，更新首尾指针

map扩容

• • 触发条件：map指针数组空间不足
• • 操作优势：
  • • 仅复制指针而非元素，开销远低于vector扩容
  • • 新map大小通常为原大小的2倍加2（预留头尾扩展空间）

容器特性对比与应用场景

核心优势：融合vector随机访问与list双端操作效率，适合队列/栈场景（STL中stack/queue默认底层容器）

数据结构本质

• • 二维动态数组模型：map（指针数组）+ 多个buffer（元素数组）
• • 逻辑连续假象：通过迭代器封装物理非连续内存，提供线性访问接口

性能特征

• • 双端操作：均摊O(1)（优于vector头部操作）
• • 随机访问：O(1)（通过迭代器缓冲区切换实现）
• • 空间效率：优于list（无额外链表节点开销）
  本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
  （加入我的知识星球，免费获取账号，解锁所有文章。）