std::priority_queue bug/problem in MSVC++ 2008/2010 Debug configuration

Briefly, my question is somewhat language-lawyerly: is the following issue a bug in MSVC++, or "acceptable" behavior?

Af开发者_Python百科ter encountering a nasty access violation in someone's code, I tracked the source of the problem to the debug implementation of std::priority_queue<> in MSVS. (I have verified that the problem exists in both 2008 and 2010.) Following is boiled-down sample code that illustrates the problem:

#include <queue>
#include <iostream>

struct Less_than
{
    bool operator() (const int *x, const int *y) const
    {
        std::cout << "Less_than(" << *x << ", " << *y << ")" << std::endl;
        return *x < *y;
    }
};

int main()
{
    std::priority_queue<int *, std::vector<int *>, Less_than> q;
    int x = 0;
    int y = 1;
    q.push(&x);
    q.push(&y);
    std::cout << "Popping " << *q.top() << "..." << std::endl;
    q.pop();
}

The output should be (and is, in the Release build configuration):

Less_than(0, 1)
Popping 1...

However, in the Debug build configuration, the output is:

Less_than(0, 1)
Less_than(1, 0)
Popping 1...
Less_than(1, 0)

The key difference is the final additional comparison that occurs as a side effect of pop(). In the Debug build, when pop()ing the top element from the queue, the pop() implementation first compares the top element to every other element in the queue to verify that it is indeed the maximal element.

This would obviously be a problem (and was the problem in the code in question) if, as in the above example, you were using a priority_queue of pointers to objects with your own comparison... but were also removing objects with the following:

delete pq.top();
pq.pop();

Here, we release the object pointed to by pq.top(), but then when we try to pop() the pointer from the queue, the Debug implementation of pop() first tries to compare the now-invalid object pointed to by top() to everything else in the queue!

Of course, a simple solution is to simply replace the above with:

T *p = pq.top();
pq.pop();
delete p;

But my question is: technically, shouldn't the original code work as well? Put more precisely, should we be able to depend on pop() not comparing the current top element to anything in the process of removing it? I read the standard as being pretty precise here; the relevant sections of C++03 are 25.2.3.2.2 (pop()) and 25.3.6.2 (pop_heap()).

Thanks in advance!

I would say that your code T *p = pq.top(); is wrong. You get a const& to an item in your queue. But you delete the object you get. So basically you made the object in your queue invalid.
So this is a dangerous thing. I would avoid doing such things.