Pointer auf Datenobjekte in einem vector heap speichern.

Ponto

1. Eigentlich kann das nicht funktionieren. Du verlässt dich auf Eigenschaften der Implementierung von push_heap. Wenn irgendwo nicht mit std::move gearbeitet wird, so dass eine Kopie erzeugt wird, kannst du dir nicht sicher sein, dass die Version, die im Heap liegt, auch beim Zuweisen von ref gewinnt.

2. Wenn ref im Destruktor NULL sein kann, dann solltest nicht ref->number rausgeben.

3. Da ein Objekt, vom dem per std::move die Daten geholt wurden, immer noch destruiert wird, solltest du ref auf NULL setzen.

4. Sollte nicht incomming und outgoing vertauscht sein?

Max3000

1. Da könntest du recht haben aber das ist die einzige Lösung die wir im letzten Thread gefunden haben. Eigentlich brauch ich ja nur ein Paar Objekte die hintereinander im Speicher liegen, damit die push_heap(&heap[0], headOfCurrentEdge)-Operation funktioniert. Wenn du eine andere Lösung kennst lass es mich wissen

2. Das ist nur ne Debug-Ausgabe und sollte nur zur Überprüfung da sein auf welchen Objekten was ausgeführt wird

3. Hab ich gemacht aber ändert auch nix. Man geht ja davon aus, dass das Objekt nach Aufruf des Destruktors nie wieder verwendet wird.

4. Das ist Ansichtssache ^^. Im eigentlichen Graphen sind die begriffe richtig. Im Dijkstra Algorithmus gehst du ja aber den Weg rückwärts. Fängst beim Ziel an und suchst die alle Knoten die eine Kante ZU dem Ziel haben und so weiter. Die Begriffe sind wirklich etwas verwirrend. headOfCurrentEdge müsste auch eigentlich tailOfCurrentEdge sein.

life

class Vertex
{
public:
	friend class MovableVertex;

	Vertex(int number, double key) : number(number), key(key), state(UNLABELED), pred(NULL), revref(NULL) {}

	std::vector<Edge*> incomingEdges;
	std::vector<Edge*> outgoingEdges;

	int number;
	double key;

	State state;  

	Vertex *pred;

	void addIncomingEdge(Edge *edge)
	{
		incomingEdges.push_back(edge);
	}
	void addOutgoingEdge(Edge *edge)
	{
		outgoingEdges.push_back(edge);
	}

	bool operator<(const Vertex &that) const
	{
		//TODO: operator< sollte nicht mit '<=' vergleichen
		return this->key <= that.key;
	}

	bool operator>(const Vertex &that) const
	{
		return this->key > that.key;
	}

	friend std::ostream& operator<<(std::ostream &os, const Vertex &v)
	{
		os << "Vertex " << v.number << " (key=" << v.key <<
			", incoming edges from=";
		for(int i=0; i<v.incomingEdges.size(); ++i)
			os << v.incomingEdges[i]->tail->number << ' ';
		os << ')';
		return os;
	}

	MovableVertex* revref;
};

class MovableVertex
{
public:
	MovableVertex(Vertex* vertex) : ref(vertex)
	{
		assert(vertex != 0);
		assert(ref->revref == 0);
		ref->revref = this;
	}
	~MovableVertex()
	{
		if(ref != 0)
		{
			assert(this == ref->revref);
			std::cout << "Destroyed " << ref->number << std::endl;
			ref->revref = 0;
		}
	}

	MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)
	{
		std::cout << "Copied " << ref->number << std::endl;
		assert(ref != 0);
		assert(&vertex != this);
		ref->revref = this;
		vertex.ref = 0;  
	}

	MovableVertex& operator=(MovableVertex&& rhs) {
		if(ref != 0)
			ref->revref = 0;
		ref = rhs.ref;
		assert(ref != 0);
		ref->revref = this;
		rhs.ref = 0;        

		return *this;
	}

	friend bool operator<(const MovableVertex &v1, const MovableVertex &v2)
	{
		//TODO: operator< sollte nicht mit '>' vergleichen
		return v1.ref->key > v2.ref->key;
	}

	Vertex* ref;

private:
	MovableVertex(const MovableVertex &vertex) {
		//MovableVertex is not copyable but only moveable
		assert(false);
	}

	MovableVertex& operator=(const MovableVertex &rhs) {
		//MovableVertex is not copyable but only moveable
		assert(false);
	}	
};

So funktionieren beide Eingabedateien bei mir (VS2010).

Ponto

Max3000 schrieb:

1. Da könntest du recht haben aber das ist die einzige Lösung die wir im letzten Thread gefunden haben. Eigentlich brauch ich ja nur ein Paar Objekte die hintereinander im Speicher liegen, damit die push_heap(&heap[0], headOfCurrentEdge)-Operation funktioniert. Wenn du eine andere Lösung kennst lass es mich wissen

Eigener Heap. Sollte weniger Code als MovableVertex haben.

Max3000

