如何使STL的priority_queue固定大小

我創建一個簡單的遊戲，我用std::priority_queue給了命令到隊（每隊有一個priority_queue<command>）。如何使STL的priority_queue固定大小

每20秒一個機器人分析的情況，將命令發送到priority_queue。

我怎樣才能讓priority_queue固定大小的，例如，將大小設置爲10？預期的效果是，當達到最大值時，如果向隊列添加2個新命令，則會自動刪除2個具有最低優先級的現有命令。

2012-07-21 Damir

這是一個新的。幸運的是，我從來沒有這樣做過。我懷疑@DeadMG有唯一明顯的解決方案 - 你將不得不編寫一些代碼來做到這一點，鎖定隊列並迭代它:( – 2012-07-21 08:41:15

[Here]（http://stackoverflow.com/a/3034221/204847））是訪問'priority_queue'的底層容器的骯髒破解（該示例使用'stack'，但原理是相同的），但可能有更好的解決方案 – 2012-07-21 11:07:47

'priority_queue'實現一個二進制排序的堆在底層容器中，它不是被設計爲迭代的 - 但是頂層元素是最大的，並且在日誌時間內具有「push」和「pop」的性能 – Aesthete 2012-07-21 15:39:40

敷在，會爲你執行此操作的類。該標準本身不提供這樣的功能。

來源

2012-07-21 08:20:43 Puppy

這是偷偷摸摸的，但你應該能夠覆蓋的std::priority_queue功能，你需要什麼。這似乎在我做的一些測試中有效：

template<typename T> 
class fixed_priority_queue : public std::priority_queue<T> 
{ 
    public: 
    fixed_priority_queue(unsigned int size) : fixed_size(size) {} 
    void push(const T& x) 
    { 
     // If we've reached capacity, find the FIRST smallest object and replace 
     // it if 'x' is larger 
     if(this->size() == fixed_size) 
     { 
     // 'c' is the container used by priority_queue and is a protected member. 
     auto beg = c.begin(); auto end = c.end(); 
     auto min = std::min_element(beg, end); 
     if(x > *min) 
     { 
      *min = x; 
      // Re-make the heap, since we may have just invalidated it. 
      std::make_heap(beg, end); 
     } 
     } 
     // Otherwise just push the new item. 
     else   
     { 
     priority_queue::push(x); 
     } 
    } 
    private: 
    fixed_priority_queue() {} // Construct with size only. 
    const unsigned int fixed_size; 
    // Prevent heap allocation 
    void * operator new (size_t); 
    void * operator new[] (size_t); 
    void operator delete (void *); 
    void operator delete[] (void*); 
};

這裏發生了什麼？

擴展std::priority_queue類
重寫priority_queue::push()方法，用新項目互換最低項目
默認的構造函數是私有的，沒有大小沒有建設
堆上限制分配，STL容器沒有虛擬析構函數。

要使用：

const unsigned int LIMIT = 20; 
fixed_priority_queue<int> fooQueue(LIMIT); 

// Testing. 
for(int i=0; i<40; i++) 
    fooQueue.push(rand()); 
for(int i=0; i<LIMIT; i++) 
{ 
    printf("%i\n", fooQueue.top()); 
    fooQueue.pop(); 
}

有什麼不好的嗎？

那麼你不能安全地在堆上創建這些隊列，所以大隊列可能是不可能的。 20左右，正如你所提到的，無論如何都應該在堆棧上很好（取決於對象）。我可能會避免大排隊，因爲...
我不確定在這裏的表現命中。 priority_queue在底層容器上調用make_heap（默認情況下爲std :: vector）。我不確定多久調用通常是，但我們經常在隊列已滿時調用它。我認爲它也可以在priority_queue::push()之內調用？
大概的其他東西堆，所以我歡迎讀者:)

希望所有建設性的反饋和修改，這是有用的，如果沒有至少有趣。

來源

2012-07-21 14:37:29 Aesthete

我認爲你應該在這裏使用私有繼承 – SPMP 2016-05-10 19:39:15

你知道你的'fixed_priority_queue'不是'std :: priority_queue'？所以，使用私有繼承或組合。 – Deduplicator 2017-06-14 22:22:06

Aryabhatta's answer of another question適用於此問題。

您使用最大堆。

假設有N元素堆（作爲陣列實現的），其包含迄今所看到的N個最小的元素。

當一個元素進來時，檢查最大（O（1）時間），並且如果它更大則拒絕。

以前幾個評論中提到的迭代是不必要的。

來源

2017-06-28 04:58:10

如何使STL的priority_queue固定大小

回答

相關問題