從priority_queue彈出時訂購問題，這是一個錯誤與std :: priority_queue

#include <functional> 
#include <queue> 
#include <vector> 
#include <iostream> 

struct Temp 
{ 
    int p; 
    std::string str; 
}; 

struct TempCompare 
{ 
    bool operator()(Temp const & a, Temp const & b) 
    { 
     return a.p > b.p; 
    } 
}; 

int main() { 

    std::priority_queue<Temp, std::vector<Temp>, TempCompare> pq; 
    //Enable and Disable the following line to see the different output 
    //{Temp t; t.p=8;t.str="str1";pq.push(t);} 
    {Temp t; t.p=8;t.str="str2";pq.push(t);} 
    {Temp t; t.p=9; t.str="str1";pq.push(t);} 
    {Temp t; t.p=9; t.str="str2";pq.push(t);} 

    while(!pq.empty()) 
    { 
     std::cout << pq.top().p << " " << pq.top().str << std::endl; 
     pq.pop(); 
    } 
}

運行上面的程序與啓用和禁用第四行主;你得到的輸出它的殘疾是從priority_queue彈出時訂購問題，這是一個錯誤與std :: priority_queue

8 str2 
9 str1 
9 str2

當而它的啓用，當你

8 str1 
8 str2 
9 str2 
9 str1

不應該的行爲是一致的？

來源

2017-07-26 rkb

是否有相同元素的排序「穩定」的文檔？如果沒有，這種行爲似乎是可能的，但不一定是你所期望的。 –

有穩定的排序算法，如['std :: stable_sort']（http://en.cppreference.com/w/cpp/algorithm/stable_sort），但[heapsort不是其中之一]（https：// stackoverflow.com/questions/19336881/why-isnt-heapsort-stable）。 –

不是。行爲沒有理由一致。 Temp{9, "str1"}和Temp{9,"str2"}根據您的比較函數是相等的，所以它們以任意順序返回。向隊列添加不同的元素很可能會改變該順序。

如果您希望它們以一致的順序返回，則需要擴展比較函數。最簡單的方法是

 bool operator()(Temp const & a, Temp const & b) 
    { 
     return std::tie(a.p,a.str) > std::tie(b.p,b.str); 
    }

如果你想「降在p，但在str上升」，你必須自己做。

來源

2017-07-26 14:52:22

我希望我可以給你多個「向上」的投票使用'std :: tie' –

「在p中遞減，但在str中遞增」 - >'return std :: tie（bp，a.str） Caleth

從priority_queue彈出時訂購問題，這是一個錯誤與std :: priority_queue

回答

相關問題