C++ standard template library priority queue throws exception with message "Invalid Heap"

Using the STL's priority_queue I get the error "invalid heap" as soon as I try to use pop(). I can push my values into the queue, the top() of the queue is what I would expect and accessible. pop(), when it goes to re-heap, seems to have a problem.

I am storing pointers to a templated class in the queue. I have the comparision overloaded:

template <class type>
class vertexPriorityCompare
{
public:
   bool operator()(Vertex<type>* leftVertex, Vertex<type>* rightVertex) const
   {
      if(leftVertex->getDistanceFromSource() < 0 && rightVertex->getDistanceFromSource() < 0)
      {
         return false;
      }
      else if(leftVertex->getDistanceFromSource() < 0)
      {
         return true;
      }
      else if(rightVertex->getDistanceFromSource() < 0)
      {
         return false;
      }
      else
      {
         return leftVertex->getDistanceFromSource() > rightVertex->getDistanceFromSource();
      }
   }
};

The priority_queue is a private member of a class:

priority_queue< Vertex<type>*, vector< Vertex<type>* >, vertexPriorityCompare<type> > Q;

The overload works in the fashion it does, because a negative distance is considered infinity, always larger than whatever else; to represent infinity, distances are initialized to -1. The queue needs to keep the smallest, but non-negative at the top.

I dereference the pointers in the overload, is what I'm doing there allowable? And, is there another operator I need to overload?

I would attach code, but it seems if I do, it scares people away. Request to see more and I'll attach to another message.

I dynamically declare an array of pointers to pointers, these are what get pushed, because I assume priority_queue stores by reference, so if I just put a pointer declared in the loop into the queue, that pointer goes out of scope. These pointers point to the proper Vertex<type>, and exist throughout the function.

Visual Studio 2008 debugger takes me into 'stdthrow.cpp' line 24.

From stackoverflow

• Where are you calling this function from?

  My guess is that the invalid heap is a pointer that you're passing into the function from "this function caller's" code. Or maybe you're going out of bounds when you are taking the vertex out of your vector.

  I don't see anything wrong with that function.

  Please supply the stack trace

• Without the callstack, it will be a bit difficult to determine what the problem is, but you are either not allocating the Vertex<...> correctly, attempting to free Vertex<...> from the stack, or not initializing the Vertex<...>* to valid values.

  MSN

• It's probably your comparison function. To test, replace it with a simple version that just compares pointers:

  bool operator()(...)
  {
    return leftVertex<rightVertex;
  }
  

  If the problem no longer occurs then the problem was your comparison function was invalid. Your comparator must define a "strict-weak ordering". I'm not man enough to show it doesn't, but I bet that's it.

  Harper Shelby : +1 Part of "strict weak ordering" says that if Compare(x,y) is true, Compare(y,x) *must* be false. This function does not handle that situation if both distance values are -1.

  Harper Shelby : In addition, the link to the SGI page points out *where* the issue is occurring - in the *_heap operations that are used on the vector to maintain the nature of the priority_queue. Internally, make_heap, push_heap, and pop_heap are called - since strict weak ordering isn't maintained, they fail.

  Douglas Leeder : Doesn't the first if ensure that -1,-1 returns false both ways round?

  Harper Shelby : @Douglas Leeder: exactly, and that's a Bad Thing(TM) for strict weak ordering.

  : @Harper Shelby not it seems OK in this respect: for this Compare when both distances are -1, Compare(x,y) = Compare(y,x) = false so the requirement is not broken. This comparison implements the following "All negative distances are equivalent and strictly lower than any non-negative distance." No problem with that.

• The comparison function looks fine, if the value of an objects getDistanceFromSource() doesn't change, while that object is in the queue. Is that ensured? Or are there maybe changes made to the objects, that influence getDistanceFromSource(), while they are in the queue or while the queue is initially filled?

  Jesse Beder : I've accidentally run into this exact problem before, and this was the reason.

• This bit scares me:

  I dynamically declare an array of pointers to pointers, these are what get pushed, because I assume priority_queue stores by reference, so if i just put a pointer declared in the loop into the queue, that pointer goes out of scope. These pointers point to the proper Vertex, and exist throughout the function.

  It's not clear quite how you are populating the queue. You must create Vertex objects and they must remain in memory and return the same distance the entire time they are in the queue.

  The queue doesn't store by reference, it stores copies - but in this case what you are putting in are pointers, so it copies the pointer, which will still point to the original objects you allocated.

  I think we'll need a short complete example in order to get any further.