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++-8.3 -Wall -g -o simple-stack simple-stack.cpp
heim$ ./simple-stack
a: 3 2 1
heim$ valgrind ./simple-stack
==30201== Memcheck, a memory error detector
==30201== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==30201== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==30201== Command: ./simple-stack
==30201== 
a: 3 2 1
==30201== 
==30201== HEAP SUMMARY:
==30201==     in use at exit: 0 bytes in 0 blocks
==30201==   total heap usage: 5 allocs, 5 frees, 76,848 bytes allocated
==30201== 
==30201== All heap blocks were freed -- no leaks are possible
==30201== 
==30201== For counts of detected and suppressed errors, rerun with: -v
==30201== 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.000000000 +0200
+++ simple-stack2.cpp	2018-05-03 14:51:49.000000000 +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++-8.3 -Wall -g -o simple-stack2 simple-stack2.cpp
heim$ valgrind ./simple-stack2
==30259== Memcheck, a memory error detector
==30259== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==30259== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==30259== Command: ./simple-stack2
==30259== 
b: 3 2 1
==30259== Invalid read of size 4
==30259==    at 0x400CEB: IntegerStack::pop() (simple-stack2.cpp:31)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AE6: main (simple-stack2.cpp:58)
==30259==  Address 0x5a87d20 is 0 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid read of size 8
==30259==    at 0x400D02: IntegerStack::pop() (simple-stack2.cpp:33)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AE6: main (simple-stack2.cpp:58)
==30259==  Address 0x5a87d28 is 8 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
c: 3
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid write of size 8
==30259==    at 0x400D11: IntegerStack::pop() (simple-stack2.cpp:34)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AE6: main (simple-stack2.cpp:58)
==30259==  Address 0x5a87d28 is 8 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid read of size 8
==30259==    at 0x400BE7: IntegerMember::~IntegerMember() (simple-stack2.cpp:10)
==30259==    by 0x400D29: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AE6: main (simple-stack2.cpp:58)
==30259==  Address 0x5a87d28 is 8 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid free() / delete / delete[] / realloc()
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AE6: main (simple-stack2.cpp:58)
==30259==  Address 0x5a87d20 is 0 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid read of size 4
==30259==    at 0x400CEB: IntegerStack::pop() (simple-stack2.cpp:31)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400B03: main (simple-stack2.cpp:60)
==30259==  Address 0x5a87d20 is 0 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid read of size 8
==30259==    at 0x400D02: IntegerStack::pop() (simple-stack2.cpp:33)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400B03: main (simple-stack2.cpp:60)
==30259==  Address 0x5a87d28 is 8 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid write of size 8
==30259==    at 0x400D11: IntegerStack::pop() (simple-stack2.cpp:34)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400B03: main (simple-stack2.cpp:60)
==30259==  Address 0x5a87d28 is 8 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
a: 3
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid read of size 8
==30259==    at 0x400BE7: IntegerMember::~IntegerMember() (simple-stack2.cpp:10)
==30259==    by 0x400D29: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400B03: main (simple-stack2.cpp:60)
==30259==  Address 0x5a87d28 is 8 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== Invalid free() / delete / delete[] / realloc()
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400B03: main (simple-stack2.cpp:60)
==30259==  Address 0x5a87d20 is 0 bytes inside a block of size 16 free'd
==30259==    at 0x4C2D2DB: operator delete(void*) (vg_replace_malloc.c:576)
==30259==    by 0x400D36: IntegerStack::pop() (simple-stack2.cpp:35)
==30259==    by 0x400A31: print(char const*, IntegerStack&) (simple-stack2.cpp:45)
==30259==    by 0x400AB5: main (simple-stack2.cpp:54)
==30259==  Block was alloc'd at
==30259==    at 0x4C2C21F: operator new(unsigned long) (vg_replace_malloc.c:334)
==30259==    by 0x400C73: IntegerStack::push(int) (simple-stack2.cpp:24)
==30259==    by 0x400A9C: main (simple-stack2.cpp:51)
==30259== 
==30259== 
==30259== HEAP SUMMARY:
==30259==     in use at exit: 0 bytes in 0 blocks
==30259==   total heap usage: 5 allocs, 7 frees, 76,848 bytes allocated
==30259== 
==30259== All heap blocks were freed -- no leaks are possible
==30259== 
==30259== For counts of detected and suppressed errors, rerun with: -v
==30259== 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.