實現可以在C++中迭代的優先級隊列

我需要爲項目實現優先級隊列，但STL的priority_queue未指示，因爲我們需要遍歷所有元素並隨機刪除它們。實現可以在C++中迭代的優先級隊列

我們正在考慮使用STL的set來做到這一點，將它包裝在一個類中以使其成爲ADT。

有沒有比這更聰明的解決方案？

我們怎樣才能讓set的公共成員函數可以公開使用？我們感興趣的是迭代器等

顯然導出STL是因爲缺少虛析構函數的不明智的：/

新代碼：

#ifndef PRIORITYQUEUE_H_ 
#define PRIORITYQUEUE_H_ 

#include <set> 

template<typename T, template<typename X> class impl_type = std::set> 
class PriorityQueue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
public: 
    void push(const T& x) { 
     insert(x); 

    } 

    void pop() { 
     erase(begin()); 
    } 

    const T& top() const { 
     return *begin(); 
    } 
}; 

#endif /* PRIORITYQUEUE_H_ */

所以，我們目前有這個。編譯器不抱怨插入，但它確實抱怨erase(begin())和return *begin()：

there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available

這是爲什麼？

來源

2010-12-12 Francisco P.

您應該將線程標記爲家庭作業。 – Pacane 2010-12-12 13:52:44

這是一個更大的項目的一小部分。但是當然，我不需要代碼的答案。 – 2010-12-12 13:53:40

您應該能夠使用std::vector,std::make_heap,std::push_heap和std::pop_heap來實現您自己的優先級隊列。這不是如何實現std::priority_queue？您只需要再次調用std::make_heap即可在刪除隨機元素時修復數據結構。

您是否需要按順序遍歷元素？有一個std::sort_heap算法來訂購底層的std::vector。

來源

2010-12-12 15:22:38 Blastfurnace

make_heap和std :: priority_queue可能是也可能不是正確的選擇，因爲它們不能保證穩定性（注意：排序順序穩定性不是崩潰穩定性。） – stonemetal 2010-12-13 02:15:20

你真的需要優先隊列嗎？

您需要遍歷所有的項目和隨機刪除 - 在開始>鏈表

如果您需要保留列表排序，排序，然後，插入新的項目，使用插入排序時（插入新項目在正確的地方）。

來源

2010-12-12 12:41:23 Vojta

STL的設置應該可以用來製作你想要的東西，但我必須注意到需求列表看起來有點奇怪。你可以定義一個新類型。

template<typename T, template<typename X> class impl_type = std::set> class prio_queue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
    // etc 
public: 
    // Forward the set's members 
    T& top() { 
     return *begin(); 
    } 
    // etc 
};

來源

2010-12-12 13:57:18 Puppy

請檢查更新後的問題，並返回一些錯誤。 – 2010-12-12 15:20:42

@Francisco：那是因爲你沒有轉發該組的成員，就像我在我的評論中寫的那樣。 – Puppy 2010-12-12 18:50:06

然後我不明白轉發的概念。 – 2010-12-13 15:49:44

我將遵循例如通過一些其他的容器的適配器在標準庫使用組合物設置，使下層容器模板參數的類型。雖然因爲這是一個學校項目，可能會有太大的靈活性。您可以從現有容器之一開始使用組合，並根據需要從那裏進行構建。

來源

2010-12-12 14:05:21 stonemetal

實現可以在C++中迭代的優先級隊列

回答

相關問題