3

使用 STLpriority_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是类的私有成员：

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

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

我取消引用重载中的指针，我在那里做什么是允许的吗？而且，我需要重载另一个运算符吗？

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

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

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

4

5 回答 5

3

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

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

如果问题不再出现，则问题是您的比较功能无效。您的比较器必须定义“严格-弱排序”。我没有足够的男人来证明它不是，但我敢打赌就是这样。

于 2009-01-23T22:45:10.237 回答
3

比较函数看起来很好，如果对象的值getDistanceFromSource()没有改变，而该对象在队列中。这有保证吗？getDistanceFromSource()或者当它们在队列中或队列最初被填充时，是否可能对对象进行了更改，这会产生影响？

于 2009-01-23T23:30:44.777 回答
0

你从哪里调用这个函数？

我的猜测是，无效堆是您从“此函数调用者的”代码传递给函数的指针。或者，当您将顶点从向量中取出时，您可能会越界。

我认为该功能没有任何问题。

请提供堆栈跟踪

于 2009-01-23T22:26:40.740 回答
0

如果没有调用堆栈，确定问题所在会有点困难，但是您要么没有Vertex<...>正确分配，要么试图Vertex<...>从堆栈中释放，要么没有将它们初始化Vertex<...>*为有效值。

于 2009-01-23T22:27:01.503 回答
0

这一点让我害怕：

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

目前尚不清楚您如何填充队列。您必须创建 Vertex 对象，并且它们必须保留在内存中并在它们在队列中的整个时间内返回相同的距离。

队列不按引用存储，它存储副本 - 但在这种情况下，您放入的是指针，因此它复制指针，该指针仍将指向您分配的原始对象。

我认为我们需要一个简短的完整示例才能进一步了解。

于 2009-01-24T00:05:41.773 回答