将值唯一地插入优先级队列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(); 
    } 
};