priority_queue是一个顺序容器适配器,其原型: template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; 可见第二个vector<int>是其Container,即优先队列的基础容器是vector<int>,优先队列在vector<int>这一容器类型基础上实现
在优先队列中,优先级高的元素先出队列。 标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。 优先队列的第一种用法,也是最常用的用法:
priority_queue < int > qi;
通过<操作符可知在整数中元素大的优先级高。 故示例1中输出结果为:9 6 5 3 2 第二种方法: 在示例1中,如果我们要把元素从小到大输出怎么办呢? 这时我们可以传入一个比较函数,使用functional.h函数对象作为比较函数。
priority_queue < int , vector < int > , greater < int > > qi2;
其中 第二个参数为容器类型。 第二个参数为比较函数。 故示例2中输出结果为:2 3 5 6 9 第三种方法: 自定义优先级。
struct node { friend bool operator < (node n1, node n2) { return n1.priority < n2.priority; } int priority; int value; };
在该结构中,value为值,priority为优先级。 通过自定义operator<操作符来比较元素中的优先级。 在示例3中输出结果为: 优先级 值 9 5 8 2 6 1 2 3 1 4 但如果结构定义如下:
struct node { friend bool operator > (node n1, node n2) { return n1.priority > n2.priority; } int priority; int value; };
则会编译不过(G++编译器) 因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。 而且自定义类型的<操作符与>操作符并无直接联系,故会编译不过。
另一位总结
#include<iostream> #include<functional> #include<queue> using namespace std;
struct node { friend bool operator< (node n1, node n2) { return n1.priority < n2.priority;//"<"为从大到小排列,">"为从小打到排列 } int priority; int value; };
int main() { const int len = 5; int i; int a[len] = {3,5,9,6,2}; //示例1 priority_queue<int> qi;//普通的优先级队列,按从大到小排序 for(i = 0; i < len; i++) qi.push(a[i]); for(i = 0; i < len; i++) { cout<<qi.top()<<" "; qi.pop(); } cout<<endl;
//示例2 priority_queue<int, vector<int>, greater<int> > qi2;//从小到大的优先级队列,可将greater改为less,即为从大到小 for(i = 0; i < len; i++) qi2.push(a[i]); for(i = 0; i < len; i++) { cout<<qi2.top()<<" "; qi2.pop(); } cout<<endl;
//示例3 priority_queue<node> qn;//必须要重载运算符 node b[len]; b[0].priority = 6; b[0].value = 1; b[1].priority = 9; b[1].value = 5; b[2].priority = 2; b[2].value = 3; b[3].priority = 8; b[3].value = 2; b[4].priority = 1; b[4].value = 4; for(i = 0; i < len; i++) qn.push(b[i]); cout<<"优先级"<<'\t'<<"值"<<endl; for(i = 0; i < len; i++) { cout<<qn.top().priority<<'\t'<<qn.top().value<<endl; qn.pop(); } return 0; }
对于队列里元素为一个结构体类型,按照某一个属性排序,就需要对比较函数进行重载
小结一下:
1、若是定义值类型对象,如:
int main() { priority_queue<node> qn;
node n1; n1.a = 9; node n2; n2.a = 2; node n3; n3.a = 50;
qn.push(n1);
qn.push(n2);
qn.push(n3);
int size = qn.size();
for ( int i = 0; i < size; i++) { cout << qn.top().a << endl;
qn.pop(); } return 0;
} 则定义优先级的时候,直接在类中写个friend 的操作符重载函数即可:
class node { public : int a;
node(){} node( int x):a(x){} friend bool operator<( const node ne1, const node ne2)//参数也可以为引用,值传递 { if (ne1.a > ne2.a) { return true ; } else { return false ; } } }; 其中在c++primer第三版 中文版中关于操作符重载有如下描述:
"程序员只能为类类型或枚举类型的操作数定义重载操作符我们可以这样来实现把重 载操作符声明为类的成员或者声明为名字空间成员同时至少有一个类或枚举类型的参数 按值传递或按引用传递"
因此不可用指针类型的参数;
2、如果想定义一个指针类型的优先队列,那就不可这么简单的定义了,你需要自定义一个自己的比较函数,在priority_queue的模板函数中,我们可以利用这样一个template<class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type> >模板,在我们的程序代码中,则需要自己定义一个类来定义第三个模板参数,如:
class nodePointerComparer { public : nodePointerComparer(){} bool operator ()( const node* ne1, const node* ne2) const { return ne1->lessthan(ne2); } };
当然在这之前我们的类Node要重新书写
class node { public : int a; node(){} node( int x):a(x){}
bool lessthan( const node* pnode) const { return a < pnode->a; } }; 这样在main函数中就可以定义指针类型的优先队列了:
int main() { priority_queue <node*, vector <node*>, nodePointerComparer> qn; node *n1 = new node(90); node *n2 = new node(2); node *n3 = new node(50);
qn.push(n1); qn.push(n2); /span>
> qn.push(n3);
int size = qn.size(); for ( int i = 0; i < size; i++) { cout << qn.top()->a << endl; qn.pop(); } return 0;
} 疑问之处:如果你使用第一种值传递的操作符重载,来实现第二种的指针类型优先队列,是不会达到想要的结果的,个人理解是因为在指针类型的优先队列中找“<”运算符的时候,重载的不是我们写的值传递friend bool operator<(const node ne1,const node ne2)//
也就是没有找到指针类型的"<"重载,所有不会达到优先队列的效果。