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

Question

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.

Answer 1

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
}