STL優先隊列：什麼時候/如何進行度假？

如果我有結構的STL priority_queue，其中優先級基於結構的某個屬性，並且我更改其中一個結構的屬性，使得新的順序會不同，優先級隊列會知道自己將自己？或者我是否必須將其從隊列中移出並再次推入？我讀過push（）和pop（）被調用時排序完成的地方，但我想確認一下。STL優先隊列：什麼時候/如何進行度假？

來源

2012-06-25 Mel

不！您應該_never_修改「priority_queue」（或「map」或「set」）的值的「優先級」。它不會訴諸自己。彈出>編輯 - >推。 –

如何修改結構？當你推入時，隊列會複製一份，之後就不應該有一種方法來獲得對隊列中項目的引用。 – jogojapan

沒有辦法做你所描述的。

有三種方法爲推項到優先級隊列：

push()（這意味着移動或複製在該項目，而不是採取參考）
傳遞另一個容器或迭代器範圍，當隊列被構造時（這也涉及複製或移動，然後在副本上形成堆;沒有保留對原始的引用）
emplace()（這意味着在隊列內創建一個新項目，豪特能夠獲得對它的引用）

只有這樣，才能訪問元素是通過top()函數返回一個const引用。

因此，在推送項目或者獲取對已存在於隊列中的項目的非常量引用時，無法保留對項目的引用。因此，無法直接修改隊列項目。

理論上，進行影響排序順序的修改的唯一方法是，如果隊列中的項包含指向外部對象的指針，並且排序順序取決於這些外部對象的內容。在這種情況下，當隊列項仍然指向它們時，您顯然可以修改這些外部對象。排序順序將變得無效–優先級隊列不會更新它，因爲它甚至不知道修改。

來源

2013-05-29 06:04:10 jogojapan

的priority_queuepush()和pop()成員函數中的與傳入作爲範圍的底層容器的全部內容物的push_heap()和pop_heap()庫功能的行爲來定義的。

這些函數要求範圍（push_heap()的容器中的最後一個項目除外，因爲這是正在添加的項目）「應該是有效的堆」。如果你修改了包含的元素，使得容器不再是一個有效的堆，那麼你會得到未定義的行爲。

所以，如果你需要以這種方式修改一個元素，你需要通過刪除它來修改它，然後再添加它。或者，你可以把內容搞亂，然後撥打make_heap()來重建堆。

請參閱C++ 11 23.6.4.3「priority_queue members」，25.4.6.1「push_heap」和25.4.6.2「pop_heap」。

來源

2013-05-29 06:14:03

這肯定不是重新排序的正確方法，至少這是不能保證的。 priority_queue的push（）和pop（）只需調用底層堆結構的std :: push_heap（）和std :: pop_heap（）。

的

push(const value_type& x)

效果是

c.push_back(x); 
push_heap(c.begin(), c.end(), comp);

根據C++ 03標準（23.2.3.2.2），其中Ç是隊列的基本容器和comp排序功能。

要求的

一個push_heap是

範圍[第一，最後 - 1]應是一個有效的堆。

根據C++ 03標準的25.3.6.1。

如果您修改了priority_queue的現有結構，則會破壞堆結構，並且必須使用make_heap重新創建一個有效的堆結構。

priority_queue也無法知道您使用外部引用/指針修改了一個元素，因爲它沒有通過對其方法之一的調用進行通知。

您應該刪除該元素並再次添加它以實現您想要的效果。你也可以使用一個完全不同的容器，你可以更靈活地選擇你想要移除和添加的元素，比如std :: map。

來源

2013-05-29 06:27:15 Pait

STL優先隊列：什麼時候/如何進行度假？

回答

相關問題