這兩個優先級隊列包裝器有什麼區別？

-1

我正在爲大學項目創建A *的線程安全版本，並遇到了這個奇怪的問題，其中優先級隊列的這兩個實現產生了不同的結果。我盯着這一段時間，我開始忽視實際的項目工作。任何人都可以發現這兩種實現之間的區別嗎？這兩個優先級隊列包裝器有什麼區別？

template<typename T, typename priority_t> 
struct PriorityQueue 
{ 
    typedef pair<priority_t, T> PQElement; 

    class Compare 
    { 
    public: 
     bool operator() (PQElement e1, PQElement e2) 
     { 
      return e2.first < e1.first; 
     } 
    }; 

    priority_queue<PQElement, vector<PQElement>, 
     Compare> elements; 

    inline bool empty() const { return elements.empty(); } 

    inline void put(T item, priority_t priority) { 
     elements.emplace(priority, item); 
    } 

    inline T get() { 
     T best_item = elements.top().second; 
     elements.pop(); 
     return best_item; 
    } 
};

而第二個實施

template<typename T, typename priorityT> 
    struct PriorityQueue { 
    typedef pair<priorityT, T> PQElement; 
    vector<PQElement> elements; 

    inline bool empty() const { return elements.empty(); } 

    inline void put(T item, priorityT priority) 
    { 
     elements.push_back(PQElement(priority, item)); 
     std::sort(elements.begin(), elements.end(), [&](PQElement e1, PQElement e2) { return e2.first < e1.first; }); 
    } 

    inline T get() { 
     PQElement bestItem = elements.back(); 
     elements.pop_back(); 
     return bestItem.second; 
    } 
};

請注意，我不感興趣的是去這兩個實現的幕後，除非它是有關通過我的功能產生輸出的變化用來與他們交互。

來源

2016-11-29 gdxn96

一個使用'std :: vector'，另一個使用'std :: priority_queue' ...注意，你沒有提到問題是什麼，所以你的問題和「爲什麼不是這個代碼加工？」這絕對不是什麼stackoverflow是 – smac89

我認爲你的隊列以相反的順序返回項目。 'priority_queue'返回前面的項目，而你的第二個實現返回後面的項目。你看到了什麼樣的「不同的結果」？ – 1201ProgramAlarm

我可以確認訂單的方向是一樣的，看到我的答案爲我有這些問題的原因。 – gdxn96

所以原因是，std::priority_queue以不同的順序返回相同優先級的元素與std::vector。我發現在發現答案後，這可能是一個愚蠢的問題，但接收到相同優先級的元素的順序影響了我算法的效率。對不起，我認爲有人會覺得這個問題很有趣。

來源

2016-11-29 18:54:05 gdxn96

這兩個優先級隊列包裝器有什麼區別？

回答

相關問題