关于优先队列priority_queue
# 关于“容器适配器(container adaptors)”
在C++ primer中关于容器适配器的定义是:
适配器是标准库中的一个通用概念。容器,迭代器和函数都有适配器。本质上,一个适配器是一种机制,能使某种事物的行为看起来像一种不同的类型。
在C++ STL中有三个顺序容器适配器:stack, queue和priority_queue。这三种数据结构并不是容器,而是对容器的一种行为限制,让它能够以例如push或者pop这种操作改变所存储的内容。
# C++ STL中的priority_queue
# 定义
定义代码如下:
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
1
2
2
可以看出默认情况下,Container是一个vector,也就是如果使用的是vector,的话,可以忽略后面Container的参数,只传class就可以了。
然后Compare默认使用的是less(STL所有的有序容器都默认用的是"<",也就是less
这里大顶堆的理解是,比如vector按less排序会是下面这样:
1 < 2 < 3 < 4
这样1是在入队的地方,而4是在出队的地方,也就是top()。
如果想创建一个小顶堆,就要用functional中的greater
priority_queue pq(int, greater<int>());
1
编辑 (opens new window)
上次更新: 2021/06/03, 13:03:33