1. 优先级队列默认是底层为vector实现的heap
2. set 基于平衡红黑树
3. 两者插入元素时间复杂度都是O(log(n))
4. 使用默认的greater 得到的结果不同

#include
#include
#include
#include
int main(){using namespace std;vector<int>vec{1,3,5,78,4,23};set<int, greater<int> > myset;priority_queue<int, vector<int>, greater<int> >myque;for(int i&＃61;0; i<6; &＃43;&＃43;i){myset.insert(vec[i]); myque.push(vec[i]); }for(set<int, greater<int> >::iterator it&＃61;myset.begin() ; it!&＃61;myset.end(); &＃43;&＃43;it){cout <<*it <<" "; }//从大到小&＃xff1a;78 23 5 4 3 1cout <for(int i&＃61;0; i<6; &＃43;&＃43;i){cout <" "; myque.pop(); }// 小顶堆&＃xff1a; 1 3 4 5 23 78getchar();getchar();return 0;}

优先级队列、sort、qsort 与 重载、自定义cmp函数的关系

#include
#include
#include // for sort()
#include // for priority_queue
#include
#include using namespace std;/*************************************************************************/
// 重载 <运算
class student_cmp{
private:string name;int id;
public:student_cmp(string name &＃61; "default", int id &＃61; 0) :name(name) ,id(id){;}inlinestring get_name(){return name;}inlineint get_id(){return id;}// priority_queue: id 大的优先级低&＃xff0c; 从小到大排列 &＃61;&＃61; greater// vector sort 中 从大到小排bool operator <(const student_cmp &s)const{return this->id > s.id;}friend ostream &operator <<(ostream & os, const student_cmp &s){os <": " <return os;}};/**********************************************************************/
// 没有重载<运算&＃xff0c; 使用自定义cmp函数
class student_nocmp{
private:string name;int id;public:student_nocmp(string name &＃61; "default", int id &＃61; 0) :name(name),id(id){;}inline string get_name(){return name;}inlineint get_id(){return id;}friend ostream &operator <<(ostream & os, const student_nocmp &s){os <": " <return os;}};
// 优先级队列&＃xff1a;从小到大排列
class mynocmp{
public:bool operator ()(student_nocmp &a, student_nocmp &b){return a.get_id() > b.get_id();}
};// for sort 必须返回bool类型
// vector: 从大到小排列
bool sort_nocmp (student_nocmp &a, student_nocmp &b)
{return a.get_id() > b.get_id();
}// for qsort 必须返回int类型, 参数是指针类型
// array: 从大到小排列
// 如果返回值小于0&＃xff0c;则qsort 就得知第一个元素应该在前&＃xff0c;如果返回值大于0&＃xff0c;则第一个元素应该在后。
// 相减顺序与参数一致就是从小到大排序
int qsort_nocmp(const void *a, const void *b)
{student_nocmp * p1, *p2;p1 &＃61; (student_nocmp *)a;p2 &＃61; (student_nocmp *)b;return p1->get_id() - p2->get_id();
}
/**********************************************************************/
int main()
{cout <<"overload operator < stuQueue;stuQueue.push(student_cmp());stuQueue.push(student_cmp("zhangsan", 23));stuQueue.push(student_cmp("lisi", 14));stuQueue.push(student_cmp("laowang", 36));stuQueue.push(student_cmp("xiaoming", 28));while (!stuQueue.empty()){cout <cout <cout <<"without overload operator <vector, mynocmp> stunoQueue;stunoQueue.push(student_nocmp());stunoQueue.push(student_nocmp("zhangsan", 23));stunoQueue.push(student_nocmp("lisi", 14));stunoQueue.push(student_nocmp("laowang", 36));stunoQueue.push(student_nocmp("xiaoming", 28));while (!stunoQueue.empty()){cout <cout </******sort******************/cout <<"overload operator <vector veccmp;veccmp.push_back(student_cmp());veccmp.push_back(student_cmp("zhangsan", 23));veccmp.push_back(student_cmp("lisi", 14));veccmp.push_back(student_cmp("laowang", 36));veccmp.push_back(student_cmp("xiaoming", 28));sort(veccmp.begin(), veccmp.end());for (vector::iterator it &＃61; veccmp.begin(); it !&＃61; veccmp.end(); &＃43;&＃43;it)cout <<*it;cout <cout <<"without overload operator <vector vecnocmp;vecnocmp.push_back(student_nocmp());vecnocmp.push_back(student_nocmp("zhangsan", 23));vecnocmp.push_back(student_nocmp("lisi", 14));vecnocmp.push_back(student_nocmp("laowang", 36));vecnocmp.push_back(student_nocmp("xiaoming", 28));sort(vecnocmp.begin(), vecnocmp.end(), &sort_nocmp);for (vector::iterator it &＃61; vecnocmp.begin(); it !&＃61; vecnocmp.end(); &＃43;&＃43;it)cout <<*it;cout <cout <<"without overload operator <5] &＃61; { student_nocmp(), student_nocmp("zhangsan", 23),student_nocmp("lisi", 14),student_nocmp("laowang", 36),student_nocmp("xiaoming", 28)};qsort(arrnocmp, 5, sizeof(student_nocmp), &qsort_nocmp);for (int i &＃61; 0; i <5; &＃43;&＃43;i)cout <return 0;
}

---

结果&＃xff1a;

---

结论&＃xff1a;

1. 优先级队列定义的<运算 规定低优先级&＃xff0c; 返回为ture的条件说明优先级低&＃xff1b;

2. 类外部定义的cmp相当于实现重载operator <;

3. 由于qsort返回值是int型&＃xff0c; /如果返回值小于0&＃xff0c;则qsort 就得知第一个元素应该在前&＃xff0c;如果返回值大于0&＃xff0c;则第一个元素应该在后。即&＃xff0c;相减顺序与参数一致就是从小到大排序&＃xff1b;

4. sort 的效率比qsort高&＃xff0c; 还是使用sort 就好了&＃xff1b;