Why am I getting a segmentation fault in this iterator?

Question

I'm writing a program that should look through a graph and calculate the minimum number of edges that need to be deleted to leave a forest where each connected group has an even number of vertices. I know how to solve the problem, but when I try and iterate through a list I get a segmentation fault and can't figure out why.

#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;
}

After using cout statements to debug the program I figured out that the problem is here:

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++;
        }
      }
    }

I get a segmentation fault after the program creates an iterator that is meant to go through another list in the vector. I don't understand why though, the syntax is the same as the first for loop with another iterator going through the first list.

Here is an example of what happens after I type in the input of the digits that represent a tree, the program then prints the adjacency matrix and goes on to the actual calculation (this part works fine, it's the end result during calculation):

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

Erasing the item under the iterator invalidates the iterator; using it further results in undefined behavior, so anything could happen. The usual idiom for this sort of thing is:

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

The erase function returns an iterator to the element immediately following the one which was removed.

This is valid for all sequence types, not just std::list.

Answer 2

You must not delete the current item in a list (the thing the iterator is pointing to) while you are iterating over it. You could do something like this:

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

However, afaik, it is considered best practice to neither shrink nor expand a list while iterating.