Heap und std::vector und das ganze auf Pointern

life

Das letztere Problem habe ich noch nicht verstanden.

Aber es ist mir zumindest klar, dass das Nicht-Abmelden der MovableNodePtr gewisse Risiken birgt. Ein Problemfall wäre z.B. wenn der Nodes-Vector schrumpft/wächst. Mit einer Abmeldung könnte man ihn vermutlich lösen ( if(revptr) revptr->ptr = this ). Ohne Abmeldung wirds schwierig ;).

Max3000

Stimmt, wenn man den Destruktor leer lässt läuft trotzdem alles noch. Nur eine Assertion musste noch weggemacht werden, aber ansonsten ist das doch jetzt eigentlich das beste was man machen kann oder was sagt ihr?

volkard

life schrieb:

Aber es ist mir zumindest klar, dass das Nicht-Abmelden der MovableNodePtr gewisse Risiken birgt. Ein Problemfall wäre z.B. wenn der Nodes-Vector schrumpft/wächst.

Nein, der Node-Vector bleibt stabil. Während des Dijkstra-Algos ändert sich der Graph nicht.

Es stört mein ästetisches Empfinden ungemein, daß bei Dir nur die Bedingung in MovableNodePtr
ptr==0 || ptr->revptr==this
gefordert wird, aber gar nicht die andere Seite in Node
revprt==0 || revptr->ptr==this

Max3000

Irgendwie klappt das doch noch nicht ganz.

struct MovableVertex  {
    Vertex* ptr;

    MovableVertex(Vertex* ptr) : ptr(ptr) {
        assert(ptr != 0);
	assert(ptr->revptr == 0);
        ptr->revptr = this;
    }

    MovableVertex(MovableVertex&& rhs) : ptr(rhs.ptr) {
      assert(ptr != 0);
      ptr->revptr = this;      
      rhs.ptr = 0;
    }

    MovableVertex& operator=(MovableVertex&& rhs) {
      if(ptr)
	ptr->revptr = 0;

      ptr = rhs.ptr;
      assert(ptr != 0); // <==== Das wird ausgelöst
      ptr->revptr = this;        
      rhs.ptr = 0;
      return *this;
    }

    ~MovableVertex(){
      assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
      if(ptr != 0 && this == ptr->revptr)
	ptr->revptr = 0;
    }    

    friend bool operator<(MovableVertex const& a,MovableVertex const& b){
        return a.ptr->key>=b.ptr->key;//juhu, wir sind comp losgeworden
    }

private:
    MovableVertex(const MovableVertex& rhs) {
        assert(false);      
    }

    MovableVertex operator=(const MovableVertex& rhs) {
        assert(false);
    }

};

Die Assertion im operator= wird immer ausgelöst.
Kann sich noch jemand vorstellen wie das zustande kommt?
Ich habe noch eine andere Variante von mir selber ausprobiert:

class MovableVertex
{
public:
  MovableVertex(Vertex* vertex) : ref(vertex) 
  {
    assert(vertex != 0);
    //assert(ref->revref == 0);
    ref->revref = this;
  }
  ~MovableVertex() 
  {
    if(ref != 0 && this == ref->revref)
      {
	ref->revref = 0;
      }
  }
  MovableVertex(const MovableVertex &vertex) : ref(vertex.ref) {
    assert(ref != 0);
    ref->revref = this; <==== Speicherzugriffsfehler
    //vertex.ref = 0;   
  }

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

    return *this;
  } 

  Vertex* ref;

  friend bool operator<(const MovableVertex &v1, const MovableVertex &v2)
  {
    return v1.ref->key >= v2.ref->key;
  }
};

Von den 4 Beispiel Graphen die ich habe klappt es für einen, für die anderen 3 ist im CopyConstructor der Fehler.
Der ref-Pointer ist zwar nicht 0

