Pointer auf Datenobjekte in einem vector heap speichern.

life

Ponto schrieb:

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

Ach ja? Wie denn?

Ponto

life schrieb:

Ponto schrieb:

Die Assertion ist einfach falsch. Du musst einfach damit umgehen können, dass ref == NULL ist. Sowas kann ja leicht passieren.

Ach ja? Wie denn?

Offensichtlich passiert es.

Irgendwas in der Art:

MovableVertex tmp = std::move(a);

a = std::move(a);

Selbstzuweisung ist natürlich auch etwas, was man beachten muss.

life

Du kannst aber nicht a in zwei Objekte moven. Das dürfte UB o.Ä. sein (müsste man sich mal den neuen Standard anschauen).

Ein Objekt in sich selbst moven finde ich auch noch etwas merkwürdig. Keine Ahnung was die g++ STL da treibt..

Ponto

life schrieb:

Du kannst aber nicht a in zwei Objekte moven. Das dürfte UB o.Ä. sein (müsste man sich mal den neuen Standard anschauen).

Ein Objekt in sich selbst moven finde ich auch noch etwas merkwürdig. Keine Ahnung was die g++ STL da treibt..

Glaube ich nicht. std::move zerstört ja nicht die Source.

life

move ist ein "potentially destructive read". Es verschiebt eben nur die Daten von a nach tmp . Anschließend kann man nicht erwarten, dass die Daten noch in a enthalten sind. Ein weiteres move von a zu irgendwoanders hin macht daher imho keinen Sinn.

Aber da müsste man mal jemanden fragen, der sich schon mehr mit dem neuen Standard beschäftigt hat. Ggf. ist es zwar sinnfrei zweimal hintereinander move vom gleichen Objekt aus auszuführen, aber nicht undefiniert. Wenn das im der g++ STL passiert, würde ich aber in jedem Fall von einem Bug ausgehen.

Max3000 schrieb:

OK ich hab den CopyAssignment Operator mal wie folgt geändert:
MovableVertex& operator=(MovableVertex&& rhs) {

Der nennt sich aber "Move-Assignment Operator".

Eventuell ist der Copy-&-Swap-Trick eleganter.

life schrieb:

move ist ein "potentially destructive read". Es verschiebt eben nur die Daten von a nach tmp . Anschließend kann man nicht erwarten, dass die Daten noch in a enthalten sind. Ein weiteres move von a zu irgendwoanders hin macht daher imho keinen Sinn.

Aber da müsste man mal jemanden fragen, der sich schon mehr mit dem neuen Standard beschäftigt hat. Ggf. ist es zwar sinnfrei zweimal hintereinander move vom gleichen Objekt aus auszuführen, aber nicht undefiniert. Wenn das im der g++ STL passiert, würde ich aber in jedem Fall von einem Bug ausgehen.

Da muss man jetzt vorsichtig sein: Die Funktion move alleine verschiebt/kopiert nichts. Sie wird benutzt, um zu sagen "Dieses Objekt interessiert mich nicht mehr, es darf verändert werden." Das einzige, was sie tut, ist einen Lvalue-Ausdruck in einen Rvalue-Ausdruck zu verwandeln. Das, was die Funktion zurückgibt ist eine Referenz auf dasselbe Objekt. Nur es ist dann eine Rvalue-Referenz. Der potentiell destruktive Teil passiert erst im Move-Konstruktor, Move-Zuweisungs-Operator (oder sonst eine Funktion, die eine non-const Rvalue-Referenz annimmt). Und wenn ein Move-Konstruktor bzw Move-Assignment-Operator das Quellobjekt "geplündert" hat, dann kann man das Quellobjekt später immer noch benutzen. Also,

vector<int> v1 = ...;
vector<int> v2 = move(v1);
vector<int> v3 = move(v1);

macht zwar nicht viel Sinn, aber alle drei Vektoren werden in einem gültigen Zustand sein. Der Move-Konstruktor beim Initialisieren von v2 wird aber wahrscheinlich sich die Elemente aus v1 geklaut haben, so dass v1 ab der zweiten Zeile ein leerer Vektor ist. Aber in welchem Zustand der genau ist, ist ja nicht so wichtig. Ein passender Name für move könnte "idontcareanymore" sein.

life

Also "sinnfrei, aber nicht undefiniert". Ich bezweifle daher immer noch, dass sowas wie

vector<int> v1 = ...;
vector<int> v2 = move(v1);
vector<int> v3 = move(v1);

im STL-Quellcode vorkommt.

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt? Edit: Zumindest bei der VS2010-STL wird eine Selbstzuweisung explizit abgefangen im Move-Assignment Operator von vector . Also wird man das wohl brauchen..

life schrieb:

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt?

Mir fallen zwar keine Situationen ein, in denen so ein Fall auftreten kann, ohne dass man absichtlich a=move(a); schreibt, aber ich denke schon, dass das eine Klasse verkraften können sollte.

life schrieb:

Edit: Zumindest bei der VS2010-STL wird eine Selbstzuweisung explizit abgefangen im Move-Assignment Operator von vector . Also wird man das wohl brauchen..

Es gibt, wie gesagt, noch den Copy&Swap-Trick. Das ist nicht unbedingt die effizienteste Lösung in allen Fällen, aber relativ einfach und man kann kaum etwas falsch machen:

class Klasse
{
  ...
public:
  ...
  Klasse(Klasse const&); // copy ctor
  Klasse(Klasse     &&); // move ctor
  ~Klasse();

  void swap(Klasse& other);

  Klasse& operator=(Klasse tmp) {  // <-- pass-by-value ist Absicht
    this->swap(tmp);
    return *this;
  }
  ...
};

volkard

krümelkacker schrieb:

life schrieb:

btw. @krümelkacker: Wie sieht es denn mit einer Selbst-Move-Zuweisung aus? Ist die erlaubt?

Mir fallen zwar keine Situationen ein, in denen so ein Fall auftreten kann, ohne dass man absichtlich a=move(a); schreibt, aber ich denke schon, dass das eine Klasse verkraften können sollte.

Hmm...

void swap(Foo&& a,Foo &&b){
   Foo tmp=move(a);
   a=move(b);
   b=move(tmp);
}

Hoffentlich stimmt das so.

Also passiert's bei jedem swap(a,a). Wo hab ich sowas bloß gesehen? Ich erinnere mich, daß ich bei manchen Algos mich darauf verlassen habe, daß swap mit sich selbst erlaubt ist und damit ein if gespart habe.

Max3000

Hallo.

Ich habe das mal mit meinen anderen Beispielgraphen ausprobiert und von den 4 riesigen Graphen die ich habe funktionierts nur für einen.

Bei dem anderem erhalte ich einen Fehler beim "MoveConstructor" (das war doch jetzt richtig oder? :-))

