Pointer auf Datenobjekte in einem vector heap speichern.

[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.

[krümelkacker]

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..

[krümelkacker]

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.

[krümelkacker]

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

[Max3000]

valgrind geht irgendwie nicht.
Der sagt mit fehlen die debug-info's zu glibc, aber die hab ich jetzt alle installiert, sowie die devel-Packete und debugsources aber hat alles nix gebracht.
Gibts vielleicht noch was anderes in der Richtung?

[Ponto]

Max3000 schrieb:

valgrind geht irgendwie nicht.
Der sagt mit fehlen die debug-info's zu glibc, aber die hab ich jetzt alle installiert, sowie die devel-Packete und debugsources aber hat alles nix gebracht.
Gibts vielleicht noch was anderes in der Richtung?

Such nach dem Problem bei google. Da gibt es eine Lösung zu. Ich glaube valgrind-Pakete aus einem Repository.

Eventuell: https://bugzilla.novell.com/show_bug.cgi?id=545721

[Max3000]

Die Seiten habe ich mir alle schon durchgelesen.
Müssen die Versionen von debug und normalem Packet übereinstimmen?
Bei einem hab ich die 2.10.irgendwas und debug hab ich die 2.11.irgendwas.