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

Heap und std::vector und das ganze auf Pointern

  • M

    Hab ich das jetzt richtig verstanden, dass ich dann sowas machen kann:

    std::vector<Node> nodes;
// ... Nodes einlesen

std::vector<MovableNodePrt> heap;
heap.push_back(MovableNodePrt(nodes.at(0));
heap.push_back(MovableNodePrt(nodes.at(2));
//...
Node* myNode = /*irgendwoher*/;
node->key = /*irgendwas kleineres*/
heap_push(heap.begin(), (&myNode->revref)+1);

    revref ist der Pointer von Node auf MocableNodePrt.
    Hab ich das richtig verstanden?

    0
  • V

    Max3000 schrieb:

    Hab ich das richtig verstanden?

    Ja.

    0
  • M

    Aber ich brauch doch einen iterator und keinen MovableNodePrt*. Das versteh ich noch nicht so ganz.

    0
  • V

    Max3000 schrieb:

    Aber ich brauch doch einen iterator und keinen MovableNodePrt*. Das versteh ich noch nicht so ganz.

    Ein Iterator ist was, was sich wie ein Zeiger anfühlt. Insbesondere ist ein Zeiger ein Iterator.
    Aber kannst auch &heap[0],&heap[revptr-heap.begin()] machen statt &heap[0],revptr
    oder heap.begin(),heap.begin()+(revptr-heap.begin()) ? Viele Wege von Rom weg.

    0
  • L

    @volkard: Das hier kompiliert zumindest mit VS2010:

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

struct MovableNodePrt;

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

struct MovableNodePrt  {
    Node* ptr;

    MovableNodePrt() : ptr(0) {
       assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
    }

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

	MovableNodePrt& operator=(MovableNodePrt&& rhs) {
		ptr = rhs.ptr;
		if(ptr != 0) {			
            ptr->revptr = this;
		}
        rhs.ptr = 0;
		assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
		assert(rhs.ptr == 0 || rhs.ptr->revptr == 0 || rhs.ptr->revptr == this);
		return *this;
	}

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

    void initPointer(Node* ptr) {
        assert(this->ptr == 0);
        this->ptr = ptr;
        assert(ptr->revptr==0);//zwei MovableNodePrts für einen Node böse sein
        ptr->revptr = this;
		assert(ptr == 0 || ptr->revptr == 0 || ptr->revptr == this);
    }

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

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

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

};

int main() {   
    std::vector<Node> nodes(42);
    std::vector<MovableNodePrt> heap(42);   
    for(std::size_t i = 0; i < heap.size(); ++i) {
        heap[i].initPointer(&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());
}
    0
  • M

    Irgendwie funktioniert das nicht.
    Ich schicke jetzt einfach mal den kompletten Code.
    Das swap und Speicherfreigabe hab ich noch nicht mit drin.
    Wollt das mal Schritt für Schritt machen, aber bekomme Compilerfehler:

    DijkstraBinary.cpp:224: error: no matching function for call to ‘push_heap(__gnu_cxx::__normal_iterator<MovableVertex*, std::vector<MovableVertex, std::allocator<MovableVertex> > >, MovableVertex**)’

    #include <stdlib.h>
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>

#include <boost/progress.hpp>

enum State
{
  LABELED, UNLABELED, SCANNED
};

class MovableVertex;
class Vertex;

/*
 * The edge class which is connecting 2 vertices
 */
class Edge
{
 public:
  Vertex* tail;
  Vertex* head;
  double length;
  double delta;

 Edge(Vertex* tail, Vertex* head, double length) 
   : tail(tail), head(head), length(length) {}
};

class Vertex
{
 public:
  friend class MovableVertex;

  Vertex(int number, double key) : number(number), key(key), state(UNLABELED), pred(NULL), revref(NULL) {}
  Vertex(const Vertex &that)
  {
    std::cout << "Copy constructor\n";
  }

  std::vector<Edge*> incomingEdges;
  std::vector<Edge*> outgoingEdges; 

  int number;
  double key;

  State state;  

  Vertex *pred;

  void addIncomingEdge(Edge *edge)
  {
    incomingEdges.push_back(edge);
  }
  void addOutgoingEdge(Edge *edge)
  {
    outgoingEdges.push_back(edge);
  }

  bool operator<(const Vertex &that) const
  {
    return this->key <= that.key;
  }

  bool operator>(const Vertex &that) const
  {
    return this->key > that.key;
  }

  friend std::ostream& operator<<(std::ostream &os, const Vertex &v)
  {
    os << "Vertex " << v.number << " (key=" << v.key <<
      ", incoming edges from=";
    for(int i=0; i<v.incomingEdges.size(); ++i)
      os << v.incomingEdges[i]->tail->key << ' ';
    os << ')';
    return os;
  }

  MovableVertex* revref;
};

class MovableVertex
{
public:
  MovableVertex(Vertex* vertex) : ref(vertex) {ref->revref = this;}
  Vertex* ref;

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

int main(int argc, char *argv[])
{
	printf("K-Shortest Path Algorithm\n\n");

	/*
		STEP 0: Initialization
	*/
	long n;
	const int repetitions = 100;

	if(argv[1]== NULL)
	{	
		printf("1 Argument required: shortestpath.exe [graph file name]\n");
		printf("Example: ./Dijkstra.exe scotland_big.dat\n");
		return 0;
	}	

	// Define test vertices
	std::vector<Vertex*> vertices;
	std::vector<Edge*> edges;

	// Read source file
	printf("Loading %s\n", argv[1]);
	std::ifstream indat(argv[1]);

	if(indat)
	{
	        indat >> n;

		for(int j=0; j<n-1 ; j++)
		{
			Vertex *v = new Vertex(j, -1);
			vertices.push_back(v);
		}

		printf("Vertices loaded...\n");

		vertices.push_back(new Vertex(n-1, 0)); 
		vertices[n-1]->state = LABELED;

		// Read edges and initialize
		while(!indat.eof())
		{
                        int tail, head, tmp;
			double length;
			indat >> tail >> head >> tmp >> length;

			Edge *edge = new Edge(vertices[tail], vertices[head], length);
			edge->head->addIncomingEdge(edge);
			edge->tail->addOutgoingEdge(edge);
			edges.push_back(edge);
		}	
	}
	else
	{
		printf("Could not open input data...\n");
		return 0;
	}

	printf("Edges loaded...\n");
	printf("Vertices: %d\nEdges: %d\n\n", vertices.size(), edges.size());
	printf("Building shortest path tree...");
	/*
		STEP 1: Shortest Path Tree
	*/

	boost::progress_display progress(repetitions);
	double elapsed = 0;
	for(int i=0; i<repetitions; ++i)
	  {
	    // Set all vertices to unlabeled
	    for(std::vector<Vertex*>::iterator i=vertices.begin(); i!=vertices.end(); ++i)
	      {
		(*i)->state = UNLABELED;
	      }

	    // Here the actual algorithm starts, so start the timer
	    boost::timer tmr;	    

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

	    bool abort = false;
	    long j = 0;
	    // Scan
	    do
	      {
		// Delete minimum path
		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));
			    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;

			    push_heap(heap.begin(), &(headOfCurrentEdge->revref) + 1); // HIER IST DER FEHLER!!!
			  }
		      }
		  }
	      }
	    while(heap.size() != 0);
	    elapsed += tmr.elapsed();
	    ++progress;
	  }
	std::cout << "\nAlgorithm finished after " << elapsed*1000./repetitions << "ms\n";

	// Print out path
	Vertex *temp = vertices[0];

	if(!temp->pred)
	{
		printf("There exist no s-t paths\n");
		return 0;
	}

	int vertexCount = 0;

	printf("Shortest Path found:\n");
	printf("Distance: %f\n", vertices[0]->key);

	while(temp)
	{
		printf("%d", temp->number);
		temp = temp->pred;
		if(temp)
			printf(" - ");

		vertexCount++;
	}

	printf("\nVertices passed: %d\n", vertexCount);

	return 0;
}
    0
  • L

    std::push_heap(&heap[0], headOfCurrentEdge->revref + 1);

    0
  • M

    Kann mir das mal bitte jemand erklären?
    Mit

    push_heap(&heap[0], headOfCurrentEdge->revref + 1);

    bekomm ich ‘push_heap’ was not declared in this scope

    Mit

    std::push_heap(&heap[0], headOfCurrentEdge->revref + 1);

    Gehts dann?
    Ist im STD namespace ein anderes push_heap?

    0
  • L

    Darüber bin ich auch gerade gestolpert. Warum ist push_heap überhaupt im global namespace sichtbar? std::push_heap sollte jedenfalls das richtige sein..

    0
  • ?

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