Styjun

I have a graph class

struct Graph

 list<Node *> vertices;
;


int main()

 Graph g;
 // fill out graph

 return 0;

I want to perform a Dijkstra-shortest-path-like algorithm. Step 1 would be creating a set out of all the nodes, which I accomplish by

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

 outstanding.insert(*itx);

Step 2 would be to extract the vertex with a certain property

 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);

I'm getting these runtime errors

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

I fear that erase() is calling free() or delete on the elements of outstanding which are pointers. But why would it do that? I just want to delete the value of the pointer from the set, I don't want to delete the data that the pointer is pointing to.

From the code you've shown, I think you aren't resetting it_max or max_height_comp between loop iterations. Thus on the second loop trip, everything is less than max_height_comp and it_max is never updated.

This problem can be avoided entirely by using a function from <algorithm>, that way the variables are kept within the correct scope by construction.

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

You don't appear to be updating max_height_comp for each iteration. After the first time thru the while loop, it will keep the largest value from the previous iteration, so that it_max will not be updated and you'll try to erase that node a second time. You need to reset max_height_comp at the start of every loop, using the data contained within outstanding or a number smaller than any possible value you could have.

There's also the possibility that the initial value for max_height_comp could be larger than any in outstanding which would result in trying to erase a default constructed iterator.

From the docs 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.

It appears that your pointer is not getting updated for some reason, and when erase() is called, it is trying to destroy something that wasn't allocated.