CODEWITHSUNDEEP
c++stlqueue
emperorspride188
emperorspride188

Reputation: 889

C++ using a priority queue of objects

I want to make a priority queue of objects, Specifically pair of (int, int). The queue should contain pairs with a priority assigned to them. 

#include <iostream>
#include <queue>

using namespace std;    

class saPair{
public:
    int s;
    int a;
    double priority;
    saPair(int s, int a, double priority){
        this->s = s;
        this->a = a;
        this->priority = priority;
    }
};

// the priority menmber variable determines the priority in the queue
// highest priority pair of (int, int) stays on the top
bool operator< (const saPair& x, const saPair& y) {
    return x.priority < y.priority;
}


int main()
{
    priority_queue<saPair> pq;
    pq.push(saPair(0,0, 0.3));
    pq.push(saPair(0,1, 0.1));
    pq.push(saPair(0,3, 0.5));
    pq.push(saPair(0,3, 5));

    cout << pq.top().a << endl;
    pq.pop();
    cout << pq.top().a << endl;
    pq.pop();
    cout << pq.top().a << endl;


}

As you can see, the pair (0,3) has highest priority so it stays on the top. But the problem with my implementation is that, if I add (0,3) pair again with different priority, I add a new element to the queue, instead of replacing the priority of the already existing (0,3) pair.

I feel like I choose the wrong data structure for my requirement. I tried map taking key value, by defining a new saPair(int, int) class with operating overload for < operator. But even that doesn't seem to work properly..

Any suggestions on how to proceed? or modify

Upvotes: 1

Views: 1478

Answers (1)

Ap31
Ap31

Reputation: 3324

It seems like you need a multi-key access to your container: you want to sort it by priority (or at least have a binary heap by priority as in priority_queue), and you want the pair values to be unique, so you'll need a pair value lookup too.

There is no default solution for that in standard library, but it shouldn't be too hard to craft your own.

I'd suggest simply storing an additional std::set<saPair> to check if the pair is already in your container. This way you can keep your priority_queue the way it is, and it won't take too much effort to implement.

Don't forget to add operator< to saPair though (or replace it by std::pair), otherwise std::set would not be able to work with it.

Another option is just manually check your priority_queue for a pair every time you add it. While asymptotically worse than std::set solution, this might very well be faster in practice, and it will save you some space. However I think the code would be much cleaner if you go with std::set.

Yet another solution is boost::multi_index, which allows you to easily construct any multi-indexed container you want. However I don't think it'll let you capitalize on the fact that you don't need a strong ordering by priority, so it won't have a linear contiguous layout like priority_queue does.

Upvotes: 1

Related Questions