当前位置：首页 > news >正文

C++STL（四）priority_queue的详细用法及仿函数实现

news 来源：原创 2024/9/28 4:07:53

一：🔥介绍

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征。
优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

二：🔥priority_queue 的基本操作

首先，使用priority_queue时需包含头文件：

#include <priority_queue>

🔥): 和队列基本操作相同

名字	描述
top	访问队头元素
empty	队列是否为空
size	返回队列内元素个数
push	插入元素到队尾 (并排序)
emplace	原地构造一个元素并插入队列
pop	弹出队头元素
swap	交换内容

三：🔥priority_queue 的原型定义

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

模板申明带3个参数：其中 T 为数据类型，Container 为保存数据的容器（适配器），Compare 为元素比较方式。
Container必须是用数组实现的容器，比如 vector,deque 等等，但不能用 list。STL里面默认用的是vector。
比较方式默认用operator<，所以如果把后面2个参数缺省的话，优先队列就是大顶堆（降序），队头元素最大。

greater和less是std实现的两个仿函数
类的对象可以像函数一样使用，其实现就是类中实现一个operator()
这个类的对象就有了类似函数的行为，就是一个仿函数类了//降序队列(默认大根堆) 把后面2个参数缺省
priority_queue <int> q;//升序队列(小根堆)
priority_queue <int,vector<int>,greater<int> > q;

四：🔥重写仿函数

4.1.仿函数的介绍

仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator() 运算符。因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符。
仿函数的优点
写一个简单类，除了维护类的基本成员函数外，只需要重载 operator() 运算符。这样既可以免去对一些公共变量的维护，也可以使重复使用的代码独立出来，以便下次复用。而且相对于函数更优秀的性质，仿函数还可以进行依赖、组合与继承等，这样有利于资源的管理。
简言之：就是一个类，可以定义一些变量，省的使用全局变量，造成命名空间污染

4.2.priority_queue仿函数代码示例

//仿函数 可以像操作函数一样操作对象 因为重载了() 不是什么新语法
template<class T>
class less
{
public:bool operator()(const T& a, const T& b){return a < b;}
};template<class T>
class greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

五：🔥priority_queue模拟底层实现（堆排序）

template<class T>
class less
{
public:bool operator()(const T& a, const T& b){return a < b;}
};template<class T>
class greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue
{
public:priority_queue() = default;    // 强制生成默认构造函数template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);}//建堆操作for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}//向下调整算法void adjust_down(size_t parent){Compare comfunc;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])){++child;}if (comfunc(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else break;}}//向上调整算法void adjust_up(size_t child){Compare comfunc;int parent = (child - 1) / 2;while (child > 0){if (comfunc(_con[parent], _con[child])) std::swap(_con[parent], _con[child]);else break;child = parent;parent = (child - 1) / 2;}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:Container _con;Compare comp;
};