当前位置：首页 > news >正文

C++ 浅谈之 STL Deque

news 2025/7/5 21:37:10

C++ 浅谈之 STL Deque

HELLO，各位博友好，我是阿呆 🙈🙈🙈

这里是 C++ 浅谈系列，收录在专栏 C++ 语言中 😜😜😜

本系列阿呆将记录一些 C++ 语言重要的语法特性 🏃🏃🏃

OK，兄弟们，废话不多直接开冲 🌞🌞🌞

一 🏠 概述

简单介绍

Deque 双端队列，在头尾对元素进行删除和插入快，中间插入或删除效率低，支持元素随机访问。它是动态分段连续空间组合而成，无 capacity 概念，可即时增加新空间（不会像 vector 因旧空间不足而重新申请）

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JUQ3IwMY-1675954090283)(E:\2022年MD文档\2023 年 MD文档\二月\浅谈系列\C++ 浅谈之 STL Deque.assets\1675951423972.png)]$

和 Vector 维护连续线性空间不同，Deque 维护多段连续空间，各段间不一定连续，Deque 用数组（名为 map）存储着各连续空间首地址 👦👦👦

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fJg1VBNk-1675954090285)(E:\2022年MD文档\2023 年 MD文档\二月\浅谈系列\C++ 浅谈之 STL Deque.assets\1675951752739.png)]$

迭代器

分段存储提高了两端添加，删除的效率，也使容器迭代器实现更复杂，有如下 2 个问题

① 迭代器遍历时，须确认各连续空间在 map 数组中的位置 👨‍🚀👨‍🚀👨‍🚀

② 迭代器在某个连续空间时，须知道是否处于空间边缘（一旦前进，需要跳到下一个连续空间）

//迭代器内部实现如上，包含 4 个指针
template<class T,...>
struct __deque_iterator{...T* cur; //指向当前正在遍历的元素T* first; //指向当前连续空间的首地址T* last; //指向当前连续空间的末尾地址map_pointer node; //T** 二级指针, 指向 map 数组中存储的指向当前连续空间的指针
}

借助这四个指针和运算符重载，使迭代器可以在分段连续空间遍历 🎅🎅🎅

//当迭代器处于当前连续空间边缘的位置时，如果继续遍历，就需要跳跃到其它的连续空间中，该函数可用来实现此功能
void set_node(map_pointer new_node){node = new_node;//记录新的连续空间在 map 数组中的位置first = *new_node; //更新 first 指针//更新 last 指针，difference_type(buffer_size())表示每段连续空间的长度last = first + difference_type(buffer_size());
}//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}//重载前置 ++ 运算符
self & operator++(){++cur;//处理 cur 处于连续空间边缘的特殊情况if(cur == last){//调用该函数，将迭代器跳跃到下一个连续空间中set_node(node+1);//对 cur 重新赋值cur = first;}return *this;
}//重置前置 -- 运算符
self& operator--(){//如果 cur 位于连续空间边缘，则先将迭代器跳跃到前一个连续空间中if(cur == first){set_node(node-1);cur == last;}--cur;return *this;
}

二 🏠 核心

底层实现

STL Deque 有如下的定义代码 👇👇👇

//_Alloc为内存分配器
template<class _Ty,class _Alloc = allocator<_Ty>>
class deque{...
protected:iterator start; // map 数组中首个连续空间的信息iterator finish; //map 数组中最后一个连续空间的信息map_pointer map;
...
}

内部空间布局，如下图所示 🐳🐳🐳

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gbKUALTy-1675954090286)(E:\2022年MD文档\2023 年 MD文档\二月\浅谈系列\C++ 浅谈之 STL Deque.assets\1675951491835.png)]$