向量迭代器不兼容（分段错误）

Question

我试图实现一些图算法，所以继续测试我在GNU C++编译器（分段错误）中收到错误。在Visual Studio中，我看到原因是“向量迭代器不兼容”。但是这是怎么发生的？当我尝试访问访问者对象的字段时，错误在行“getName（）”中的shortestPathBFS函数中抛出。 Visitor是Vertice *队列的一个元素，所以在我看来，它不能依赖队列迭代器。如果你能解释我为什么，我将不胜感激。

#include <queue> 
#include <stack> 
#include <vector> 
#include <set> 
#include <string> 
#include <iostream> 

using namespace std; 

//#define traverse(container,iterator) \ 
//for(typeof(container.begin()) iterator = container.begin(); iterator != container.end(); iterator++) 

class Edge; 
class Vertice 
{ 
private: 
    string name; 
    vector<Edge*> incidences; 
    bool visited; 
public: 
    Vertice() {name = "NULL"; visited = false;} 
    Vertice(string name) {this->name = name; visited = false;} 
    void setName(string name) {this->name = name;} 
    string getName() {return name;} 
    bool isVisited() {return visited;} 
    void setVisited() {visited = true;} 
    void setUnvisited() {visited = false;} 
    void connectTo(Vertice*); 
    void connectTo(Vertice*,int); 
    void printNeighbors(); 
    vector<Vertice*> getNeighbors(); 
}; 

class Edge 
{ 
private: 
    int cost; 
    Vertice *start,*end; 
public: 
    friend class Vertice; 
    Edge() {cost = 0;} 
    Edge(Vertice * start, Vertice * end) {this->start = start; this->end = end;} 
    Edge(Vertice * start, Vertice * end, int cost) 
    {this->start = start; this->end = end; this->cost = cost;} 
    Vertice* getEnd() {return end;} 
    Vertice* getStart() {return start;} 
}; 

void Vertice::connectTo(Vertice * w) 
{ 
    incidences.push_back(new Edge(this,w)); 
} 

void Vertice::connectTo(Vertice* w,int cost) 
{ 
    incidences.push_back(new Edge(this,w,cost)); 
} 

vector<Vertice*> Vertice::getNeighbors() 
{ 
    vector<Vertice*> temp; 
    for(vector<Edge*>::iterator it = incidences.begin(); it != incidences.end(); it++) 
    { 
     temp.push_back((*it)->getEnd()); 
    } 
    return temp; 
} 

void Vertice::printNeighbors() 
{ 
    for (vector<Edge*>::iterator i=incidences.begin(); i!= incidences.end(); i++) 
    { 
     cout<<(*i)->start->getName()<<"--"<<(*i)->cost<<"--"<<(*i)->end->getName()<<endl; 
    } 
} 

class Graph 
{ 
public: 
    // using set for non-comparable elements are not good 
    // but this is for exercising 
    set<Vertice *> vertices; 
public: 
    void initGraph() 
    { 
     Vertice *v; 
     v = new Vertice("IST");vertices.insert(v); 
     v = new Vertice("ANK");vertices.insert(v); 
     v = new Vertice("IZM");vertices.insert(v); 
     v = new Vertice("BER");vertices.insert(v); 
     v = new Vertice("TOR");vertices.insert(v); 
     v = new Vertice("BEJ");vertices.insert(v); 
     v = new Vertice("PER");vertices.insert(v); 

     (*findByName("IST"))->connectTo(*findByName("ANK"),10); 
     (*findByName("IST"))->connectTo(*findByName("IZM"),5); 
     (*findByName("IST"))->connectTo(*findByName("BER"),61); 

     (*findByName("IZM"))->connectTo(*findByName("ANK"),3); 
     (*findByName("IZM"))->connectTo(*findByName("TOR"),98); 
     (*findByName("IZM"))->connectTo(*findByName("BER"),70); 

     (*findByName("BER"))->connectTo(*findByName("ANK"),59); 
     (*findByName("BER"))->connectTo(*findByName("TOR"),91); 

     (*findByName("ANK"))->connectTo(*findByName("PER"),77); 
     (*findByName("ANK"))->connectTo(*findByName("BEJ"),151); 

     (*findByName("BEJ"))->connectTo(*findByName("TOR"),48); 
     (*findByName("TOR"))->connectTo(*findByName("ANK"),100); 
     (*findByName("PER"))->connectTo(*findByName("BEJ"),162); 
     (*findByName("TOR"))->connectTo(*findByName("PER"),190); 
     (*findByName("BEJ"))->connectTo(*findByName("PER"),163); 
    } 

    set<Vertice*>::iterator findByName(string name) 
    { 
     for(set<Vertice*>::iterator it = vertices.begin(); it != vertices.end(); it++) 
     { 
      if ((*it)->getName() == name) 
      { 
       return it; 
      } 
     } 
     return vertices.end(); 
    } 

    int shortestPathBFS(Vertice * start, Vertice * finish) 
    { 
     queue<Vertice *> q; 
     q.push(start); 

     Vertice *visitor; 
     while(!q.empty()) 
     { 
      visitor = q.front();q.pop(); 
      visitor->setVisited(); 
      cout<<"BFS : "<<visitor->getName()<<endl; 
      if (visitor->getName() == finish->getName()) 
      { 
       break; 
      } 
      for(vector<Vertice*>::iterator it = (visitor->getNeighbors()).begin(); it != (visitor->getNeighbors()).end(); it++) 
      { 
       if (!(*it)->isVisited()) 
       { 
        q.push((*it)); 
       } 
      } 
     } 
     return 0; 
    } 

    void printAll() 
    { 
     for(set<Vertice*>::iterator it = vertices.begin(); it != vertices.end(); it++) 
     { 
      (*it)->printNeighbors(); 
     } 
    } 
}; 

int main(int argc, char **argv) 
{ 
    Graph g; 
    g.initGraph(); 
    g.printAll(); 
    g.shortestPathBFS(*(g.findByName("IST")),*(g.findByName("PER"))); 

    return 0; 
} 

Answer 1

罪魁祸首是这一行Graph::shortestPathBFS：

for(vector<Vertice*>::iterator it = (visitor->getNeighbors()).begin(); it != (visitor->getNeighbors()).end(); it++) 

的问题是，你不能从两个不同的容器（即使该容器是同一类型）比较迭代器，但visitor->getNeighbors()返回一个新的对象每次被调用。因此，it从一个对象初始化，然后与来自不同对象的迭代器进行比较。

重写环路：

vector<Vertice*> neighbors = visitor->getNeighbors(); 
for(vector<Vertice*>::iterator it = neighbors.begin(); it != neighbors.end(); ++it) 
{ 
    if (!(*it)->isVisited()) 
    { 
     q.push((*it)); 
    } 
}