一.仿函数
1.介绍
函数对象,又称仿函数,是可以像函数一样使用的对象,其原理就是重载了函数调用符:()
因此在此类中,一定有operator()
的成员函数。
2.示例
template<class T>
struct _less
{
//lhs:left-hand side
bool operator() (const T& lhs, const T& rhs)
{
return lhs < rhs;
}
};
如果T是内置类型,则直接进行比较。如果T是自定义类型,则会调用其operator<()。
先创建一个_less类型的对象smaller,对于smaller(),则调用其
operator()
函数
二.priority_queue
1.介绍
priority_queue,也是一种容器适配器:
class Container = vector<T>
,底层默认为vector同时,对于其元素存储,类似于大/小 堆(父节点大于(小于)子节点的值),根据某种排序标准,使它的第一个元素总是其所有元素中最大/小的。
是按大还是小来存储,通过第3个模板参数来规定
class Compare= less<T>
,缺省为less,即第一个元素总是最大的(其他插入的元素都比第一个less)。
2.成员函数
3.模拟实现
可以根据大小堆的算法,进行模拟实现
数据结构——堆
#include <vector>
#include <functional>
namespace yyjs
{
template<class T, class Container = std::vector<T>,class Compare = std::less<T>>
class priority_queue
{
public:
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
const T& top() const
{
return _con.front();
}
T& top()
{
return _con.front();
}
//从child位置开始向上调整,直到符合Compare的规则
void AdjustUp(size_t child)
{
//根据二叉树,求出父节点的位置
size_t parent = (child - 1) / 2;
//如果当前当前节点不是根节点,且其父节点与当前节点进行比较,符合规则
while (child > 0 && _cmp(_con[parent], _con[child]))
{
//交换当前节点与其父节点的值
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
}
//尾插入一个节点,并将这个节点按规则进行调整
void push(const T& x)
{
_con.push_back(x);
AdjustUp(size() - 1);
}
//从parent位置开始向下进行调整,使其符合Compare规则
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;//左孩子
//当其子节点在有效范围内
while (child < size())
{
//如果有右节点其右节点更大(小),选择右节点
if (child + 1 < size() && _cmp(_con[child],_con[child + 1]))
{
child++;
}
//当前节点与其子节点进行比较,符合规则,进行交互
if (_cmp(_con[parent], _con[child]))
{
::swap(_con[parent],_con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//删除第一个元素,然后将剩余元素按规则调整
void pop()
{
//先交换首尾元素,然后再删尾元素
std::swap(_con.back(), _con.front());
_con.pop_back();
//把交换上去的首元素向下调整,使符合规则
AdjustDown(0);
}
private:
Container _con;
Compare _cmp;
};
}
4.使用
三.其他
1.typename Container::value_type
在less的显示实例化时,所传入的typename Container::value_type类型,所代表的是:Container类中定义的value_type类型
因为class Container = vector<T>
,以vector示例:
using:相当于typedef
由此可见typename Container::value_type其实就相当于T类型,只是库中的更加规范文章来源:https://www.toymoban.com/news/detail-495616.html
🦀🦀观看~~文章来源地址https://www.toymoban.com/news/detail-495616.html
到了这里,关于STL之priority_queue与仿函数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!