priority queue clear method

Question

How do I delete all elements from a priority queue? That means how do I destroy a priority queue? advanced thanks for your answer. Is there any clear- or erase-like method?

Answer 1

priority_queue takes a templated container type, and while the default is vector any container can be used.

Hence, using a reference (i.e. vector&, instead of vector) allows ownership of the underlying container to remain with the caller. The container can then be cleared by the caller.

Note that you need to supply an appropriate wrapper from your container (e.g. vector&), as outlined in the standard under Container adaptors.

#include <iostream>
#include <queue>
#include <vector>

template <typename T>
struct SomeRef
{
    T& _obj;
    using value_type = typename T::value_type;
    using reference = typename T::reference;
    using const_reference = typename T::const_reference;
    using size_type = typename T::size_type;
    auto begin() { return _obj.begin(); }
    auto end() { return _obj.end();}
    bool empty() const { return _obj.empty(); }
    reference front() { return _obj.front(); }
    const_reference front() const { return _obj.front(); }
    void push_back(value_type t) { return _obj.push_back(std::move(t)); }
    void pop_back() { return _obj.pop_back(); }
};

int main()
{
    std::vector<int> underlyingVector;
    using vecref = SomeRef<std::vector<int>>;
    vecref refToUnderlyingVector{underlyingVector};
    std::priority_queue<int, vecref> a(std::less<int>(), refToUnderlyingVector);
    a.push(5);
    a.push(15);
    a.push(10);
    std::cout << "top=" << a.top() << "\n"; //15
    std::cout << "empty=" << a.empty() << "\n"; //0
    a.pop();
    std::cout << "top=" << a.top() << "\n"; //10
    std::cout << "empty=" << a.empty() << "\n"; //0
    underlyingVector.clear();
    std::cout << "empty=" << a.empty() << "\n"; //1
}

Note: I found I also had to implement methods such as empty that I can't find listed in the standard under priority_queue but appear to be part of MSVC and GCC nonetheless. Similarly, methods not used by your implementation's priority_queue could be ommitted, but you may wish to include them for portability anyway.

Answer 2

you can use the std::priority_queue::c method in combination with the std::vector::clear method or assign a new container to clear the contents of a priority queue. Here's an example:

#include <iostream>
#include <queue>
#include <vector>

template <typename T>
class MyPriorityQueue : public std::priority_queue<T>
{
public:
    void clear() {
        this->c = std::vector<T>();
    }
};

int main() {
    MyPriorityQueue<int> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);

    pq.clear();

    std::cout << "The priority queue is now empty" << std::endl;
    return 0;
}

depending on the size of the container, you may just pop out the elements from the queue since it can be faster than memory allocation, so you have to test both methods an compare the empirical results

Answer 3

priority_queue<int> a;
a.push(10);
a.push(9);
a.push(8);
a   =   {};
a.push(1);
a.push(4);
a.push(6);

while(!a.empty())
    {
    std::cout<< a.top();
    a.pop();
    }

results in

641

So you can simply

a = {};

Answer 4

there is no clear method supported for priority_queue in c++ but, this below is a good method to clear the priority_queue and has O(log(n)) time

while (!pq.empty())
      pq.pop();

Answer 5

Here's a clean and simple method to clear any priority_queue (and queue, and most other containers as well):

template <class Q>
void clearQueue(Q & q) {
    q = Q();
}

Since it's a template, you don't have to remember all the template parameters.

Example:

std::priority_queue<MyType> simpleQueue;
std::priority_queue<MyType, std::deque<MyType>, MyHashFunction> customQueue;

// ... later ...

clearQueue(customQueue);
clearQueue(simpleQueue);

Answer 6

priority_queue doesn't have a clear method. It may be that this is for interface simplicity, or because it there may be situations in which elements must be destroyed in priority-order, making a generic clear function unsafe.

Regardless, the following code block includes two functions to clear priority queues. The first works by building a temporary instance of a wrapper class around the priority_queue and then using this to access the underlying storage object, which is assumed to have a clear() method. The second works by replacing the existing priority_queue with a new queue.

I use templating so that the functions can be recycled time and again.

#include <queue>
#include <iostream>
using namespace std;

template <class T, class S, class C>
void clearpq(priority_queue<T, S, C>& q) {
    struct HackedQueue : private priority_queue<T, S, C> {
        static S& Container(priority_queue<T, S, C>& q) {
            return q.*&HackedQueue::c;
        }
    };
    HackedQueue::Container(q).clear();
}

template <class T, class S, class C>
void clearpq2(priority_queue<T, S, C>& q){
    q=priority_queue<T, S, C>();
}

int main(){
    priority_queue<int> testq, testq2;

    //Load priority queue
    for(int i=0;i<10;++i)
        testq.push(i);

    testq2=testq;

    //Establish it is working
    cout<<testq.top()<<endl;
    testq.pop();
    cout<<testq.top()<<endl;
    testq.pop();

    //Clear it and prove that it worked
    clearpq(testq);
    cout<<testq.size()<<endl;

    //Use the second clearing function
    cout<<testq2.size()<<endl;
    clearpq2(testq2);
    cout<<testq2.size()<<endl;
}

Answer 7

As any C++ STL reference will show you, the STL Priority Queue class does not have a function like 'clear' or 'erase'. http://www.cplusplus.com/reference/stl/priority_queue/

It is a container class, and as such, a very simple destructor is generated by the compiler (in most cases). If your priority queue uses only locally-allocated information in its nodes, then this should work fine for clearing out the memory.

However, if you have dynamically allocated memory for the information in your priority queue, you will need to manually create a 'clear'-like function.

Hope this helps!

Answer 8

The priority_queue interface doesn't have a clear() method (for no good reason I've ever been able to discern). A simple way to clear it is just to assign a new, empty queue:

priority_queue <int> q;
// use it
q = priority_queue <int>(); // reset it