Question

对pair优先队列如何使小值先出队列 即按pair第一个元素排序 小的先出

typedef pair<int,int> pii;
priority_queue<pii> Q;
STL这东西用的还不是很熟悉 求帮助。。。

Answer 1

typedef pairpii;
priority_queue<pii, vector, yourcomparison> Q;

//yourcomparison @@@@I'm not sure if it's reference here, you can try it yourself
bool yourcomparison(const pii& p1, const pii& p2) {
return p1.first < p2.first;
}

Answer 2

typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, yourcomparison> Q;

//yourcomparison @@@@I'm not sure if it's reference here, you can try it yourself
bool yourcomparison(const pii& p1, const pii& p2) {
return p1.first < p2.first;

Answer 3

typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, yourcomparison> Q;

//yourcomparison @@@@I'm not sure if it's reference here, you can try it yourself
bool yourcomparison(const pii& p1, const pii& p2) {
return p1.first < p2.first;
}

Answer 4

默认的是先把 pair 的第一位作为第一关键字， pair 的第二位作为第二关键字

例如：

typedef pair <long long, int> point;
priority_queue <point, vector<point>, greater<point> > q;

中，通过 typedef 将 point 转化为一种类似于自定义类型的形式，优先队列先考虑 point 的 first 位