Klappt bei mir leider nicht :(.
Ich nutze gcc 4.4.1. werd aber gleich mal andere Versionen ausprobieren.
Bei mir wird eine Assertion ausgelöst:

DijkstraBinary: DijkstraBinary.cpp:186: MovableVertex& MovableVertex::operator=(MovableVertex&&): Assertion `ref != 0' failed.

Gleich die erste im Copy-Assignment.

Das passiert gleich im pop_heap, dann wird kopiert und dann assigned und da kommt der Fehler. Und zwar meine Debug ausgabe:

POP_HEAP

Copied 6 from 0x60dac0 to 0x7fffffffd920

Program received signal SIGSEGV, Segmentation fault.
0x00000000004029f8 in MovableVertex::operator= (this=0x60dac0, rhs=...) at DijkstraBinary.cpp:186

und der Debugger sagt an dieser Stelle:

(gdb) print this
$7 = (MovableVertex * const) 0x60dac0
(gdb) print &rhs
$8 = (MovableVertex 0x60dac0

also wird ein Movable Vertex sich selbst zugewiesen.
Wie kann man sowas am besten abfragen? In dem Fall sollte ja dann gar nix passieren oder?

Max3000

OK ich hab den CopyAssignment Operator mal wie folgt geändert:

MovableVertex& operator=(MovableVertex&& rhs) {

      if(&rhs == this)
	{
	  std::cout << "Assigning this. No action required\n";
	  return *this;
	}
      std::cout << "Assigned " << rhs.ref->number << " from " << &rhs << " to " << this << std::endl;
      if(ref != 0)
	ref->revref = 0;
      ref = rhs.ref;
      assert(ref != 0);
      ref->revref = this;
      rhs.ref = 0;        
      return *this;
    }

Und siehe da... es klappt. Der Fall &rhs==this tritt zwar bei mir nur beim ersten pop_heap auf aber dem werde ich noch auf den Grund gehen.

Vielen Dank nochmal an alle die sich die Zeit genommen haben.
Besonders an life der sich noch die Mühe gemacht hat das auszuprobieren.

Ponto

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

life

Ponto schrieb:

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

Ach ja? Wie denn?

Ponto

life schrieb:

Ponto schrieb:

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

Ach ja? Wie denn?

Offensichtlich passiert es.

Irgendwas in der Art:

MovableVertex tmp = std::move(a);

a = std::move(a);

Selbstzuweisung ist natürlich auch etwas, was man beachten muss.

life

Du kannst aber nicht a in zwei Objekte moven. Das dürfte UB o.Ä. sein (müsste man sich mal den neuen Standard anschauen).

Ein Objekt in sich selbst moven finde ich auch noch etwas merkwürdig. Keine Ahnung was die g++ STL da treibt..

Ponto

life schrieb:

Du kannst aber nicht a in zwei Objekte moven. Das dürfte UB o.Ä. sein (müsste man sich mal den neuen Standard anschauen).

Ein Objekt in sich selbst moven finde ich auch noch etwas merkwürdig. Keine Ahnung was die g++ STL da treibt..

Glaube ich nicht. std::move zerstört ja nicht die Source.

life

move ist ein "potentially destructive read". Es verschiebt eben nur die Daten von a nach tmp . Anschließend kann man nicht erwarten, dass die Daten noch in a enthalten sind. Ein weiteres move von a zu irgendwoanders hin macht daher imho keinen Sinn.

Aber da müsste man mal jemanden fragen, der sich schon mehr mit dem neuen Standard beschäftigt hat. Ggf. ist es zwar sinnfrei zweimal hintereinander move vom gleichen Objekt aus auszuführen, aber nicht undefiniert. Wenn das im der g++ STL passiert, würde ich aber in jedem Fall von einem Bug ausgehen.

Max3000 schrieb:

OK ich hab den CopyAssignment Operator mal wie folgt geändert:
MovableVertex& operator=(MovableVertex&& rhs) {

Der nennt sich aber "Move-Assignment Operator".

Eventuell ist der Copy-&-Swap-Trick eleganter.

life schrieb:

move ist ein "potentially destructive read". Es verschiebt eben nur die Daten von a nach tmp . Anschließend kann man nicht erwarten, dass die Daten noch in a enthalten sind. Ein weiteres move von a zu irgendwoanders hin macht daher imho keinen Sinn.

Aber da müsste man mal jemanden fragen, der sich schon mehr mit dem neuen Standard beschäftigt hat. Ggf. ist es zwar sinnfrei zweimal hintereinander move vom gleichen Objekt aus auszuführen, aber nicht undefiniert. Wenn das im der g++ STL passiert, würde ich aber in jedem Fall von einem Bug ausgehen.

Da muss man jetzt vorsichtig sein: Die Funktion move alleine verschiebt/kopiert nichts. Sie wird benutzt, um zu sagen "Dieses Objekt interessiert mich nicht mehr, es darf verändert werden." Das einzige, was sie tut, ist einen Lvalue-Ausdruck in einen Rvalue-Ausdruck zu verwandeln. Das, was die Funktion zurückgibt ist eine Referenz auf dasselbe Objekt. Nur es ist dann eine Rvalue-Referenz. Der potentiell destruktive Teil passiert erst im Move-Konstruktor, Move-Zuweisungs-Operator (oder sonst eine Funktion, die eine non-const Rvalue-Referenz annimmt). Und wenn ein Move-Konstruktor bzw Move-Assignment-Operator das Quellobjekt "geplündert" hat, dann kann man das Quellobjekt später immer noch benutzen. Also,

vector<int> v1 = ...;
vector<int> v2 = move(v1);
vector<int> v3 = move(v1);

macht zwar nicht viel Sinn, aber alle drei Vektoren werden in einem gültigen Zustand sein. Der Move-Konstruktor beim Initialisieren von v2 wird aber wahrscheinlich sich die Elemente aus v1 geklaut haben, so dass v1 ab der zweiten Zeile ein leerer Vektor ist. Aber in welchem Zustand der genau ist, ist ja nicht so wichtig. Ein passender Name für move könnte "idontcareanymore" sein.

life

Also "sinnfrei, aber nicht undefiniert". Ich bezweifle daher immer noch, dass sowas wie

vector<int> v1 = ...;
vector<int> v2 = move(v1);
vector<int> v3 = move(v1);

im STL-Quellcode vorkommt.

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt? Edit: Zumindest bei der VS2010-STL wird eine Selbstzuweisung explizit abgefangen im Move-Assignment Operator von vector . Also wird man das wohl brauchen..

life schrieb:

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt?

Mir fallen zwar keine Situationen ein, in denen so ein Fall auftreten kann, ohne dass man absichtlich a=move(a); schreibt, aber ich denke schon, dass das eine Klasse verkraften können sollte.

life schrieb:

Edit: Zumindest bei der VS2010-STL wird eine Selbstzuweisung explizit abgefangen im Move-Assignment Operator von vector . Also wird man das wohl brauchen..

Es gibt, wie gesagt, noch den Copy&Swap-Trick. Das ist nicht unbedingt die effizienteste Lösung in allen Fällen, aber relativ einfach und man kann kaum etwas falsch machen:

class Klasse
{
  ...
public:
  ...
  Klasse(Klasse const&); // copy ctor
  Klasse(Klasse     &&); // move ctor
  ~Klasse();

  void swap(Klasse& other);

  Klasse& operator=(Klasse tmp) {  // <-- pass-by-value ist Absicht
    this->swap(tmp);
    return *this;
  }
  ...
};

volkard

krümelkacker schrieb:

life schrieb:

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt?

Mir fallen zwar keine Situationen ein, in denen so ein Fall auftreten kann, ohne dass man absichtlich a=move(a); schreibt, aber ich denke schon, dass das eine Klasse verkraften können sollte.

Hmm...

void swap(Foo&& a,Foo &&b){
   Foo tmp=move(a);
   a=move(b);
   b=move(tmp);
}

Hoffentlich stimmt das so.

Also passiert's bei jedem swap(a,a). Wo hab ich sowas bloß gesehen? Ich erinnere mich, daß ich bei manchen Algos mich darauf verlassen habe, daß swap mit sich selbst erlaubt ist und damit ein if gespart habe.

Max3000

Hallo.

Ich habe das mal mit meinen anderen Beispielgraphen ausprobiert und von den 4 riesigen Graphen die ich habe funktionierts nur für einen.

Bei dem anderem erhalte ich einen Fehler beim "MoveConstructor" (das war doch jetzt richtig oder? :-))

MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)
    {
      //std::cout << "Copied " << ref->number << " from " << &vertex << " to " << this << std::endl;

      assert(ref != 0);
      assert(&vertex != this);
      ref->revref = this; // <==== Hier krachts
      vertex.ref = 0;  
    }

Speicherzugriffsfehler.
Beim debuggen habe ich dann festgestellt dass ref zwar != 0 ist, aber irgendwie auch ungültig ist, darum bringen hier die ganzen 0-Checks ja rein gar nix.
Der Debugger sagt:

(gdb) print ref
$1 = (Vertex ) 0x20011
(gdb) print ref
Cannot access memory at address 0x20011

Wie kann so etwas zustande kommen?
Wie gesagt das passiert bei 3 von 4 riesigen Graphen.

Ponto

Lass es durch valgrind laufen.

Max3000

Habs versucht aber irgendwie scheint das unter openSUSE 11.2 nicht zu funktionieren. Ich versuch das mal zum laufen zu bringen und dann kommen Ergebnisse.

volkard schrieb:

Hmm...

void swap(Foo&& a,Foo &&b){
   Foo tmp=move(a);
   a=move(b);
   b=move(tmp);
}

Hoffentlich stimmt das so.

Ja, die zweite Zeile wäre dann bei &a==&b eine "Selbst-Move-Zuweisung". Allerdings müsste es heißen swap(Foo& a,Foo& b) . Dass die Rvalue-Referenzen sich mit Lvalue-Ausdrücken initialisieren lassen stimmt seit 1 1/2 Jahre nicht mehr. Leider ist so gut wie kein Rvalue-Referenz-Artikel im Netz auf dem aktuellen Stand. Es gibt eigentlich nur eine Artikel-Serie, die die aktuellen Regeln erklärt (beachte: Die Liste der Artikel auf der verlinkten Seite ist chronologisch verkehrt herum).

kk