STL C++ 优先队列能与 STL set 一起使用吗？

Question

我的问题和“是否有一个队列（PriorityQueue）实现，它也是一个集合？”一模一样，只不过这个问题是关于C++和STL的。

可以使用STL优先级队列作为容器类来使用STL集合吗？如果不能，是否有一种替代的容器类可以与优先级队列一起使用，从而使其成为一个集合？

- owagh

---

你能否说明你想要达成什么目标，而不是试图把一个方形木钉塞进一个圆孔里？（除了打磨掉木钉的棱角之外） - Pete Becker

为什么你想把它变成一个集合？你想要唯一的成员吗？ - Kerrek SB

为了更加建设性，容器适配器queue需要一个容器类型，在其后面添加新元素并从其前面弹出元素。 std::set不具备这种功能；它有自己的元素排序方式，因此不支持推送和弹出操作。 - Pete Becker

@Peter，你在谈论“队列”，而OP在谈论优先队列（它不是STL中的数据结构类，尽管它被实现为一组算法）。 - Konrad Rudolph

std::priority_queue的序列要求不仅仅是push和pop。你应该阅读容器要求本身。你可以这样做，但它将需要你满足额外的限制（唯一性）来创建一个容器，因为我不知道有一个标准库容器能够满足所有必需的条件+唯一性（我假设你会通过抛出异常来强制执行）。 - WhozCraig

Answer 1

std::priority_queue 的规范不允许“唯一成员”。如果您想在优先队列中拥有唯一成员，则您不需要 std::priority_queue。

如果您想要一个具有唯一成员的优先队列实现，那么std::set 已经做到了这一点，因为它保持其成员按排序顺序排列。

- user1084944

---

我没有意识到由于集合已经按排序顺序排列，它已经是一个优先队列了。谢谢。 - owagh

Answer 2

这可能不是最有效的实现方式，但你可以像这样做。 （请注意，我并不试图满足std :: priority_queue的确切接口，不想更改比较运算符，底层容器或std :: set分配器）。

与其在推入重复项时抛出异常，此实现只是假装推入成功。

template<class T>
class UniquePriorityQueue
{
public:
    typedef typename std::priority_queue<T>::size_type size_type;

    void push(const T& v)
    {
        auto i = membership_.insert(v);
        if(i.second)
        {
            queue_.push(v);
        }
    }

    void pop(void)
    {
        membership_.erase(queue_.top());
        queue_.pop();
    }

    const T& top() const
    {
        return queue_.top();
    }

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

    size_type size() const 
    {
        return queue_.size();
    }

private:
    std::priority_queue<T> queue_;
    std::set<T> membership_;
};

主函数驱动实现的功能...

int main()
{
    UniquePriorityQueue<int> q;
    q.push(1);
    q.push(1);
    q.push(8);
    q.push(4);
    q.push(2);
    q.push(8);
    q.push(5);
    q.push(7);

    assert(q.size() == 6);
    assert(q.top() == 8);
    q.pop();

    assert(q.top() == 7);
    q.pop();

    assert(q.top() == 5);
    q.pop();

    assert(q.top() == 4);
    q.pop();

    assert(q.top() == 2);
    q.pop();

    assert(q.top() == 1);
    q.pop();

    assert(q.empty());  
}

- oz10