跳到主要内容 C++ STL 双端队列 deque 与优先级队列模拟实现及仿函数详解 | 极客日志
C++ 算法
C++ STL 双端队列 deque 与优先级队列模拟实现及仿函数详解 C++ STL 双端队列 deque 底层原理基于分段连续空间与中控数组，支持头尾高效操作且随机访问性能接近 vector。优先级队列基于堆结构实现，默认使用 vector 作为容器，通过仿函数自定义比较规则以支持最大堆或最小堆逻辑。详细解析了 deque 迭代器设计、性能对比，并模拟实现了优先级队列的向上调整与向下调整算法，展示了仿函数在自定义类型排序中的应用。
清酒独酌 发布于 2026/2/6 更新于 2026/4/18 C++ STL 双端队列 deque 与优先级队列模拟实现及仿函数详解
前言
本文聚焦 STL 双端队列（deque）与优先级队列的底层实现，深度剖析 deque 如何融合 vector 与 list 的优势，通过中控数组与分段缓存实现高效头尾操作；结合优先级队列的堆结构，详解仿函数在自定义排序规则中的核心作用。通过模拟实现代码与性能对比，帮助大家理解容器适配器。
一、deque（双端队列）
1.1 list 和 vector 的优缺点
在前面介绍栈和队列的原型时我们为 deque 埋下了伏笔，那么 deque 是什么？
deqe 是 vector 和 list 的结合体，存在 deque 的原因便是 list 和 vector 有着鲜明的优缺点。
在 deque 的官方文档的接口中，我们发现 deque 既有 vector 的下标随机访问也有 list 的头插/头删两种容器的独特接口。
vector 的优点：
尾插尾删效率不错，支持高效的下标随机访问
物理空间连续，所以高速缓存利用率高
缺点：
空间需要扩容，扩容有一些代价（效率和空间浪费）
头部和中间的插入删除效率低
list 的优点：
按需申请释放空间，不需要扩容
支持任意位置的插入删除
缺点：
不支持下标的随机访问
1.2 deque 的原理介绍
dque（双端队列）：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。
deque 并不是真正连续的空间 ，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下图所示：
图 1：
图 2：
我们定义一段一段的 buff 小数组，当 buff 满了再开辟 buff 数组，这样便可以解决链表的缓存效率低下的问题，我们再定义一个中控数组 (本质是指针数组) ptr，在该数组中我们将第一个 buff 数组的地址存放在其的中间，因为我们如果头插时便可以直接在中控数组中间位置的前一个位置存放新的 buff 地址即可，同理尾插也是如此。当中控数组满了再进行扩容。
当我们定义好了 deque 的大框架后，那么怎么获取第 i 个数据？
我们可以用 i / N 就知道该数据是存放在哪个 buff 里面，再将 i % N 就知道了在该 buff 的哪个位置，在图 1 中，假设我们要寻找的数据在 ptr 中的第 x 位置，那么我们便可以 ptr[x] 便知道了该数据存放在第 x 个 buff 里面，ptr[x][y] 便可以知道其存放在 buff 的哪个位置了
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其'整体连续'以及随机访问的假象，落在了 deque 的迭代器身上（也就是 operator++ 和 operator-- 两个运算符重载身上），因此 deque 的迭代器设计就比较复杂。
dque 的缓存区，中控器和迭代器的关系如下：
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
那 deque 是如何借助其迭代器维护其假想连续的结构呢？
deque::begin() 传回迭代器 start，deque::end() 传回迭代器 finish，迭代器由 cur（指向当前位置），first（指向当前 buff 的开始位置），last（当前 buff 的的结束位置），node（指向中控区存放该数组的地址）组成，如下图：
实现 operator++ 时，我们需要判断当前 buff 有没有走完，如果没有走完，直接++cur 即可，走完，我们则需找到下一个 buff，通过 node+1 再解引用就找到了下一个 buff 的开始位置，因此我们将迭代器的 first 指向找到的新的 buff 即可，由于 buff 的大小是固定的，因此 last 也找到了，再让 cur 指向第一个位置便大功告成了！
分析：deque 的头插尾插效率高于 vector 和 list，在 list 中，每次开辟空间只开一个，而 deque 每次开一段空间（一次申请 40 个字节的空间比 10 次申请 4 个字节的效率高），而 vector 的扩容代价太大（在后期扩容时，需要将原来的大量数据拷贝下来，并且还需要释放旧空间），在 deque 中如果 buff 没满插入数据即可，满了就新开 buff，再将迭代器的四个指针指向的位置改下即可，只有在中控区满的时候需要扩容（扩容代价很低，只拷贝指针）
总结：
deque 的头插尾插效率很高，更甚于 vector 和 list
下标随机访问效率还不错，但是比不上 vector（需要调用几个函数并且还有运算）
在中间插入删除数据（所有的 buff 均向前/向后移动，效率和 vector 一样，如果只让当前 buff 移动，那么就需要对当前 buff 扩容，导致每个 buff 大小都不一样，会导致下标 +[] 效率更低）的效率为 O(n)
但正是因为栈和队列不需要对中间元素进行处理，所以我们使用 deque 作为其的默认适配容器便很合理了
1.3 deque 和 vector 的性能对比 我们在 release 版本下，对比 100w 数据下，deque 和 vector 的排序。
void test_op1 () srand (time (0 ));
const int N = 1000000 ;
deque<int > dq;
vector<int > v;
for (int i = 0 ; i < N;++i){
auto e = rand () + i;
v.push_back (e);
dq.push_back (e);
}
int begin1 = clock ();
sort (v.begin (), v.end ());
int end1 = clock ();
int begin2 = clock ();
sort (dq.begin (), dq.end ());
int end2 = clock ();
printf ("vector:%d\n" , end1 - begin1);
printf ("deque:%d\n" , end2 - begin2);
}
总结：在 release 下，大量访问数据时，deque 的性能约 vector 的 1/2。
二、优先级队列
2.1 定义及其作用 我们根据官方文档便知道优先级队列也是一个容器适配器，那么其是什么及其作用又是什么？
总结： 优先级队列是一种抽象数据类型（ADT） ，它类似普通队列，但核心特性是：元素的处理顺序不由插入顺序决定（与普通队列不同） ，而是由元素的'优先级'决定 。每次从队列中取出的，总是当前优先级最高的元素（优先级可自定义，例如'数值大的优先'或'数值小的优先'），由于其核心的特性类似于堆，而堆的底层是 vector 实现的（不断地需要根据父亲节点算孩子即下标访问），且 deque 的随机访问效率低于 vector，因此容器默认 vector。
在这些接口中我们需要注意 top 和 pop 接口，其要取优先级高的数据（默认是大的数据优先级高，如果想让小的数据优先级高，可以使用仿函数）
2.2 模拟实现优先级队列 由于其的机制类似于堆，那么我们将用堆来实现优先级队列。
namespace hxx {
template <class T , class Container = vector<int >>
class PriorityQueue {
public :
void push (const T& x) {}
void pop () {}
void top () {}
private :
Container _con;
};
}
实现插入数据的底层逻辑和堆的插入数据一模一样 (物理结构是数组，逻辑结构是堆，因此我们需要把数组的元素一层一层放到堆上，即完全二叉树，其节点下标关系满足 left child=parent*2+1)：
先将元素插入到堆的末尾，即最后一个孩子之后
插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适位置即可 (向上调整算法)
void AdjustUp (int child) int parent = (child - 1 ) / 2 ;
while (child > 0 ){
if (_con[child] > _con[parent]){
swap (_con[child], _con[parent]);
child = parent;
parent = (child - 1 ) / 2 ;
} else {
break ;
}
}
}
那么向上调整算法搞定了，push 接口便轻松实现了，当然向上调整算法也不需要我们进行底层的搭建，在 C++ 算法库中便已经实现了。
将堆顶元素与堆中最后一个元素进行交换
删除堆中的最后一个元素
将堆顶元素向下调整到满足堆的特性为止
void AdjustDown (int parent) size_t child = parent * 2 + 1 ;
Compare com;
while (child < _con.size ()){
if (child + 1 < _con.size () && _con[child + 1 ] > _con[child]){
++child;
}
if (_con[child] > _con[parent]){
swap (_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1 ;
} else {
break ;
}
}
}
这些接口实现完后，那么简单的优先级队列便已经实现好了。
注意：如果对二叉树的性质不熟悉的，可以阅读相关数据结构文章。
2.3 仿函数 可是如果按照上面的写法，那么优先级队列也就写死了，只允许大的优先级高。那么是否要实现两个堆，这样是否过于冗余，因此在前面官方文档的介绍中埋下的伏笔——仿函数便起到了点睛之笔。
仿函数（也称为函数对象）并不是函数，本质是一个重载了 operator() 的类 —— 它的对象可以像普通函数一样被调用，因此得名'仿函数'。
template <class T >
class Less {
public :
bool operator () (int x, int y) return x < y;
}
};
int main () int > lessFunc;
cout << lessFunc (1 , 2 ) << endl;
cout << lessFunc.operator ()(1 , 2 ) << endl;
}
在 STL 算法（如 sort、priority_queue）中，替代普通函数作为比较/操作规则。例如在代码中的 Less 和 Greater，用于控制优先级队列的堆结构（最大堆/最小堆）
class Greater {
public :
bool operator () (int a, int b) const return a > b;
}
};
vector<int > v = {3 , 1 , 4 , 1 , 5 , 9 };
sort (v.begin (), v.end (), Greater ());
普通函数无法携带成员变量（状态），但仿函数可以通过类的成员变量保存状态，在多次调用中共享信息
class Counter {
private :
int _count = 0 ;
public :
void operator () () "调用次数：" << _count << endl;
}
};
Counter cnt;
cnt ();
cnt ();
仿函数可以作为模板参数，让算法/数据结构的行为更具通用性（如 priority_queue 模板中通过 Compare 仿函数支持自定义比较）
在实际实现优先级队列时，我们并不需要实现仿函数，直接用即可。
int main () int , vector<int >, greater<int >> pq;
pq.push (4 );
pq.push (1 );
pq.push (5 );
pq.push (7 );
pq.push (9 );
while (!pq.empty ()){
cout << pq.top () << " " ;
}
cout << endl;
return 0 ;
}
一般场景仿函数不需要我们写，那么既然有一般情况，就会有特殊情况需要我们写仿函数，这里特殊情况分为两种：
类类型不支持比较大小
支持比较大小，但是比较的逻辑不是你想要的
在之前学类和对象的过程我们便模拟实现了日期类这个小项目，这里优先级队列里仿函数是支持日期内里面实现的比大小。
class Date {
friend ostream& operator <<(ostream& _cout, const Date& d);
public :
Date (int year = 1900 , int month = 1 , int day = 1 ) :_year(year),_month(month),_day(day){}
bool operator <(const Date& d) const {
return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day);
}
bool operator >(const Date& d) const {
return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day);
}
private :
int _year;
int _month;
int _day;
};
ostream& operator <<(ostream& _cout, const Date& d){
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
class DateLess {
public :
bool operator () (Date* p1, Date* p2) return *p1 < *p2;
}
};
int main () 1. push (Date (2025 , 12 , 7 ));
q1. push (Date (2025 , 12 , 7 ));
q1. push (Date (2025 , 12 , 7 ));
cout << q1. top () << endl;
while (!q1. empty ()){
cout << q1. top () << " " ;
}
cout << endl;
return 0 ;
}
因此哪怕是自定义类型，但是只要我们在该类中实现了内部的比大小即可，但是如果我们在自定义类中没有重载比大小，那么我们就需要自己实现仿函数。
int main () 2. push (new Date (2025 , 12 , 7 ));
q2. push (new Date (2025 , 12 , 7 ));
q2. push (new Date (2025 , 12 , 7 ));
cout << *q2. top () << endl;
q2. pop ();
cout << *q2. top () << endl;
q2. pop ();
cout << *q2. top () << endl;
}
欧吼，我们发现两次输出的结构并不相同，我们思考下为什么每次比较大小的结果不一样，仔细观察下代码，我们发现，由于每次 new 的地址每个大小是随机的，所以比较结果各不相同，那么这时候我们就需要自己写仿函数实现我们想要的比大小的逻辑。
class DateLess {
bool operator () (Date* d1, Date* d2) return *d1 < *d2;
}
};
int main () 2. push (new Date (2025 , 12 , 7 ));
q2. push (new Date (2025 , 8 , 25 ));
q2. push (new Date (2025 , 9 , 30 ));
cout << *q2. top () << endl;
q2. pop ();
cout << *q2. top () << endl;
q2. pop ();
cout << *q2. top () << endl;
return 0 ;
}
三、总结 希望读完本文可以帮助读者更好了解栈和队列的底层逻辑！
