我有一个图类
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_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
}
您似乎没有为每次迭代更新max_height_comp
。 第一次通过 while
循环后,它将保留上一次迭代中的最大值,这样it_max
就不会更新,您将尝试再次擦除该节点。 您需要在每个循环开始时重置max_height_comp
,使用outstanding
中包含的数据或小于您可能拥有的任何可能值的数字。
max_height_comp
的初始值也有可能大于outstanding
中的任何值,这将导致尝试擦除默认构造的迭代器。
从这里的文档中:
标准::设置::擦除
从设置容器中删除单个元素或一系列元素([第一个,最后一个((。
这有效地减小了容器尺寸,减少了被移除的元素数量。
由于某种原因,您的指针似乎没有更新,当调用erase()
时,它正在尝试销毁未分配的内容。