priority_queue，迭代器和排序

考慮一個std::priority_queue其中N元素具有相同的優先級。現在考慮一些具有任何優先級的元素pop()s和push()s，使得所得到的隊列由所有上述元素N加上M新元素組成，其中所有N+M元素具有相同的優先級。priority_queue，迭代器和排序

以下pop()是否保證刪除頂層元素遵循FIFO順序，其中首先刪除第一個插入的元素？

另一個問題是如何找到一個元素並將其從優先級隊列中刪除？（一個簡短的例子表示讚賞）

來源

2011-10-11 Martin

一個問題，請：你只能使用。 –

如果所有元素具有相同的優先級，則最好使用常規隊列。如果您想隨機查找元素，則可能需要查看一個集合或多個集合。 – Eva

我不認爲有任何這樣的保證。根據sgi's docs，它取決於底層的數據結構。

我認爲最常見的實現使用堆。推入並彈出堆中的任何項目只需更新其中的元素，使得沒有其子節點大於父節點的節點（用於最大堆）。如果兩個孩子都具有相同的優先級，並且其中一個孩子必須替代父母，則在選擇要推廣哪個節點方面沒有區別。所以完全取決於實現選擇左側還是右側節點。

如果您確實需要按照先進先出順序排列節點（如果所有優先級相同），則傳入一個比較函數，該函數首先按優先級排序，並使用存儲在保存推入的對象數的對象中的值它之前的priority_queue。

int cmp(my_object a, my_object b){ 
    if (a.priority!=b.priority) return a.priority<b.priority; 
    else return a.index<b.index; 
}

來源

2011-10-11 11:31:05 MAK

您可以/應該使用標準列表（或向量）和make_heap，push_heap，pop_heap模擬一個（雙端）優先級隊列。

這會給你更多的選擇。（包括你描述的那種操作）。不過，你必須自己實現邏輯。

通常，標準容器適配器（stack，priority_queue）在其公開的操作集中是限制性的。

來源

2011-10-11 11:18:01 sehe

如何找到一個元素並將其從優先級隊列中刪除？（短的例子理解）

你沒有「發現」優先級隊列中的元素，就像您與地圖或套......而這是一個隊列，隊列的行爲是刪除元素位於隊列的前面，並在隊列後面推送新元素。訪問隊列中間的元素與預期的行爲不同（如果修改了該對象，會嚴重破壞預期的行爲模式）。在優先級隊列中，元素是排序的，因此隊列中的第一個元素是具有最高優先級的元素，或者如果所有元素具有相同的優先級，則會返回到第一個問題，即「不是「，因爲許多實現使用堆排序，所以它不能保證處於FIFO順序，並且由於堆是二叉樹的線性表示，所以排序的結果對於相同優先級的對象將是不明確的（即對於兩個相等的子對象，當在pop()期間從隊列中移除根節點時，在根的兩個子節點之間成爲一個模糊的選擇，作爲新的根節點...換句話說，具有相同優先級的對象將被組合在一起，但是它們從隊列中彈出的順序可能不是按照FIFO順序。你可以在這裏看到一個快速的例子：http://ideone.com/DjSDi

來源

2011-10-11 11:25:06 Jason

如果您可以指出在具有相同優先級的情況下哪些元素是從FIFO順序中提取的？ – Martin

你是對的......我修改了我的答案以反映這一點，並附上一個例子。 – Jason

1，如果你想執行FIFO排序時元素具有相同的優先級字段t添加到您的類（這是說，當元素添加到優先級隊列）和運營商<如果兩個比較牛逼元素具有相同的優先級。

或者你可以使用pair< T , int >當T是你的元素的類型，並且當你給你的優先級隊列添加一些東西時，當t是一個整數時，把int設置爲t。

2-您不能訪問優先級隊列中的其他任何元素。同時

constructor 
top() 
pop() 
push() 
size() 
empty()

see here for more description

來源

2011-10-11 12:49:14

priority_queue，迭代器和排序

回答

相關問題