visweshn92 visweshn92 - 2 months ago 8
C++ Question

How do achieve this comparison in STL priority_queue inside C++ Class

This is NOT a duplicate question It differs here as the comparison function has a dependancy on the main class.

All my logic is in a class. I have a map

nodeCnt
which can be looked up upon
getCnt()
. I am figuring out for how to have a custom comparison
myCmp
for my priority queue
pq
which will do comparison based on the map.

The following snippet does not work. And having
auto cmp
as described in reference docs cannot be done as Class cannot have such declarations for comparison function.

Class AllLogic {

private:
std::map<int, int> nodeCnt;

// This is my confusing part
std::priority_queue<int, std::vector<int>, decltype(&myCmp)> pq(&myCmp);

public:

int getCnt(int val) {
if (nodeCnt.find(val) != nodeCnt.end())
return nodeCnt[val];
return 0;
}

bool myCmp(int left, int right) {
return getCnt(left) < getCnt(right);
}
};

Answer

You can rework the code a bit to the following (note: the following is c++11):

#include <map>
#include <queue>

The comparison functor takes a reference to the map, and uses it to compare:

struct myCmp {
    explicit myCmp(std::map<int, int> &nodeCnt) : nodeCnt_{&nodeCnt} {}

    bool operator()(int lhs, int rhs) const {
        auto lhs_it = nodeCnt_->find(lhs);
        auto rhs_it = nodeCnt_->find(rhs);
        auto lhs_val = lhs_it == nodeCnt_->end()? 0: lhs_it->second;
        auto rhs_val = rhs_it == nodeCnt_->end()? 0: rhs_it->second;
        return lhs_val < rhs_val; 
    }

private:
   std::map<int, int> *nodeCnt_;
};

The class sets the map, then the comparison functor, then the queue; each one uses the previous one:

class AllLogic {
private:
   std::map<int, int> nodeCnt;
   myCmp myCmp_{nodeCnt};
   std::priority_queue<int, std::vector<int>, myCmp> pq{myCmp_};
};

int main(){}
Comments