在家做的打字兼职的网站,用网站源码做网站,官网微信,厦门网站建设方案策划介绍完了stack和queue的介绍以及模拟的相关内容后#xff1a;C初阶#xff1a;容器适配器介绍、stack和queue常用接口详解及模拟实现 接下来进行priority_queue的介绍以及模拟#xff1a; 文章目录 1.priority_queue的介绍和使用1.1priority_queue的初步介绍1.2priority_que…介绍完了stack和queue的介绍以及模拟的相关内容后C初阶容器适配器介绍、stack和queue常用接口详解及模拟实现 接下来进行priority_queue的介绍以及模拟 文章目录 1.priority_queue的介绍和使用1.1priority_queue的初步介绍1.2priority_queue的使用1.3进一步补全介绍 2.仿函数/函数对象讲解3.模拟priority_queue文件规划和一览3.1模拟priority_queuepriority_queue.h3.2测试test.cpp) 1.priority_queue的介绍和使用
1.1priority_queue的初步介绍 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的默认是大堆 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素) 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 1.2priority_queue的使用 函数声明接口说明priority_queue()构造一个空的优先级队列priority_queue(first, last)构造一个优先级队列包含范围为[first, last)的元素empty()检测优先级队列是否为空是返回true否则返回falsetop()返回优先级队列中最大最小元素即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大最小元素即堆顶元素
#includeiostream
#includevector
#includequeue
using namespace std;int main()
{priority_queueint pq;//这里默认是大堆pq.push(3);pq.push(2);pq.push(6);pq.push(9);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;priority_queueint, vectorint, greaterint pq2;//这里传入一个类型greaterint(马上就讲了)pq2.push(3);pq2.push(2);pq2.push(6);pq2.push(9);while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;return 0;
}1.3进一步补全介绍
优先队列priority_queue是一个特殊的队列它根据元素的优先级进行排序而不是按照它们被插入的顺序。在C中优先队列通常使用堆heap数据结构来实现这使得它能够在O( l o g n logn logn)的时间复杂度内对元素进行插入和删除操作并能够以O(1)的时间复杂度获取队列中的最大或最小元素。
以下是优先队列priority_queue的一些重要特性和接口
构造函数 priority_queueType, Container, Compare创建一个优先队列对象其中Type是元素类型Container是底层容器类型默认为vectorCompare是元素比较的函数对象类型默认为std::less用于最大堆。priority_queue(first, last)使用范围为[first, last)的迭代器构造一个优先队列。 默认行为 默认情况下优先队列是最大堆即最大元素位于堆顶。可以通过自定义比较函数对象来改变这一行为从而创建最小堆或者基于自定义的优先级规则进行排序。 底层实现 在C中优先队列通常使用vector或deque作为底层容器并通过堆算法来维护元素的顺序。 2.仿函数/函数对象讲解 函数对象Functor也称为仿函数Function Object是C中的一种重要概念它是一个行为类似函数的对象可以被当作函数来调用。在C中函数对象可以以类的形式实现其实是个类重载operator()运算符从而可以像函数一样被调用。 函数对象可以提供比普通函数更多的灵活性和功能它可以保存状态、具有成员变量、可以在构造函数中接受参数等。函数对象通常用于STL中的算法、容器和适配器中它们可以作为参数传递给算法用于自定义排序、查找、比较等操作。 namespace FunctionObject
{templateclass Tclass less{public:bool operator()(const T a, const T b){return a b;}};templateclass Tclass greater{public:bool operator()(const T a, const T b){return a b;}};
}void test1()
{int a 1;int b 10;FunctionObject::greaterint big;//定义一个对象cout big(a, b) endl;//只看big(a, b) 跟函数调用长得一样
}int main()
{test1();return 0;
}3.模拟priority_queue
文件规划和一览 priority_queue.h:用来实现queue test.cpp:进行测试 3.1模拟priority_queuepriority_queue.h
#pragma oncenamespace MyPriority_queue
{templateclass Tclass less{public:bool operator()(const T a, const T b){return a b;}};templateclass Tclass greater{public:bool operator()(const T a, const T b){return a b;}};templateclass T, class Container vectorT, class Compare lessT//默认是大堆class priority_queue{public:void adjust_up(int child){Compare com;int father (child - 1) / 2;//得到父节点的索引while (child 0)//再怎么向上也只能到0{if (com(_con[father], _con[child])){swap(_con[father], _con[child]);childfather;father (child - 1) / 2;//更新两个节点}else{break;}}}void adjust_down(int father){Compare com;int child father * 2 1;//假设左孩子较大while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child 1]))//右孩子存在且比左孩子大{child;}if(com(_con[father], _con[child])){swap(_con[father], _con[child]);fatherchild;child father * 2 1;//更新两个节点}else{break;}}}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}//先交换后再向下调整void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}3.2测试test.cpp)
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
#includevector
#includequeue
using namespace std;#includepriority_queue.hint main()
{MyPriority_queue::priority_queueint pq;//这里默认是大堆pq.push(3);pq.push(2);pq.push(6);pq.push(9);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;priority_queueint, vectorint, MyPriority_queue::greaterint pq2;pq2.push(2);pq2.push(6);pq2.push(9);while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;return 0;
}后天开学今天也是才到学校正月十五就一人在宿舍过了 到此为止容器的部分我们大都讲完啦大家敬请期待接下来的知识分享吧