MovableVertex(MovableVertex&& vertex) : ref(vertex.ref)
    {
      //std::cout << "Copied " << ref->number << " from " << &vertex << " to " << this << std::endl;

      assert(ref != 0);
      assert(&vertex != this);
      ref->revref = this; // <==== Hier krachts
      vertex.ref = 0;  
    }

Speicherzugriffsfehler.
Beim debuggen habe ich dann festgestellt dass ref zwar != 0 ist, aber irgendwie auch ungültig ist, darum bringen hier die ganzen 0-Checks ja rein gar nix.
Der Debugger sagt:

(gdb) print ref
$1 = (Vertex ) 0x20011
(gdb) print ref
Cannot access memory at address 0x20011

Wie kann so etwas zustande kommen?
Wie gesagt das passiert bei 3 von 4 riesigen Graphen.

Ponto

Lass es durch valgrind laufen.

Max3000

Habs versucht aber irgendwie scheint das unter openSUSE 11.2 nicht zu funktionieren. Ich versuch das mal zum laufen zu bringen und dann kommen Ergebnisse.

volkard schrieb:

Hmm...

void swap(Foo&& a,Foo &&b){
   Foo tmp=move(a);
   a=move(b);
   b=move(tmp);
}

Hoffentlich stimmt das so.

Ja, die zweite Zeile wäre dann bei &a==&b eine "Selbst-Move-Zuweisung". Allerdings müsste es heißen swap(Foo& a,Foo& b) . Dass die Rvalue-Referenzen sich mit Lvalue-Ausdrücken initialisieren lassen stimmt seit 1 1/2 Jahre nicht mehr. Leider ist so gut wie kein Rvalue-Referenz-Artikel im Netz auf dem aktuellen Stand. Es gibt eigentlich nur eine Artikel-Serie, die die aktuellen Regeln erklärt (beachte: Die Liste der Artikel auf der verlinkten Seite ist chronologisch verkehrt herum).

kk

Max3000

valgrind geht irgendwie nicht.
Der sagt mit fehlen die debug-info's zu glibc, aber die hab ich jetzt alle installiert, sowie die devel-Packete und debugsources aber hat alles nix gebracht.
Gibts vielleicht noch was anderes in der Richtung?

Ponto

Max3000 schrieb:

valgrind geht irgendwie nicht.
Der sagt mit fehlen die debug-info's zu glibc, aber die hab ich jetzt alle installiert, sowie die devel-Packete und debugsources aber hat alles nix gebracht.
Gibts vielleicht noch was anderes in der Richtung?

Such nach dem Problem bei google. Da gibt es eine Lösung zu. Ich glaube valgrind-Pakete aus einem Repository.

