如何在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(){}