Is it possible to clear priority_queue by clearing its base container?

Question

The following code inherits std :: priority_queue and provides clear() , which calls the internal std::vector 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 gives the expected result:

 -1 -2 -3 -4 -5 

But I did not see any guarantee for this, that is, clearing the internal vector will be the same as calling pop() when priority_queue is not empty. Although I know other ways to clean it, such as swap or assign it using an empty priority, I think that if this code can work well, it will be more efficient, since the allocated memory in the vector will be reused. So I wonder, is this code portable or not always working?

Answer 1

Very good question. Although I cannot find a strict guarantee that this is the right 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 others. Effectively calls c = other.c; . (implicitly declared)

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

Given this and the fact that a reasonable implementation of the priority queue is unlikely to be necessary to maintain any state other than the size of the queue, I believe that it can be safely assumed that cleaning the base container is an acceptable way to empty the queue.

Answer 2

But I did not see any guarantee for this, that is, clearing the internal vector will be the same as calling pop() when priority_queue is not empty.

Because it is not the same thing. A std::priority_queue is a specially designed container adapter that organizes things according to strict weak orders. If you do not specify the type of container that the queue will have (which you do not see in the example), then the default type is std::vector .

Therefore, calling pop() on a non-empty priority queue will remove the top element from the queue, when clear() called in the base container, it will remove all elements from the queue, not just the topmost one.

Although I know other ways to clean it, such as swap or assign it using an empty priority, I think that if this code can work well, it will be more efficient, since the allocated memory in the vector will be reused. So I wonder, is this code portable or not always working?

According to the reference, the base member object c is protected, so access to how you should be guaranteed in different compilers, i.e. call this->c.clear(); It must be portable (by analogy, it works on g++ 4.2.1 in the old version of OpenBSD).

As for efficiency, this will depend somewhat. Doing something like this->c.clear(); vs. q = priority_queue <int>(); may differ from memory usage or complexity, although you will have to test it on different platforms to verify. However, do something like this->c.clear(); vs. while(!q.empty()) { q.pop(); } while(!q.empty()) { q.pop(); } will be more efficient.

In terms of memory efficiency, the priority queue pop function calls the base containers pop_back , and neither pop_back and clear affect the underlying capacity vector, so there really is no "saving"; although at the same time you can resize the vector to increase / decrease the capacity if you have a certain need.

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

Hope this helps.