[X] Speicherverwaltung in C++ (und C)

[CStoll]

Vorbemerkungen

Für einfache Anwendungen reicht es völlig aus, sich auf die automatische Speicherverwaltung über lokale Variablen zu verlassen. Aber sobald die Datenmengen größer werden, kommt man nicht mehr daran vorbei, Speicherplatz vom Heap anzufordern und zu verwalten.

Inhalt

1. Funktionsfamilien
2. Allokatoren
3. Hilfsfunktionen
4. Smart-Pointer
5. STL Container

1 Funktionsfamilien

Grundsätzlich gehören zur Speicherverwaltung immer zwei Teile. Erstens muß ein Speicherbereich angefordert werden und zweitens muß der benutzte Speicher am Ende der Arbeit wieder zurückgegeben werden. Aus diesem Grund exisitieren Speicherverwaltungsfunktionen normalerweise paarweise und teilen sich diese Arbeit.

Bei der Arbeit mit C++ Objekten kommt noch dazu, den angeforderten Speicher mit sinnvollen Startwerten zu füllen bzw. die Daten des Objekts am Ende der Arbeit wieder aufzuräumen. Für diesen Zweck gibt es Konstruktoren und Destruktoren, die je nach den verwendeten Verwaltungsfunktionen automatisch aufgerufen werden oder manuell behandelt werden müssen.

Im Laufe der Zeit wurden verschiedene Funktionspaare entwickelt, mit denen Speicher angefordert und wieder freigegeben werden kann. Dabei ist es besonders wichtig, die verschiedenen Methoden der Speicherverwaltung NICHT miteinander zu mischen. Im einfachsten Fall ergibt sich "nur" ein Speicherleck (wenn die Freigabefunktion "nur" vergisst, den Objektdestruktor aufzurufen oder zu wenig Heap-Speicher zurückgibt), im schlimmsten Fall kann nicht vorhergesagt werden, was das Programm machen wird (z.B. kann es passieren, daß die Freigabefunktion versucht, etwas in der ihr unbekannten Speicherstruktur zu interpretieren).

Aus diesem Grund sollten Bibliotheken, die Heap-Bereiche anfordern und dem Nutzer übergeben, immer eine kompatible Freigabefunktion bereitstellen, die passend zur eigenen Speicherverwaltung arbeitet - oder zumindest in der Dokumentation angeben, welche Methode der Speicherverwaltung sie verwenden.

1.1 malloc() und free()

Diese Familie stammt noch aus C und wurde aus Kompatibilitätsgründen auch für C++ übernommen:

• malloc(s)
  reserviert einen Speicherbereich mit (mindestens) s Byte Größe und gibt einen Zeiger auf den Beginn dieses Bereichs zurück. Der Inhalt dieses Bereichs ist undefiniert.
• calloc(n,s)
  reserviert genug Speicher für n Objekte der Größe s zur Verfügung und initialisiert ihn mit Nullen
• realloc(p,s)
  ändert die Größe des Speichers, auf den p zeigt, auf s Byte und gibt die neue Adresse des Speichers zurück ("realloc(NULL,s)" ist äquivalent zu "malloc(s)" und "realloc(p,0)" entspricht "free(p)")
• free(p)
  gibt den durch malloc() etc angeforderten Speicherbereich wieder frei (p darf auch der NULL-Zeiger sein, in dem Fall passiert gar nichts)

Diese Funktionen kümmern sich nicht um den Inhalt der verwalteten Speicherbereiche und sollten deshalb nur mit POD (plain old data) Datentypen verwendet werden.

Anmerkung: Die Funktion realloc() kann auch im Alleingang die komplette Speicherverwaltung eines Programmes übernehmen, indem ihre Parameter passend gesetzt werden:

char*str = realloc(NULL,100);//Speicheranforderung
...
realloc(str,0);//Speicherfreigabe

1.2 new und delete

Für C++ wurde ein neues System zur Speicherverwaltung eingeführt, das besser auf das Klassenkonzept eingeht. Im Gegensatz zu malloc()/free() werden die Speicherbereiche als Objekte beliebiger Klassen aufgefasst und sofort mit einem geeigneten Konstruktor initialisiert.

• new T(...)
  reserviert genug Speicher für ein Objekt vom Typ T und ruft dessen Konstruktor entsprechend der angegebenen Parameterliste auf (die Parameterliste kann auch wegfallen, dann wird der Default-Konstruktor verwendet)
• delete p;
  ruft den Destruktor des Objekts auf, auf das p zeigt, und gibt anschließend dessen Speicher frei

Ein weiterer Vorteil von new und delete ist die Tatsache, daß sie vom Nutzer überschrieben werden können. Dazu benötigt man entweder eine globale (für jeden new-Aufruf) oder statische Memberfunktion (für die eigene Klasse und alle Kinder) "operator new()" bzw. "operator delete()", die den Speicher anfordern bzw. freigeben können. Diese Operatoren arbeiten mit unstrukturierten Datenbereichen - der Aufruf von Konstruktoren und Destruktoren erfolgt unabhängig davon:

void* operator new(size_t s)
{
  void* p;
  //reseviere Speicher für mindestens s Bytes
  return p;
}

void operator delete(void* p)
{
  //gib Zeiger p frei
}

Beide Funktionen können zusätzliche Parameter von beliebigem Typ erhalten, um das sogenannte "Placement new" zu implementieren. Diese Parameter werden durch den Aufruf "new(values) T(ctor-Parameter)" übergeben. Die häufigsten Anwendungsfälle hierfür sind die Vorgabe einer Zieladresse (um ein Objekt in vorhandenem Speicher zu initialisieren) und der Einbau von Debugging-Angaben (der MFC Operator "DEBUG_NEW" übergibt z.B. Dateiname und Programmzeile, um Speicherlecks verfolgen zu können).

Anmerkung: "operator new" und "operator delete" arbeiten mit nackten Speicherbereichen. Der Konstruktor und Destruktor des beteiligten Objekts wird aufgerufen, nachdem operator new zurückgekehrt ist bzw. bevor operator delete aufgerufen wird.

