STL中优先队列的模拟实现与仿函数的介绍
2023-12-23 18:29:10
仿函数
上回我们说到,优先队列的实现需要用到仿函数的特性
让我们再回到这里
这里我们发现他传入的用于比较的东西竟然是一个类模板,而不是我们所见到的函数
我们可以先创建一个类,用于比较大小
struct Less
{
bool operator()(int x, int y)
{
return x < y;
}
};
这里我们创建了一个Less类,并且重载了圆括号,让他比较x<y是否成立
我们可以这样使用
Less ls;
cout << ls(1, 2) << endl;
结果是1
我们单单从cout这一句来看,ls就好像一个函数一样,可以比较1和2的大小,但是实际上是由Less创建的一个对象来比较的
我们把这一句还原
Less ls;
cout << ls(1, 2) << endl;
cout << ls.operator()(1, 2) <<endl;
实际上后面这一句才是原本的样子
如果我们给这个类加上个模板
例如
template<class T>
struct Less
{
bool operator()(T x, T y)
{
return x < y;
}
};
这样就可以用来比较不止整形的大小了
这样我们就可以在别的类内部通过类模板来传递函数的功能
讲到这我们就明白了,这个仿函数实际上的功能类似于函数指针,是用来传递函数的逻辑的
这样做的好处是我们可以自行定义需要的函数
例如当堆中的数据为自定义类型,通用的less和greater比较就不起作用了,需要自行定义传入了
优先队列的模拟实现
#include <iostream>
using namespace std;
#include <vector>
namespace xu
{
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
}; // 仿函数的实现
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
}; // 仿函数的实现
template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue
{
public:
// 创造空的优先级队列
priority_queue() : c() {}
template<class Iterator>
priority_queue(Iterator first, Iterator last)
: c(first, last)
{
// 将c中的元素调整成堆的结构
int count = c.size();
int root = ((count - 2) >> 1);
for (; root >= 0; root--)
AdjustDown(root);
}
void push(const T& data)
{
c.push_back(data);
AdjustUP(c.size() - 1);
}
void pop()
{
if (empty())
return;
swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
size_t size()const
{
return c.size();
}
bool empty()const
{
return c.empty();
}
const T& top()const
{
return c.front();
}
private:
// 向上调整
void AdjustUP(int child)
{
int parent = ((child - 1) >> 1);
while (child)
{
if (Compare()(c[parent], c[child]))
{
swap(c[child], c[parent]);
child = parent;
parent = ((child - 1) >> 1);
}
else
{
return;
}
}
}
// 向下调整
void AdjustDown(int parent)
{
size_t child = parent * 2 + 1;
while (child < c.size())
{
// 找以parent为根的较大的孩子
if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
child += 1;
// 检测双亲是否满足情况
if (Compare()(c[parent], c[child]))
{
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
}
else
return;
}
}
private:
Container c;
};
}
文章来源:https://blog.csdn.net/ye_yumo/article/details/135172195
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!