C ++ STL | 用户定义的优先级队列比较器

  • Z时代
  • 2024-01-10
  • 分类：综合

在本文中，我们将看到如何使用lambda函数在C ++ STL中为优先级队列编写比较器函数。当您可能不考虑如何创建数据类型的优先级队列或使用比较器时，这无疑将帮助您更广泛地使用优先级队列。

C ++ STL中默认优先级队列的语法为：

priority_queue<int> pq;

默认情况下，上述优先级队列用作最大堆，即from的最大值将排在顶部，依此类推。因此，如果我们弹出并打印，我们将得到一个降序排列的列表。

使用priority_queue STL创建最小堆

我们可以使用Greater <int>类来定义最小堆

语法为：

priority_queue<int,vector<int>,greater<int>> pq;

其中，vector <int>用作容器，Greater <int>用作比较器类，

为优先级队列定义自己的比较器

您可能经常遇到需要使用优先级队列的情况，但是您的数据类型是默认情况下无法比较的其他内容（默认情况下使用'<'运算符）。在这种情况下，我们需要声明比较器函数。

我们可以为此使用lambda函数。

例如，

假设我们需要比较以下对象，

student{
    int roll
    int marks
};

比较规则是，如果任何两个学生的分数相同，则将根据他们的成绩进行排序（以先到的成绩优先），否则，得分越高的学生的优先级越高。

我们如何定义以上比较器？

下面是lambda函数的使用，它将作为我们的比较器

语法为：

auto it=[](student a, student b){
    //比较逻辑
    if(a.marks>b.marks)
        return false;
    else if(a.marks<b.marks)
        return true
    else //当标记相同时
    if a.roll<b.roll
        return false
    else
        return true
};

上面是lambda比较器函数，该函数将两个数据成员作为参数并使用逻辑两个比较，false表示当前位置可以，即不需要交换，true表示需要交换。

现在，优先级队列将声明为：

priority_queue<student, vector<student>, decltype(it)> pq(it);

它是我们的比较器功能。需要注意的一点是，比较器函数也作为构造函数传递。

因此，无论何时将项目添加到优先级队列中，

它会根据用户定义的逻辑进行必要的交换，并按顺序放置项目。

示例

假设我们有5位学生的以下数据，

Roll	Marks
1	65
2	78
3	87
4	65
5	78

因此，将第一个学生数据插入优先级队列。

由于没有其他成员。

优先队列现在是

1	65

因此，将第二个学生数据插入优先级队列。

现在，根据我们的比较器将进行交换。

因此，优先级队列现在是

2	78
1	65

因此，在优先级队列中插入第三个学生数据。

现在，根据我们的比较器，将进行交换。

因此，优先级队列现在是

3	87
2	78
1	65

因此，在优先级队列中插入第四个学生数据。

因此，根据我们的比较器，优先级队列现在为

3	87
2	78
1	65
4	65

因此，在优先级队列中插入第五个学生数据。

因此，根据我们的比较器，优先级队列现在为

3	87
2	78
5	78
1	65
4	65

因此，弹出后，我们将获得学生列表，

3 87
2 78
5 78
1 65
4 65

优先级队列的用户定义比较器的C ++实现

#include <bits/stdc++.h>
using namespace std;
class student {
public:
    int roll;
    int marks;    student()
    {
        roll = 0;
        marks = 0;
    }
};
void sort_students(vector<student> arr)
{
    //比较器lambda函数
    auto comp = [](student a, student b) {
        //比较逻辑
        if (a.marks > b.marks)
            return false;
        else if (a.marks < b.marks)
            return true;
        else { //当标记相同时
            if (a.roll < b.roll) {
                return false;
            }
            else
                return true;
        }
    };
    priority_queue<student, vector<student>, decltype(comp)> pq(comp);
    for (auto& ij : arr) {
        pq.push(ij);
    }
    //打印排序列表
    cout << "roll marks\n";
    while (!pq.empty()) {
        cout << pq.top().roll << " " << pq.top().marks << endl;
        pq.pop();
    }
}
int main(){
    int n;
    
    cout << "Enter number of students\n";
    cin >> n;
    
    vector<student> arr(n);
    cout << "Enter roll and marks for each student\n";
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        arr[i].roll = x;
        arr[i].marks = y;
    }
    
    cout << "sorting students according to marks and roll no: \n";
    
    sort_students(arr);
    
    return 0;
}

输出：

Enter number of students
5
Enter roll and marks for each student
1 65
2 78
3 87
4 65
5 78
sorting students according to marks and roll no: 
roll marks
3 87
2 78
5 78
1 65
4 65

以上是 C ++ STL | 用户定义的优先级队列比较器 的全部内容， 来源链接： utcz.com/z/315996.html

回到顶部