Heap und std::vector und das ganze auf Pointern

[Max3000]

Stimmt.
Wenn man das sauber gemacht hätte, wäre die 2. Bedingung im if überflüssig.
Aber das schau ich mir morgen an. Jetzt ists zu spät :).

Im laufe dieser Diskussion hatte ich noch was am FibonacciHeap geändert, der jetzt auch nicht mehr funktioniert, weil ich einige Performance-Killer da drin gefunden habe.
Dort wollte ich ja auch die Kind-Elemente in einem std::vector speichern, aber ich muss manchmal im Algo ein Kind löschen, das heißt wieder erase auf ein Element in der Mitte einer Liste. Das geht natürlich wieder nicht weil ich einen Iterator dafür brauche.
Da bin ich jetzt noch dran und ich werd das mal posten wenn ichs fertig habe.

Außerdem hatte ich am Anfang dieses Threads mal nachgefragt was ich für eine Datenstruktur für folgendes nehme:

Ich muss beim DeleteMin alle Kinder von minRoot in die RootList verschieben und die verlinken wenn 2 Elemente den selben Rang haben (Rang = Anzahl der Kindelemente).

Dazu füg ich nacheinander die Kinder an die Rank-te Position einer Liste. Wenn das erste Kind Rang 5 hat und so, dann kann ich keinen Vector oder sowas nehmen.
Ich habe dann std::map ausprobiert, aber das ist noch langsamer als mein ursprünglicher Array aus 100 Elementen (das ist hässlich, ich weiß). Was fällt dir spontan dazu ein was man da nehmen könnte?

Habe vorhin auch eine C Implementierung vom FibonacciHeap gefunden wo die das auch mit einem dynamischen Array machen, aber die Größe immer unterschiedlich haben. Also irgendwie wurde der dort aus einem logarithmus-ausdruck immer berechnet. Das wäre was was ich noch versuchen könnte.

Ok Danke für alles volkard und life.

Grüße

Max

[volkard]

life schrieb:

Richtig. Da läuft irgendwas schief..

Mein Fehlerfund würde es erklären. Er paßt zum Symptom.

[life]

volkard schrieb:

life schrieb:

Richtig. Da läuft irgendwas schief..

Mein Fehlerfund würde es erklären. Er paßt zum Symptom.

Imho nein. Ich stimme dir zwar zu, dass es ein Fehler ist (Inkonsistent mit Destruktor), aber im Prinzip sollte es doch egal sein, ob bei ptr->revptr 0 oder irgend ein ungültiger Wert steht: wenn man darauf zugreift macht man in beiden Fällen was falsch.

Eigentlich sollte es doch auch so funktionieren:

struct MovableNodePtr  {
    Node* ptr;

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

    MovableNodePtr(MovableNodePtr&& rhs) : ptr(rhs.ptr) {
        ptr->revptr = this;        
    }

    MovableNodePtr& operator=(MovableNodePtr&& rhs) {
        ptr = rhs.ptr;
        ptr->revptr = this;		
		return *this;
    }

    ~MovableNodePtr(){

    }    

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

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

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

};

[Max3000]

Ich hab das nochmal ohne das && gemacht, da ich grad lese, dass das nur eine Erweiterung vom C++ Standard ist, aber nicht wirklich dazu gehört, richtig?

Mein Code sieht so aus

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;
    //vertex.ref = 0;   
  }

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

    return *this;
  }

Ohne die zweite Bedingung kommt aber immer ein Speicherfehler:

