前言
本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。
一、priority_queue的底层实现
priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆
在库的实现中,使用vector作为该优先级队列的适配容器。
由于priority_queue也是一个适配器,所以它的接口函数也可以对其他容器的函数进行封装使用。
下面来对priority_queue进行模拟实现。
#pragma once
//优先级队列底层是堆,heap
namespace bit
{
//仿函数
template<class T>
class Less
{
public:
bool operator()(const T& t1, const T& t2)
{
return t1 < t2;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& t1, const T& t2)
{
return t1 > t2;
}
};
//类名不是类型
template<class T, class Container = vector<T>, class Compare = Less<T> >
//默认大堆
class PriorityQueue
{
//com是一个仿函数
Compare com;
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child > 0)
{
//可能右孩子存在且大于左孩子
if (child + 1 < _con.size() && com(_con[child],_con[child + 1]))
{
++child;
}
//如果孩子存在且孩子大于父亲,交换
if (child < _con.size() && com(_con[parent],_con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
Compare com;
//类名实例化类对象,该类型是一个仿函数,实例化的com可以调用仿函数的比较方法
//记录父亲的下标
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
}
child = parent;
parent = (child - 1) / 2;
}
}
public:
PriorityQueue()
{}
//默认建大堆
template<class InputIterator>
PriorityQueue(InputIterator first, InputIterator end)
{
//插入数据
while (first != end)
{
_con.push_back(*first);
++first;
}
//向下调整建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
void push(const T& val)
{
//插入元素
_con.push_back(val);
//然后向上调整
AdjustUp(_con.size() - 1);
}
void pop()
{
//1.堆顶和堆尾交换
swap(_con[0], _con[_con.size() - 1]);
//2.删除堆尾
_con.pop_back();
//3.向下调整,恢复堆
AdjustDown(0);
}
T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
注解:
- 1.在进行构造时,我们使用迭代区间进行构造
-
- (1)向空间中插入数据
-
- (2)向下调整建堆,建N个数据,从第一个非叶子节点开始进行建堆,每次都向下调整,时间复杂度O(N)。
push函数的实现:
向堆尾插入一个元素,插入的元素可能会改变堆的结构,所以我们需要将该元素向上调整,以维护堆的特性。
pop函数的实现:
删除堆顶元素,首先将堆顶元素和堆的最后一个元素进行交换,然后进行尾删,删除后原来的堆尾的元素现在在堆顶,我们需要将其进行向下调整以维持堆的状态。
empty函数:
判断堆是否为空即可。
size函数:
计算堆的元素个数。
top函数:
取堆顶元素,也就是取第一个元素。
priority_queue容器的作用:有需要使用堆的地方就可以使用该容器。
二、使用仿函数控制priority_queue的底层
什么是仿函数?
仿函数:仿造的函数,它并不是一个真正意义上的函数。能够重载operator(),内部实现自己想要的方法,然后实例化出一个方法对象,调用该对象作为参数,此时就可以调用该方法类对象内部实现的operator()方法了。
由于库中的优先级队列的底层结构是堆,且默认是大堆,我们在模拟实现和使用时,如果遇到需要使用小堆的场景,需要改变的东西很多,比如向上调整算法和向下调整算法的比较方法。
现在我们需要指定一个方法,这个方法可以由我们控制,从而实现大小堆。
仿函数:
//仿函数
template<class T>
class Less
{
public:
bool operator()(const T& t1, const T& t2)
{
return t1 < t2;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& t1, const T& t2)
{
return t1 > t2;
}
};
这里实现了两个类,并重载了一个比较方法。
在priority_queue模板的实现中,我们可以多传递一个模板参数:class Compare,也就是多传递一个比较方法。然后我们自己写一个比较方法传递过去,然后在priority_queue的实现中实例化一个方法对象来控制堆的生成。
总结
本文章讲解了仿函数控制priority_queue容器的底层实现的过程以及priority_queue的底层实现。文章来源:https://www.toymoban.com/news/detail-602330.html
只要有堆的地方就可以使用priority_queue容器。文章来源地址https://www.toymoban.com/news/detail-602330.html
到了这里,关于【C++】STL使用仿函数控制优先级队列priority_queue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!