3. Heap und std::vector und das ganze auf Pointern

Heap und std::vector und das ganze auf Pointern

  • L

    Nochmal in schön:

    #include <assert.h>
#include <algorithm>
#include <vector>
#include <iostream>

struct MovableNodePtr;

class Node {
public:
    MovableNodePtr* revptr;
    int key;
    //etc  
};

struct MovableNodePtr  {
    Node* ptr;

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

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

        rhs.ptr = 0;		
    }

    MovableNodePtr& operator=(MovableNodePtr&& rhs) {
        ptr = rhs.ptr;
        assert(ptr != 0);        
        ptr->revptr = this;

		rhs.ptr = 0;        

        return *this;
    }

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

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

};

int main() {  
    std::vector<Node> nodes(42);
    std::vector<MovableNodePtr> heap;  
    for(std::size_t i = 0; i < nodes.size(); ++i) {
        heap.push_back(MovableNodePtr(&nodes[i]));
    }
    std::make_heap(heap.begin(), heap.end());
    std::pop_heap(heap.begin(), heap.end());
    heap.pop_back();
    std::push_heap(heap.begin(), heap.end());
}

    edit: Mit g++ müsste du dann das flag "-std=gnu++0x" (oder so) hinzufügen.

    0
  • V

    Max3000 schrieb:

    Bei GLIBCXX_MOVE ist dann schluss.

    lokalePlatte/move.h

    #ifdef __GXX_EXPERIMENTAL_CXX0X__
_GLIBCXX_BEGIN_NAMESPACE(std)
#define _GLIBCXX_MOVE(_Tp) std::move(_Tp)
#else
#define _GLIBCXX_MOVE(_Tp) (_Tp)
#endif

    und
    http://www.boost.org/doc/libs/1_40_0/boost/config/compiler/gcc.hpp

    #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ > 2)) && defined(__GXX_EXPERIMENTAL_CXX0X__)
// C++0x features are only enabled when -std=c++0x or -std=gnu++0x are
// passed on the command line, which in turn defines
    0
  • M

    Ich werds sofort ausprobieren, Danke.
    Aber wozu brauchst du operator=, das Zeugs unter private und was ist das &&? Seh ich ehrlich gesagt grad zum ersten mal ^^.

    Ich meld mich in 3 Minuten wieder 🙂

    0
  • V

    Max3000 schrieb:

    &&?

    http://www.c-plusplus.net/forum/viewtopic-var-t-is-270735.html

    0
  • L

    Dachte auch, dass GLIBCXX_MOVE sehr nach C++0x aussieht ;). Aber komisch, dass die g++ STL anscheinend kein swap für die heap functionen benutzt.

    0
  • M

    life du hast mich schon ein bisschen weitergebracht aber es geht immer noch nicht :D.
    Dein Copy Assignment Operator macht auf jeden Fall Sinn und der Check im CopyConstruktor auch. Das Programm rechnet schon weiter als vorher aber das push_heap beim decreaseKey übersteht es immer noch nicht.

    0
  • L

    Wenn du es selbst nicht debugged bekommst, am besten mal aktuellen Quellcode + Beispieleingabedatei anhängen.

    0
  • M

    Ok zu dem && beles ich mich morgen nochmal.

    Ich bekomm nur als Fehler ein: expected ‘,’ or ‘...’ before ‘&&’ token
    Weiterhin muss das Argument im Copy Contruktor const sein, sonst beschwert sich der Compiler: /usr/include/c++/4.4/bits/vector.tcc:306: error: no matching function for call to ‘MovableVertex::MovableVertex(const MovableVertex&)’

    @volkard: heißt das wir müssen move überladen?

    0
  • V

    life schrieb:

    Dachte auch, dass GLIBCXX_MOVE sehr nach C++0x aussieht ;). Aber komisch, dass die g++ STL anscheinend kein swap für die heap functionen benutzt.

    template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
    void
    __push_heap(_RandomAccessIterator __first,
		_Distance __holeIndex, _Distance __topIndex, _Tp __value)
    {
      _Distance __parent = (__holeIndex - 1) / 2;
      while (__holeIndex > __topIndex && *(__first + __parent) < __value)
	{
	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
	  __holeIndex = __parent;
	  __parent = (__holeIndex - 1) / 2;
	}
      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
    }

    Er fügt erstmal nicht ein, sondern läßt anhand des value erstmal nur das Loch hochblubbern/versickern.
    Ein swap sind drei MOVS, ein move mit ptr->revptr=this;rhs.ptr=0; dürfte ähnlich sein. Also egal. Aber wenn im Heap nur platte integers oder Zeiger sind, dürfte die move-Variante die swap-Variante plattmachen.

    0
  • L

    @Max3000: Du musst C++0x mittels Compilerflag aktivieren, wenn du '&&' verwenden willst.

    0
  • V

    Max3000 schrieb:

    @volkard: heißt das wir müssen move überladen?

    Nein. std::move benutzt automagisch lifes &&-Versionen.

    0
  • M

    Geht das ganze irgendwie auch ohne das &&?
    Mit -std=c++0x als Compiler Flag kompiliert er zwar wieder, aber es kommt immer noch ein Speicherzugriffsfehler an der selben stelle. So langsam weiß ich nicht mehr weiter :(.

    0
  • M

    @life: Dein assert im Destruktor wird irgendwie ausgelöst. Muss das wirklich

    assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);

    sein?
    Wenn man den CopyConstruktor für ein anderes Objekt aufruft, wird ptr doch auf 0 gesetzt.

    0
  • V

    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.

    0
  • M

    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?

    0
  • M

    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);
  } 
};
    0
  • V

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

};
    0
  • M

    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

    0
  • V

    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.

    0
  • V

    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.

    0
Anmelden zum Antworten