Klassen mit dynamische Datenstrukturen
Content |
Etwas komplizierter wird es, wenn Objekte bzw. deren Klassen dynamische Datenstrukturen unterhalten. Es lohnt sich, dies zuerst an einer trivialen Stack-Implementierung anzusehen. Gegeben sei folgende Klasse IntegerStack mit der Hilfsklasse IntegerMember, bei der momentan noch die Kopierkonstruktoren und Zuweisungsoperatoren fehlen:
#include <cassert> #include <iostream> class IntegerMember { public: IntegerMember(int member, IntegerMember* next) : member(member), next(next) { } ~IntegerMember() { delete next; } int member; IntegerMember* next; }; class IntegerStack { public: IntegerStack() : top(nullptr) { } ~IntegerStack() { delete top; } void push(int member) { top = new IntegerMember(member, top); } bool empty() { return top == nullptr; } int pop() { assert(top != nullptr); int member = top->member; IntegerMember* old = top; top = top->next; old->next = nullptr; delete old; return member; } private: IntegerMember* top; }; void print(const char* name, IntegerStack& s) { std::cout << name << ":"; while (!s.empty()) { std::cout << " " << s.pop(); } std::cout << std::endl; } int main() { IntegerStack a; a.push(1); a.push(2); a.push(3); print("a", a); }
Wenn Sie diese Fassung ausprobieren, scheint es zunächst zu klappen:
heim$ g++-7.2 -Wall -o simple-stack simple-stack.cpp heim$ ./simple-stack a: 3 2 1 heim$ valgrind ./simple-stack ==15083== Memcheck, a memory error detector ==15083== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. ==15083== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info ==15083== Command: ./simple-stack ==15083== a: 3 2 1 ==15083== ==15083== HEAP SUMMARY: ==15083== in use at exit: 72,704 bytes in 1 blocks ==15083== total heap usage: 4 allocs, 3 frees, 72,752 bytes allocated ==15083== ==15083== LEAK SUMMARY: ==15083== definitely lost: 0 bytes in 0 blocks ==15083== indirectly lost: 0 bytes in 0 blocks ==15083== possibly lost: 0 bytes in 0 blocks ==15083== still reachable: 72,704 bytes in 1 blocks ==15083== suppressed: 0 bytes in 0 blocks ==15083== Rerun with --leak-check=full to see details of leaked memory ==15083== ==15083== For counts of detected and suppressed errors, rerun with: -v ==15083== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) heim$
Anders sieht es aber aus, wenn die vom Übersetzer gelieferten Kopierkonstruktor und Zuweisungsoperatoren zum Einsatz kommen:
heim$ diff -U 2 simple-stack.cpp simple-stack2.cpp --- simple-stack.cpp 2018-05-03 14:34:32.116641531 +0200 +++ simple-stack2.cpp 2018-05-03 14:51:49.807947596 +0200 @@ -50,4 +50,12 @@ int main() { IntegerStack a; a.push(1); a.push(2); a.push(3); + { + IntegerStack b{a}; + print("b", b); + } + { + IntegerStack c; c = a; + print("c", c); + } print("a", a); } heim$ g++-7.2 -Wall -o simple-stack2 simple-stack2.cpp heim$ valgrind ./simple-stack2 ==15159== Memcheck, a memory error detector ==15159== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. ==15159== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info ==15159== Command: ./simple-stack2 ==15159== b: 3 2 1 ==15159== Invalid read of size 4 ==15159== at 0x400D9F: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B9B: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d20 is 0 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid read of size 8 ==15159== at 0x400DB6: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B9B: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d28 is 8 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid write of size 8 ==15159== at 0x400DC5: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B9B: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d28 is 8 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) c: 3 ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid read of size 8 ==15159== at 0x400C9B: IntegerMember::~IntegerMember() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400DDD: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B9B: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d28 is 8 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid free() / delete / delete[] / realloc() ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B9B: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d20 is 0 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid read of size 4 ==15159== at 0x400D9F: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400BB8: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d20 is 0 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid read of size 8 ==15159== at 0x400DB6: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400BB8: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d28 is 8 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== a: 3 ==15159== Invalid write of size 8 ==15159== at 0x400DC5: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400BB8: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d28 is 8 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid read of size 8 ==15159== at 0x400C9B: IntegerMember::~IntegerMember() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400DDD: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400BB8: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d28 is 8 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== Invalid free() / delete / delete[] / realloc() ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400BB8: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== Address 0x5a89d20 is 0 bytes inside a block of size 16 free'd ==15159== at 0x4C2A360: operator delete(void*) (vg_replace_malloc.c:507) ==15159== by 0x400DEA: IntegerStack::pop() (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400AE6: print(char const*, IntegerStack&) (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== by 0x400B6A: main (in /home/numerik/cpp/ss18/sessions/session02/simple-stack2) ==15159== ==15159== ==15159== HEAP SUMMARY: ==15159== in use at exit: 72,704 bytes in 1 blocks ==15159== total heap usage: 4 allocs, 5 frees, 72,752 bytes allocated ==15159== ==15159== LEAK SUMMARY: ==15159== definitely lost: 0 bytes in 0 blocks ==15159== indirectly lost: 0 bytes in 0 blocks ==15159== possibly lost: 0 bytes in 0 blocks ==15159== still reachable: 72,704 bytes in 1 blocks ==15159== suppressed: 0 bytes in 0 blocks ==15159== Rerun with --leak-check=full to see details of leaked memory ==15159== ==15159== For counts of detected and suppressed errors, rerun with: -v ==15159== ERROR SUMMARY: 10 errors from 10 contexts (suppressed: 0 from 0) heim$
Frage
Wozu ist die Anweisung old->next = nullptr; notwendig in der Methode pop der Klasse IntegerStack?
Aufgabe
Ergänzen Sie die obige Fassung mit Kopierkonstruktoren und Zuweisungsoperatoren, so dass alles ordnungsgemäß läuft und valgrind keine Fehler liefert. Machen Sie sich dabei das Leben so einfach wie möglich. Schleifen werden keine benötigt, da sich alles rekursiv erledigen lässt.