Heap und std::vector und das ganze auf Pointern

[Max3000]

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.

[life]

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

[volkard]

Max3000 schrieb:

Kann irgendwie so tief nicht rein debuggen.

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

[Max3000]

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?

[life]

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.

[volkard]

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

[Max3000]

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

[volkard]

Max3000 schrieb:

&&?

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

[life]

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.

[Max3000]

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.

[life]

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

[Max3000]

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?

[volkard]

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.

[life]

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

[volkard]

Max3000 schrieb:

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

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

[Max3000]

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 :(.

[Max3000]

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

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