如何在C++中实现STL priority_queue中的这种比较类

Question

这不是一个重复的问题它与此处的不同之处在于比较函数对主类有依赖性。

我所有的逻辑都属于一个类。我有一张地图nodeCnt，可以查询getCnt()。我正在计算如何为我的优先队列pq定制比较myCmp，该比较将根据地图进行比较。

以下代码段不起作用。如reference docs中所述的auto cmp不能完成，因为Class不能具有用于比较功能的这种声明。

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 1

使这样的结构：

// forward declare your class, because the comparator will use it 
class AllLogic; 

struct MyCompareT 
{ 
    AllLogic* object; 
    bool operator()(int left, int right) const; 
}; 

// after AllLogic has been defined 
bool MyCompareT::operator()(int left, int right) const { 
    return object->myCmp(left, right); 
} 

而且你priority_queue可以定义为：

std::priority_queue<int, std::vector<int>, MyCompareT> pq; 

并初始化在构造是这样的：

AllLogic() :pq(MyCompareT{this}) {} 

Answer 2

你可以重做码的位以如下（注意：下面的是C++ 11）：

#include <map> 
#include <queue> 

比较仿函数取到地图的引用，并使用它进行比较：

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

类设置地图，然后是比较函子，然后是队列;每个使用前一个：

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

int main(){}