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

Heap und std::vector und das ganze auf Pointern

  • ?

    life schrieb:

    struct MovableNodePrt;

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

struct MovableNodePrt  {
	Node* ptr;
	MovableNodePrt() : ptr(0){
		
	}

	MovableNodePrt(MovableNodePrt&& rhs) : ptr(rhs.ptr) {
		if(ptr != 0)
			ptr->revptr = this;
		//rhs.ptr = 0;
	}

	~MovableNodePrt(){
		if(ptr != 0)
			ptr->revptr=0;
	}

    Im Destruktor gehst Du beim Setzen von revptr auf 0 davon aus, dass ptr==0 || ptr->revptr==this gilt. Weil Du aber im move-Konstruktor rhs.ptr=0; auskommentiert hast, gilt das natürlich nicht immer. Also entweder wird das im Destruktor nochmal überprüft, oder Du machst aus der Bedingung von oben eine Invariante und achtest darauf, dass sie immer eingehalten wird.

    kk

    0
  • M

    Ich hab zu folgender Schleife noch eine kurze Frage.
    Bei push_back aufruf unten kommt ein Speicherzugriffsfehler.
    Um genau zu sein in der operator<(MovableVertex, MovableVertex)-Funktion. Da sind beide Objekte ungültig.
    Kann das daran liegen, weil an der Stelle wo ich "// geht das?" dahinter geschrieben habe ein Objekt angelegt wird, was am Ende des Schleifenrumpfes wieder gelöscht wird?

    std::vector<MovableVertex> heap;
	    heap.push_back(MovableVertex(vertices[n-1]));

	    bool abort = false;
	    long j = 0;
	    // Scan
	    do
	      {
		// Delete minimum path
		std::pop_heap(heap.begin(), heap.end());
		Vertex *v = heap.back().ref;
		heap.pop_back();

		v->state = SCANNED;

		for(int i = 0; i < v->incomingEdges.size(); i++)
		  {
		    Edge *currentEdge = v->incomingEdges[i];
		    Vertex *headOfCurrentEdge = currentEdge->tail;

		    if(headOfCurrentEdge->state != SCANNED)
		      {
			if(headOfCurrentEdge->state == UNLABELED)
			  {
			    // Insert a vertex with infinite key
			    headOfCurrentEdge->state = LABELED;
			    headOfCurrentEdge->pred = v;
			    headOfCurrentEdge->key = v->key + currentEdge->length;

			    heap.push_back(MovableVertex(headOfCurrentEdge)); // Geht das?
			    std::push_heap(heap.begin(), heap.end());
			  }
			else if(headOfCurrentEdge->key > v->key + currentEdge->length )
			  {
			    // decrease the key of a vertex with finite key
			    headOfCurrentEdge->pred = v;
			    headOfCurrentEdge->key = v->key + currentEdge->length;

			    std::push_heap(&heap[0], headOfCurrentEdge->revref + 1); // SPEICHERZUGRIFFSFEHLER
			  }
		      }
		  }
	      }
	    while(heap.size() != 0);
    0
  • L

    krümelkacker schrieb:

    Also entweder wird das im Destruktor nochmal überprüft, oder Du machst aus der Bedingung von oben eine Invariante und achtest darauf, dass sie immer eingehalten wird.

    Ich habe mich noch nicht weiter mit rvalue references beschäftigt, aber ich hatte irgendwie im Kopf, dass es ein Vorteil des Move-Konstruktors war, dass man die rhs in einem ungültigen Zustand zurücklassen darf oder so. Aber ich vertraue dir mal und habe entsprechend den Code oben editiert.

    0
  • M

    Ich komme irgendwie nicht mehr weiter.
    Es wird ständig der Copy-Konstruktor von MoveVertexPrt aufgerufen.
    Beim Einfügen in den Heap einmal und beim Push_Heap unterschiedlich oft.

    Die Frage ist was da zu tun ist.

    MovableVertex(const MovableVertex &vertex) : ref(vertex.ref) {
    ref->revref = this;
  }

    Tuts irgendwie auch nicht.
    Auf was musst revref zeigen? Welche Kopie ist nun die richtige?

    Danke nochmal für eure Hilfe bis hier hin.
    Auf die jetzige Lösung wäre ich ohne euch nie gekommen.

    0
  • V

    Max3000 schrieb:

    Ich komme irgendwie nicht mehr weiter.
    Es wird ständig der Copy-Konstruktor von MoveVertexPrt aufgerufen.
    Beim Einfügen in den Heap einmal und beim Push_Heap unterschiedlich oft.

    Das ist gar nicht gut.
    Warum macht der sowas?
    Also swap hätte ich erwartet und den Move-Konstruktor könnte ich tolerieren.
    Beides müßte funktionieren.
    Wozu braucht überhaupt jemand den Kopierkonstruktor? Den würde ich verbieten. Und den Zuweisungsoperator gleich mit. Weil einfach nicht zwei MovableVertexes auf den/das selbe(n) Vertex zeigen sollen.

    push_back müßte mit rvalue-referenz doch erst lecker werden. Und im Versickern... das geht doch auch wahlweise mit move oder swap.
    Wobei unser MovableVertex inhaltlich noch Quatsch macht, glaube ich.

    Mal suchen, vielleicht hab ich irgendwo nen Heap rumliegen...
    Nee, ich müßte eine alte Platte anschließen.

    Auf was musst revref zeigen? Welche Kopie ist nun die richtige?

    Immer auf den/das(?) einzige(n) MovableVertex, der/das überleben wird.

    0
  • M

    2 Sachen wundern mich noch.
    Da der Copy-Konstruktor aufgerufen wird, wird das andere Objekt ja wieder gelöscht, also

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

    Das darf ja nicht passieren, dass das revref von node jetzt doch auf 0 gesetzt wird.

    Und was mich noch wundert ist, dass mein swap gar nicht aufgerufen wird.
    Am Ende nimmt der immer das std::swap. Wie finde ich das raus? Kann irgendwie so tief nicht rein debuggen.

    0
  • L

    Wenn du VS2010 benutzt, probiers doch mal mit meinem Code. Dort sind nur die rvalue ref Varianten von Copyconstructor und operator= überladen und es kompiliert. Damit sollte es eigentlich immer nur einen gültigen MovableVertexPtr geben.

    Ich denke auch, dass MovableVertexPtr inhaltlich ok ist ;).

    0
  • V

    Max3000 schrieb:

    Kann irgendwie so tief nicht rein debuggen.

    Kannst nicht mit rechter MauTa auf push_heap die Definition suchen und anzeigen?

    0
  • M

    Ich hab Linux und da benutze ich emacs. Ich komm schon in die stl_vector.h und stl_heap.h Funktionen rein, aber da kann ich eigentlich nix erkennen was nach swap aussieht.

    Kompilieren tut mein Programm auch, aber bei der pop_heap-Funktion kommt ein Speicherzugriffsfehler und zwar genau hier:

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

    weil v1 und v1 ungültig sind.
    Nullpointer oder sowas.

    Beim Debuggen komm ich bis zu:

    template<typename _RandomAccessIterator>
    inline void
    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));
    }

    Bei GLIBCXX_MOVE ist dann schluss.
    Wird sicherlich was externes sein oder?
    Ich such mal ob ich irgendwo die debug informationen dazu finde.
    von da drin aus wird jedenfalls mein copy-konstruktor überladen.
    Kann ich auch im std::swap einen breakpoint setzen? Weiß jemand in welcher datei die funktion zu finden ist?

    0
  • 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
Anmelden zum Antworten