AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++初阶】十一、STL---priority_queue（总）

2023-04-19 117
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 目录一、priority_queue介绍二、priority_queue使用三、仿函数四、priority_queue模拟实现4.1 版本14.2 版本2

目录

一、priority_queue介绍

二、priority_queue使用

三、仿函数

四、priority_queue模拟实现

4.1 版本1

4.2 版本2

一、priority_queue介绍

priority_queue文档介绍

image.png

翻译;

       （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 来自动完成此操作


template<classT, classContainer=vector<T>,
classCompare=less<typenameContainer::value_type>>classpriority_queue;

     优先级队列 priority_queue 默认使用的适配器是 vector（class Container = vector），第三个模板参数是仿函数（class Compare = less ），仿函数下面解释

image.png

       使用 priority_queue 要包含头文件 <queue>，与 queue 的头文件一致

#include <queue>

注：priority_queue 的结构就是堆，即二叉树

二、priority_queue使用

成员函数介绍：

image.png

接口简单介绍，C++11先不介绍，后面再学

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


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

注意：默认情况下 priority_queue 是大堆（即降序）

      优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆；如果想控制小的优先级高，需手动传 greater 仿函数，其底层是一个小堆

image.png

测试代码

#include <iostream>#include <queue>usingnamespacestd;
voidTest_priority_queue() 
{
priority_queue<int>pq;
pq.push(3);
pq.push(6);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
    {
cout<<pq.top() <<" ";
pq.pop();
    }
cout<<endl;
}
intmain()
{
Test_priority_queue();
return0;
}

运行结果，降序

image.png

如果要改成小堆（即升序），需要手动传第三个参数 greater ，使用 greater 需要包含头文件 

#include <functional>  // greater的头文件

要传第三个模板参数，就必须传第二个模板参数，这是使用缺省参的语法规定

priority_queue<int, greater<int>> pq; //error

正确使用如下

priority_queue<int, vector<int>, greater<int> > pq;
#include <iostream>#include <queue>#include <functional>usingnamespacestd;
voidTest_priority_queue()
{
priority_queue<int, vector<int>, greater<int>>pq;
pq.push(3);
pq.push(6);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
    {
cout<<pq.top() <<" ";
pq.pop();
    }
cout<<endl;
}
intmain()
{
Test_priority_queue();
return0;
}

运行结果，升序

image.png

三、仿函数

仿函数是 STL 的六大组件之一

image.png

       仿函数：使一个类的使用看上去像一个函数，该类定义出来的对象称为函数对象

       仿函数的实现就是在类中重载 () 操作符，使得该类具备类似函数的行为，就是一个仿函数

测试，创建一个仿函数

namespacefy{
classless    {
public:
booloperator()(intx, inty)
        {
returnx<y;
        }
    };
}
voidTest()
{
fy::lesslessCompare;
cout<<lessCompare(10, 20) <<endl;
}

运行结果

image.png

仿函数支持泛型

namespacefy{
template<classT>classless    {
public:
booloperator()(constT&x, constT&y)const        {
returnx<y;
        }
    };
template<classT>classgreater    {
public:
booloperator()(constT&x, constT&y)const        {
returnx>y;
        }
    };
}
voidTest()
{
fy::less<int>lessCompare;
cout<<lessCompare(10, 20) <<endl;
fy::greater<double>greaterCompare;
cout<<greaterCompare(10.0, 20.0) <<endl;
}

运行结果

image.png

这就是仿函数，实际上仿函数调用的只是重载的 operator() 而已

为什么要有仿函数？为了替代 C语言中的函数指针，使用代码更直观，函数指针使用起来头大，难理解！！

void( * set_malloc_handler(void (*f)()))() //这是函数指针.......

所以，仿函数的出现就是为了替代 C语言的函数指针

四、priority_queue模拟实现

       优先级队列的模拟实现也是很简单，因为它是容器适配器，可以使用已有的生成我们想要的

4.1 版本1

       这里要注意的向上调整和向下调整的写法，数据结构已经学过，就不废话了。这个版本的缺陷是不能很好的支持升序和降序，只能是其中的一种，使用改升序或降序就必须修改源代码，修改后也是两者不能兼并，极其不好，版本2 则是使用仿函数，可以使两者可以同时兼并

