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

Question

我需要为一个项目实现一个优先级队列，但 STL 的 priority_queue 未指示，因为我们需要迭代所有元素并随机删除它们。

我们正在考虑为此使用 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 argument to ' begin'依赖于模板参数，因此'begin'声明必须可用

这是为什么？

Answer 1

你真的需要优先级队列吗？

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

如果需要保持列表排序，请在开头排序，然后在插入新项目时，使用插入排序（在正确的位置插入新项目）。

Answer 2

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

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

Answer 3

STL 的集合应该可以用来制作你想要的东西，尽管我必须指出，需求列表看起来有点奇怪。您可以定义一个新类型。

template<typename T, template<typename X> class impl_type = std::set> class prio_queue {
    typedef impl_type<T> set_type;
    typedef typename set_type::iterator iterator;
    // etc
public:
    // Forward the set's members
    T& top() {
        return *begin();
    }
    // etc
};

Answer 4

我将遵循标准库中其他一些容器适配器设置的示例使用组合，并将底层容器的类型作为模板参数。但由于这是一个学校项目，可能灵活性太大。您可以首先将组合与现有容器之一结合使用，并在必要时从那里进行构建。