温州网站关键字优化,网站规划总结,数据分析系统,郑州团购网站建设文章目录 一、优先级队列是什么#xff1f; 二、如何使用优先级队列 1、优先级队列容器用法 2、为什么容器本身无序#xff1f; 三、什么是仿函数#xff1f; 1. 什么是仿函数#xff1f; 2. 仿函数的优势 四、仿函数如何使用#xff1f; 1、重载operator()函数 2、运用第…文章目录 一、优先级队列是什么 二、如何使用优先级队列 1、优先级队列容器用法 2、为什么容器本身无序 三、什么是仿函数 1. 什么是仿函数 2. 仿函数的优势 四、仿函数如何使用 1、重载operator()函数 2、运用第三个参数模板 3、大小堆切换 大堆测试代码 小堆测试代码 4、头文件总代码 五、什么是容器适配器 前言 本文主要介绍了优先级队列是什么如何使用优先级队列并且由优先级队列引出仿函数从中认识仿函数最后了解一下什么是适配器。 一、优先级队列是什么 1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素)。
3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作
empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素
5. 标准容器类vector和deque都满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。
6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
二、如何使用优先级队列
1、优先级队列容器用法
我们从cplusplus网站中看一些优先级队列的结构 优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。 我们用一段代码来带大家初步认识
#include vector
#include queue
#include functional // greater算法的头文件
void TestPriorityQueue()
{// 默认情况下创建的是大堆其底层按照小于号比较vectorint v{3,2,7,6,0,4,1,9,8,5};priority_queueint q1;for (auto e : v)q1.push(e);cout q1.top() endl;// 如果要创建小堆将第三个模板参数换成greater比较方式priority_queueint, vectorint, greaterint q2(v.begin(), v.end());cout q2.top() endl;
} 这段代码打印的结果是堆顶的数据如果是大堆那么堆顶就是最大的反之堆顶的数据就是最小的。
打印结果 打印第一行就是默认大堆的结果第二行是我们增加了参数模板改成了小堆。 我们看到这里第一想法就是可以用优先级队列来排序是的没错但是你将容器中的数打印出来却发现并不是有序的只是符合了大堆的性质
2、为什么容器本身无序 我们都知道了他是大堆每次取出顶部元素之后删除顶部元素再进行向下调整取出第二个最大元素所以我们就知道有序的不是容器本身而是我们从堆顶依次取出的数据。 我们用默认大堆将堆顶的数据依次取出查看顺序结果
while (!q1.empty())
{cout q1.top() ;q1.pop();
}
cout endl; 三、什么是仿函数 在我们上面优先级队列使用时我们想将默认大堆改成小堆因此我们添加了额外的两个参数模板其中控制大小堆变化的就是第三个参数greaterint 在C中仿函数或函数对象是通过重载operator()的类实例来模拟函数行为的对象。这种特性使得C的对象可以像函数一样被调用从而为编程提供了极大的灵活性和强大的功能。
1. 什么是仿函数
仿函数是一个类它定义了一个或多个operator()成员函数使得其对象可以像普通函数那样被调用。仿函数通常用于以下场景
作为算法的比较函数作为算法的操作函数存储状态或属性使行为可定制
2. 仿函数的优势
与普通函数和函数指针相比仿函数具有以下优势
状态维护仿函数可以持有状态每次调用可以根据状态改变行为。内联调用由于仿函数是通过对象调用的编译器可以轻易地将其内联减少调用开销。高度定制可以通过对象的属性来调整其行为。
四、仿函数如何使用
我们通过对优先级队列的实现写出一个可以作为比较函数的仿函数
我们先在头文件中写出默认大堆的代码实现优先级队列的几个功能 代码如下
#pragma once
#includequeue
#includevector
#includealgorithmusing namespace std;
namespace bit
{templateclass T, class Container vectorTclass priority_queue{public:void adjust_up(size_t child){size_t parent (child - 1) / 2;while (child 0){if (_con[parent] _con[child]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child parent * 2 1;while (child _con.size()){if ( child 1 _con.size() _con[child] _con[child 1]){child;}if (_con[parent]_con[child]){swap(_con[parent], _con[child]);parent child;child parent * 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);}bool empty(){return _con.empty();}const T top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}
我们这个是默认大堆的创建对象之后每次取出堆顶的数据只会是最大了那个数据因为我们在向上调整或者向下调整时全都是大堆的比较方法所以我们只能用大堆。
那我们应该如何切换小堆呢
1、重载operator()函数
我们重载operator()函数使其成为一个可以被调用的可以比较大小的函数
代码如下 templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass greater{public:bool operator()(const T x, const T y){return x y;}};
在这两个比较函数中less就是大堆的比较方法而greater就是小堆的比较方法
2、运用第三个参数模板
我们知道我们所写的operator()函数是在类里面所以这个类就可以作为一个类模板去使用
我们在第三个参数模板中写一个比较模板用来切换在向上调整或者向下调整中的比较方法进而去切换大小堆
模板代码
templateclass T, class Container vectorT,class ComparelessT
我们将第三个模板命名为Compare ,后面调用less类的比较方法在默认情况下仍是大堆。
接下来我们可以把向上调整或者向下调整中的比较方法修改成我们的仿函数。
先创建Compare对象
Compare com;
接下来开始替换(向上调整举例)
void adjust_up(size_t child)
{Compare com;size_t 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;}}
}
我们可以看到我们在if判断语句中的比较已经改成了我们的仿函数。
3、大小堆切换
当我们想要从大堆切换小堆时我们直接改变第三个参数模板的底层类就可以了将lessT修改成greaterT即可(头文件和源文件的模板都要修改)
templateclass T, class Container vectorT,class ComparegreaterT
我们进行一下测试
大堆测试代码
void Test_priority_queue()
{bit::priority_queueint,vectorint,lessint pq;pq.push(2);pq.push(7);pq.push(1);pq.push(8);while (!pq.empty()){ cout pq.top() ;pq.pop();}cout endl;
}
int main()
{Test_priority_queue();return 0;
}
打印结果 小堆测试代码
void Test_priority_queue()
{bit::priority_queueint,vectorint,greaterint pq;pq.push(2);pq.push(7);pq.push(1);pq.push(8);while (!pq.empty()){ cout pq.top() ;pq.pop();}cout endl;
}
int main()
{Test_priority_queue();return 0;
}
打印结果 4、头文件总代码
#pragma once
#includequeue
#includevector
#includealgorithmusing namespace std;
namespace bit
{//仿函数切换大堆小堆仿函数作为一个类型可以作为类模板使用templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass greater{public:bool operator()(const T x, const T y){return x y;}};templateclass T, class Container vectorT,class ComparegreaterTclass priority_queue{public:void adjust_up(size_t child){Compare com;size_t 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[parent], _con[child]);parent child;child parent * 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);}bool empty(){return _con.empty();}const T top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
} 五、什么是容器适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。
