優先級隊列：使用一個對象來比較而不是類

開始於priority_queue s，我有這樣的問題：我需要將元素存儲在隊列中，但是它們的排序方式不包含在元素中本身，而是不同的地方，就像在一個地圖：優先級隊列：使用一個對象來比較而不是類

std::map<element, value> element_values; 
std::priority_queue<element> queue;

我現在需要的是類似的東西：

struct Comp 
{ 
    std::map<...>& the_map; 
    Cpmp(std::map<...> _map) : the_map(_map) {} 

    bool operator() (element a, element b) 
    { 
     return the_map[a] < the_map[b]; 
    } 
} 

Comp comp(element_values); 
std::priority_queue<element, std::vector<element>, comp> queue; // does not work 
std::priority_queue<element, std::vector<element>, Comp> queue; // does work but I'd not be able to pass values to the constructor

本身沒有intrensic順序的元素。一個解決方法是定義一個包裝這個東西的結構，但也許有人知道一個更聰明的方法。我也想過提供一個只在當前範圍內有效的比較函數（它本身就是一個函數），但據我所知C++不支持這個函數，至少不需要像我需要的那樣捕獲局部變量。

來源

2012-02-08 wal-o-mat

從C++的角度來看，一個仿函數是覆蓋（）操作的結構。你所問的代碼是解決問題的完全合理的方法。 Dietmar的答案填入空格:) – Bukes 2012-02-08 20:50:44

'Comp'應該將地圖作爲構造函數中的const引用，存儲const引用，並且運算符應該是const。 – 2012-02-08 20:53:21

我注意到cppreference.com沒有記錄帶比較函數的構造函數。我想知道這是否是混淆的根源。 – 2012-02-08 20:54:58

std::priority_queue<T, Cont, Comp>將比較對象類型作爲模板參數。傳遞對象引用的東西，你需要把它作爲構造函數的參數：

std::priority_queue<element, std::vector<element>, Comp> queue(comp);

來源

2012-02-08 20:50:44

可以使用priority_queue類的比較模板參數。因爲你的代碼中有幾個問題，這裏是一個全面清理後的版本：

#include <deque> 
#include <queue> 
#include <map> 
#include <cassert> 

typedef std::map<element, value> element_map; 

struct Comp 
{ 
    element_map const & m; 

    Comp(element_map const & m_) : m(m_) { } 

    bool operator()(element a, element b) const 
    { 
     element_map::const_iterator it1 = m.find(a), it2 = m.find(b); 

     assert(it1 != m.end() && it2 != m.end()); 

     return it1->second < it2->second; 
    } 
}; 

typedef std::priority_queue<element, std::deque<element>, Comp> element_pq;

我們使用：

int main() 
{ 
    element_map m; 
    element_pq pq((Comp(m))); // ... sigh ... 
}

來源

2012-02-08 20:57:47

感謝您清理我的代碼，實際上它看起來不同於我在這裏發佈的內容，只是爲了說明這一點我的函子需要參數通過:) – 2012-02-08 21:29:42

優先級隊列：使用一個對象來比較而不是類

回答

相關問題