if(ref != 0 && this == ref->revref

Aber warum ist das so?
Im Copy-Konstruktor wird ref->revref auf this gesetzt,
im CopyAssignment ebenfalls und im Konstruktor, der ein Vertex-Element annimmt auch.
Wie kann es also sein, dass ref->revref nicht auf this zeigt?
Wahrscheinlich so:
revref zeigt auf this, das Element wird dann in ein anderes Kopier, in dessen Copy-Construktor revref auf das neue Element gesetzt wird, also ist die zweite Bedingung nicht erfüllt.
Darum ist sie also doch unbedingt nötig. Was sagt ihr?

[life]

Max3000 schrieb:

Wie kann es also sein, dass ref->revref nicht auf this zeigt?
Wahrscheinlich so:
revref zeigt auf this, das Element wird dann in ein anderes Kopier, in dessen Copy-Construktor revref auf das neue Element gesetzt wird, also ist die zweite Bedingung nicht erfüllt.

Ja, darum setzen wir auch bei den rvalue reference Varianten rhs->ptr auf 0. Dadurch wird die Invariante ptr == 0 || ptr->revptr == this gewahrt.

Bei deinen normalen Copy-Constructors "klaust" du einem anderen einfach den refptr. Das ist eigentlich nicht im Sinne eines const Parameters. Wenn du aber den Destruktor einfach mal leerst bei deinem Code, sollte es auch funktionieren (siehe man Vorpost).

[volkard]

Wenn im push_back der vector wächst? Oh, ALLE zeigen ins Nirvana. Ok, vector.reserve() muß am Anfang dringend gemacht werden. Weiß nicht, ob das geschah. Finde gerade keinen Komplett-Code.

[Max3000]

Reserve wurde nicht gemacht, aber hat bei mir jetzt auch nix verändert.
Ist

std::vector<MovableVertex> heap;
heap.reserve(vertices.size());

das selbe wie

std::vector<MovableVertex> heap(vertices.size());

?

Ich werd morgen wieder schreiben.
Vielen Dank nochmal.
Ihr seid echt gut.

[volkard]

life schrieb:

volkard schrieb:

life schrieb:

Richtig. Da läuft irgendwas schief..

Mein Fehlerfund würde es erklären. Er paßt zum Symptom.

Imho nein. Ich stimme dir zwar zu, dass es ein Fehler ist (Inkonsistent mit Destruktor), aber im Prinzip sollte es doch egal sein, ob bei ptr->revptr 0 oder irgend ein ungültiger Wert steht: wenn man darauf zugreift macht man in beiden Fällen was falsch.

Eigentlich sollte es doch auch so funktionieren:

struct MovableNodePtr  {
    Node* ptr;

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

    MovableNodePtr(MovableNodePtr&& rhs) : ptr(rhs.ptr) {
        ptr->revptr = this;        
    }

    MovableNodePtr& operator=(MovableNodePtr&& rhs) {
        ptr = rhs.ptr;
        ptr->revptr = this;		
		return *this;
    }

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

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

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

};

Ja, stimmt.
Aber was mache ich eigentlich, wenn der Heap wächst und schrumpft?
Als Node kann ich machen muß:

if(!refptr)
   vec.push_back(MoveableNode(this));//setzt automatisch meinen refptr
push_heap(vec.begin(),refptr);

Dazu muß der MovableNode bei Vernichtung sich auch korrekt bei seinem Node abmelden.

[life]

volkard schrieb:

Wenn im push_back der vector wächst? Oh, ALLE zeigen ins Nirvana. Ok, vector.reserve() muß am Anfang dringend gemacht werden. Weiß nicht, ob das geschah. Finde gerade keinen Komplett-Code.

Welcher vector? Dem MovableNodePtr-Vektor sollte das eigentlich nichts ausmachen.

[volkard]

life schrieb:

volkard schrieb:

Wenn im push_back der vector wächst? Oh, ALLE zeigen ins Nirvana. Ok, vector.reserve() muß am Anfang dringend gemacht werden. Weiß nicht, ob das geschah. Finde gerade keinen Komplett-Code.

Welcher vector? Dem MovableNodePtr-Vektor sollte das eigentlich nichts ausmachen.

Doch. Die Nodes haben doch Zeiger namens revptr genau in den vector-Speicher voller MovableNodePrt, also genau in den Heap.
Wenn ich dann den ganzen vector woanders hinschiebe. Oh, hast recht. Ich schiebe ja. Mit Move-Semantik in den MovableNodePrts.
Wer rechnet denn auch damit, daß NodePtrs Movable sind. Das waren sie in den letzten 20 Jahren nicht. Ganz neue Welten hier. Das verwirrt mich.
Aber auch das müßte empfindlich reagieren, wenn Nodes ihren refptr nicht auf 0 setzen, wenn die zugehörigen MovableNodePtrs aus dem Heap rausgepoppt werden und sterben.

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

[krümelkacker]

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