Eventuell: https://bugzilla.novell.com/show_bug.cgi?id=545721

Max3000

Die Seiten habe ich mir alle schon durchgelesen.
Müssen die Versionen von debug und normalem Packet übereinstimmen?
Bei einem hab ich die 2.10.irgendwas und debug hab ich die 2.11.irgendwas.

Max3000

Ah jetzt gehts. Hab ein Repo gefunden was die selbe Version anbietet.
Das kommt dabei raus:

> valgrind --leak-check=yes ./DijkstraBinary scotland_small.dat
==7787== Memcheck, a memory error detector
==7787== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==7787== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==7787== Command: ./DijkstraBinary scotland_small.dat
==7787==
K-Shortest Path Algorithm

Loading scotland_small.dat
Vertices loaded...
Edges loaded...
Vertices: 16384
Edges: 65025

Building shortest path tree...
0% 10 20 30 40 50 60 70 80 90 100%
|----|----|----|----|----|----|----|----|----|----|
==7787== Invalid read of size 8
==7787== at 0x402694: MovableVertex::MovableVertex(MovableVertex&&) (DijkstraBinary.cpp:174)
==7787== by 0x40302E: void std::push_heap<MovableVertex*>(MovableVertex*, MovableVertex*) (stl_heap.h:168)
==7787== by 0x401D18: main (DijkstraBinary.cpp:348)
==7787== Address 0x72a4b38 is 8 bytes before a block of size 131,072 alloc'd
==7787== at 0x4C249DC: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==7787== by 0x40565E: __gnu_cxx::new_allocator<MovableVertex>::allocate(unsigned long, void const*) (new_allocator.h:89)
==7787== by 0x404B9C: std::_Vector_base<MovableVertex, std::allocator<MovableVertex> >::_M_allocate(unsigned long) (stl_vector.h:140)
==7787== by 0x403BA9: MovableVertex* std::vector<MovableVertex, std::allocator<MovableVertex> >::_M_allocate_and_copy<std::move_iterator<MovableVertex*> >(unsigned long, std::move_iterator<MovableVertex*>, std::move_iterator<MovableVertex*>) (stl_vector.h:963)
==7787== by 0x402CD8: std::vector<MovableVertex, std::allocator<MovableVertex> >::reserve(unsigned long) (vector.tcc:74)
==7787== by 0x401AAC: main (DijkstraBinary.cpp:306)
==7787==
DijkstraBinary: DijkstraBinary.cpp:178: MovableVertex::MovableVertex(MovableVertex&&): Assertion `ref != 0' failed.
==7787==
==7787== HEAP SUMMARY:
==7787== in use at exit: 5,366,322 bytes in 114,183 blocks
==7787== total heap usage: 244,770 allocs, 130,587 frees, 10,514,919 bytes allocated
==7787==
==7787== 26 bytes in 1 blocks are possibly lost in loss record 1 of 11
==7787== at 0x4C249DC: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==7787== by 0x4ECCAF0: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.12)
==7787== by 0x4ECD724: ??? (in /usr/lib64/libstdc++.so.6.0.12)
==7787== by 0x4ECD8C1: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.12)
==7787== by 0x401850: main (DijkstraBinary.cpp:292)
==7787==
==7787== LEAK SUMMARY:
==7787== definitely lost: 0 bytes in 0 blocks
==7787== indirectly lost: 0 bytes in 0 blocks
==7787== possibly lost: 26 bytes in 1 blocks
==7787== still reachable: 5,366,296 bytes in 114,182 blocks
==7787== suppressed: 0 bytes in 0 blocks
==7787== Reachable blocks (those to which a pointer was found) are not shown.
==7787== To see them, rerun with: --leak-check=full --show-reachable=yes
==7787==
==7787== For counts of detected and suppressed errors, rerun with: -v
==7787== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 4 from 4)
Abgebrochen

Ponto

Der Fehler sagt wohl alles:

main (DijkstraBinary.cpp:348)

Address 0x72a4b38 is 8 bytes before a block of size 131,072 alloc'd

Sorry aber damit kann ich noch nix anfangen.
Was soll das bedeuten?
Dass 8 bytes vor einem Block von 131.072 bytes allokiert wurde?

SeppJ

max3001 schrieb:

Sorry aber damit kann ich noch nix anfangen.
Was soll das bedeuten?
Dass 8 bytes vor einem Block von 131.072 bytes allokiert wurde?

Nein, dass heißt, dass auf nicht reservierten Speicher zugegriffen wurde. Die Adresse des Zugriffs liegt aber 8 Bytes vor einem reservierten Block. Dies deutet auf einen fehlerhaften (möglicherweise negativen) Index beim Zugriff hin.