Achtung: Überladen Sie die globalen Operatoren nur, wenn Sie sich absulut sicher sind, was Sie damit erreichen wollen. Die globale Version von operator new und operator delete übernimmt wirklich JEDE Speicheranforderung innerhalb des Programms - und im Gegensatz zu klasseninternen Operatoren können Sie von hier aus nicht auf die vordefinierten Speicher-Operatoren zugreifen.

Eine weitere typische Anwendung für operator new und operator delete ist der Einsatz eines Pool-Managers: Um Rechenzeit zu sparen, wird der Speicher vorsorglich in größeren Blöcken angefordert, aufgehoben und bei Bedarf an das Programm weitergegeben. Vom Programm freigegebener Speicher wird nicht ans System zurückgegeben, sondern für späteren Anforderungen ebenfalls aufgehoben.

1.3 new[] und delete[]

Parallel zu new und delete, die mit einzelnen Objekten hantieren, gibt es Versionen, um ganze Objekt-Arrays zu verwalten:

• new T[n]
  reserviert genug Speicher für n Objekte vom Typ T und ruft für jedes Objekt dessen Default-Konstruktor auf
  Anmerkung: Es ist nicht möglich, Parameter für den aufgerufenen Konstruktor anzugeben
• delete[] p;
  ruft für alle Objekte im Array hinter p den Destruktor auf und anschließend den Speicher frei

Genau wie new/delete lassen sich auch diese Funktionen anpassen, indem "void* operator new[](size_t s);" bzw. "void operator delete[](void* p);" überschrieben werden.

Anmerkung: new[] merkt sich (genau wie malloc()) intern die Größe des reservierten Speichers. Es gibt jedoch keine portable Möglichkeit, auf diese Informationen zuzugreifen.

Achtung: Trotz der Namensähnlichkeit ist nicht garantiert, daß new/delete und new[]/delete[] zueinander kompatibel sind. Also versuchen Sie NIE, beide miteinander zu vermischen.

1.4 weitere Familien

Viele Bibliotheken definieren eigene Funktionspaare, um Speicher anzufordern und wieder freizugeben, z.B. VirtualAlloc()/VirtualFree() aus der WinAPI, die Speicher im "shared Memory" verwalten oder ??? (Speicherverwaltung UNIX). Allen dieser Funktionsfamilien gemeinsam ist, daß sie aus mindestens zwei Funktionen bestehen - eine zum Anfgordern von Speicher, eine zur Freigabe. Analog zur malloc()-Familie können weitere Funktionen dazukommen, die den verwalteten Speicher reorganisieren können.

Da verschiedene Speicherstrategien nicht unbedingt miteinander kompatibel sind, sollten Sie immer die richtige Freigabefunktion verwenden, wenn Sie Ihren Speicher nicht mehr benötigen. Deshalb ist es idR eine gute Idee, sich innerhalb eines Programmes auf eine Strategie festzulegen und diese weitgehend durchzuhalten. Wenn das nicht generell möglich ist, sollte auf jeden Fall für jeden verwendeten Pointer festgelegt werden, woher er seinen Speicher beziehen soll.

Auch in der Standardbibliothek ist noch eine weitere Funktionsfamilie definiert, die zur Verwaltung von temporärem Speicher genutzt werden können:

• get_temporary_buffer<T>(num)
  reserviert einen temporären Puffer für maximal num Objekte vom Typ T und gibt ein Paar mit dessen Adresse und dem verfügbaren Speicherplatz zurück
• return_temporary_buffer(p)
  gibt einen angeforderten temporären Puffer wieder an das System zurück

Diese temporären Puffer können innerhalb einer Funktion verwendet werden, um größere Mengen an Zusatzspeicher bereitzustellen (z.B. benötigt MergeSort einen Hilfsspeicher für seine Daten). Achten Sie darauf, daß der zurückgegebene Speicherbereich kleiner sein kann als angefordert.

2 Allokatoren

Die Container der STL verwenden standardmäßig new[] und delete[], um sich den Speicher für ihre Elemente anzufordern. Da es jedoch möglich sein sollte, auf eine andere Speicherverwaltung auszuweichen, wurde dieses Verhalten in sogenannte Alloaktoren ausgelagert - diese lassen sich austauschen, um ein anderes Speicherverhalten zu verwenden. Dazu hat jede Containerklasse als letzten Template-Parameter die Angabe der verwendeten Allokator-Klasse. Der Defaultwert hierfür ist std::allocator<T> - dieser reserviert Speicher mit Hilfe von new[] und gibt ihn mit delete[] wieder frei.

Ein Allokator muß, um mit der STL eingesetzt werden zu können, einige grundlegende Methoden und Definitionen bereitstellen. Wenn Sie einen Allokator nur für eigene Zwecke schreiben, sind die Anforderungen möglicherweise geringer.

2.1 Verwaltungsfunktionen

Das wichtigste an der Allokatorklasse sind natürlich die Funktionen, die den Speicher verwalten können:

• allocate(n,h=0)
  Reserviert uninitialisierten Speicher für n Elemente und gibt ihn zurück (z.B. per ::operator new() oder malloc()). Der optional angegebene Pointer h kann zur Beeinflussung der Speicherstrategie verwendet werden.

• construct(p,val)
  Initialisiert das Objekt, auf das p zeigt, als Kopie von val (idR per Placement new)

• destroy(p)
  Zerstört das Objekt, auf das p zeigt (idR durch direkten Destruktor-Aufruf)

• deallocate(p,n)[/b]
  Gibt einen Bereich hinter p frei, der aus n Elementen besteht (der Parameter kann nützlich werden, wenn die Größe des verwendeten Speichers nicht aus dem Zeiger selber ermittelt werden kann) - die Objekte müssen vorher zerstört werden

Außerdem bietet der Allokator die Hilfsmethoden max_size(), die die maximal mögliche Größe eines Speicherblocks (in Elementen) angeben kann und adress(ref), mit der zu einem gegebenen Objekt die Adresse ermittelt werden kann.

Eigene Allokatoren werden in der Regel die Methoden allocate(), deallocate() und max_size() überschreiben, um die Speicherstrategie zu implementieren. construct() und destroy() dürften sich nur in den seltensten Fällen von der Standard-Version unterscheiden:

