Vector Iterator nicht inkrementiert

Question

Ich versuche topologische Sortierung mit dfs (nach CLRS) zu implementieren. Ich bekomme die erforderliche Ausgabe angezeigt, aber das Programm läuft immer noch und führt zu einem Segmentierungsfehler. Mit wenigen print-Anweisungen zum Debuggen konnte ich feststellen, dass die for-Schleife nie verlassen wird, obwohl sie sollte (wenn == Edges.end()). Beachten Sie jedoch, dass auch valgrind den Fehler zeigt an

dfsVisit(it->first); 

innerhalb innerhalb dfs(). Was vermisse ich? Warum wird der Iterator nicht inkrementiert und die for-Schleife beendet? Und warum verschiedene Gründe in Valgrind?

#include<cstdio> 
#include<set> 
#include<list> 
#include<stack> 
#include<algorithm> 
#include<vector> 
#include<utility> 

struct node 
{ 
    int d, f, value; 
}; 

std::vector< std::pair<node, node> > Edges; 
std::vector< std::pair<node, node> >::iterator it; 
bool *visited; 
int N, myTime=0; 
node node1, node2; 
void dfsVisit(node); 

void dfs() 
{ 
    for(it=Edges.begin(); it!=Edges.end(); it++) 
     if(it->first.value<N) 
      if(!visited[it->first.value]) 
       dfsVisit(it->first); 
} 

void dfsVisit(node n) 
{ 
    myTime++;       //increment myTime 
    n.d=myTime;       //set the discovery time for node n 

    if(n.value<N) 
     if(visited[n.value]) 
      return; 

    for(it=Edges.begin(); it!=Edges.end(); ++it) 
    { 
     if(it->second.value>=N) 
      continue; 
     printf("In the for loop!\n"); 
     if(it->first.value==n.value && !visited[it->second.value]) 
     { 
      printf("it->first.value: %d\n",it->first.value+1); 
      printf("it->second.value: %d\n",it->second.value+1); 
      dfsVisit(it->second); 
      printf("Inside for and if\n"); 
     } 

     printf("Inside for but outside if!\n"); 
     printf("Edges.end()-it: %d\n",Edges.end()-it); 
    } 

    visited[n.value]=true; 
    myTime++; 
    n.f=myTime; 

    printf("For node %d, discovery time and finishing time is: %d, %d", n.value, n.d, n.f); 
    return; 
} 

int main() 
{ 
    int M, firstOfRule, secondOfRule, data, i; 
    //node node1, node2; 
    scanf("%d""%d",&N,&M); 
    visited=new bool[N]; 

    for(i=0;i<N;i++) 
     visited[i]=false; 

    while(M--) 
    { 
     scanf("%d",&firstOfRule); 
     scanf("%d",&secondOfRule); 

     while(secondOfRule--) 
     { 
      scanf("%d",&data); 
      node1.value=firstOfRule-1; 
      node2.value=data-1; 
      Edges.push_back(std::make_pair(node1,node2)); 
      printf("Pair: %d,%d\n", node1.value+1, node2.value+1); 
     } 
    } 

    for(std::vector< std::pair<node, node> >::const_iterator it=Edges.begin(); it!=Edges.end(); ++it) 
     printf("Connected %d and %d\n",it->first.value+1,it->second.value+1); 

    dfs(); 

    return 0; 
} 

Ausgabedatei ist wie folgt:

Pair: 1,2 
Pair: 2,3 
Connected 1 and 2 
Connected 2 and 3 
In the for loop! 
it->first.value: 1 
it->second.value: 2 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: 2 
In the for loop! 
it->first.value: 2 
it->second.value: 3 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: 2 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: 1 
For node 2, discovery time and finishing time is: 3, 4Inside for and if 
Inside for but outside if! 
Edges.end()-it: 0       //-----> Why doesn't it exit here? 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: -1 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: -2 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: -3 
... and so on until the program crashes! 

Vielen Dank für Ihre Hilfe!

Answer 1

Sie haben std::vector< std::pair<node, node> >::iterator it; als globale Variable deklariert.

Aber Sie verwenden es in einer rekursiven Funktion dfsVisit. Wenn ein verschachtelter Anruf zu dfsVisit endet, verlässt es it == Edges.end(). Aber dann fährt der frühere dfsVisit fort, seine Schleife auszuführen, was ++it tut, was undefiniertes Verhalten verursacht.

Um dies zu beheben, machen Sie it eine lokale Variable für die dfsVisit Funktion.

Hinweis: Wenn Ihr Compiler C 11 ++ unterstützt, können Sie einige Tipparbeit vermeiden und verwenden auto den Iterator zu erklären.