【C++】深度解析：用 C++ 模拟实现 priority_queue类，探索其底层实现细节(仿函数、容器适配器)

2024-08-22 16:12
文章标签 c++ 实现 函数 深度 模拟 解析 底层 探索 容器 细节 适配器 queue priority

本文主要是介绍【C++】深度解析：用 C++ 模拟实现 priority_queue类，探索其底层实现细节(仿函数、容器适配器)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

⭐前言

✨堆

✨容器适配器

✨仿函数

⭐priority_queue介绍 

⭐priority_queue参数介绍 

⭐priority_queue使用

⭐priority_queue实现

✨仿函数实现

✨堆的向上调整和向下调整 

✨完整代码 

⭐前言

✨堆

堆是一种特殊的树形数据结构，通常以二叉树的形式实现，具有特定的排序特性。堆分为两种类型：最大堆和最小堆。 

具体可以参见这篇文章：【数据结构】二叉树-CSDN博客

✨容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

STL标准库中stack和queue的底层结构：

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

✨仿函数

在 C++ 中，仿函数通常指的是一种行为类似于函数的对象，即可以像调用函数那样被调用的对象。这种对象通常包含一些数据成员，并且重载了括号运算符 operator()，从而允许以函数的方式调用。

看下面这段代码：

class Less
{
public:bool operator()(const int& x, const int& y){return x < y;}
};int main()
{Less lesscom;cout << lesscom(1, 2) << endl;return 0;
}

代码中定义了Less类，重载()，函数中定义了x、y两个参数，当x小于y就返回true，否则返回false。

        在main函数中创建了Less类的对象，如果想要调用重载()，常规的调用方法应该是对象名.函数名(参数列表)。但因为重载()函数是可以省略.operator()，所以当我们使用这个仿函数对象的时候，使用的方法就和调用一个函数一样，这就是仿函数的使用。

仿函数的特点

  1. 可调用性：仿函数通过重载括号运算符 operator() 实现了可调用性，使得我们可以像调用普通函数一样调用仿函数对象。
  2. 状态：仿函数可以拥有自己的数据成员（状态），这意味着每次调用仿函数时，它可以访问这些成员变量，这与普通的函数不同，后者通常不保留状态。
  3. 多态性：由于仿函数是对象，它们可以被用作多态的一部分，这意味着你可以通过基类指针或引用调用派生类的仿函数对象。

仿函数的用途

  • 算法参数化：仿函数可以作为算法的参数，使得算法可以根据传入的不同仿函数表现出不同的行为。
  • 事件处理：在 GUI 编程中，可以使用仿函数作为事件处理器，当事件发生时调用相应的仿函数对象。
  • 模板编程：在 C++ 模板编程中，仿函数经常被用作模板参数，以实现泛型算法

⭐priority_queue介绍 

priority_queue 是 C++ 标准库中的一个容器适配器，它提供了基于最大堆或最小堆的数据结构来实现优先队列的功能。priority_queue 自动维护元素的排序，使得每次插入或删除操作都能保持堆的性质。

priority_queue 底层将vector作为默认容器，默认情况下为大堆。

⭐priority_queue参数介绍 

template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > 
class priority_queue;

  1. T: 这是优先队列中存储的元素类型。例如，如果存储整数，则 T 将是 int。

  2. Container: 这是一个可选的模板参数，用来指定底层容器的类型。默认情况下，std::priority_queue 使用 std::vector<T> 作为其底层容器。但是，可以选择任何支持随机访问迭代器的容器类型，例如 std::deque<T>。请注意，底层容器必须支持 push_back 和 pop_back 操作。

  3. Compare: 这也是一个可选的模板参数，用来指定元素之间的比较方式。默认情况下，使用 std::less<typename Container::value_type>，这意味着对于类型 T 的元素，将使用 < 运算符进行比较，创建出一个大堆。如果要创建一个最小堆，则可以使用 std::greater<typename Container::value_type>。

我们其实可以发现 priority_queue使用的是容器适配器模式，底层是vector和deque这样支持下标随机访问等操作的容器；并且还是要了仿函数 Compare来控制比较逻辑，使用less<typename Container::value_type>创建出大堆，使用greater<typename Container::value_type> 创建出小堆。

priority_queue的一个完整的声明如下：

priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

⭐priority_queue使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成 堆 的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

注意： 默认情况下priority_queue是大堆。 

函数声明接口说明
priority_queue()/priority_queue(first, last）构造一个空的优先级队列
empty()检测优先级队列是否为空，是返回true，否则返回 false
top()返回优先级队列中最大(最小元素)，即堆顶元素
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素，即堆顶元素

 默认情况下，priority_queue是大堆。

#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{// 默认情况下，创建的是大堆，其底层按照小于号比较vector<int> v{3,2,7,6,0,4,1,9,8,5};priority_queue<int> q1;for (auto& e : v)q1.push(e);cout << q1.top() << endl;// 如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;
}

 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

class Date
{
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);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;
}

⭐priority_queue实现

✨仿函数实现

仿函数就是它的对象可以想函数一样去使用，本质上是重载了()。

//仿函数//控制大堆
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;}
};

 实际上的使用应该像下面图中第二行那样，但是重载之后就省略了。

✨堆的向上调整和向下调整 

大体上的逻辑和堆的实现相同，但是使用仿函数控制比较的逻辑，使得优先队列不仅对基础数据类型，如int，有效，也对想Date这样的日期类型有效（需要重载了>和<）。

//向上调整
void adjust_up(size_t child)
{Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//向下调整
void adjust_down(size_t parent)
{Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

✨完整代码 

//仿函数//控制大堆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;}};//less 控制为大堆template<class T,class Container = vector<T>,class Compare = less<T>>class priority_queue{public://向上调整void adjust_up(size_t child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1) ;}//向下调整void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};

____________________

⭐感谢你的阅读，希望本文能够对你有所帮助。如果你喜欢我的内容，记得点赞关注收藏我的博客，我会继续分享更多的内容。⭐

这篇关于【C++】深度解析：用 C++ 模拟实现 priority_queue类，探索其底层实现细节(仿函数、容器适配器)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1096754。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2