Extended priority queue

Question

I am looking for a priority queue implementation in C ++. In addition to the basic functions in the STL priority queue, the following methods are required:

• It can remove all the same elements (defined by a function) when pressed (like a set)
• It can filter out some elements (defined by another function).

Do you have any suggestions for its implementation?

Answer 1

You can use std::set as a priority queue without duplicates. The top element can be found through rbegin() . The asymptotic complexity is the same as for the binary heap: O (1) top according to the Standard requirements for rbegin , O (log n) push and O (log n) pop . However, the constants will be higher.

As for the filter, I suggest you wrap std::set in a class using a custom push method (which is a good idea anyway) that launches the filter predicate for you.

Answer 2

Just wrap priority_queue :

 #include <set> #include <queue> // Default predicate allows all objects through template <typename T> struct allow_any { bool operator()(T const&) const { return true; } }; // F is a callable type for the filtering predicate -- either a // function pointer, or a class having an operator()(T const&). template <typename T, typename F = allow_any<T> > class filtering_priority_queue { public: explicit filtering_priority_queue(F f) : allow(f) {} void push(T x) { if (allow(x) && s.find(x) == s.end()) { q.push(x); s.insert(x); } } T const& top() const { return q.top(); } void pop() { s.erase(top()); q.pop(); } private: std::set<T> s; std::priority_queue<T> q; F allow; };