c++ - 实现可在 C++ 中迭代的优先级队列

Question

我需要为一个项目实现一个优先级队列，但是 STL 的 priority_queue 没有显示，因为我们需要遍历所有元素并随机删除它们。

我们正在考虑为此使用 STL 的 set，将其包装在一个类中以使其成为 ADT。

是否有更智能的解决方案？

我们怎样才能使 set 的一些公共(public)成员函数可以公开使用？我们对迭代器等感兴趣。

显然推导 STL 是不明智的，因为缺少虚拟析构函数:/

---

新代码:

#ifndef PRIORITYQUEUE_H_
#define PRIORITYQUEUE_H_

#include <set>

template<typename T, template<typename X> class impl_type = std::set>
class PriorityQueue {
    typedef impl_type<T> set_type;
    typedef typename set_type::iterator iterator;
public:
    void push(const T& x) {
        insert(x);

    }

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

    const T& top() const {
        return *begin();
    }
};

#endif /* PRIORITYQUEUE_H_ */

所以，我们目前有这个。编译器不会提示插入，但会提示 erase(begin()) 和 return *begin():

'begin' 没有依赖于模板参数的参数，因此 'begin' 声明必须可用

这是为什么？

Answer 1

你真的需要优先队列吗？

您需要遍历所有项目并随机删除 -> 链表

如果您需要保持列表排序，请在开头对其进行排序，然后在插入新项目时使用插入排序(在正确的位置插入新项目)。