priority_queue.h

#pragma once#include <iostream>#include <vector>usingnamespacestd;
namespacefy//防止命名冲突{
//优先级队列模拟实现template<classT, classContainer=vector<T>>classpriority_queue    {
public:
priority_queue(){}
//迭代器区间构造template<classInputIterator>priority_queue(InputIteratorfirst, InputIteratorlast)
            :_con(first, last)
        {
for (inti= (_con.size() -1-1) /2; i>=0; --i)
            {
adjust_down(i);
            }
        }
//堆的向上调整voidadjust_up(size_tchild)
        {
size_tparent= (child-1) /2;
while (child>0)
            {
if (_con[parent] <_con[child])
                {
swap(_con[parent], _con[child]);
child=parent;
parent= (child-1) /2;
                }
else//已经成堆                {
break;
                }
            }
        }
//队尾插入元素voidpush(constT&x)
        {
_con.push_back(x);
adjust_up(_con.size() -1);
        }
//堆的向下调整voidadjust_down(size_tparent)
        {
size_tchild=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;
                }
            }
        }
//弹出堆顶元素voidpop()
        {
swap(_con[0], _con[_con.size() -1]);
_con.pop_back();
adjust_down(0);
        }
//获取堆顶元素constT&top()const        {
return_con[0];
        }
boolempty()const        {
return_con.empty();
        }
size_tsize()const        {
return_con.size();
        }
private:
Container_con;
    };
}

Test.cpp

#include "PriorityQueue.h"voidTest_priority_queue()
{
fy::priority_queue<int>pq;
pq.push(5);
pq.push(1);
pq.push(9);
pq.push(6);
pq.push(3);
pq.push(3);
while (!pq.empty())
    {
cout<<pq.top() <<" ";
pq.pop();
    }
cout<<endl;
}
intmain()
{
Test_priority_queue();
return0;
}

运行结果

image.png

4.2 版本2

priority_queue.h

#pragma once#include <iostream>#include <vector>usingnamespacestd;
namespacefy//防止命名冲突{
//比较方式 < --- 使其结构形成大堆template<classT>classless    {
public:
booloperator()(constT&x, constT&y) const        {
returnx<y;
        }
    };
//比较方式 > --- 使其结构形成小堆template<classT>classgreater    {
public:
booloperator()(constT&x, constT&y) const        {
returnx>y;
        }
    };
//优先级队列模拟实现template<classT, classContainer=vector<T>, classCompare=less<T>>classpriority_queue    {
public:
priority_queue(){}
//迭代器区间构造template<classInputIterator>priority_queue(InputIteratorfirst, InputIteratorlast)
            :_con(first, last)
        {
for (inti= (_con.size() -1-1) /2; i>=0; --i)
            {
adjust_down(i);
            }
        }
//堆的向上调整voidadjust_up(size_tchild)
        {
Comparecom;
size_tparent= (child-1) /2;
while (child>0)
            {
//if (_con[parent] < _con[child])if (com(_con[parent], _con[child]))
                {
swap(_con[parent], _con[child]);
child=parent;
parent= (child-1) /2;
                }
else//已经成堆                {
break;
                }
            }
        }
//队尾插入元素voidpush(constT&x)
        {
_con.push_back(x);
adjust_up(_con.size() -1);
        }
//堆的向下调整voidadjust_down(size_tparent)
        {
Comparecom;
size_tchild=parent*2+1;
while (child<_con.size())
            {
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child+1<_con.size() &&com(_con[child], _con[child+1]))
                {
child++;
                }
//if (_con[parent] < _con[child])if (com(_con[parent], _con[child]))
                {
swap(_con[parent], _con[child]);
parent=child;
child=parent*2+1;
                }
else//已经成堆                {
break;
                }
            }
        }
//弹出堆顶元素voidpop()
        {
swap(_con[0], _con[_con.size() -1]);
_con.pop_back();
adjust_down(0);
        }
//获取堆顶元素constT&top()const        {
return_con[0];
        }
boolempty()const        {
return_con.empty();
        }
size_tsize()const        {
return_con.size();
        }
