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

Funktionsfamilien
Allokatoren
Hilfsfunktionen
Smart-Pointer
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 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. 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;

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

Muss man new auf NULL überprüfen?

GPC

AlexRanzel schrieb:

Muss man new auf NULL überprüfen?

Nein, muss man nicht. new löst eine bad_alloc exception aus.
Man kann new aber auf das malloc-Verhalten umbiegen: http://www.cplusplus.com/reference/std/new/nothrow/

Ich hab nicht verstanden wie groß den Bytes s jetzt ist ... oder das mit den anderwn Buchstaben