template<typename T>
class Alloc
{
  ...
public:
  void construct(pointer p, const T& val)
  { new((void*)p) T(val); }
  void destroy(pointer p)
  { p->~T(); }
  ...
};

2.2 rebind<>

Um die Möglichkeit zu bieten, verschiedenartige Objekte speichern zu können, enthält die Allokatorklasse eine Unterstruktur namens "rebind". Diese wird zum Beispiel von den Assoziativen Containerklassen verwendet, die als Template-Parameter einen allocator<T> erhalten, aber intern einen allocator<treenode<T> > benötigen.

Diese Struktur ist recht simpel aufgebaut und dient nur zur "Verpackung" des Ausweichtyps:

template<typename T>
class Alloc
{
  ...
public:
  template<tyename U>
  struct rebind
  { typedef Alloc<U> other; };
  ...
};

Auf diese Weise lässt sich problemlos ein Allokator für beliebige Daten erhalten, indem man diese Struktur inspiziert:

template<typename T,typename A = std::allocator<T> >
class mycont
{
public:
  //...
  typedef A allocator_type;
  typedef typename A::rebind<T*>::other ptr_allocator;//kompatibler Allokator für Pointer
  //...
};

2.3 Vergleiche

Verschiedene Allokatoren können miteinander mit den Operatoren == und != verglichen werden. Dabei kennzeichnet Gleichheit, daß zwei Allokatoren gegenseitig austauschbar sind - von a angeforderter Speicher kann über b wieder freigegeben werden.

Z.B. sind Allokatoren, die auf new/delete aufbauen, untereinander austauschbar, da man für den delete-Aufruf kein Steuerobjekt benötigt. Dagegen sind Pool-Allokatoren nur bedingt austauschbar, weil jeder Allokator seine eigene Liste an Reservespeicher verwaltet.

Anmerkung: STL-taugliche Allokatoren müssen untereinander austauschbar sein. Deshalb reduzieren sich die Vergleichsoperatoren meistens zu einem "return true;" bzw. "return false;".

2.4 Typdefinitionen

Allokatoren definieren auch einige Grundtypen, die von den angeschlossenen Containerklassen weiter verwendet werden:

• value_type (T)
  der zugrundeliegende Wertetyp
• size_type (size_t) und difference_type (ptrdiff_t)
  zwei Ganzzahltypen zur Angabe von Speichergrößen (vorzeichenlos) bzw. Zeiger-Differenzen (vorzeichenbehaftet)
• pointer (T*) und const_pointer (const T*)
  Zeiger auf veränderliche bzw. konstante Objekte
• reference (T&) und const_reference (const T&)
  Referenzen auf veränderliche bzw. konstante Objekte

Anmerkung: Für STL-taugliche Allokatoren ist die Vergabe dieser Grundtypen vorgegeben (entsprechend der obigen Angaben).

3 Hilfsfunktionen zur Speicherverwaltung

Zusätzlich zu den Allokatoren definiert die Standardbibliothek noch einige Hilfsfunktionen, die mit nicht-initialisiertem Speicher umgehen können. Diese dienen als logische Erweiterung von memset() und memcpy():

