Правильный способ удалить элемент в std :: set

Question

У меня есть класс графов

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() вызывает free() или delete для элементов outstanding, которые являются указателями.Но зачем это делать?Я просто хочу удалить значение указателя из набора, я не хочу удалять данные, на которые указывает указатель.

Answer 1

Вы не обновляете max_height_comp для каждой итерации.После первого прохождения цикла while оно сохранит наибольшее значение из предыдущей итерации, поэтому it_max не будет обновлено, и вы попытаетесь стереть этот узел во второй раз.Вам нужно сбросить max_height_comp в начале каждого цикла, используя данные, содержащиеся в outstanding или число меньше, чем любое возможное значение, которое вы можете иметь.

Существует также вероятность того, что начальное значение для max_height_comp может быть больше любого в outstanding, что приведет к попытке стереть созданный по умолчанию итератор.

Answer 2

Из кода, который вы показали, я думаю, вы не сбрасываете 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
}

Answer 3

Из документов здесь :

std :: set :: erase

Удаляет из заданного контейнера либо один элемент, либо диапазон элементов ([first, last)).

Это эффективно уменьшает размер контейнера на количество удаленных элементов, которые были уничтожены.

Похоже, ваш указатель по какой-то причине не обновляется, и когда вызывается erase(), он пытается уничтожить то, что не было выделено.