删除 std::set<Node *> 中的元素的正确方法



我有一个图类

struct Graph
{
  list<Node *> vertices;
};

int main()
{
  Graph g;
  // fill out graph
  return 0;
}

我想执行类似Dijkstra最短路径的算法。第 1 步是从所有节点中创建一个集合,我通过以下方式完成

set<Node *> outstanding;
for (auto itx=g.vertices.begin(); itx!=g.vertices.end(); itx++)
{
  outstanding.insert(*itx);
}

第 2 步是提取具有特定属性的顶点

  double max_height_comp = (*(g.vertices.begin()))->max_height;
  set<Node *>::const_iterator it_max;
  while (!outstanding.empty())
  {
    for (auto its=outstanding.begin(); its!=outstanding.end(); its++)
    {
      if ((*its)->max_height >= max_height_comp)
      {
        max_height_comp = (*its)->max_height;
        it_max = its;
      }
    } 
 outstanding.erase(it_max);

我收到这些运行时错误

malloc: *** error for object 0x7fc485c02de0: pointer being freed was not allocated 
malloc: *** set a breakpoint in malloc_error_break to debug

我担心erase()outstanding的要素上呼吁free()delete,这些元素是指针。但它为什么要这样做呢?我只想从集合中删除指针的值,我不想删除指针指向的数据。

从您展示的代码来看,我认为您不会在循环迭代之间重置it_maxmax_height_comp。因此,在第二次循环旅行中,一切都小于max_height_comp并且it_max永远不会更新。

这个问题可以通过使用 <algorithm> 中的函数来完全避免,这样变量通过构造保持在正确的范围内。

while (!outstanding.empty())
{
    auto it_max = std::max_element(outstanding.begin(), outstanding.end(),
        [](Node * left, Node * right)
        {
            return left->max_height < right->max_height;
        });
    Node * node_max = *it_max;
    outstanding.erase(it_max);
    // Use the node
}

您似乎没有为每次迭代更新max_height_comp。 第一次通过 while 循环后,它将保留上一次迭代中的最大值,这样it_max就不会更新,您将尝试再次擦除该节点。 您需要在每个循环开始时重置max_height_comp,使用outstanding中包含的数据或小于您可能拥有的任何可能值的数字。

max_height_comp的初始值也

有可能大于outstanding中的任何值,这将导致尝试擦除默认构造的迭代器。

从这里的文档中:

标准::

设置::擦除

从设置容器中删除单个元素或一系列元素([第一个,最后一个((。

这有效地减小了容器尺寸,减少了被移除的元素数量。

由于某种原因,您的指针似乎没有更新,当调用erase()时,它正在尝试销毁未分配的内容。

相关内容

  • 没有找到相关文章

最新更新