当前位置:首页 » 《资源分享》 » 正文

【C++】—— priority_queue与仿函数

22 人参与  2024年09月30日 13:20  分类 : 《资源分享》  评论

点击全文阅读


【C++】—— priority_queue 与仿函数

1 priority_queue 介绍2 priority_queue 的使用2.1 priority_queue 的函数接口2.2 priority_queue 的使用 3 仿函数3.1 什么是仿函数3.2 仿函数的应用 4 需自己写仿函数的情况4.1 类类型不支持比较大小4.2 类中支持的比较方式不是我们想要的 5 priority_queue 的模拟实现

1 priority_queue 介绍

  
p r i o i r t prioirt prioirt_ q u e u e queue queue 文档介绍

优先级队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大(或最小)的此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于定部的元素)优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类, q u e u e queue queue 提供一组特定的成员函数来访问其元素。元素从特定容器的"尾部"弹出,其称为优先队列的顶部。底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
函数名检测容器是否为空
e m p t y empty empty()检测容器是否为空
s i z e size size()返回容器中有效元素个数
f r o n t front front()返回容器中第一个元素的引用
p u s h push push_ b a c k back back()在容器尾部插入数据
p o p pop pop_ b a c k back back()删除容器尾部元素
标准容器类 v e c t o r vector vector 和 d e q u e deque deque 满足这些需求。默认情况下,如果没有为特定的 p r i o r i t y priority priority_ q u e u e queue queue 类实例化特定容器类,则使用 vector需要支持随机访问的迭代器,以便始终在内部保存堆结构。容器适配器通过在需要时自动调用算法函数 make_heappush_heappop_heap 来自动完成此操作

  

2 priority_queue 的使用

2.1 priority_queue 的函数接口

  优先级队列默认使用 v e c t o r vector vector 作为其底层存储数据的容器,在 v e c t o r vector vector 上又使用了堆算法将 v e c t o r vector vector 中元素构成堆的结构,因此 p r i o r i t y priority priority_ q u e u e queue queue 就是 堆,所有需要用到堆的地方,都可以考虑使用 p r i o r i t y priority priority_ q u e u e queue queue。
  注意:默认情况下 p r i o r i t y priority priority _ q u e u e queue queue 是大堆

函数声明接口说明
p r i o r i t y priority priority_ q u e u e queue queue()构造一个空的优先级队列
e m p t y empty empty()检测优先级队列是否为空,是返回 t r u e true true,否则返回 f a l s e false false
t o p top top()返回优先级队列中最大(最小)元素,即堆定元素
p u s h push push( x x x)在优先级队列中插入元素 x x x
p o p pop pop()删除优先级队列中最大(最小)元素,即堆顶元素

  

2.2 priority_queue 的使用

在这里插入图片描述

  优先级队列一个有三个模板参数:class Tclass Container = vector<T>class Compare = less<typename Container::value_type>
  第一个参数是确定优先级队列的存储类型;第二个参数确定 p r i o r i t y priority priority_ q u e u e queue queue 底层容器的结构,默认为 v e c t o r vector vector,priority_queue也是一种适配器模式;第三个参数确定是建大堆还是小堆,默认是大堆,建立小堆的话要自己传递一个仿函数。

  我们来简单使用一下 p r i o r i t y priority priority_ q u e u e queue queue

void test1(){priority_queue<int> pq;pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}

运行结果:

在这里插入图片描述

  
  我们再来试试小堆

void test2(){priority_queue<int, vector<int>, greater<int>> pq;pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);cout << " ";while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}

在这里插入图片描述

  但第三个模板参数class Compare = less<typename Container::value_type> 是什么东西呢?为什么传 g r e a t e r < i n t > greater<int> greater<int> 就从大堆变小堆了呢?这其实是一个仿函数,我们慢慢来介绍。
  
  

3 仿函数

3.1 什么是仿函数

  什么是仿函数呢?仿函数本质是一个 !它里面重载了 o p e r a t o r operator operator() 函数(即函数调用操作符:func()中的())。
  
  比如现在我想写两个整型的比较的仿函数,可以怎么写呢?

class Less{public:bool operator()(int x, int y){return x < y;}};

   可以看到它没有成员变量;其实仿函数大部分都是空类 ,都是没有成员变量的
  
  我们将其改造一下就成了模板,可以支持多种类型的比较。但并不是说仿函数就是模板,仿函数类指的是它重载了 o p e r a t o r ( ) operator() operator() 函数的类

template<class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};

  那我们又如何调用呢?如下:

int main(){Less<int> LessFunc;cout << LessFunc(1, 2) << endl;return 0}

  按照我们以前的理解,LessFunc(1, 2)是个函数调用,LessFunc是一个函数名或函数指针。但现在,它一个对象。
  仿函数本质是一个类,这个类重载 o p e r a t o r ( ) operator() operator(),它的对象可以像函数一样使用
  
LessFunc本质是调用了 o p e r a t o r ( ) operator() operator()

cout << LessFunc(1, 2) << endl;cout << LessFunc.operator()(1, 2) << endl;

  
同样,我们还可以实现一个 g r e a t e r greater greater 的仿函数

