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

Question

我有一个图表class

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。但它为什么要这样做呢？我只想从集合中删除指针的值，我不想删除指针指向的数据。

Answer 1

来自文档 here:

std::set::erase

Removes from the set container either a single element or a range of elements ([first,last)).

This effectively reduces the container size by the number of elements removed, which are destroyed.

您的指针似乎由于某种原因没有得到更新，当调用 erase() 时，它试图破坏未分配的内容。

Answer 2

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

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

Answer 3

根据您显示的代码，我认为您没有在循环迭代之间重置 it_max 或 max_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
}

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

Right way to remove an element in std::set<Node *>

c++

malloc

pointers

stdset