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

Question

我需要为项目实现优先级队列,但是priority_queue没有指示STL,因为我们需要迭代所有元素并随机删除它们.

我们正在考虑将STL set用于此,将其包装在一个类中以使其成为ADT.

有更聪明的解决方案吗？

我们如何能够set公开使用某些公共成员职能呢？我们对迭代器等感兴趣

由于缺少虚拟析构函数,显然导出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():

there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available

为什么是这样？

Answer 1

您应该能够使用std::vector、std::make_heap、std::push_heap和实现您自己的优先级队列std::pop_heap。不就是这样std::priority_queue实现的吗？std::make_heap当您删除随机元素时，您只需要再次调用来修复数据结构。

您需要按顺序迭代元素吗？有一种std::sort_heap算法可以对底层进行排序std::vector。