segmentation fault bei Dereferenzierung eines Pointers

leche

Hallo c++ Forum, ich habe hier einen sehr seltsamen Fehler bei der dereferenzierung eines Pointers und zwar geht es um die Darstellung eines Graphen. Dazu habe ich folgende Datenstruktur

Die Klasse Graph benutzt einen vector<vertex> um Instanzen der Vertex Klasse zu speichern. Jeder vertex hat fuer sich wieder einen vector<vertex*>, der Pointer auf seine Nachbarknoten speichern soll. So genug geredet, Code sagt sicher mehr als tausend Worte.

graph& graph::getInstance()
{
	static graph instance;
	return instance;
}

graph::graph()
{
	vertexList = new vector<vertex>;
	if (vertexList == NULL)
	{
		cerr << "Error, could not allocate enough memory" << endl;
	}
}

void graph::addVertex(string name)
{
	if(findVertexByName(name) == NULL)
	{
		vertex tempVertex(name);
		vertexList->push_back(tempVertex);
	}
}

//adds a pointer to vertex2 in vertex1s neighbourlist
//this would be directed edge, but our parser will call this function twice for each edge 
void graph::addEdge(string vertex1, string vertex2)
{
	//cout << "trying to add an edge from " << vertex1 << " to " << vertex2 << endl;
	vertex* vertexPtr1 = findVertexByName(vertex1);
	vertex* vertexPtr2 = findVertexByName(vertex2);
	std::printf("%s: %p, %s: %p\n",vertex1.c_str(), vertexPtr1, vertex2.c_str(), vertexPtr2);
	cout << vertexPtr1->getName() << " to " << vertexPtr2->getName() << endl; // hier kann ich die Pointer noch dereferenzieren
	if (vertexPtr1 != NULL && vertexPtr2 != NULL)
		vertexPtr1->addNeighbour(vertexPtr2);
}

vector<vertex>* graph::getVertexList()
{
	return vertexList;

}

void graph::print()
{
	cout << vertexList->size() << endl;
	for (vector <vertex>::iterator it = vertexList->begin(); it != vertexList->end(); ++it) 
	{
		cout << it->toString() <<endl;
	}
}

vertex* graph::findVertexByName(string name)
{
	for (vector <vertex>::iterator it = vertexList->begin(); it != vertexList->end(); ++it) 
	{
		if(name.compare((*it).getName())==0)
		{
			return &(*it);
		}
	}
	return NULL;
}

Und der Implementationsteil der Vertex Klasse:

vertex::vertex(string vertexname)
{
	id = vertex::count;
	vertex::count++;
	name = vertexname;
}

void vertex::addNeighbour(vertex* neigh)
{
	neighbours.push_back(neigh);
}

string vertex::toString()
{
	string str=getName();
	cout << "Printing vertex: " << str << endl;
	str.append(" at (");
	str.append(doubleToString(coords.x()));
	str.append("|");
	str.append(doubleToString(coords.y()));
	str.append("), has ");

	stringstream tmp;
	tmp << neighbours.size();
	str.append(tmp.str());

	str.append(" neighbours: |");

	for (vector <vertex*>::iterator it = neighbours.begin(); it != neighbours.end(); ++it) 
	{
		cout << "Found neighbour "<< (*it)->getName() << endl; // diese dereferenzierung geht schief
		str.append((*it)->getName()); /
		str.append("|");
	}

	return str;
}

string vertex::getName()
{
	return name;
}

Der eingelesene Graph sieht folgendermassen aus und wird von bison und flex geparst (der von bison generierte parser ruft die Funktionen addVertex() und addEdge() auf)

graph graphname {
a -- b -- c;
}

Ausgabe:
c: 0x9f162b0, b: 0x9f16288
c to b
b: 0x9f16288, c: 0x9f162b0
b to c
b: 0x9f16330, a: 0x9f16380
b to a
a: 0x9f16380, b: 0x9f16330
a to b
Anzahl der Knoten: 3
Printing vertex: b
zsh: segmentation fault (core dumped)