(gdb) print ref
$15 = (Vertex 0x20011

aber hat auch keinen gültigen Wert, der zu Vertex passt:

(gdb) print* ref
Cannot access memory at address 0x20011

Das wird aber sicherlich daran liegen, dass ich die ref-Pointer vom alten MovableVertex im CopyConstructor nicht 0 setzen darf, weil es ja const ist (siehe auskommentiertes), oder?

Kann mir bitte jemand weiter helfen.
Ich verzweifle.
Der Fehler kommt allerdings erst nach einer ganzen Weile, also beim paar-tausendsten Knoten den ich vom Heap nehme und wieder rein pushe, etc.

Vielen Dank

Max

Max3000

Ich habe rausgefunden, dass wenn ich im MoveConstructor (heißt der so?) das rhs.ref = 0 weglasse, dann komm ich genau auf das selbe wie in der 2. Variante.
Wahrscheinlich passiert im Hintergrund sowas wie:

MovableVertex rhs = getVertex();
anotherVertex1 = std::move(rhs);
anotherVertex2 = std::move(rhs);

Nach dem 1. Move ist rhs aber nicht mehr gültig, da dort ref auf 0 gesetzt wird, was im 2. Move aber noch benötigt wird.

Was meint ihr?

life

Ich würde ja immer noch versuchen rauszufinden, warum du das if(this == ptr->revptr) im Destruktor brauchst. Das darf nämlich eigentlich nicht sein.

Max3000

Was passiert eigentlich in der "move"-Funktion?
Von da aus werden doch die MovableVertex(MovableVertex&&) und operator=(MovableVertex&&) aufgerufen richtig?

Irgendwie passt das alles noch nicht zusammen.
Was ist wenn CopyConstructor und operator= auf dem selben MovableVertex als Argument hintereinander ausgeführt werden? Da werden doch im CopyConstructor schon die Pointer auf ref wieder gelöscht und im operator= wenn man das nochmal brauch, gibts den ja nicht mehr.

Max3000 schrieb:

Was passiert eigentlich in der "move"-Funktion?

Meinst Du std::move ?
Da passiert gar nichts. Damit wandelst Du nur ein LValue- in ein RValue-Ausdruck um, der sich aber noch auf dasselbe Objekt bezieht. Beispiel:

void foo(int & x); // #1
void foo(int&& x); // #2

int main() {
  int i = 23;
  foo(          i ); // ruft #1 auf
  foo(std::move(i)); // ruft #2 auf
}

in std::move passiert sonst nichts. Nur, wenn man einen std::move(...)-Ausdruck als Quelle eines Kopiervorgangs verwendet, wird der entsprechende move ctor/assignment operator ausgewählt (falls es so einen gibt). So gesehen, ist der Name der Funktion etwas unglücklich. Der Name sagt nicht, was in der Funktion passiert, sondern nur, wofür Du den Aufruf danach benutzen willst.

Max3000 schrieb:

Von da aus werden doch die MovableVertex(MovableVertex&&) und operator=(MovableVertex&&) aufgerufen richtig?

Nee.

Gibt es eigentlich irgendwo eine Zusammenfassung von dem, was Du eigentlich machen willst? Vielleicht fängst Du mal nen neuen Thread an. Denn die ursprüngliche Frage (bzgl des Comparators) wurde ja beantwortet. Oder Update zumindest deinen ersten Post mit den Infos, die sich hier über 10 Seiten verstreuen, über die Art von Datenstruktur, die Du haben willst.

kk

Ponto

Ich habe jetzt nicht jeden Beitrag 100% gelesen, aber hier ein paar Anmerkungen:

1. Für viele Graphen kann man es sich leisten auf ein decrease_key() zu verzichten. Man wirft einfach den Knoten in die Queue neu rein und wenn man einen Knoten rausnimmt überprüft man, ob der Knoten schon bearbeitet wurde.

2. Es ist recht einfach einen eigenen Heap zu schreiben, der für jeden Knoten mitführt, welche die aktuelle Position im Heap ist. Damit kann man decrease_key() sehr einfach ausführen.

Max3000

Danke nochmal für die Antworten.

Ich glaube ich werde wirklich mal einen neuen Thread aufmachen weil mein jetziges Problem ein ganz anderes ist als ursprünglich.

Einen eigenen Heap schreiben wollte ich eigentlich nicht, weil ich sehen wollte wir schnell die heap-Sachen aus der STL sind.

Bis bald im nächsten Thread ;).