May I clear a priority_queue by clearing its underlying container?

Question

The following code inherits std::priority_queue and provides clear() which calls the internal std::vector's clear()

#include<iostream>
#include<queue>
using namespace std;
template<class type>
struct mypq :public priority_queue<type> {
    void clear(){
        this->c.clear();
    }
};
mypq<int>pq;
int main() {
    for(int i=0;i<10;++i)
        pq.push(i);
    pq.clear();
    for(int j=-5;j<0;++j)
        pq.push(j);
    while (!pq.empty()){
        cerr<<pq.top()<<endl;
        pq.pop();
    }
}

When I tested it with g++, MSVC++ and clang, it produces the expected output:

-1
-2
-3
-4
-5

But I haven't seen any guarantee for this, i.e. clearing the internal vector will be the same as calling pop() when the priority_queue isn't empty. Although I know other ways to clear it such as swap or assign it using an empty priority_queue, I think if this code can work well, it would be more efficient since the allocated memory in the vector is reusable. So I wonder if this code is portable or won't always work?

Answer 1

But I haven't seen any guarantee for this, i.e. clearing the internal vector will be the same as calling pop() when the priority_queue isn't empty.

Because that's not the same thing. A std::priority_queue is a specifically designed container adaptor that keeps things ordered via strict weak ordering. If you don't specify the type of container the queue will have (which you don't in the example), then the default type is a std::vector.

So calling pop() on a non-empty priority queue will have the effect of removing the top element from the queue while calling clear() on the underlying container will remove all elements from the queue, not just the top most.

Although I know other ways to clear it such as swap or assign it using an empty priority_queue, I think if this code can work well, it would be more efficient since the allocated memory in the vector is reusable. So I wonder if this code is portable or won't always work?

According to the reference, the underlying c member object is protected, so accessing the way you are should be guaranteed across compilers, that is, calling this->c.clear(); should be portable (anecdotally, it works on g++ 4.2.1 on an older version of OpenBSD).

As far as efficiency is concerned, it would somewhat depend. Doing something like this->c.clear(); vs. q = priority_queue <int>(); might not be that different in terms of memory usage or complexity, though you would have to test it on the different platforms to verify. However, doing something like this->c.clear(); vs. while(!q.empty()) { q.pop(); }, would be more efficient.

In terms of memory efficiency, the pop function of the priority queue calls the underlying containers pop_back function, and neither the pop_back nor the clear affect the underlying vector's capacity, so there's not really any "savings" to be had in that way; though with this, you could resize the vector to increase/decrease capacity if you had a specific need to.

Just remember that the priority queue pop function calls the underlying containers pop_back function, and calling pop_back on an empty container is undefined behavior.

Hope that can help.

Answer 2

A very good question. While I can't seem to find any strict guarantee that it is a correct method, there are some reasons to think that it is.

For example, consider the docs for operator=:

Copy assignment operator. Replaces the contents with a copy of the contents of other. Effectively calls c = other.c;. (implicitly declared)

Since the other queue may be of a different size, this essentially means that there is no internal state that is dependent on size. Moreover, it also implies that assigning an empty queue essentially replaces the container with an empty one and does nothing else.

With that in mind, and the fact that a reasonable implementation of a priority queue would hardly need to maintain any state except for the size of the queue, I believe it can be safely assumed that clearing the underlying container is a valid way to empty the queue.