將值唯一地插入優先級隊列C++

Question

我編寫了下面的代碼，用於將唯一值插入數據結構中，從中我可以按排序順序檢索值（在下面的代碼中，我使用了優先級隊列來實現此目的，但是，任何其他數據結構如分類矢量也可以使用）。但是，我發現下面的代碼非常慢，因爲我將100萬個值插入到我的優先級隊列中。是否有人可以幫助我明白，我怎麼能提高如下代碼：

class unique_queue1 { 
//private: 
public:  
    std::priority_queue<std::pair<vector<int>, double>, vector<std::pair<vector<int>, double> >, CompareClass1 > m_queue; 
    std::set<vector<int> > m_set; 
//public: 
    bool push(const pair<vector<int>, double> & t) { 
     if (m_set.insert(t.first).second) { 
      m_queue.push(t); 
      return true; 
     } 
     return false; 
    } 

    void pop() { 
     assert(!m_queue.empty()); 
     const std::pair<vector<int>, double>& val = front(); 

     std::set<vector<int> >::iterator it = m_set.find(val.first); 
     assert(it != m_set.end()); 

     m_set.erase(it); 
     m_queue.pop(); 
    } 

    const pair<vector<int>, double>& front() const { 
     return m_queue.top(); 
    }  

    bool empty() const{ 
     return m_queue.empty(); 
    } 
}; 

Answer 1

既然要強制唯一性，你真的只需要設定。現在

#include <vector> 
#include <set> 

using namespace std; 
class unique_queue1 
{ 
public: 
    using value_type = std::pair<vector<int>, double>; 
    std::set<value_type, CompareClass1> m_set; 

    bool push(const value_type& t) { 
     return m_set.insert(t).second; 
    } 

    void pop() { 
     m_set.erase(m_set.begin()); 
    } 

    const value_type& front() const { 
     return *m_set.begin(); 
    } 

    bool empty() const{ 
     return m_set.empty(); 
    } 
}; 

，除非你做的那類你一些額外的魔法，你當然可以只需更換整個事情只用一套...

除此之外，您的介紹文字讀起來就像您實際上首先需要用數據填充容器，並且只有在完全填充數據後，才需要按排序順序獲取唯一條目。

我建議你嘗試一切推到一個載體，然後使用算法std::sort和std::unique和std::reverse，然後使用pop_back檢索數據。我相當肯定，這會比使用set快得多。

這裏是如何做到這一點的樣子（未經測試）：

class unique_queue1 
{ 
public: 
    using value_type = std::pair<vector<int>, double>; 
    std::vector<value_type> values; 

    void push_back(const value_type& t) 
    { 
    return values.push_back(t); 
    } 

    // Must be called between push_back and (pop or front) 
    void prepare() 
    { 
    sort(values.begin(), 
     values.end(), 
     CompareClass1()); // Maybe use lambdas for comparison 
    erase(unique(values.begin(), 
       values.end(), 
       CompareClass2()), // Need a comparator for equality, again, 
            // you might want to use a lambda 
      values.end()); 

    reverse(values.begin(), values.end()); 
    } 

    void pop() 
    { 
    values.pop_back(); 
    } 

    const value_type& front() const 
    { 
    return values.back(); 
    } 

    bool empty() const 
    { 
    return values.empty(); 
    } 
};