按第一和第二元素排序的C++对中的优先级队列
在C++中,优先级队列是一个非常实用的容器,它可以根据元素的优先级自动排序,并在需要时弹出优先级最高的元素。如果你需要一个可以方便地按照元素的第一和第二属性排序的优先级队列,那么你来对地方了。本文将介绍如何在C++中使用自定义比较函数来排序元素,并展示一些示例代码。
自定义比较函数
在C++中,我们可以通过自定义一个比较函数来定义元素的排序方式。比较函数必须返回一个布尔值,如果第一个参数应该排在第二个参数之前,则返回true,否则返回false。以下是一个简单的比较函数示例:
bool compare(int a, int b) {
return a > b; // 从大到小排序
}
上述比较函数将整数从大到小排序。你可以通过修改函数体来定义其他的排序方式。比如,如果你想按照字符串长度从小到大排序,你可以这样定义比较函数:
bool compare(string s1, string s2) {
return s1.length() < s2.length(); // 从小到大排序
}
另外,你也可以通过自定义一个结构体来定义元素的排序方式。以下是一个存储学生信息的结构体示例:
struct student {
string name;
double score;
bool operator < (const student& s) const { // 自定义小于运算符
if (score != s.score) {
return score > s.score;
} else {
return name < s.name;
}
}
};
上述结构体将学生按照分数从高到低排序,如果分数相同,则按照姓名的字典序从小到大排序。你可以通过修改小于运算符来定义其他的排序方式。
按第一和第二元素排序的优先级队列
现在,我们可以使用定义的自定义比较函数来定义一个可以方便地按照元素的第一和第二属性排序的优先级队列了。以下是一个简单的示例代码:
priority_queue< pair<int, int>, vector<pair<int, int>>, function<bool(pair<int, int>, pair<int, int>)> > q(compare);
上述代码定义了一个按照第一和第二元素排序的优先级队列。每个元素都是一个pair<int, int>类型的值,第一元素存储第一属性的值,第二元素存储第二属性的值。优先级队列的比较方式由自定义的比较函数compare决定。
现在,我们可以向队列中添加元素了:
q.push(make_pair(3, 4));
q.push(make_pair(1, 5));
q.push(make_pair(2, 2));
q.push(make_pair(4, 3));
上述代码添加了四个元素到队列中,它们的第一和第二属性依次是(3,4),(1,5),(2,2),(4,3)。由于我们定义的比较函数compare按照第一和第二属性排序,所以队列中的元素应该依次是(1,5),(4,3),(3,4),(2,2)。
现在,我们可以使用pop()函数弹出优先级最高的元素了:
pair<int, int> p = q.top();
q.pop();
cout << p.first << " " << p.second << endl; // 输出1 5
由于队列中的第一个元素是(1,5),它是所有元素中第一属性最小的,因此它会被弹出队列。
示例代码
下面是一个按照座位距离和学生编号排序的优先级队列的示例代码,可以参考它的实现方式:
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
using namespace std;
const int MAXN = 100;
struct student {
string name;
int seat;
bool operator < (const student& s) const { // 自定义小于运算符
if (seat != s.seat) {
return seat > s.seat;
} else {
return name < s.name;
}
}
};
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
if (a.first != b.first) {
return a.first > b.first;
} else {
return a.second > b.second;
}
}
int main() {
priority_queue< pair<int, int>, vector<pair<int, int>>, function<bool(pair<int, int>, pair<int, int>)> > q(compare);
student s[MAXN] = {
{"Jack", 5},
{"Tom", 2},
{"Lucy", 1},
{"Peter", 3},
{"Mike", 4},
{"John", 2},
{"Mary", 3},
{"Lily", 1}
};
for (int i = 0; i < MAXN; i++) {
q.push(make_pair(s[i].seat, i));
}
while (!q.empty()) {
pair<int, int> p = q.top();
q.pop();
cout << s[p.second].name << " " << s[p.second].seat << endl;
}
return 0;
}
上述代码将学生按照座位距离和学生编号排序,并输出排序后的顺序。
结论
本文介绍了如何在C++中使用自定义比较函数来定义元素的排序方式,并展示了如何使用自定义比较函数来定义一个可以方便地按照元素的第一和第二属性排序的优先级队列。通过本文的介绍和示例代码,你应该学会了如何在C++中使用自定义比较函数来排序元素,以及如何使用自定义比较函数来定义一个可以方便地按照元素的第一和第二属性排序的优先级队列。