admin管理员组文章数量:1624321
目录
一、priority_queue的使用
二、仿函数
2.1如果在priority_queue中放自定义类型的数据,需要自定义类型中重载>或者<
三、模拟实现
优先级队列和栈,队列一样,也是容器适配器,用其他结构包装而成的
一、priority_queue的使用
创建的默认的是一个大堆
当然,我们也是可以实现小堆的
二、仿函数
仿函数其实是一个对象
这里p1明明就是一个对象,但却能执行10+20的操作,就像是在调用函数一样
正是因为他本身不是函数,但用起来像函数,才把他叫做仿函数
这个plus本质其实是一个结构体,他的特殊之处就是重载了小括号
2.1如果在priority_queue中放自定义类型的数据,需要自定义类型中重载>或者<
原因就是系统并不知道自定义类型的比较规则
这时候就需要我们自己去定义,明确的告诉系统比较的规则
大堆(默认)要定义 <
小堆要定义 >
三、模拟实现
namespace bit
{
template<class T, class Cont = vector<T>, class Pred = less<Cont::value_type>>
class priority_queue
{
public:
priority_queue() : c()
{}
template<typename _It>
priority_queue(_It first, _It last): c(first, last)
{
int curpos = c.size()/2 - 1;//找到最后一个非叶子节点分支
while(curpos >= 0)
{
_AdjustDown(curpos);
curpos--;
}
}
public:
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
void push(const T& x)
{
c.push_back(x);
_AdjustUp(c.size() - 1);
}
T& top()
{
return c[0];
}
void pop()
{
//swap(c[0], c[c.size()-1]);
swap(c.front(), c.back());
c.pop_back();
_AdjustDown(0);
}
void show()const
{
for(int i=0; i<c.size(); ++i)
cout<<c[i]<<" ";
cout<<endl;
}
protected:
void _AdjustUp(int start)
{
int j = start; //child
int i = (j-1) / 2; //parent
T tmp = c[j];
while(j > 0)
{
//if(tmp <= c[i])
if(comp(tmp, c[i]))
break;
c[j] = c[i];
j = i;
i = (j-1) / 2;
}
c[j] = tmp;
}
void _AdjustDown(int start)
{
int i = start; //parent
int j = 2*i + 1; //child
T tmp = c[i];
while(j <= c.size()-1)
{
//if(j+1<=c.size()-1 && c[j]<c[j+1])
if(j+1<=c.size()-1 && comp(c[j], c[j+1]))
j++;
//if(tmp >= c[j])
if(!comp(tmp, c[j]))
break;
c[i] = c[j];
i = j;
j = 2*i + 1;
}
c[i] = tmp;
}
private:
Cont c;
Pred comp; //仿函数对象
};
};
本文标签: stlpriorityqueue
版权声明:本文标题:STL之priority_queue 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728895088a1178307.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论