template<class T>class Greater{public:bool operator()(const T& x, const T& y){return x > y;}};

  

3.2 仿函数的应用

  那 p r i o r i t y priority priority_ q u e u e queue queue 为什么要仿函数作为模板参数呢?
  我们知道堆的插入,是要调用向上调整算法

template<class T, class Container = vector<T>>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}private:Container _con;};

  
  上述实现的向上调整算法,判断条件是if (_con[parent] < _con[child])建的是大堆,那如果我想建小堆怎么办?自己手动改代码吗?那也太离谱了吧。
  
  这时,仿函数的作用就出来了。
  我们再增加一个模板参数: C o m p a r e Compare Compare, C o m p a r e Compare Compare 是一个类型,传递一个仿函数。我们还可以给一个缺省值

template<class T, class Container = vector<T>, class Compare = Less<T>>

  
  这时,我们就可以将比较逻辑写成泛型

if (Compare(_con[parent], _con[child]))

  
  如果我们想建大堆,比较逻辑是 < ,传递 Less<T> 类型;反之传递 Greater<T> 类型。(库中是 l e s s less less<T> 和 g r e a t e r greater greater<T>)

int main(){Priority_queue<int, vector<int>, Less<int>> p3;Priority_queue<int, vector<int>, Greater<int>> p4;return 0;}

  
注:模板模板实例化时传递的是类型,而函数模板传参时需要传的是对象

如:写一个向上调整算法的函数模板

template<class Compare>void AdjustUp(int* a, int child, Compare com){int parent = (child - 1) / 2;while (child > 0){if (com(a[child], a[parent])){swap(a[child], a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}int main(){int a[] = { 1 };Less<int> LessFunc;AdjustUp(a, 1, LessFunc);//传递有名对象AdjustUp(a, 1, Less<int>());//传递匿名对象return 0;}

  
  

4 需自己写仿函数的情况

  库中是帮我们实现了仿函数 l e s s less less 和 g r e a t e r greater greater 的,也就是说一般情况下我们是不用自己实现仿函数,这直接调用库里的就好了

在这里插入图片描述

less

在这里插入图片描述

greater

  但有些情况时需要我们自己写的。
  

4.1 类类型不支持比较大小

class Date{ public :Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}private:int _year;int _month;int _day;};int main(){priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));return 0;}

   D a t e Date Date类 中并没有重载 o p e r a t o r operator operator< 和 o p e r a t o r operator operator> 的函数,编译就会报错

在这里插入图片描述

  这时,就需要我们自己实现 l e s s less less 和 g r e a t e r greater greater 仿函数
  

4.2 类中支持的比较方式不是我们想要的

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);}private:int _year;int _month;int _day;};

  
  现在 D a t e Date Date类 中支持了比较方式,但如果我们这样传参呢?

int main(){priority_queue<Date*> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));cout << *q1.top() << endl;q1.pop();cout << *q1.top() << endl;q1.pop();cout << *q1.top() << endl;q1.pop();return 0;}

在这里插入图片描述

  你会发现,每次的结果都不一样,我们控制不住。这时因为我们传递的是指针,它是按指针大小来比较

  这时就需要我们自己实现仿函数

class DateLess{bool operator()(Date* p1, Date* p2){return *p1 < *p2;}};

  

5 priority_queue 的模拟实现

namespace my_priority_queue{       template <class T, class Container = vector<T>, class Compare = less<T> >    class priority_queue    {    public:       template <class InputIterator>       priority_queue(InputIterator first, InputIterator last)       {           InputIterator it = first;           while (it != last)           {               push(*it);               ++it;           }       }        priority_queue() {}                bool empty() const        {            return _c.empty();        }        size_t size() const        {            return _c.size();        }        const T& top() const        {            return _c.front();        }        T& top()        {            return _c.front();        }        void push(const T& x)        {            _c.push_back(x);            AdjustUp(size() - 1);        }        void AdjustUp(int child)        {                      int parent = (child - 1) / 2;            while (child > 0)            {                if (_comp(_c[parent], _c[child]))                {                    swap(_c[parent], _c[child]);                    child = parent;                    parent = (child - 1) / 2;                }                else                    break;            }        }        void AdjustDown(int parent, int end)        {            int child = parent * 2 + 1;            while (child <= end)            {                if (child + 1 <= end && _comp(_c[child], _c[child + 1]))                    ++child;                if (_comp(_c[parent], _c[child]))                {                    std::swap(_c[parent], _c[child]);                    parent = child;                    child = parent * 2 + 1;                                }                else                    break;            }        }        void pop()        {            assert(!empty());            std::swap(_c[0], _c[size() - 1]);            _c.pop_back();            AdjustDown(0, size() - 1);        }    private:        Container _c;        Compare _comp;    };}

  

  
  
  


  好啦,本期关于 priority_queue 与仿函数 的知识就介绍到这里啦,希望本期博客能对你有所帮助。同时,如果有错误的地方请多多指正,让我们在 C++ 的学习路上一起进步!


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/166591.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1