c++ - 创建包含唯一元素的优先级队列

Question

我想创建一个包含唯一元素的优先级队列。我发现可以按如下方式创建包含唯一 vector 元素的队列:

template <typename T>
class queue1 {
private:
    std::queue<T> m_queue;
    std::set<T> m_set;
public:
    bool push(const T& t) {
        if (m_set.insert(t).second) {
            m_queue.push(t);
            return true;
        }
        return false;
    }
};

queue1<vector<unsigned> > queueUnique;

但我的要求是除了包含唯一 vector 元素的队列外，它还应该是优先级队列，因为我队列中的每个 vector 都有一个与之关联的分数。我尝试使用以下方法创建此队列:

priority_queue<queueUnique, vector<queueUnique>, ComparisonFunction> pq;

然而，这似乎是不正确的，因为它给出了一个队列的队列。

我不知道我应该如何将分数与每个 vector 相关联，这样我得到的结果队列是一个具有唯一 vector 元素的优先级队列。例如，如果我的队列是:

struct myDS{
  vector<unsigned> vec;
  double score;
};
queue<myDS> myqueue;
vector<unsigned> dummyVec1;
dummyVec1.push_back(5);
myDS obj;
obj.vec=dummyVec1;
obj.score=0.9;
vector<unsigned> dummyVec2;
dummyVec2.push_back(5);
myDS obj2;
obj2.vec=dummyVec2;
obj2.score=0.9; //with duplicate values score is always same so can be eliminated

那么我如何创建一个优先级队列，该队列在 obj.score 上排序但不包含重复元素。例如，上面的 myqueue 应该只包含一次“5”。

Answer 1

鉴于与每个 std::vector 关联的分数是唯一的，向您的 struct myDS 添加一个比较函数就足够了，这样 std::priority_queue 可以确定顺序:

像这样:

struct myDS
{
    std::vector<unsigned> vec;
    double score;

    // Comparison function for ordering
    // based on score 
    bool operator<(const myDS& rhs) const
    {
        return score < rhs.score;
    }
};

template<typename T>
class queue1
{
private:

    std::priority_queue<T> m_queue;
    std::set<T> m_set;
public:
    bool push(const T& t)
    {
        if(m_set.insert(t).second)
        {
            m_queue.push(t);
            return true;
        }
        return false;
    }
};

queue1<myDS> queueUnique;