使用對象的優先級隊列的C++

我想創建一個對象的優先級隊列，特別是對（int，int）。隊列應該包含分配給它們的優先級。使用對象的優先級隊列的C++

#include <iostream> 
#include <queue> 

using namespace std;  

class saPair{ 
public: 
    int s; 
    int a; 
    double priority; 
    saPair(int s, int a, double priority){ 
     this->s = s; 
     this->a = a; 
     this->priority = priority; 
    } 
}; 

// the priority menmber variable determines the priority in the queue 
// highest priority pair of (int, int) stays on the top 
bool operator< (const saPair& x, const saPair& y) { 
    return x.priority < y.priority; 
} 


int main() 
{ 
    priority_queue<saPair> pq; 
    pq.push(saPair(0,0, 0.3)); 
    pq.push(saPair(0,1, 0.1)); 
    pq.push(saPair(0,3, 0.5)); 
    pq.push(saPair(0,3, 5)); 

    cout << pq.top().a << endl; 
    pq.pop(); 
    cout << pq.top().a << endl; 
    pq.pop(); 
    cout << pq.top().a << endl; 


}

正如您所看到的，對（0,3）具有最高的優先級，因此它保持在最高位置。但是我的實現的問題是，如果我以不同的優先級再次添加（0,3）對，我會向隊列中添加一個新元素，而不是替換已存在的（0,3）對的優先級。

我覺得我爲我的要求選擇了錯誤的數據結構。我試圖通過定義一個新的saPair（int，int）類來爲映射獲取關鍵值，該類具有操作超載的運算符<。但即使這似乎並沒有正常工作..

關於如何進行的任何建議？或修改

來源

2017-04-03 emperorspride188

它是一個隊列，所以沒有關於唯一性的要求。也許你想要的是一套？！ – Arash

是的。沒有辦法直接使用隊列。我正在尋找一種替代數據結構。這感覺就像是一種常見的數據結構，但我無法找到一個簡單的解決方案。一個對象，以及分配給該對象的相應優先級。按優先級順序對對象進行排序。我需要一個滿足這一點的數據結構。 – emperorspride188

看起來您需要對您的容器進行多鍵訪問：您希望按照優先級對其進行排序（或者至少按照priority_queue中的優先級對二進制堆進行排序），並且希望對值爲獨特的，所以你也需要一對值查找。

標準庫中沒有默認的解決方案，但是製作自己的應用程序不應該太難。

我建議簡單地存儲一個額外的std::set<saPair>來檢查是否已經在你的容器中。通過這種方式，您可以保持priority_queue的原樣，並且不需要太多的努力來實施。

不要忘記將operator<加到saPair雖然（或者用std::pair代替它），否則std::set將無法使用它。

另一種選擇是每次添加時手動檢查您的priority_queue。雖然漸近地比std::set解決方案更差，但實際上這可能會更快，並且會爲您節省一些空間。不過，我認爲如果您使用std::set，代碼將會更清晰。

另一種解決方案是boost::multi_index，它允許您輕鬆構建任何你想要的多索引容器。不過，我認爲它不會讓你利用這個事實，即你不需要按優先級進行強排序，所以它不會有像priority_queue那樣的線性連續佈局。

來源

2017-04-03 05:45:46 Ap31

使用對象的優先級隊列的C++

回答

相關問題