C++ 标准模板库优先级队列抛出异常并显示消息“无效堆”

发布于 2024-07-12 06:14:18 字数 1486 浏览 7 评论 0原文

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

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

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

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

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

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

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

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

扛起拖把扫天下 2024-07-19 06:14:19

你从哪里调用这个函数？

我的猜测是，无效堆是您从“此函数调用者”代码传递到函数中的指针。或者，当您将顶点移出矢量时，您可能会超出范围。

我不认为该功能有什么问题。

请提供堆栈跟踪

回复收藏 0 原文

北方。的韩爷 2024-07-19 06:14:19

这一点让我害怕：

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

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

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

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

回复收藏 0 原文

我家小可爱 2024-07-19 06:14:19

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

回复收藏 0 原文

撧情箌佬 2024-07-19 06:14:18

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

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

如果问题不再出现，则问题是您的比较函数无效。您的比较器必须定义“严格弱排序”。我还不够男子气概，无法证明这一点，但我敢打赌就是这样。

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.

回复收藏 0 原文