Почему я получаю ошибку сегментации в этом итераторе?

Question

Я пишу программу, которая должна просматривать график и вычислять минимальное количество ребер, которые необходимо удалить, чтобы оставить лес, где каждая связанная группа имеет четное число вершин. Я знаю, как решить проблему, но когда я пытаюсь выполнить итерацию по списку, я получаю ошибку сегментации и не могу понять, почему.

#include <cmath> 
#include <cstdio> 
#include <list> 
#include <vector> 
#include <iostream> 
#include <algorithm> 
using namespace std; 

int main() { 
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 

    int N; 
    cin >> N; 
    int M; 
    cin >> M; 

    // matrix of adjacency list to hold node values 
    vector<list<int> > adjList(N, list<int>()); 

    // find the number of children nodes each node has 
    int ui, vi; 
    for (int i = 0; i < M; i++) { 
     cin >> ui; 
     cin >> vi; 
     ui--; 
     vi--; 
     //cout << ui << " " << vi << endl; 
     adjList[ui].push_back(vi); 
     adjList[vi].push_back(ui); 
     //cout << "list length: " << adjList[ui].size() << endl; 
    } 
    //cout << "after for loop" << endl; 
    // count the number of nodes with even numbers of children 

    for (int i = 0; i <= M; i++) { 
     cout << i << "-> "; 
     for (list<int>::iterator it = adjList[i].begin(); it != adjList[i].end(); it++) { 
     cout << *it << " "; 
     } 
     cout << endl; 
    } 

    int edgesRemoved = 0; 

    for (int i = 0; i <= M; i++) { 
     for (list<int>::iterator it = adjList[i].begin(); it != adjList[i].end(); ++it) { 
     int j = *it; 
     if (adjList[j].size() % 2 == 1) { 
      // delete vertex from current list 
      cout << "test" << endl; 
      adjList[i].erase(it); 

      // delete vertex on the other list 
      cout << "test" << endl; 
      cout << j << endl; 
      cout << *adjList[j].begin() << endl; 
      for (list<int>::iterator it2 = adjList[j].begin(); it2 != adjList[j].end(); ++it2) { 
      cout << *it2 << " "; 
      if (i == *it2) { 
       adjList[j].erase(it2); 
      } 
      } 

      edgesRemoved++; 
     } 
     } 
    } 
    cout << edgesRemoved << endl; 
    return 0; 
} 

После использования заявления COUT для отладки программы я понял, что проблема здесь:

for (int i = 0; i <= M; i++) { 
     for (list<int>::iterator it = adjList[i].begin(); it != adjList[i].end(); ++it) { 
     int j = *it; 
     if (adjList[j].size() % 2 == 1) { 
      // delete vertex from current list 
      cout << "test" << endl; 
      adjList[i].erase(it); 

      // RIGHT UNDER HERE 
      // vvvvvvvvvv 

      for (list<int>::iterator it2 = adjList[j].begin(); it2 != adjList[j].end(); ++it2) { 
      cout << *it2 << " "; 
      if (i == *it2) { 
       adjList[j].erase(it2); 
      } 
      } 

      edgesRemoved++; 
     } 
     } 
    } 

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

Вот пример того, что происходит после ввода ввода цифр, представляющих дерево, программа затем печатает матрицу смежности и переходит к фактическому вычислению (эта часть работает нормально, это конечный результат во время расчет):

10 9 
2 1 
3 1 
4 3 
5 2 
6 1 
7 2 
8 6 
9 8 
10 8 
0-> 1 2 5 
1-> 0 4 6 
2-> 0 3 
3-> 2 
4-> 1 
5-> 0 7 
6-> 1 
7-> 5 8 9 
8-> 7 
9-> 7 
test 
test 
1 
0 
Segmentation fault 

Answer 1

вы не должны удалить текущий элемент в списке (вещь итератор, указывающий на) в то время как вы итерацию над ним. Вы не могли бы сделать что-то вроде этого:

adjList[j].erase(it2++); 

Однако, AFAIK, это считается лучшей практики для ни сжиматься, ни расширить список во время прохода.

Answer 2

Удаление элемента под итератором аннулирует итератор; использование его в дальнейшем приводит к неопределенному поведению, поэтому все может случиться. Обычная идиома для такого рода вещи:

std::list<int>::iterator it = adjList[i].begin(); 
while (it != adjList[i].end()) { 
    if (*it == i) { 
     it = adjList[j].erase(it); 
    } else { 
     ++ it; 
    } 
} 

erase функция возвращает итератор на элемент сразу после той, которая была удалена.

Это действительный для всех типов последовательностей, а не только std::list.