实现可以在C ++中迭代的优先级队列 [英] Implementing a priority queue that can be iterated over in C++

问题描述

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

I need to implement a priority queue for a project, but the STL's priority_queue is not indicated since we need to iterate over all elements and remove them randomly.

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

We are thinking about using the STL's set for this, wrapping it in a class to make it an ADT.

有没有更聪明的解决方案？

Is there a smarter solution for this?

我们如何让一些 的公共成员函数可以公开使用？我们对迭代器等感兴趣。

How can we make it so some of set's public member functions can be used publicly? We're interested in iterators, etc.

显然，导出STL是不明智的，因为缺乏虚拟析构函数：/

Apparently deriving the STL is unwise because of the lack of virtual destructors :/

新代码：

#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（）：

So, we currently have this. The compiler doesn't complain about insert, but it does complain about erase(begin()) and return *begin():

没有依赖于模板参数的begin参数，因此必须提供begin声明

为什么是这样？

推荐答案

你应该能够使用 std :: vector ， std :: make_heap ， std :: push_heap 和 std :: pop_heap 。这不是如何实现 std :: priority_queue ？当您删除随机元素时，只需再次调用 std :: make_heap 即可修复数据结构。

You should be able to implement your own priority queue using std::vector, std::make_heap, std::push_heap, and std::pop_heap. Isn't this how std::priority_queue is implemented? You'll just need to call std::make_heap again to fix the data structure when you remove a random element.

你需要按顺序遍历元素吗？有一个 std :: sort_heap 算法来订购底层的 std :: vector 。

Do you need to iterate over the elements in order? There's a std::sort_heap algorithm to order the underlying std::vector.

这篇关于实现可以在C ++中迭代的优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！