private:
Container_con;
    };
}

est.cpp

#include "PriorityQueue.h"voidTest_priority_queue()
{
//默认是大堆 lessfy::priority_queue<int>pq;
pq.push(5);
pq.push(1);
pq.push(9);
pq.push(6);
pq.push(3);
pq.push(3);
while (!pq.empty())
    {
cout<<pq.top() <<" ";
pq.pop();
    }
cout<<endl;
intarr[] = { 5,1,9,6,3,3 };
//默认是大堆 lessfy::priority_queue<int>pq2(arr, arr+6);
while (!pq2.empty())
    {
cout<<pq2.top() <<" ";
pq2.pop();
    }
cout<<endl;
//小堆, greaterfy::priority_queue<int, vector<int>, greater<int>>pq3(arr, arr+6);
while (!pq3.empty())
    {
cout<<pq3.top() <<" ";
pq3.pop();
    }
cout<<endl;
}
intmain()
{
Test_priority_queue();
return0;
}

运行结果

#include "PriorityQueue.h"voidTest_priority_queue()
{
//默认是大堆 lessfy::priority_queue<int>pq;
pq.push(5);
pq.push(1);
pq.push(9);
pq.push(6);
pq.push(3);
pq.push(3);
while (!pq.empty())
    {
cout<<pq.top() <<" ";
pq.pop();
    }
cout<<endl;
intarr[] = { 5,1,9,6,3,3 };
//默认是大堆 lessfy::priority_queue<int>pq2(arr, arr+6);
while (!pq2.empty())
    {
cout<<pq2.top() <<" ";
pq2.pop();
    }
cout<<endl;
//小堆, greaterfy::priority_queue<int, vector<int>, greater<int>>pq3(arr, arr+6);
while (!pq3.empty())
    {
cout<<pq3.top() <<" ";
pq3.pop();
    }
cout<<endl;
}
intmain()
{
Test_priority_queue();
return0;
}

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

文章标签：
C++
C语言
容器
算法
存储
关键词：
C++初阶
枫叶先生_
目录
相关文章
反季雪
|
5月前
|
存储 编译器 C++
【C++ 初阶路】--- 类和对象(下)
【C++ 初阶路】--- 类和对象(下)
反季雪
24 1
反季雪
|
5月前
|
存储 编译器 C语言
【C++初阶路】--- 类和对象(中)
【C++初阶路】--- 类和对象(中)
反季雪
28 1
反季雪
|
5月前
|
安全 编译器 程序员
【C++初阶】--- C++入门（上）
【C++初阶】--- C++入门（上）
反季雪
35 1
Eternity._
|
5月前
|
存储 编译器 C++
【C++初阶】—— 类和对象 (中）
【C++初阶】—— 类和对象 (中）
Eternity._
35 3
Eternity._
|
5月前
|
编译器 C++
【C++初阶】—— 类和对象 (下）
【C++初阶】—— 类和对象 (下）
Eternity._
25 2
Eternity._
|
5月前
|
C语言 C++
【C++初阶】—— C++内存管理
【C++初阶】—— C++内存管理
Eternity._
30 1
Eternity._
|
5月前
|
存储 编译器 C语言
【C++初阶】—— 类和对象 (上）
【C++初阶】—— 类和对象 (上）
Eternity._
34 1
7fa6b5ui5pmtk
|
5月前
|
C语言 C++ 容器
【C++初阶学习】第十二弹——stack和queue的介绍和使用
【C++初阶学习】第十二弹——stack和queue的介绍和使用
7fa6b5ui5pmtk
46 8
7fa6b5ui5pmtk
|
5月前
|
存储 C++
C++初阶学习第九弹——探索STL奥秘（四）——vector的深层挖掘和模拟实现
C++初阶学习第九弹——探索STL奥秘（四）——vector的深层挖掘和模拟实现
7fa6b5ui5pmtk
45 8
7fa6b5ui5pmtk
|
5月前
|
存储 C++
C++初阶学习第十一弹——探索STL奥秘（六）——深度刨析list的用法和核心点
C++初阶学习第十一弹——探索STL奥秘（六）——深度刨析list的用法和核心点
7fa6b5ui5pmtk
53 7