我如何在優先隊列中找到價值？

Question

我想找到我的優先級隊列中的一個節點，但我沒有找到一個解決辦法:( 如果你有一個解決方案，我很感興趣。

THX的幫助。

Answer 1

如果您確實需要通過std::priority_queue進行搜索並希望高效地進行搜索，則可以派生出新類並添加find成員函數。既然你沒有添加任何額外的狀態，你不必擔心切片或其他問題，因爲std::priority_queue不是多態。

#include <queue> 
template< 
    class T, 
    class Container = std::vector<T>, 
    class Compare = std::less<typename Container::value_type> 
> class MyQueue : public std::priority_queue<T, Container, Compare> 
{ 
public: 
    typedef typename 
     std::priority_queue< 
     T, 
     Container, 
     Compare>::container_type::const_iterator const_iterator; 

    const_iterator find(const T&val) const 
    { 
     auto first = this->c.cbegin(); 
     auto last = this->c.cend(); 
     while (first!=last) { 
      if (*first==val) return first; 
      ++first; 
     } 
     return last; 
    } 
}; 

Answer 2

我認爲ü需要基本的幫助。讀這可能這將幫助ü

http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html

Answer 3

如果你不關心性能，你可以聲明iterator遍歷priority_queue的容器，但在C++中，底層的容器被宣佈爲protected，無法直接訪問。

我的解決方案之一是獲取容器的迭代器是聲明一個繼承自std::priority_queue的新類。

typedef int Val_TYPE; 
typedef vector<Val_TYPE> Container_TYPE; 
typedef priority_queue<Val_TYPE, Container_TYPE> pri_queue; 

class Queue: public pri_queue{ 
public: 
    Container_TYPE::iterator begin(){ 
     return pri_queue::c.begin(); 
    } 
    Container_TYPE::iterator end(){ 
     return pri_queue::c.end(); 
    } 
}Q; 

然後你可以得到容器的迭代器。

Q.push(4); 
Q.push(3); 
Q.push(35); 
for(vector<int>::iterator p=Q.begin(); p!=Q.end(); p++) 
cout << *p << endl; 

---

爲了更有效，例如尋找某些關鍵數據，你可以使用pointers to data。

假設類Data包含您的每項數據。 Data.key是搜索的關鍵，Data.value是priority_queue中的優先。

struct Data{ 
    VALUE_TYPE value; 
    KEY_TYPE key; 
    ... 
    ... 
}; 

將所有數據存儲在單獨的集合中，例如數組或鏈接列表。

Data data[MAX]; 

定義存儲用於特定的一個data[i]

struct Node{ 
    Data* data; 
    Node(Data* ptr){data=ptr;} 
}; 

使用priority_queue和其它數據結構中的支持的搜索即binary search tree，hash指針新結構。這裏我使用multimap。

同時保持priority_queue的Node和multimap的Node。

struct cmp1{ 
    bool operator(Node a, Node b){ return a.data->value < b.data->value; } 
}; 

struct cmp2{ 
    bool operator(Node a, Node b){ return a.data->key < b.data->key; } 
}; 

priority_queue<Node, vector<Node>, cmp1> q; 

multimap <KEY_TYPE, Node, cmp2> d; 

for(int i = 0; i < n; ++i){ 
    q.push(Node(&a[i])); 
    d.insert(a[i].key, Node(&a[i])); 
} 

然後，你可以使用多重映射d數據的pointer通過鍵搞定。通過使用priority_queue q也滿足對priority_queue的需求。

以上所有僅僅是使用指針。