c++ - 唯一地将值插入优先级队列 C++

Question

我编写了以下代码，用于将唯一值插入到数据结构中，我可以从中按排序顺序检索值(在以下代码中，我为此目的使用了优先级队列，但是，任何其他数据结构(如排序 vector )都可以也可以使用)。但是，我发现以下代码非常慢，因为我要将 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();
    }
};

现在，除非你在你的那个类中做一些额外的魔法，否则你当然可以只用集合替换整个东西......

除此之外，您的介绍文本读起来就像您实际上想先用数据填充容器，只有在完全填充之后，您才想按排序顺序获取唯一条目。

我建议您尝试将所有内容放入 vector 中，然后使用算法 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();
  }
};