目录
前言
一、初始仿函数
1、仿函数是什么
2、仿函数的使用
二、优先级队列
1、 优先级队列的基本概念
2、堆的储存结构与结点之前关系
3、堆的使用
4、堆的模拟实现
前言
本文主要介绍优先级队列与仿函数,优先级队列实际上是我们在数据结构中学的堆;在介绍优先级队列之前,我们必须的初步的认识学习一下什么叫仿函数,与仿函数的使用;
一、初始仿函数
1、仿函数是什么
仿函数实际上是一个重载了()的类;仿函数也叫对象函数;我们通过对象访问成员函数的方式调用函数;与其相对的是C语言的函数指针,因为C语言的函数指针在某些情况下太过于复杂,于是C++设计出了仿函数;
2、仿函数的使用
我们通过一下代码来学习仿函数的定义与使用;
#include <functional>
// 带模板参数的仿函数
template<class T>
struct Greater
{
// 重载()
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
void test_func()
{
int x = 3;
int y = 10;
// 创建一个仿函数对象
Greater<int> Gre;
// 通过对象调用仿函数
cout << Gre(x, y) << endl;
// 通过匿名对象调用仿函数
cout << Greater<int>()(x, y) << endl;
}
int main()
{
test_func();
return 0;
}
我们通过重载对象里的圆括号,来实现用对象来模拟函数功能;而我们的优先级队列也巧妙的使用了仿函数,来实现通过模板参数控制我们实现的是大堆还是小堆;
二、优先级队列
1、 优先级队列的基本概念
优先级队列在数据结构中又被称为堆,堆是一种完全二叉树结构;分为大堆与小堆;
大堆:父节点大于子节点
小堆:父节点小于父节点
大小堆并没有要求左右孩子大小顺序,也就是说在任意堆中,左孩子可能大于右孩子,也可能小于右孩子;
2、堆的储存结构与结点之前关系
一般情况下,我们用顺序结构储存堆,通过下标关系来定位孩子与父亲之间的关系;
父亲下标 = (孩子下标 - 1)/ 2
左孩子下标 = (父亲下标 * 2) + 1
右孩子下标 = (父亲下标 * 2) + 2
我们可以通过下图尝试使用以上规则是否适用;
3、堆的使用
堆有如下几个接口;使用成本也不高;
void test_priority_queue()
{
// 创建优先级队列
std::priority_queue<int, vector<int>, greater<int>> pq;
// 插入数据
pq.push(13);
pq.push(17);
pq.push(23);
pq.push(27);
pq.push(33);
pq.push(35);
pq.push(43);
pq.push(47);
pq.push(54);
pq.push(56);
// 判空
while (!pq.empty())
{
// 获得堆顶数据
cout << pq.top() << " ";
// 取出堆顶数据
pq.pop();
}
cout << endl;
}
4、堆的模拟实现
堆的模拟实现也不是很难,与前面的stack与queue一样,堆也是适配器容器,我们仅仅只需实现向上调整与向下调整两个接口即可,其他接口均复用;
#include <vector>
#include <functional>
namespace MySpace
{
template<class T, class Container = std::vector<T>, class Compara = std::less<T>>
class priority_queue
{
private:
void adjust_up(size_t child)
{
// 计算父节点下标
size_t parent = (child - 1) / 2;
// 假若孩子结点已经为根节点了,则无法继续向上调整了
while (child > 0)
{
// 通过仿函数比较父节点与子节点的大小关系
if (Compara()(_con[parent], _con[child]))
{
// 条件满足,交换两个结点的值
std::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() && Compara()(_con[child], _con[child + 1]))
{
child++;
}
// 拿大的(小的)那个孩子进行比较,查看是否需要交换
if (Compara()(_con[parent], _con[child]))
{
// 交换父节点与子节点的数据
std::swap(_con[child], _con[parent]);
// 跟新父节点与子节点下标
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
public:
void push(const T& val)
{
_con.push_back(val);
adjust_up(_con.size() - 1);
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top() const
{
return _con.front();
}
private:
Container _con;
};
}
在push函数中,我们插入一个数据会插入到尾部,此时我们需要向上调整,使堆重新恢复堆结构;
文章来源:https://www.toymoban.com/news/detail-554002.html
我们结合前面的知识,计算出父节点的下标,依次通过仿函数比较是否需要进行调整数据;关于向下调整,具体思路也一样,代码有具体注释;文章来源地址https://www.toymoban.com/news/detail-554002.html
到了这里,关于C++ | 仿函数与priority_queue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!