STL 容器之 priority_queue小结
优先队列是一种容器适配器类型,它设计为第一个元素总是它所包含的的最大的元素,但这只是默认情况,默认算子为less算子,如果想要使第一个元素为最小的元素,那就应该使用greater算子,当然你也可以自己定义算子。优先队列很类似于数据结构中的堆结构,因此在一般编程时我们都倾向于使用优先队列来模拟堆的操作(个人经常这么干)
首先,我们看一下优先队列的定义:
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
解释:
T:优先队列中元素类型
Container: 优先队列中元素的载体类型容器,一般来说,可以使用vector和deque,
默认情况是vector
Compare:比较算子,从定义中可以看出,若comp是这个Compare类的对象,则comp(a,b)(a,b为
该元素类型元素)返回一个bool值,当a排在b前面时(严格弱排序)返回true
成员函数:
priority_queue pq;
pq.empty();//判断是否为空
pq.size();//pq元素长度
pq.top();//堆顶元素
pq.pop();//删除堆顶元素
pq.push();//入堆
下面我们来看具体运用:
例子:
// constructing priority queues #include <iostream> #include <queue> using namespace std; class mycomparison { bool reverse; public: mycomparison(const bool& revparam=false) {reverse=revparam;} bool operator() (const int& lhs, const int&rhs) const { if (reverse) return (lhs>rhs); else return (lhs<rhs); } }; int main () { int myints[]= {10,60,50,20}; priority_queue<int> first; priority_queue<int> second (myints,myints+3); priority_queue< int, vector<int>, greater<int> > third (myints,myints+3); // using mycomparison: priority_queue< int, vector<int>, mycomparison > fourth; typedef priority_queue<int,vector<int>,mycomparison> mypq_type; mypq_type fifth (mycomparison()); mypq_type sixth (mycomparison(true)); return 0; }
分析:
first:这是一个空的优先队列
second:使用myints数组来初始化优先队列,默认容器vector,默认算子为less算子,
second.top()元素为60(作用类似于大顶堆)
third:同样使用myints数组初始化,但是此时算子是greater,即小顶堆,third.top()元素为10
fourth:使用自定义算子,但是是空优先队列
未完待续......