stl priority_queue of C++ with struct

Question

How can we use STL priority_queue for struct ? Any illustration of pushing & popping , where struct has multiple data-types?
Say : struct thing { int a; char b;} glass[10]; .
Now how can i put this struct on priority_queue using 'int a' for ordering ?

Insinuating

Answer 1

Here is a slightly modified answer to your original question, which you deleted for no apparent reason. The original contained enough information for you to figure this out, but here it goes: provide a less than comparison that uses the int for comparison.

All you need to do is provide a functor that implements a less-than comparison with strict weak ordering, or a less-than operator for your class implementing the same. This struct satisfies the requirements:

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

then

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();

Masseter

Thanks ^_^ & just 1 last thing : how will i push say (3,a) to the queue direclty ? i dont know how to put (3,a) to 'thing stuff= ...' . – Insinuating

In c++11, you can say q.push(thing{42, 'x'}) or q.emplace(42, 'x'). If you don't have C++11 support, you need to give thing a constructor. – Masseter

Is it necessary for the argument to be a const reference? Why cant we simply do bool operator<(thing rhs) ? – Slowly

The q.emplace(424242, 'z'); // C++11 only line is wrong, it will throw errors all the way up to c++20. For this to work the struct needs to have an explicit constructor. – Typescript

Answer 2

Overload < operator for 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();

Agnusago

Answer 3

You need to implement a compare function or overload operator to tell priority queue that on which order you want to sort your custom data. When priority queue will sort your data then it will need a way to know how to compare among them. You have to specify this by passing a function to priority queue or overloading operator in you custom data class or structure.

You can check this answer. This might help you. I have tried to explain multiple ways of using priority queue for custom data types.

Domitiladomonic

Answer 4

You can do it like this!

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);

Yolk

Answer 5

Priority Queue in Structure can be Implemented in two ways::

1. Overloading the < operator
2. Passing the boolean comparator operator wrapped in structure.

Let us take a structure car which has model and price both integers and build priority queue based on highest price at the top.

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

For Method 1 we need to do this:

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

For Method 2 we need to pass this structure:

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

Full Code for illustration:::

#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;
}

Output will be:::

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

Niue

bool operator < (const Car& c1,const Car& c2){ return c1.p < c2.p; } Here Priority Queue order will be Car 2 will be given more priority over Car1 if return true It will be above in Priority List. < (const Car& c1,const Car& c2) ==> if true priority of c2 will be higher than c1. As Priority Queue are by default implemented as Max Heap Fashion. – Niue