So, ich hoffe ich habe alles gepasted was zur Loesung beitragen kann.
Das seltsame an diesem Problem ist, dass ich die Pointer eben beim hinzufuegen zum neighbours vector dereferenzieren kann und per getName() den namen auslesen kann, wenn ich aber die liste durchgehe, klappt das nicht mehr, sobald mehr als 3 Knoten im Spiel sind.

Danke schonmal fuer das lesen des vielen Textes.

Janjan

So auf die Schnelle seh ich nicht den Fehler im Code, allerdings einen kleinen anderen Abschnitt der einen Kommentar verdient:

leche schrieb:

graph::graph()
{
	vertexList = new vector<vertex>;
	if (vertexList == NULL)
	{
		cerr << "Error, could not allocate enough memory" << endl;
	}
}

Die Überprüfung auf NULL ist überflüssig, da die Bedingung niemals wahr sein kann. new wirft eine Exception, wenn der Speicher nicht allokiert werden kann. Es würde funktionieren, wenn du dem new das nothrow Argument mit übergibst - aber in der Regel will man das gar nicht.

Fedaykin

Fehler hab ich jetzt auch keinen wirklichen gesehen. Hast du schon debuggt? Steigt das ganze sicher an der stelle aus? Vielleicht sind die Iteratoren auch ungültig? Ist der Neighbours vektor korrekt aufgebaut? Das sind jetzt Ansätze die ich als erstes Probieren würde.

vertex* graph::findVertexByName(string name)

liefert einen Pointer auf dein Element im vector.
Wenn du jetzt allerdings einen neuen Vertex hinzufügst, dann
kann dieser, wenn der vector seinen Speicherplatz neuallokieren muss,
ungültig werden, so dass dein 'addNeighbour()' später auf einen ungültigen
Speicherbereich verweist.

Soweit jedenfalls meine Vermutung....

EDIT: In welcher Reihenfolge wird denn hinzugefügt?
EDIT 2: Mach dir mal Debug-Ausgaben in den Copy-Constructor von vertex,
wenn aufeinmal alle Elemente kopiert werden, allokiert der vector (wahrscheinlich)
neu.

leche

Janjan schrieb:

So auf die Schnelle seh ich nicht den Fehler im Code, allerdings einen kleinen anderen Abschnitt der einen Kommentar verdient:

leche schrieb:
graph::graph()
{
	vertexList = new vector<vertex>;
	if (vertexList == NULL)b
	{
		cerr << "Error, could not allocate enough memory" << endl;
	}
}
Die Überprüfung auf NULL ist überflüssig, da die Bedingung niemals wahr sein kann. new wirft eine Exception, wenn der Speicher nicht allokiert werden kann. Es würde funktionieren, wenn du dem new das nothrow Argument mit übergibst - aber in der Regel will man das gar nicht.

Danke, das wusste ich noch nicht, hatte es mir irgendwie angewohnt angeforderten Heap Speicher zu überprüfen

Cspille: Sprich ich müsste den copy constructor überladen und alle Pointer anpassen (falls das das Problem ist, ich prüfe es gerade nach)?

Edit: Oder wäre das Problem behoben, wenn ich keine Pointer sondern Referenzen speichere?

Nexus

Warum speicherst du in der Klasse graph einen std::vector<vertex>* und keinen std::vector<vertex> ? Durch den Zeiger bekommst du viele Probleme und musst manuell Speicher verwalten. Wenn eine Klasse nur Wert-Objekte hat, ist die Überladung von Kopierkonstruktor, Zuweisungsoperator und Destruktor in der Regel unnötig, weil bereits die vom Compiler generierten Versionen das Richtige tun.

leche

Der vollstaendigkeit halber,

nach einer kleinen emailkonferenz mit Cspille (danke nochmal) speichere ich meine Knoten nun in einer std::list, die die Objekte nur einmal kopiert (da als linked list implementiert?) werden und so die Pointer konsistent bleiben.