Heap und std::vector und das ganze auf Pointern

volkard

Max3000 schrieb:

Geht das ganze irgendwie auch ohne das &&?

Die Alternative, die ich mir ausgedacht hatte, als ich noch nicht müde war, ist sich selber einen Heap zu bauen, der swap benutzt. Und auf den Destruktor und möglichst viel Magie der MoveableVerices zu verzichten.

Max3000

Ich hab grad nochmal durchdebuggt und der Fehler liegt jetzt wo anders und zwar hier:

push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap(__first, __last - 1);

      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
		       _DistanceType(0), _GLIBCXX_MOVE(__value));
    }

__first sieht ganz gut aus, aber __last ist 0:

(gdb) print __last
$18 = (MovableVertex 0x0

, wobei ein MovableVertex* nur im Konstruktor von MovableVertex selbst 0 gesetzt wird, also:

~MovableVertex()
{
if(ref != 0)
ref->revref = 0;
}

Kann es sein dass revref auf ein anderes MovableVertex zeigt und nicht einmal auf das, was gelöscht wird?

Max3000

Jetzt habe ich den Fehler schon wieder wo anders.
Und zwar kommt im Debugger nur:

Program received signal SIGABRT, Aborted.
0x00007ffff733d4e5 in raise () from /lib64/libc.so.6

Mein MovableVertex sieht mitlerweile so aus:

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);
	ref->revref = 0;
      }
  }
  MovableVertex(MovableVertex &&vertex) : ref(vertex.ref) {
    std::cout << "Copy Constructor\n";
    if(ref != 0)
      ref->revref = this;
    vertex.ref = 0;   
  }

  MovableVertex& operator=(MovableVertex &&rhs) {
    std::cout << "Assignment operator\n";
   ref = rhs.ref;
    if(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;
  }

  void swap(MovableVertex& a,MovableVertex& b){
    std::cout << "swap\n";
    std::swap(a.ref,b.ref);
    std::swap(a.ref->revref,a.ref->revref);
  } 
};

volkard

Mein Köpfchen qualmt, aber vielleicht habe ich ein Fehlerchen in der letzten life-Version gefunden.

struct MovableNodePtr  { 
    Node* ptr; 

    MovableNodePtr(Node* ptr) : ptr(ptr) { //Ich heirate ihn
        assert(ptr != 0); //ja, den Mann muß es geben
        assert(ptr->revptr == 0); //und er darf noch keine Frau haben
        ptr->revptr = this; //Und er heiratet mich
    } 

    MovableNodePtr(MovableNodePtr&& rhs) : ptr(rhs.ptr) { //Ich heirate ihn auch
    	//Jetzt ist er ein Bigamist
        assert(ptr != 0); //Den Mann muß es geben
        ptr->revptr = this; //Er heiratet mich und läßt sich gleichzeitig von ihr scheiden
        rhs.ptr = 0; //Sie läßt sich von ihm scheiden. 
    } 

    MovableNodePtr& operator=(MovableNodePtr&& rhs) { 
//>>> Die folgenden 2 Zeilen fehlte!
        if(ptr)//Falls ich verheiratet bin
                ptr->revptr = 0; //Mein alter läßt sich von mir scheiden
        ptr = rhs.ptr; //Ich heirate den Neuen und lasse mich von meinem alten scheiden
        assert(ptr != 0); //Es muß den Mann geben
        ptr->revptr = this; //Der Mann heiratet mich
        rhs.ptr = 0; //sie läßt sich scheiden
        return *this; 
    } 

    ~MovableNodePtr(){ 
        assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this); 
        if(ptr != 0) { //Falls ich verheiratat war
            ptr->revptr=0; //Der Mann läßt sich von mir scheiden
        } 
    }     

    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 den Fehler gefunden

Lag wirklich am Destruktor.
Ich hab ihn jetzt so:

~MovableVertex() 
  {
    if(ref != 0 && this == ref->revref)
      {
	  ref->revref = 0;
      }
  }

Der revref vom vertex auf die man zeigt darf nicht auf einen anderen movablevertex zeigen. Wenn der auf einen anderen zeigt darf der pointer nicht einfach 0 gesetzt werden.

Und der Algorithmus läuft jetzt schneller als mit dem kompletten make_heap, falls ihr euch noch an den Anfang dieses Thread erinnern könnt.

Vielen dank für eure Hilfe.
Hab wieder sehr viel durch euch gelernt

Grüße

Max

volkard

Max3000 schrieb:

Und der Algorithmus läuft jetzt schneller als mit dem kompletten make_heap, falls ihr euch noch an den Anfang dieses Thread erinnern könnt.

Ja, das war anzunehmen. Aber wie schnell im Vergleich zum Fibonacci-Heap?
Weil ich auch den Verdacht hege, daß der Fibonacci-Heap eher von theoretischem Interesse ist.

volkard

Max3000 schrieb:

Der revref vom vertex auf die man zeigt darf nicht auf einen anderen movablevertex zeigen.

Ja, das sehe ich auch so.

Max3000 schrieb:

Wenn der auf einen anderen zeigt darf der pointer nicht einfach 0 gesetzt werden.

Hätte nie passieren dürfen, daß ich auf einen Mann zeige, der nicht auf mich zeigt. Dachte ich.

life

volkard schrieb:

Max3000 schrieb:

Wenn der auf einen anderen zeigt darf der pointer nicht einfach 0 gesetzt werden.

Hätte nie passieren dürfen, daß ich auf einen Mann zeige, der nicht auf mich zeigt. Dachte ich.

Richtig. Da läuft irgendwas schief..

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?