C++ 标准模板库优先级队列抛出异常，消息为 "Invalid Heap"

Question

使用 STL 的 priority_queue我一尝试使用 pop() 就收到错误“无效堆” .我可以将我的值插入队列，top()队列的数量是我所期望的并且可以访问。 pop() ，当它重新堆时，似乎有问题。

我正在队列中存储指向模板类的指针。我的比较重载了:

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();
      }
   }
};

priority_queue是类的私有(private)成员:

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

重载以它的方式工作，因为负距离被认为是无穷大，总是比其他任何距离都大；为了表示无穷大，距离被初始化为-1。队列需要保持最小的，但在顶部是非负的。

我取消引用重载中的指针，允许我在那里做的事情吗？还有，我需要重载另一个运算符吗？

我会附上代码，但似乎如果我这样做，它会吓跑人们。请求查看更多信息，我将附加到另一条消息中。

我动态地声明了一个指向指针的指针数组，这些是被推送的，因为我假设 priority_queue通过引用存储，所以如果我只是将循环中声明的指针放入队列中，该指针就会超出范围。这些指针指向正确的 Vertex<type> , 并存在于整个函数中。

Visual Studio 2008 调试器将我带到“stdthrow.cpp”第 24 行。

Answer 1

这可能是您的比较功能。要进行测试，请将其替换为仅比较指针的简单版本:

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

如果问题不再出现，则问题是您的比较功能无效。您的比较器必须定义一个 "strict-weak ordering" .我不够勇敢，无法证明它不是，但我敢打赌就是这样。