• uninitialized_fill(beg,end,val)
  initialisiert den Bereich (im STL-Sinn) [beg,end[ mit entsprechend vielen Kopien von 'val'
• uninitialized_fill_n(beg,n,val)
  initialisiert das Array hinter 'beg' mit n Kopien von 'val'
• uninitialized_copy(beg,end,nbeg)
  initialisiert das Array hinter 'nbeg' mit Kopien des Bereichs [beg,end[

Mit diesen Funktionen lässt sich auch die in Kapitel 1.3 genannte Einschränkung umgehen, daß new[] nur den Default-Konstruktor aufrufen kann:

T* data = ::operator new[](n*sizeof(T));
unitialized_fill_n(data,n,T(4711));
...
delete[] data;

~Ich hoffe mal, das klappt so wirklich - in meinem Buch steht nur ein analoges Beispiel mit Allokatoren.~

Im Notfall ist es auch möglich, über placement new einen uninitialisierten Speicherbereich mit Werten zu füllen:

myType*p = (myType*)malloc(sizeof(myType));
new(p) myType(params);
...
p->~myType();//direkter Destruktor-Aufruf
free(p);

(Anmerkung: Im Normalfall sollte statt dieser Konstruktion lieber direkt auf new/delete zurückgegriffen werden)

3.1 Rohspeicher-Iteratoren

voller Name:

template<typename OutIt,typename T>
class raw_storage_iterator;

Diese Hilfsiteratoren können verwendet werden, um einen uninitialisierten Speicherbereich als Ziel eines STL-Algorithmus' anzugeben. Sie übersetzen Wertzuweisungen in Aufrufe des Copy-Konstruktors über placement new.

Die Template-Parameter dieser Klasse sind erstens ein Ausgabe-Iterator, der als Grundlage für die Iterator-Arithmetik verwendet wird (normalerweise reicht hierfür ein 'T*') und zweitens der verwendete Datentyp.

3.2 Funktionen der C-Bibliothek

Im Gegensatz zu C++ interpretiert die C-Bibliothek normalerweise nichts in die Speicherbereiche, die sie verwaltet. Logisch gesehen, erhält man von malloc() einen Haufen Bytes ohne innere Struktur. Anschließend hängt es vom Programmierer ab, wie er den Speicherinhalt füllt und interpretiert.

Zur Verarbeitung dieser nackten Speicherbereiche kann man entweder den von malloc() erhaltenen Zeiger in den "richtigen" Typ casten und von Hand verarbeiten oder einige vorgefertigte Funktionen der C-Bibliothek (memcpy(), memset() etc) oder (mit Einschränkungen) die Stringverarbeitungsfunktionen (strcpy(), strcat() etc) zu Hilfe nehmen.

Anmerkung: Versuchen Sie besser nicht, blanken Speicher als C++ Objekte zu interpretieren. Die meisten Methoden erwarten eine vorhandene Grundstruktur und führen zu undefiniertem Verhalten, wenn sie Datenmüll vorgesetzt bekommen.

4 Smart Pointer

Die Verwaltung von Heap-Speicher (egal wie er angefordert wurde) über blanke Zeiger leidet immer unter dem selben Problem - man kann nicht überprüfen, wann und von wem der Speicher wieder freigegeben werden muß. Vergißt der letzte Besitzer die Freigabe, ergibt sich ein Speicherleck, weil niemand mehr von der Existenz des Speicherblocks weiß. Wird der Speicher zu früh freigegeben, erhält man Zugriffsverletzungen und undefiniertes Verhalten, wenn andere Nutzer auf den freigegebenen Speicher zugreifen wollen.

Eine Lösung dieses Problems ist es, die Zeiger selber mit der Speicherverwaltung zu beauftragen, indem man statt blanken Zeigern sogenannte "Smart-Pointer" verwendet. Dabei unterscheiden sich grundsätzlich drei verschiedene Vorgehensweisen, die Zugriffsrechte zu steuern und zu kontrollieren:

• Referenzzählung (boost::shared_ptr, boost::shared_array)
  Das referenzierte Objekt zählt mit, wieviele Zeiger auf es verweisen. Und erst, wenn der letzte Zeiger sich vom Objekt trennt, wird der Speicher freigegeben.
• Exklusiver Zugriff (boost::scoped_ptr, boost::scoped_array)
  Die Adresse darf nicht übergeben werden. Der Besitzer des Zeigers legt ihn an und ist am Ende auch dafür zuständig, ihn wieder freizugeben.
• Besitzübergabe (std::auto_ptr)
  Es existiert immer genau ein Zeiger, der auf einen Speicher verweist (Besitzer). Bei einer Zuweisung wird der Besitz weitergegeben und der bisherige Besitzer verliert den Zugriff auf den Speicher.

Die Funktionsweise und Besonderheiten verschiedener Smart-Pointer-Klassen wurde vor einiger Zeit im Artikel "schlaue Zeiger" von peterchen erklärt.

Achtung: Normale Smart-Pointer-Klassen sind auf eine bestimmte Speicherverwaltungsfuktion (üblicherweise new/delete oder new[]/delete[]) festgelegt und erwarten deshalb, daß ihr verwalteter Speicher "richtig" angelegt wurde.

Die obengenannten Smart-Pointer-Klassen sind (außer auto_ptr) in der Boost-Bibliothek oder in der Standard-Erweiterung TR1 zu finden. Die Klasse auto_ptr ist Bestandteil der C++ Standardbibliothek.

5 Container

Wem der ganze Aufwand der Speicherverwaltung zu kompliziert ist, der kann es sich auch einfacher machen - und die verschiedenen Containerklassen der STL verwenden. Alle Container kümmern sich selbständig darum, genug Speicher bereitzustellen und zu verwalten, so daß der Anwender sich nicht mehr darum zu kümmern braucht, wo seine Daten untergebracht werden.

Die verwendbaren Containerklassen unterscheiden sich aus Sicht der Speicherverwaltung hauptsächlich darin, nach welcher Strategie sie Speicher anfordern und organisieren:

• vector<> und basic_string<>
  verwenden einen zusammenhängenden Speicherbereich, der bei Bedarf mitwächst
• deque<>
  verwendet meist eine zweischichtige Struktur mit mehreren logisch aneinandergehängten Speicherblöcken, die bei Bedarf erweitert bzw. freigegeben werden
• list<>
  verwendet eine verkettete Liste, bei der jedes einzelne Element einnen Zeiger auf Vorgänger und Nachfolger besitzt
• set<>, multiset<>, map<> und multimap<>
  verwenden einen (balancierten) Binärbaum aus einzeln angeforderten Knoten, in den sie ihre Elemente einsortieren

Anmerkung: Dabei hängt es natürlich vom verwendeten Allocator ab, woher die Container ihren Speicher erhalten.

Weitere Informationen zu den Containern finden Sie in meinem Artikel "Aufbau der STL".

[CStoll]

Ja, ich weiß, hier fehlen noch ein paar Kleinigkeiten (aber ich hab' meine Notizen nicht dabei), aber trotzdem würde ich die Kollegen mal bitten, mir ihre Meinung dazu zu sagen. Was kann erweitert werden? Was ist unverständlich? Wo habe ich Nonsens geschrieben? ...?

[Artchi]

Kannst du bitte zu den Smartpointern noch schreiben, das diese mittlerweile im ISO-C++ TR1 drin sind?

Werde mir das ganze aber nochmal durchlesen.

[CStoll]

Artchi schrieb:

Kannst du bitte zu den Smartpointern noch schreiben, das diese mittlerweile im ISO-C++ TR1 drin sind?

Werde ich machen.

(ich sollte mich echt einmal informieren, was alles zur TR1 gehört - so oft wie ich schon darauf hingewiesen wurde)

[evilissimo]

CStoll schrieb:

Artchi schrieb:

Kannst du bitte zu den Smartpointern noch schreiben, das diese mittlerweile im ISO-C++ TR1 drin sind?

Werde ich machen.

(ich sollte mich echt einmal informieren, was alles zur TR1 gehört - so oft wie ich schon darauf hingewiesen wurde)

Ähm und du solltest eventuell auch den Titel ändern, die 10 Zeilen über malloc und co reißen es ja wohl net raus das du das groß als C Speicherverwaltung schimpfen kannst (imho!)

=> Speicherverwaltung in C++

BR
Vinzenz

[CStoll]

evilissimo schrieb:

Ähm und du solltest eventuell auch den Titel ändern, die 10 Zeilen über malloc und co reißen es ja wohl net raus das du das groß als C Speicherverwaltung schimpfen kannst (imho!)

=> Speicherverwaltung in C++

Ganz rausnehmen will ich den C-Anteil nun doch nicht. Aber du hast recht, der Hauptanteil gehört C++

Achja, wenn niemand mehr etwas zum Inhalt zu sagen hat, könnte der Artikel auch in die Rechtschreibkontrolle.

PS: An die Unix-Experten: Gibt es eigentlich spezielle Zugriffsfunktionen auf Unix-Ebene, die ich noch erwähnen könnte (Kapitel 1.4)?

[ness]

Naja, die meisten unixsysteme haben brk bzw. sbrk (is aber nich in posix), in posix sind noch mmap/munmap mit denen man speicher allozieren/freigeben kann.

[michba]

Vorbemerkungen

Für einfache Anwendungen reicht es völlig aus, sich auf die automatische Speicherverwaltung über lokale Variablen zu verlassen. Aber sobald die Datenmengen größer werden, kommt man nicht mehr daran vorbei, Speicherplatz vom Heap anzufordern und zu verwalten.

Inhalt

1. Funktionsfamilien
2. Allokatoren
3. Hilfsfunktionen
4. Smart-Pointer
5. STL-Container

1 Funktionsfamilien

Grundsätzlich gehören zur Speicherverwaltung immer zwei Teile. Erstens muss ein Speicherbereich angefordert werden und zweitens muss der benutzte Speicher am Ende der Arbeit wieder zurückgegeben werden. Aus diesem Grund existieren Speicherverwaltungsfunktionen normalerweise paarweise und teilen sich diese Arbeit.

Bei der Arbeit mit C++-Objekten kommt noch dazu, den angeforderten Speicher mit sinnvollen Startwerten zu füllen bzw. die Daten des Objekts am Ende der Arbeit wieder aufzuräumen. Für diesen Zweck gibt es Konstruktoren und Destruktoren, die je nach den verwendeten Verwaltungsfunktionen automatisch aufgerufen werden oder manuell behandelt werden müssen.

Im Laufe der Zeit wurden verschiedene Funktionspaare entwickelt, mit denen Speicher angefordert und wieder freigegeben werden kann. Dabei ist es besonders wichtig, die verschiedenen Methoden der Speicherverwaltung NICHT miteinander zu mischen. Im einfachsten Fall ergibt sich "nur" ein Speicherleck (wenn die Freigabefunktion "nur" vergisst, den Objektdestruktor aufzurufen oder zu wenig Heap-Speicher zurückgibt), im schlimmsten Fall kann nicht vorhergesagt werden, was das Programm machen wird (z.B. kann es passieren, dass die Freigabefunktion versucht, etwas in der ihr unbekannten Speicherstruktur zu interpretieren).

Aus diesem Grund sollten Bibliotheken, die Heap-Bereiche anfordern und dem Nutzer übergeben, immer eine kompatible Freigabefunktion bereitstellen, die passend zur eigenen Speicherverwaltung arbeitet - oder zumindest in der Dokumentation angeben, welche Methode der Speicherverwaltung sie verwenden.

1.1 malloc() und free()

Diese Familie stammt noch aus C und wurde aus Kompatibilitätsgründen auch für C++ übernommen:

• malloc(s)
  reserviert einen Speicherbereich mit (mindestens) s Byte Größe und gibt einen Zeiger auf den Beginn dieses Bereichs zurück. Der Inhalt dieses Bereichs ist undefiniert.
• calloc(n,s)
  reserviert genug Speicher für n Objekte der Größe s ~das "zur Verfügung" hat hier irgendwie nicht gepasst~ und initialisiert ihn mit Nullen
• realloc(p,s)
  ändert die Größe des Speichers, auf den p zeigt, auf s Byte und gibt die neue Adresse des Speichers zurück ("realloc(NULL,s)" ist äquivalent zu "malloc(s)" und "realloc(p,0)" entspricht "free(p)")
• free(p)
  gibt den durch malloc() etc. angeforderten Speicherbereich wieder frei (p darf auch der NULL-Zeiger sein, in dem Fall passiert gar nichts)

Diese Funktionen kümmern sich nicht um den Inhalt der verwalteten Speicherbereiche und sollten deshalb nur mit POD (plain old data) Datentypen verwendet werden.

Anmerkung: Die Funktion realloc() kann auch im Alleingang die komplette Speicherverwaltung eines Programms übernehmen, indem ihre Parameter passend gesetzt werden:

char*str = realloc(NULL,100);//Speicheranforderung
...
realloc(str,0);//Speicherfreigabe

1.2 new und delete

Für C++ wurde ein neues System zur Speicherverwaltung eingeführt, das besser auf das Klassenkonzept eingeht. Im Gegensatz zu malloc()/free() werden die Speicherbereiche als Objekte beliebiger Klassen aufgefasst und sofort mit einem geeigneten Konstruktor initialisiert.

• new T(...)
  reserviert genug Speicher für ein Objekt vom Typ T und ruft dessen Konstruktor entsprechend der angegebenen Parameterliste auf (die Parameterliste kann auch wegfallen, dann wird der Default-Konstruktor verwendet)
• delete p;
  ruft den Destruktor des Objekts auf, auf das p zeigt, und gibt anschließend dessen Speicher frei

Ein weiterer Vorteil von new und delete ist die Tatsache, dass sie vom Nutzer überschrieben werden können. Dazu benötigt man entweder eine globale (für jeden new-Aufruf) oder statische Memberfunktion (für die eigene Klasse und alle Kinder) "operator new()" bzw. "operator delete()", die den Speicher anfordern bzw. freigeben können. Diese Operatoren arbeiten mit unstrukturierten Datenbereichen - der Aufruf von Konstruktoren und Destruktoren erfolgt unabhängig davon:

void* operator new(size_t s)
{
  void* p;
  //reserviere Speicher für mindestens s Bytes
  return p;
}

void operator delete(void* p)
{
  //gib Zeiger p frei
}

Beide Funktionen können zusätzliche Parameter von beliebigem Typ erhalten, um das sogenannte "Placement new" zu implementieren. Diese Parameter werden durch den Aufruf "new(values) T(ctor-Parameter)" übergeben. Die häufigsten Anwendungsfälle hierfür sind die Vorgabe einer Zieladresse (um ein Objekt in vorhandenem Speicher zu initialisieren) und der Einbau von Debugging-Angaben (der MFC-Operator "DEBUG_NEW" übergibt z.B. Dateiname und Programmzeile, um Speicherlecks verfolgen zu können).

Anmerkung: "operator new" und "operator delete" arbeiten mit nackten Speicherbereichen. Der Konstruktor und Destruktor des beteiligten Objekts wird aufgerufen, nachdem operator new zurückgekehrt ist bzw. bevor operator delete aufgerufen wird.

Achtung: Überladen Sie die globalen Operatoren nur, wenn Sie sich absolut sicher sind, was Sie damit erreichen wollen. Die globale Version von operator new und operator delete übernimmt wirklich JEDE Speicheranforderung innerhalb des Programms - und im Gegensatz zu klasseninternen Operatoren können Sie von hier aus nicht auf die vordefinierten Speicher-Operatoren zugreifen.

Eine weitere typische Anwendung für operator new und operator delete ist der Einsatz eines Pool-Managers: Um Rechenzeit zu sparen, wird der Speicher vorsorglich in größeren Blöcken angefordert, aufgehoben und bei Bedarf an das Programm weitergegeben. Vom Programm freigegebener Speicher wird nicht ans System zurückgegeben, sondern für spätere Anforderungen ebenfalls aufgehoben.

1.3 new[] und delete[]

Parallel zu new und delete, die mit einzelnen Objekten hantieren, gibt es Versionen, um ganze Objekt-Arrays zu verwalten:

• new T[n]
  reserviert genug Speicher für n Objekte vom Typ T und ruft für jedes Objekt dessen Default-Konstruktor auf
  Anmerkung: Es ist nicht möglich, Parameter für den aufgerufenen Konstruktor anzugeben
• delete[] p;
  ruft für alle Objekte im Array hinter p den Destruktor auf und gibt anschließend den Speicher frei

Genau wie new/delete lassen sich auch diese Funktionen anpassen, indem "void* operator new[](size_t s);" bzw. "void operator delete[](void* p);" überschrieben werden.

Anmerkung: new[] merkt sich (genau wie malloc()) intern die Größe des reservierten Speichers. Es gibt jedoch keine portable Möglichkeit, auf diese Informationen zuzugreifen.

Achtung: Trotz der Namensähnlichkeit ist nicht garantiert, dass new/delete und new[]/delete[] zueinander kompatibel sind. Also versuchen Sie NIE, beide miteinander zu vermischen.

1.4 weitere Familien

Viele Bibliotheken definieren eigene Funktionspaare, um Speicher anzufordern und wieder freizugeben, z.B. VirtualAlloc()/VirtualFree() aus der WinAPI, die Speicher im "shared Memory" verwalten oder ??? (Speicherverwaltung UNIX). Allen diesen Funktionsfamilien gemeinsam ist, dass sie aus mindestens zwei Funktionen bestehen - eine zum Anfordern von Speicher, eine zur Freigabe. Analog zur malloc()-Familie können weitere Funktionen dazukommen, die den verwalteten Speicher reorganisieren können.

Da verschiedene Speicherstrategien nicht unbedingt miteinander kompatibel sind, sollten Sie immer die richtige Freigabefunktion verwenden, wenn Sie Ihren Speicher nicht mehr benötigen. Deshalb ist es idR eine gute Idee, sich innerhalb eines Programms auf eine Strategie festzulegen und diese weitgehend durchzuhalten. Wenn das nicht generell möglich ist, sollte auf jeden Fall für jeden verwendeten Pointer festgelegt werden, woher er seinen Speicher beziehen soll.

Auch in der Standardbibliothek ist noch eine weitere Funktionsfamilie definiert, die zur Verwaltung von temporärem Speicher genutzt werden können:

• get_temporary_buffer<T>(num)
  reserviert einen temporären Puffer für maximal num Objekte vom Typ T und gibt ein Paar mit dessen Adresse und dem verfügbaren Speicherplatz zurück
• return_temporary_buffer(p)
  gibt einen angeforderten temporären Puffer wieder an das System zurück

Diese temporären Puffer können innerhalb einer Funktion verwendet werden, um größere Mengen an Zusatzspeicher bereitzustellen (z.B. benötigt MergeSort einen Hilfsspeicher für seine Daten). Achten Sie darauf, dass der zurückgegebene Speicherbereich kleiner sein kann als angefordert.

2 Allokatoren

Die Container der STL verwenden standardmäßig new[] und delete[], um sich den Speicher für ihre Elemente anzufordern. Da es jedoch möglich sein sollte, auf eine andere Speicherverwaltung auszuweichen, wurde dieses Verhalten in sogenannte Allokatoren ausgelagert - diese lassen sich austauschen, um ein anderes Speicherverhalten zu verwenden. Dazu hat jede Containerklasse als letzten Template-Parameter die Angabe der verwendeten Allokator-Klasse. Der Defaultwert hierfür ist std::allocator<T> - dieser reserviert Speicher mit Hilfe von new[] und gibt ihn mit delete[] wieder frei.

Ein Allokator muss, um mit der STL eingesetzt werden zu können, einige grundlegende Methoden und Definitionen bereitstellen. Wenn Sie einen Allokator nur für eigene Zwecke schreiben, sind die Anforderungen möglicherweise geringer.

2.1 Verwaltungsfunktionen

Das wichtigste an der Allokatorklasse sind natürlich die Funktionen, die den Speicher verwalten können:

• allocate(n,h=0)
  Reserviert uninitialisierten Speicher für n Elemente und gibt ihn zurück (z.B. per ::operator new() oder malloc()). Der optional angegebene Pointer h kann zur Beeinflussung der Speicherstrategie verwendet werden.
• construct(p,val)
  Initialisiert das Objekt, auf das p zeigt, als Kopie von val (idR per Placement new)
• destroy(p)
  Zerstört das Objekt, auf das p zeigt (idR durch direkten Destruktor-Aufruf)
• deallocate(p,n)
  Gibt einen Bereich hinter p frei, der aus n Elementen besteht (der Parameter kann nützlich werden, wenn die Größe des verwendeten Speichers nicht aus dem Zeiger selber ermittelt werden kann) - die Objekte müssen vorher zerstört werden

Außerdem bietet der Allokator die Hilfsmethoden max_size(), die die maximal mögliche Größe eines Speicherblocks (in Elementen) angeben kann und adress(ref), mit der zu einem gegebenen Objekt die Adresse ermittelt werden kann.

Eigene Allokatoren werden in der Regel die Methoden allocate(), deallocate() und max_size() überschreiben, um die Speicherstrategie zu implementieren. construct() und destroy() dürften sich nur in den seltensten Fällen von der Standard-Version unterscheiden:

template<typename T>
class Alloc
{
  ...
public:
  void construct(pointer p, const T& val)
  { new((void*)p) T(val); }
  void destroy(pointer p)
  { p->~T(); }
  ...
};

2.2 rebind<>

Um die Möglichkeit zu bieten, verschiedenartige Objekte speichern zu können, enthält die Allokatorklasse eine Unterstruktur namens "rebind". Diese wird zum Beispiel von den assoziativen Containerklassen verwendet, die als Template-Parameter einen allocator<T> erhalten, aber intern einen allocator<treenode<T> > benötigen.

Diese Struktur ist recht simpel aufgebaut und dient nur zur "Verpackung" des Ausweichtyps:

template<typename T>
class Alloc
{
  ...
public:
  template<tyename U>
  struct rebind
  { typedef Alloc<U> other; };
  ...
};

Auf diese Weise lässt sich problemlos ein Allokator für beliebige Daten erhalten, indem man diese Struktur inspiziert:

template<typename T,typename A = std::allocator<T> >
class mycont
{
public:
  //...
  typedef A allocator_type;
  typedef typename A::rebind<T*>::other ptr_allocator;//kompatibler Allokator für Pointer
  //...
};

2.3 Vergleiche

Verschiedene Allokatoren können miteinander mit den Operatoren == und != verglichen werden. Dabei kennzeichnet Gleichheit, dass zwei Allokatoren gegenseitig austauschbar sind - von a angeforderter Speicher kann über b wieder freigegeben werden.

Zum Beispiel sind Allokatoren, die auf new/delete aufbauen, untereinander austauschbar, da man für den delete-Aufruf kein Steuerobjekt benötigt. Dagegen sind Pool-Allokatoren nur bedingt austauschbar, weil jeder Allokator seine eigene Liste an Reservespeicher verwaltet.

Anmerkung: STL-taugliche Allokatoren müssen untereinander austauschbar sein. Deshalb reduzieren sich die Vergleichsoperatoren meistens zu einem "return true;" bzw. "return false;".

2.4 Typdefinitionen

Allokatoren definieren auch einige Grundtypen, die von den angeschlossenen Containerklassen weiter verwendet werden:

• value_type (T)
  der zugrundeliegende Wertetyp
• size_type (size_t) und difference_type (ptrdiff_t)
  zwei Ganzzahltypen zur Angabe von Speichergrößen (vorzeichenlos) bzw. Zeiger-Differenzen (vorzeichenbehaftet)
• pointer (T*) und const_pointer (const T*)
  Zeiger auf veränderliche bzw. konstante Objekte
• reference (T&) und const_reference (const T&)
  Referenzen auf veränderliche bzw. konstante Objekte

Anmerkung: Für STL-taugliche Allokatoren ist die Vergabe dieser Grundtypen vorgegeben (entsprechend der obigen Angaben).

3 Hilfsfunktionen zur Speicherverwaltung

Zusätzlich zu den Allokatoren definiert die Standardbibliothek noch einige Hilfsfunktionen, die mit nicht-initialisiertem Speicher umgehen können. Diese dienen als logische Erweiterung von memset() und memcpy():

• uninitialized_fill(beg,end,val)
  initialisiert den Bereich (im STL-Sinn) [beg,end[ mit entsprechend vielen Kopien von 'val'
• uninitialized_fill_n(beg,n,val)
  initialisiert das Array hinter 'beg' mit n Kopien von 'val'
• uninitialized_copy(beg,end,nbeg)
  initialisiert das Array hinter 'nbeg' mit Kopien des Bereichs [beg,end[

Mit diesen Funktionen lässt sich auch die in Kapitel 1.3 genannte Einschränkung umgehen, dass new[] nur den Default-Konstruktor aufrufen kann:

T* data = ::operator new[](n*sizeof(T));
unitialized_fill_n(data,n,T(4711));
...
delete[] data;

~Ich hoffe mal, das klappt so wirklich - in meinem Buch steht nur ein analoges Beispiel mit Allokatoren.~

Im Notfall ist es auch möglich, über placement new einen uninitialisierten Speicherbereich mit Werten zu füllen:

myType*p = (myType*)malloc(sizeof(myType));
new(p) myType(params);
...
p->~myType();//direkter Destruktor-Aufruf
free(p);

(Anmerkung: Im Normalfall sollte statt dieser Konstruktion lieber direkt auf new/delete zurückgegriffen werden)

3.1 Rohspeicher-Iteratoren

voller Name:

template<typename OutIt,typename T>
class raw_storage_iterator;

Diese Hilfsiteratoren können verwendet werden, um einen uninitialisierten Speicherbereich als Ziel eines STL-Algorithmus' anzugeben. Sie übersetzen Wertzuweisungen in Aufrufe des Copy-Konstruktors über placement new.

Die Template-Parameter dieser Klasse sind erstens ein Ausgabe-Iterator, der als Grundlage für die Iterator-Arithmetik verwendet wird (normalerweise reicht hierfür ein 'T*') und zweitens der verwendete Datentyp.

3.2 Funktionen der C-Bibliothek

Im Gegensatz zu C++ interpretiert die C-Bibliothek normalerweise nichts in die Speicherbereiche, die sie verwaltet. Logisch gesehen, erhält man von malloc() einen Haufen Bytes ohne innere Struktur. Anschließend hängt es vom Programmierer ab, wie er den Speicherinhalt füllt und interpretiert.

Zur Verarbeitung dieser nackten Speicherbereiche kann man entweder den von malloc() erhaltenen Zeiger in den "richtigen" Typ casten und von Hand verarbeiten oder einige vorgefertigte Funktionen der C-Bibliothek (memcpy(), memset(), etc.) oder (mit Einschränkungen) die Stringverarbeitungsfunktionen (strcpy(), strcat(), etc.) zu Hilfe nehmen.

Anmerkung: Versuchen Sie besser nicht, blanken Speicher als C++-Objekte zu interpretieren. Die meisten Methoden erwarten eine vorhandene Grundstruktur und führen zu undefiniertem Verhalten, wenn sie Datenmüll vorgesetzt bekommen.

4 Smart Pointer

Die Verwaltung von Heap-Speicher (egal wie er angefordert wurde) über blanke Zeiger leidet immer unter demselben Problem - man kann nicht überprüfen, wann und von wem der Speicher wieder freigegeben werden muss. Vergisst der letzte Besitzer die Freigabe, ergibt sich ein Speicherleck, weil niemand mehr von der Existenz des Speicherblocks weiß. Wird der Speicher zu früh freigegeben, erhält man Zugriffsverletzungen und undefiniertes Verhalten, wenn andere Nutzer auf den freigegebenen Speicher zugreifen wollen.

Eine Lösung dieses Problems ist es, die Zeiger selbst mit der Speicherverwaltung zu beauftragen, indem man statt blanken Zeigern sogenannte "Smart-Pointer" verwendet. Dabei unterscheiden sich grundsätzlich drei verschiedene Vorgehensweisen, die Zugriffsrechte zu steuern und zu kontrollieren:

• Referenzzählung (boost::shared_ptr, boost::shared_array)
  Das referenzierte Objekt zählt mit, wie viele Zeiger auf es verweisen. Und erst, wenn der letzte Zeiger sich vom Objekt trennt, wird der Speicher freigegeben.
• Exklusiver Zugriff (boost::scoped_ptr, boost::scoped_array)
  Die Adresse darf nicht übergeben werden. Der Besitzer des Zeigers legt ihn an und ist am Ende auch dafür zuständig, ihn wieder freizugeben.
• Besitzübergabe (std::auto_ptr)
  Es existiert immer genau ein Zeiger, der auf einen Speicher verweist (Besitzer). Bei einer Zuweisung wird der Besitz weitergegeben und der bisherige Besitzer verliert den Zugriff auf den Speicher.

Die Funktionsweise und Besonderheiten verschiedener Smart-Pointer-Klassen wurde vor einiger Zeit im Artikel "Schlaue Zeiger" von peterchen erklärt.

Achtung: Normale Smart-Pointer-Klassen sind auf eine bestimmte Speicherverwaltungsfunktion (üblicherweise new/delete oder new[]/delete[]) festgelegt und erwarten deshalb, dass ihr verwalteter Speicher "richtig" angelegt wurde.

Die oben genannten Smart-Pointer-Klassen sind (außer auto_ptr) in der Boost-Bibliothek oder in der Standard-Erweiterung TR1 zu finden. Die Klasse auto_ptr ist Bestandteil der C++-Standardbibliothek.

5 Container

Wem der ganze Aufwand der Speicherverwaltung zu kompliziert ist, der kann es sich auch einfacher machen - und die verschiedenen Containerklassen der STL verwenden. Alle Container kümmern sich selbständig darum, genug Speicher bereitzustellen und zu verwalten, so dass der Anwender sich nicht mehr darum zu kümmern braucht, wo seine Daten untergebracht werden.

Die verwendbaren Containerklassen unterscheiden sich aus Sicht der Speicherverwaltung hauptsächlich darin, nach welcher Strategie sie Speicher anfordern und organisieren:

• vector<> und basic_string<>
  verwenden einen zusammenhängenden Speicherbereich, der bei Bedarf mitwächst
• deque<>
  verwendet meist eine zweischichtige Struktur mit mehreren logisch aneinander gehängten Speicherblöcken, die bei Bedarf erweitert bzw. freigegeben werden
• list<>
  verwendet eine verkettete Liste, bei der jedes einzelne Element einen Zeiger auf Vorgänger und Nachfolger besitzt
• set<>, multiset<>, map<> und multimap<>
  verwenden einen (balancierten) Binärbaum aus einzeln angeforderten Knoten, in den sie ihre Elemente einsortieren

Anmerkung: Dabei hängt es natürlich vom verwendeten Allokator ab, woher die Container ihren Speicher erhalten.

Weitere Informationen zu den Containern finden Sie in meinem Artikel "Aufbau der STL".

[michba]

Hi CStoll,
es waren wie immer wenig Fehler, aber wie immer auch alte Rechtschreibung ;).
Ich habe bei daß/dass und muß/muss jeweils nur die erste Korrektur mit kor-Tags gekennzeichnet, beim Rest habe ich sie weggelassen.
Zwei Hinweise noch:
Wie ist das in Abschnitt 3, willst du die Anmerkung im endgültigen Artikel stehen lassen oder nimmst du sie noch raus?
Und in 1.4 stehen noch die Fragezeichen wegen der Speicherverwaltung in UNIX. Musst dich dann auch noch entscheiden, ob du was hinschreibst oder es weglässt.

[CStoll]

-predator- schrieb:

es waren wie immer wenig Fehler, aber wie immer auch alte Rechtschreibung ;).

Die Macht der Gewohnheit

Wie ist das in Abschnitt 3, willst du die Anmerkung im endgültigen Artikel stehen lassen oder nimmst du sie noch raus?

Die Anmerkung fliegt noch raus - das sind nur Notizen für mich und andere Redakteure. (wer will, kann mir ja erklären, ob das funktioniert - oder warum nicht)

Und in 1.4 stehen noch die Fragezeichen wegen der Speicherverwaltung in UNIX. Musst dich dann auch noch entscheiden, ob du was hinschreibst oder es weglässt.

Vermutlich lasse ich es weg, denn mit ness' Vorschlägen kann ich nicht wirklich etwas anfangen (könntest du die Funktionen bitte genauer erklären?)

[estartu]

Du hast das Quote-Ende vergessen wegzumachen.

[estartu]

Noch Korrekturen? Oder kann er mit raus?
Ich wollte eigentlich jetzt das machen...

[CStoll]

Sorry, ich wußte, ich hab' was vergessen. Von meiner Seite spricht nichts dagegen, den rauszuschicken.

(soll ich noch eine neue Version für die Veröffentlichung anlegen oder nimmst du die da oben?)

[estartu]

Ich nehme die von oben (wurde ja geändert, guck mal den Thread von GPC).
Naja, dann kanns ja losgehen!