使用C++的STL优先队列与结构体的实现

Question

我们如何使用STL的priority_queue来处理结构体？
请举一个例子说明如何在结构体中有多种数据类型时进行推送和弹出操作。
比如，假设我们有这样一个结构体：struct thing { int a; char b;} glass[10]; ，现在我们想要按照其中的'int a'对其进行排序并放入优先队列中，该怎么做呢？

- Manas Verma

Answer 1

这是对您原来的问题，您无缘无故删除了稍加修改后的答案。原始内容已经包含了足够的信息让您能够理解，但以下是具体步骤：提供一个使用int进行比较的小于比较。

你需要做的就是提供一个实现严格弱序的小于比较的函数对象，或者为实现相同功能的类提供一个小于运算符。以下结构体可以满足要求：

struct thing
{
    int a;
    char b;
    bool operator<(const thing& rhs) const
    {
        return a < rhs.a;
    }
};

那么

std::priority_queue<thing> q;
thing stuff = {42, 'x'};
q.push(stuff);
q.push(thing{4242, 'y'}); // C++11 only
q.emplace(424242, 'z'); // C++11 only    
thing otherStuff = q.top();
q.pop();

- juanchopanza

---

谢谢 ^_^ 还有最后一件事：我该如何直接将(3,a)推入队列？我不知道如何将(3,a)放入“thing stuff= **...**”中。 - Manas Verma

在c++11中，您可以使用q.push(thing{42, 'x'})或q.emplace(42, 'x')。如果您没有C ++ 11支持，则需要给thing一个构造函数。 - juanchopanza

参数必须是const引用吗？为什么不能简单地这样做：bool operator<(thing rhs)？ - Evil_Transistor

“q.emplace(424242, 'z'); // 仅适用于C++11”这行代码是错误的，它会一直抛出错误，直到c++20。为了让它正常工作，结构体需要有一个显式的构造函数。 - Setsu

Answer 2

为 thing 重载 < 运算符：

struct thing
{
    int a;
    char b;

    bool operator<(const thing &o) const
    {
        return a < o.a;
    }
};

priority_queue<thing> pq;

thing t1, t2, t3;

// ...

pq.push(t1);
pq.push(t2);

// ...

t3 = pq.top();
pq.pop();

- masoud

Answer 3

你需要实现一个比较函数或重载运算符，告诉优先队列按照哪个顺序对自定义数据进行排序。当优先队列对数据进行排序时，它需要知道如何在它们之间进行比较。你必须通过向优先队列传递一个函数或在你的自定义数据类或结构中重载运算符来指定这一点。

你可以查看this的答案。这篇文章可能会对你有所帮助。我已经尝试解释了多种使用优先队列处理自定义数据类型的方法。

- Taohidul Islam

Answer 4

结构中的优先队列可以通过两种方式实现：

1. 重载 < 运算符
2. 传递包装在结构中的布尔比较运算符。

让我们以一个名为 car 的结构为例，该结构具有模型和价格两个整数，并基于最高价格构建优先队列。

struct Car
{
    int m;
    int p;
    void set(int a,int b){
        m =a,p = b;
    }
};

对于方法1，我们需要这样做：

bool operator < (const Car& c1,const Car& c2){
    return c1.p < c2.p;
}

对于方法2，我们需要传递这个结构：

struct Cmp{
    bool operator()(const Car& c1,const Car& c2){
            return c1.p < c2.p;
    }
};

完整的代码示例：

#include <iostream>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
using namespace std;

struct Car
{
    int m;
    int p;
    void set(int a,int b){
        m =a,p = b;
    }
};
struct Car cT[50];
int cI=0;
void printC(){
    for(int i=0;i<cI;i++){
        cout <<" car model: " << cT[i].m << " price: " <<cT[i].p <<endl;
    }
}

bool operator < (const Car& c1,const Car& c2){
    return c1.p < c2.p;
} //Method 1

struct Cmp{
    bool operator()(const Car& c1,const Car& c2){
            return c1.p < c2.p;
    }
}; //Method 2

void pushQ(priority_queue<Car,vector<Car>,Cmp>& Q){
 for(int i=0;i<cI;i++){
        Q.push(cT[i]);
        cout <<"Queue Push car model: " << cT[i].m << " price: " <<cT[i].p <<endl;
    } 
};

void printQ(priority_queue<Car,vector<Car>,Cmp> Q){
    while(!Q.empty()){
        Car c = Q.top();
        Q.pop();
        cout <<" car model: " << c.m << " price: " <<c.p <<endl;
    }
}
int main() {
    // Write C++ code here
    
    // priority_queue<Car> Q; // #Method 1 
    priority_queue<Car,vector<Car>,Cmp> Q;// #Method 2 
    cT[cI++].set(4,5);
    cT[cI++].set(34,4);
    cT[cI++].set(43,6);
    cT[cI++].set(41,15);
    pushQ(Q);
    printQ(Q);
   // printC();
    // cout << "Hello world!" <<f1;

    return 0;
}

输出将是：

car model: 41 price: 15
car model: 43 price: 6
car model: 4 price: 5
car model: 34 price: 4

- Bhanu Mahto

---

bool operator < (const Car& c1,const Car& c2){ return c1.p < c2.p; }在这里，如果返回true，则Car2将比Car1具有更高的优先级，并且将位于优先级列表的顶部。“<（const Car＆c1，const Car＆c2）”==>如果为真，则c2的优先级将高于c1。由于优先队列默认以最大堆方式实现。 - Bhanu Mahto

Answer 5

你可以像这样做！

struct example{
   int height;
   int weight;
};

struct comp{
        bool operator()(struct example a, struct example b){
         //Sorting on the basis of height(Just for example)
            return (a.height > b.height);
        }
    };

// And here comes your priority queue
 priority_queue<struct example, vector<struct example>, comp> pq;
struct example your_obj;
pq.push(your_obj);

- Sahilgrewalhere