C++算法
C++ STL 容器适配器 stack、queue、priority_queue 详解与实现
C++ STL 中的三种容器适配器：stack、queue 和 priority_queue。详细阐述了它们的标准接口、模拟实现原理及底层容器选择策略（如 deque）。内容涵盖优先队列的大顶堆与小顶堆配置方法、仿函数的定义与应用，以及 deque 双端队列的底层存储结构与性能分析。通过代码示例展示了适配器的基本操作与自定义实现逻辑，帮助读者深入理解 STL 组件的设计思想。
C++ STL 中的三种容器适配器：stack、queue 和 priority_queue。详细阐述了它们的标准接口、模拟实现原理及底层容器选择策略（如 deque）。内容涵盖优先队列的大顶堆与小顶堆配置方法、仿函数的定义与应用，以及 deque 双端队列的底层存储结构与性能分析。通过代码示例展示了适配器的基本操作与自定义实现逻辑，帮助读者深入理解 STL 组件的设计思想。
// stack::top
#include<iostream>
#include<stack>
int main(){
std::stack<int> mystack;
mystack.push(10);
mystack.push(20);
mystack.top()-=5;
std::cout << "现在栈顶的元素是：" << mystack.top() << '\n';
return 0;
}
// stack::push/pop
#include<iostream>
#include<stack>
int main(){
std::stack<int> mystack;
for(int i = 0; i < 5;++i){
mystack.push(i);
}
std::cout << "从栈中弹出元素..." << std::endl;
while(!mystack.empty()){
std::cout << mystack.top() << ' ';
mystack.pop();
}
std::cout << '\n';
return 0;
}
// stack::size
#include<iostream>
#include<stack>
int main(){
std::stack<int> myints;
std::cout << "初始状态下的 size: " << myints.size() << '\n';
for(int i = 0; i < 5; i++){
myints.push(i);
}
std::cout << "入栈元素后的 size: " << myints.size() << '\n';
myints.pop();
std::cout << "出栈元素后的 size: " << myints.size() << '\n';
return 0;
}
// stack::empty
#include<iostream>
#include<stack>
int main(){
std::stack<int> mystack;
int sum(0);
for(int i=1;i<=10;i++) mystack.push(i);
while(!mystack.empty()){
sum += mystack.top();
mystack.pop();
}
std::cout << "total: " << sum << '\n';
return 0;
}
// queue::front
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
myqueue.push(77);
myqueue.push(16);
myqueue.front()-= myqueue.back();
std::cout << "现在的队头元素是：" << myqueue.front() << '\n';
return 0;
}
// queue::back
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
myqueue.push(12);
myqueue.push(75);
myqueue.back()-= myqueue.front();
std::cout << "现在的队尾元素是：" << myqueue.back() << '\n';
return 0;
}
// queue::push/pop
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
int myint;
std::cout << "请输入一些整数（输入 0 以结束）：\n";
do{
std::cin >> myint;
myqueue.push(myint);
}while(myint);
std::cout << "myqueue 队列中的内容是： ";
while(!myqueue.empty()){
std::cout << ' '<< myqueue.front();
myqueue.pop();
}
std::cout << '\n';
return 0;
}
// queue::size
#include<iostream>
#include<queue>
int main(){
std::queue<int> myints;
std::cout << "初始状态下的 size: " << myints.size() << '\n';
for(int i = 0; i < 5; i++){
myints.push(i);
}
std::cout << "入队元素后的 size: " << myints.size() << '\n';
myints.pop();
std::cout << "出队元素后的 size: " << myints.size() << '\n';
return 0;
}
// queue::empty
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
int sum(0);
for(int i = 1; i <=10; i++){
myqueue.push(i);
}
while(!myqueue.empty()){
sum += myqueue.front();
myqueue.pop();
}
std::cout << "队列中的元素之和是：" << sum << '\n';
return 0;
}
// priority_queue::top
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> mypq;
mypq.push(10);
mypq.push(20);
mypq.push(15);
std::cout << "现在优先队列中的队头的元素是：" << mypq.top() << '\n';
return 0;
}
// priority_queue::push/pop
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> mypq;
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
std::cout << "从优先队列中出队元素..." << std::endl;
while(!mypq.empty()){
std::cout << mypq.top() << " ";
mypq.pop();
}
std::cout << '\n';
return 0;
}
// priority_queue::size
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> myints;
std::cout << "初始状态下的 size: " << myints.size() << '\n';
for(int i = 0; i < 5; i++){
myints.push(i);
}
std::cout << "入队元素后的 size: " << myints.size() << '\n';
myints.pop();
std::cout << "出队元素后的 size: " << myints.size() << '\n';
return 0;
}
// priority_queue::empty
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> mypq;
int sum(0);
for(int i = 1; i <=10; i++){
mypq.push(i);
}
while(!mypq.empty()){
sum += mypq.top();
mypq.pop();
}
std::cout << "队列中的元素之和是:" << sum << '\n';
return 0;
}
在 C++ 中，若要显式将 priority_queue 定义为小顶堆（元素值越小，优先级越高），需通过模板参数指定底层容器和比较器。具体点说就是显式指定使用默认的 vector 底层容器和使用标准库 <functional> 提供的 greater<T> 比较器。
注：上面博主没有写错哦，就是要显示指定上面的两种的东西，可能你会有疑问底层容器使用的就是默认的 vector 啦，我还显示指定个蛋啊！
哈哈 O(∩_∩)O，这是因为 priority_queue 的模板参数列表要求：当你指定第三个参数（比较器）时，必须同时指定第二个参数（底层容器）。若不指定比较器：可省略所有模板参数，默认使用 vector 和 less。若指定比较器：必须显式指定底层容器，否则会导致编译错误。
总结：如果你想让优先队列定义为'小顶堆'，可以使用下面的定义方法：std::priority_queue<T, std::vector<T>, std::greater<T>> 或 std::priority_queue<T, std::deque<T>, std::greater<T>>
代码案例：使用优先队列定义'小顶堆'（存储内置类型）
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int main(){
/*------------------测试 1：优先队列创建的'大顶堆'------------------*/
cout << "---------测试 1：优先队列创建的'大顶堆'---------" << endl;
/*-------------第一步：创建'大顶堆'的一个优先队列-------------*/
//1.先创建一个 vector 容器（目的：为优先队列进行赋值）
vector<int> v{3,2,7,6,0,4,1,9,8,5};
//2.使用默认的方式创建一个优先队列（不指定：'底层容器'+'比较器'）
priority_queue<int> q1;
//3.为优先队列进行赋值
for(auto& it : v)
q1.push(it);
/*-------------第二步：输出优先队列的队头元素验证'大顶堆'-------------*/
cout << "优先的队列的队头元素是：" << q1.top() << endl;
/* 注意事项： * 默认情况下，priority_queue 使用 vector 作为底层容器，less<int> 作为比较器 * 这会构建一个'大顶堆'（即：堆顶元素为最大值） * 创建大顶堆：优先级最高的元素是最大值 *
/*------------------测试 2：优先队列创建的'小顶堆'------------------*/
cout << "---------测试 1：优先队列创建的'小顶堆'---------" << endl;
/*-------------第一步：创建'小顶堆'的一个优先队列-------------*/
/*---------方式一：逐个插入方式初始化---------*/
priority_queue<, vector<>, greater<>> q2;
(& it : v){
q(it);
}
cout << << q() << endl;
在 priority_queue 中存储 自定义类型 的数据时，用户需要在自定义类型中重载 < 或 > 运算符，以明确元素的优先级规则。
核心逻辑：priority_queue（优先级队列）本质是堆结构，需要根据元素的优先级来调整堆的顺序。对于自定义类型，编译器无法默认判断元素的大小关系因此必须通过 运算符重载 或 自定义比较器 告诉编译器如何比较元素的优先级。
常见场景：
< 运算符，定义'当前对象小于另一个对象'的逻辑。> 运算符，并搭配 std::greater<自定义类型> 比较器。代码案例：使用优先队列定义'小顶堆'（存储内置类型）
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
/*-------------------------定义日期类-------------------------*/
class Date{
public:
/*-------------第一部分：定义友元函数-------------*/
//1.实现：'<<运算符重载函数'
friend ostream& operator<<(ostream& out, const Date& d){
out << d._year << "-" << d._month << "-" << d._day;
return out;
}
/*-------------第二部分：定义成员函数-------------*/
//1.实现：'全缺省构造函数'
Date(int year = 1900, int month = 1, int day = 1):_year(year),_month(month),_day(day){}
//2.实现：'<运算符重载函数'
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);
}
//3.实现：'>运算符重载函数'
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:
_year;
_month;
_day;
};
{
priority_queue<Date> q1;
q((,,));
q((,,));
q((,,));
cout << q() << endl;
priority_queue<Date, vector<Date>, greater<Date>> q2;
q((,,));
q((,,));
q((,,));
cout << q() << endl;
;
}
#pragma once
#include<deque>
namespace mySpace {
template<class T, class Container = std::deque<T>>
class stack {
private:
Container _con;
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_back(); }
const T& top() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
};
}
#pragma once
#include<deque>
namespace mySpace {
template<class T, class Container = std::deque<T>>
class queue {
private:
Container _con;
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
const T& front() const { return _con.front(); }
const T& back() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
};
}
#pragma once
#include<vector>
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) { return x < y; }
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) { return x > y; }
};
namespace mySpace {
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_queue {
private:
Container _con;
void AdjustUp(int child) {
Compare com;
int parent = (child - 1) / 2;
while(child > 0) {
if(com(_con[parent], _con[child])) break;
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - ) / ;
}
}
{
Compare com;
minchild = parent * + ;
(minchild < _con.()) {
(minchild + < _con.() && (_con[minchild + ], _con[minchild])) minchild++;
((_con[parent], _con[minchild])) ;
std::(_con[minchild], _con[parent]);
parent = minchild;
minchild = parent * + ;
}
}
:
{
_con.(x);
(_con.() - );
}
{
(()) ;
std::(_con[], _con[_con.() - ]);
_con.();
();
}
{ _con[]; }
{ _con.(); }
{ _con.(); }
};
}
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include"Stack.h"
#include"Queue.h"
#include"PriorityQueue.h"
using namespace std;
void test01(){
cout << "------------测试栈的功能------------" << endl;
mySpace::stack<int, list<int>> stk;
stk.push(1); stk.push(2); stk.push(3); stk.push(4);
cout << "入栈之后，此时栈顶的元素是：" << stk.top() << endl;
stk.pop();
cout << "出栈之后，此时栈顶的元素是：" << stk.top() << endl;
cout << "------------测试队列的功能------------" << endl;
mySpace::queue<int> que;
que.push(1); que.push(2); que.push(); que.();
cout << << que.() << endl;
cout << << que.() << endl;
que.();
cout << << que.() << endl;
cout << << que.() << endl;
}
{
cout << << endl;
mySpace::priority_queue<, vector<>, Greater<>> pqu;
pqu.(); pqu.(); pqu.(); pqu.(); pqu.();
(!pqu.()){
cout << pqu.() << ;
pqu.();
}
cout << endl;
}
{
();
();
;
}
在自定义的 priority_queue 类模板中，AdjustUp 和 AdjustDown 方法的参数之所以从原始的数组指针和长度简化为 child 或 parent 下标，是因为：类模板内部已经封装了底层容器（如：vector），无需再通过外部传入数据数组和长度。
原始参数设计的问题：这种设计需要用户手动传入数组和长度，耦合性高且不通用。当 priority_queue 封装了底层容器（如：vector）后，这些数据应属于类的内部状态，无需外部暴露。
修改后参数简化的原因：封装底层容器，类模板中定义了成员变量 Container _con，用于存储堆元素。AdjustUp 和 AdjustDown 直接通过 _con 访问元素，无需外部传入数组指针。自动获取容器长度，通过 _con.size() 获取当前元素个数，替代旧版本的 n 参数，避免手动传递长度可能导致的越界问题。依赖类模板参数，比较逻辑通过类模板参数 Compare 实现（仿函数 com），而非硬编码比较规则，提升了代码的灵活性（可适配大堆/小堆）。
在代码中使用 std::swap(_con[child], _con[parent]) 替换原始的 Swap(&a[child], &a[parent])，主要是因为：底层容器的封装方式改变 和 C++ 标准库的易用性。
原始代码的问题：a 是外部传入的数组指针，需要通过 &a[child] 获取元素地址，再传递给自定义的 Swap 函数进行交换。这种方式依赖原始数组的内存布局，且 Swap 函数可能需要手动实现，耦合性高且不通用。
修改后使用 std::swap 的原因：自定义的 priority_queue 类模板中，元素存储在成员变量 _con（底层容器，如：vector<T>）中。_con[child] 和 _con[parent] 直接通过容器的 operator[] 接口访问元素，无需通过指针操作原始内存。
仿函数（Functor）：也称为函数对象（Function Object），是一种在 C++ 中通过类或结构体实现的可调用实体。仿函数的核心特点是 重载了 operator() 运算符，使得类的对象可以像普通函数一样被调用。仿函数是 C++ 中 '以类模拟函数' 的重要机制，这种机制结合了面向对象的封装性和函数的灵活性，在 STL 和算法中有着广泛应用。
仿函数的核心特点：
状态或参数，这使得它比普通函数更灵活。使用时：
Add add;
int result = add(3, 5);
通过在类中定义 operator() 运算符，使得该类的对象可以像函数一样被调用：
class Add {
public:
int operator()(int a, int b) {
return a + b;
}
};
在自定义算法中，通过仿函数将逻辑抽象出来，提高代码复用性。
template<class Compare>
void BubbleSort(int* a, int n, Compare com){
if(com(a[j], a[j - 1])){
swap(a[j-1], a[j]);
}
}
谓词：用于筛选元素（如：find_if、remove_if）
class IsEven {
public:
bool operator()(int x) const {
return x % 2 == 0;
}
};
比较器：通过仿函数指定排序规则（如：升序/降序）
#include<algorithm>
#include<vector>
using namespace std;
class Greater {
public:
bool operator()(int a, int b) const {
return a > b;
}
};
int main(){
vector<int> nums = {3, 1, 4, 2};
sort(nums.begin(), nums.end(), Greater());
return 0;
}
| 特性 | 普通函数 | 仿函数 |
|---|---|---|
| 调用方式 | 直接调用 | 通过对象调用 |
| 状态存储 | 无法存储状态 | 可通过成员变量存储状态 |
| 类型安全 | 弱 | 强 |
| 可复用性 | 低 | 高 |
| 重载 | 通过不同参数列表 | 通过多个 operator() 实现 |
| 性能 | 取决于编译器 | 容易 |
假如我们想要对一批数据使用冒泡排序同时实现升序和降序排序，该怎么做呢？可能有些小伙伴会说：这很简单的啦，把原来的冒泡排序代码复制一份，修改其中的比较逻辑就行啦！
哈哈，小伙伴的回答简单粗暴没毛病，但是呢会导致重复代码冗余，违背了 DRY（Don't Repeat Yourself）原则。
为解决这个问题，我们可以引入 仿函数（Functor） 来实现比较逻辑的抽象，避免硬编码比较规则，从而提升代码的灵活性和可维护性。
代码案例：使用仿函数使冒泡排序同时实现升序和降序排序
#include<iostream>
using namespace std;
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) const {
return x > y;
}
};
template<class Compare>
void BubbleSort(int* a, int n, Compare com){
for(int i = 1; i <= n - 1; i++){
for(int j = 1; j <= n - i; j++){
if(com(a[j], a[j - 1])){
swap(a[j - 1], a[j]);
}
}
}
}
int main{
Less<> lessFunc;
Greater<> greaterFunc;
a[] = {, , , , , , , , };
n = (a)/(a[]);
(a, n, lessFunc);
(a, n, greaterFunc);
;
}
容器适配器（Container Adapter）：是 C++ 标准库中的一种特殊容器，它不直接提供完整的数据存储功能，而是通过封装其他底层容器（如：vector、deque、list）并限制其接口，来实现特定的数据结构。这种设计遵循适配器模式，将已有容器的功能转换为用户期望的接口。
核心特点：
deque），所有操作都委托给该容器执行push/pop/top），隐藏底层容器的其他功能，确保数据结构的语义正确性deque（兼顾效率与灵活性）| 适配器 | 默认底层容器 | 可选底层容器 | 数据结构 | 主要操作 | 典型用途 |
|---|---|---|---|---|---|
| stack | deque | vector, list | 栈 (LIFO) | push, pop, top | 函数调用栈，撤销操作 |
| queue | deque | list | 队列 (FIFO) | push, pop, front, back | 任务调度，消息队列 |
| priority_queue | vector | deque | 优先队列 | push, pop, top | 任务优先级调度，Dijkstra 算法 |
适配器 queue：底层容器既可以是标准容器类模板（如：deque、list 等），也能是其他专门设计的容器类。但这类底层容器至少需支持以下操作：front、back、pop_front、push_back、size、empty。
在 C++ 标准库中，deque 和 list 这两种标准容器类满足上述全部要求，而容器 vector 却不满足上面的要求。因此，默认情况下，若创建 queue 时未手动指定底层容器，STL 会自动使用 deque 作为其底层容器。也可以显示指定使用 list 作为底层容器。但是不能使用 vector 作为底层容器。
适配器 priority_queue：底层容器既可以是标准容器类模板（如：vector、deque 等），也可以是其他专门设计的容器类。但该容器至少需支持以下操作：支持随机访问迭代器，以便内部能通过迭代器操作维持堆结构；需实现 front()、push_back()、pop_back()、size()、empty()。
在 C++ 标准库中，vector 和 deque 这两种标准容器类满足上述全部要求，而容器 list 却不满足上面的要求。因此，默认情况下，若创建 priority_queue 时未手动指定底层容器，STL 会自动使用 vector 作为其底层容器。也可以显示指定使用 deque 作为底层容器。但是不能使用 list 作为底层容器。
既然 vector 和 deque 都可以作为 priority_queue 的底层容器，那为什么默认选择 vector 而不是 deque 呢？这主要与 priority_queue 的核心操作特性和两种容器的性能差异有关。 priority_queue 的核心操作（如：push、pop）依赖 随机访问迭代器 和 下标操作 来调整堆结构。 vector 的优势：支持连续内存存储和随机访问迭代器，通过下标 operator[] 访问元素的时间复杂度为 O(1)。 dque 的劣势：虽然也支持随机访问迭代器，但内部采用分段连续存储（缓冲区链表），迭代器的底层实现更复杂，下标访问的性能略低于 vector。
使用容器适配器时我们需要注意以下两点的内容：
deque（双端队列）：是 C++ 标准模板库（STL）中的一种序列式容器，全称是 double-ended queue。它允许在容器的头部和尾部高效地执行元素的插入、删除和访问操作，同时支持随机访问（通过下标访问元素）。
总结：它结合了 vector 和 list 的部分优点。
dque 的核心特点：
dque 的底层实现通常通过 分块数组（分段连续存储） 实现：由多个固定大小的数组块（buffer）组成，每个块存储部分元素。通过一个中央控制映射表（map）管理，记录每个缓冲区的地址和边界，保证逻辑上的连续性。 总结：这种结构使得 deque 在头部和尾部扩展时只需分配新的缓冲区，无需移动已有元素，适合需要频繁双端操作的场景。
dque 的底层并非真正的连续内存空间，而是由多个分段连续的小内存块（缓冲区）拼接而成。从逻辑上看，它类似于一个动态的二维数组，通过巧妙的设计让用户感知到'整体连续'的访问体验，但实际上每个小段内存是连续的，段与段之间通过指针连接。 为了维护这种连续空间和随机访问的假象，deque 的迭代器承担了关键角色。由于其内存结构的特殊性，deque 的迭代器需要处理跨段访问的逻辑，因此设计比 vector 的迭代器更复杂。 具体来说，迭代器需要记录：当前所在的缓冲区、缓冲区中的位置、以及指向下一个/上一个缓冲区的指针，从而在遍历或随机访问时能够正确跳转至目标位置。 简单来说：deque 通过分段连续存储 + 复杂迭代器的组合，实现了双端高效操作与随机访问的平衡，尽管底层物理空间不连续，但逻辑上呈现为一个连续的队列。
| 特性 | vector | deque |
|---|---|---|
| 内存连续性 | 连续存储 | 分段连续存储（非连续） |
| 随机访问性能 | 高（缓存利用率好） | 稍低（跨缓冲区时需指针跳转） |
| 头部操作效率 | O(n)（需移动所有元素） | O(1) |
| 扩容策略 | 按需翻倍（整体复制） | 新增缓冲区（局部扩展） |
| 适用场景 | 随机访问多、尾部操作多 | 双端操作多、长度频繁变化 |
dque 的优势在于：
dque 存在一个致命缺陷：不适合频繁遍历。由于其底层是分段连续的内存块，遍历时迭代器需要频繁检测是否到达当前缓冲区的边界，并跳转至下一段缓冲区，这会导致额外的性能开销，遍历效率低于 vector 和 list。 在需要线性遍历的场景中，deque 的这一特性可能成为瓶颈，因此实际开发中，当需要线性数据结构时，开发者通常优先选择 vector（适合随机访问和尾部操作）或 list（适合双向遍历和中间插入/删除），而 deque 的应用场景相对较少，目前，deque 的典型应用是作为 STL 中 stack（栈）和 queue（队列）的底层数据结构，充分利用其双端操作高效的特性，同时规避了频繁遍历的需求。
stack（栈）：是一种后进先出（LIFO）的线性数据结构。因此只要具备 push_back() 和 pop_back() 操作的线性容器，都可以作为其底层容器。例如：vector 和 list。 queue（队列）：是一种先进先出（FIFO）的线性数据结构。只需支持 push_back() 和 pop_front() 操作的容器即可作为底层容器。例如：list。 但在 STL 中，stack 和 queue 默认选择 deque 作为底层容器，主要原因如下：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online