優先級隊列自定義比較

我試圖用一個優先級隊列將與下面的成員變量反對自定義：優先級隊列自定義比較

class Jobs{ 
    string id; 
    string location; 
    int start; 
    int end; 
};

我會從文件中讀取作業ID的HashMap和的重量工作。我將最終有一個

unordered_map<string, int> jobWeight;

舉行此信息。我希望將作業列表最終以基於hashmap jobWeight的優先級推送到priority_queue中。最重要的工作應該是第一位的。

參考其他教程，我注意到你應該創建一個單獨的類/結構並實現operator（）。然後你可以將這個比較類傳遞給priority_queue參數。但是，看起來priority_queue使用默認參數創建了這個比較器類的新實例？我怎麼能夠從這個比較類中引用我的jobWeight hashmap？

class CompareJobs{ 

    map<string, int> jobWeight; 

public: 

    CompareJobs(map<string, int> &jobWeight){ 
     jobWeight = jobWeight; 
    } 

    bool operator() (const Jobs &a, const Jobs &b){ 

     return jobWeight.find(a)->second < jobWeight.find(b)->second; 

    } 

};

來源

2016-09-18 David Yuan

你最初說'jobWeight'是一個'unordered_map'。你想把它轉換成一個'map'並把它作爲參數傳遞給你的比較器或者什麼？ – WhiZTiM

這個圖是否用於比這個比較器的其他任何東西？而且：它有多大？ –

@DanielJour當我插入到我的優先級隊列中時，地圖只應用於比較。這張地圖會和工作數量一樣大（每個工作都會有一定的重量），因此可能會超大。目前，最終目標是在每個時間範圍內選擇一份工作（工作從開始到結束不需要持續整個工作時間......所以選擇工作的貪婪方法應該足夠了，我只是使用priority_queue填滿整個時間範圍。 –

std::priority_queue的默認構造函數，其實需要的可選參數：

explicit priority_queue(const Compare& x = Compare(), Container&& = Container());

你會注意到，第一個參數是比較類的一個實例。

首先構造您的比較器類，使其以任何方便的方式引用您的哈希映射，然後使用比較器類構造您的優先級隊列。

來源

2016-09-18 23:42:50

啊從來沒有注意到這一點。非常感謝！ –

我該如何從這個比較器類中引用我的jobWeight散列表？

將對地圖的引用添加到您的Compare類中！當然你需要確保這個引用保持有效。而且你不能使用一個簡單的引用（因爲這些引用是不可複製的，你的Compare類必須是可複製的），而是可以使用std::reference_wrapper。

using IDMap = std::unordered_map<std::string, int>; 

struct JobsByWeight { 
    std::reference_wrapper<IDMap const> weights_ref; 
    bool operator()(Job const & lhs, Job const & rhs) const { 
    auto const & weights = weights_ref.get(); 
    auto lhsmapping = weights.find(lhs.id); 
    auto rhsmapping = weights.find(rhs.id); 
    if (lhsmapping == weights.end() || rhsmapping == weights.end()) { 
     std::cerr << "damn it!" << std::endl; 
     std::exit(1); 
    } 
    return lhsmapping->second < rhsmapping->second; 
    } 
};

然後，只需通過你的比較類的對象你priority queue's constructor（過載（1）中的鏈接）：

std::priority_queue<Job, std::vector<Job>, JobsByWeight> queue{std::cref(that_id_map)};

既然沒有構造，使您可以將您的比較級在隊列中，您確實需要參考JobsByWeight。否則就會有你的地圖副本（如你所說，這可能很大）。

注意：未經測試的代碼。

來源

2016-09-18 23:53:10

感謝您的支持！從來沒有意識到priority_queues帶參數。 –

優先級隊列自定義比較

回答

相關問題