Im heutigen Artikel soll es noch einmal um die bereits vorgestellten strukturierten Datentypen gehen; konkret wollen wir uns anschauen, wie diese intern im Speicher abgelegt werden, welche Probleme es dabei bei der Komposition von strukturierten Typen geben kann und wie Pointer helfen, diese Probleme zu lösen.

Fangen wir mit der “einfachsten” Sache an: der Repräsentation der Strukturen im Speicher. Natürlich ist das Thema zwar – wie so oft – doch etwas komplexer, als hier im Folgenden beschrieben, für das allgemeine Verständnis ist es aber ausreichend, sich auf die Grundlagen zu beschränken1.

1Für interessierte Leser seien hier einmal die beiden Stichworte Data Alignment und Data Structure Padding erwähnt.

In einem früheren Artikel wurde bereits beschrieben, wie einfache, primitive Datentypen (also zum Beispiel ganze Zahlen) im Speicher repräsentiert werden – sie stehen dort einfach als Bitkette in einer einzelnen Speicherzelle. Haben wir in einer Funktion zwei Variablen nacheinander deklariert, so werden sie im Speicher auch in aufeinanderfolgenden Zellen gespeichert. Wie im vorherigen Artikel beschrieben, werden strukturierte Datentypen genutzt, um logisch zusammengehörige Werte auch im Programm zusammengefasst zu repräsentieren. Was also liegt näher, als die Bestandteile eines strukturierten Datentyps im Speicher ebenfalls einfach in aufeinanderfolgenden Zellen abzulegen? Richtig, nichts.

Handelsübliche C++-Compiler sind genau so aufgebaut, dass sie einen strukturierten Datentyp als Sammlung seiner einzelnen Bestandteile betrachten. Variablen, die mit so einem Typen deklariert werden, belegen also im Speicher genau so viele Zellen, wie die einzelnen Bestandteile für sich benötigen2.

2Wie bereits erwähnt ist dass zwar eine Vereinfachung der tatsächlichen Umsetzung, aber eine hinreichend genaue.

Woher dem Compiler bekannt ist, welche Speicherzelle durch eine bestimmte Variable angesprochen wird, wissen wir – die Variablen sind in der Reihenfolge ihrer Deklaration durchnummeriert, so dass die 3. Variable (bei rein primitiven Datentypen) der 3. Speicherzelle ausgehend von der Basis des aktuellen Stack Frames entspricht. Auf die Bestandteile eines strukturierten Datentyps kann nach der gleichen Logik zugegriffen werden: auf die einzelnen Werte eines strukturierten Datentyps kann über die (bekannte) Nummer ihrer Speicherzelle zugegriffen werden.

Schauen wir uns das einmal am Beispiel an, ausgehend von der Datenstruktur für gebrochene Zahlen aus dem letzten Artikel:

struct Fraction { int numerator; int denominator; };

Nehmen wir weiterhin eine Funktion f an, in welcher 2 Variablen vom Fraction-Typ deklariert werden:

void f() { Fraction x; Fraction y; ... }

Beim Aufruf der Funktion f wird sich dadurch nun (ungefähr) das folgende Speicherbild ergeben. Verweisen mehrere Variablen auf die gleiche Speicherzelle, ist das entsprechend vermerkt; zudem sind alle zu den Variablen x und y gehörenden Speicherzellen in der Spalte Var entsprechend markiert (auf die ebp-Offsets verzichte ich jetzt einmal, die sollten klar sein):

Adresse Inhalt Inhalt Inhalt Inhalt Var
123450 <– esp
123454 <– x
<– x.numerator
x
123458 <– x.denominator
123462 <– y
<– y.numerator
y
123466 <– y.denominator
123470 <– ebp
123490 <– bottom

Werden Werte eines solchen strukturierten Datentyps gespeichert oder gelesen, muss nur auf die passende Speicherzelle zugegriffen werden.

Natürlich können strukturierte Datentypen selbst wiederum Bestandteile eines strukturierten Datentyps sein (man spricht hier von der Komposition von strukturierten Typen), etwa in der folgenden Art, wo der Datentyp FractionPair ein Paar aus Brüchen darstellt (die Reihenfolge der Deklaration ist in C++ übrigens wichtig: erst, nachdem ein Datentyp deklariert wurde, kann er auch in weiter unten liegendem Code genutzt werden):

struct Fraction { int numerator; int denominator; }; struct FractionPair { Fraction f; Fraction s; };

Die Werte des FractionPair-Datentyps belegen nun nicht mehr einzelne Speicherzellen, sondern so viele, wie durch die einzelnen Bestandteile benötigt werden – hier also jeweils zwei Zellen. Haben wir also zum Beispiel die folgende Funktion:

void g() { FractionPair p; ... }

Dann sieht das zugehörige Speicherbild so aus (die Variablenzugehörigkeiten sind wieder entsprechend in Var1 und Var2 angegeben):

Adresse Inhalt Inhalt Inhalt Inhalt Var1 Var2
123450 <– esp
123454 <– p
<– p.f
<– p.f.numerator
p p.f
123458 <– p.f.denominator
123462 <– p.s
<– p.s.numerator
p.s
123466 <– p.s.denominator
123470 <– ebp
123490 <– bottom

Nun habe ich am Anfang des Artikels erwähnt, dass es bei der Komposition von strukturierten Datentypen zu Problemen kommen kann. Konkret geht es um die folgende Situation; nehmen wir eine Struktur Human an, die den Namen eines Menschen festhält, sowie die Eltern dieses Menschen (mit char* werden Zeichenketten beschrieben – die Details dahinter sollen an dieser Stelle nicht weiter interessieren, können aber theoretisch aus den Informationen der Artikel 7 und 8 hergeleitet werden)

struct Human { char* name; Human mother; Human father; };

Soweit sieht das ja eigentlich ganz logisch aus; das Problem ist nur, dass es so nicht machbar ist. Versucht man, diesen Code zu kompilieren, wird der Compiler unweigerlich Fehlermeldungen bringen, die leider nicht unbedingt auf das eigentliche Problem hinweisen; der Visual-Studio-Compiler von Microsoft wird etwa wenig aussagekräftig melden:

error C2460: 'Human::mother': Verwendet gerade definiertes 'Human'

Das Problem hier liegt natürlich in der Art des Speicherlayouts. Wie weiter oben beschrieben, benötigt eine Variable eines strukturierten Datentyps so viele Speicherzellen, wie die einzelnen Bestandteile des Datentyps benötigen. Für die Human-Struktur wäre das also einmal eine Speicherzelle für den Verweis auf den Namen (char* name) und der benötigte Speicher für die Mutter und den Vater. Die Mutter ist wieder ein Human, die wiederum eine Speicherzelle für den Namen und entsprechenden Speicher für deren Eltern benötigt; für die Eltern der Mutter (und natürlich des Vaters) gilt wieder das gleiche, und so weiter. Wir haben es also mit dem Problem einer unendlichen Rekursion zu tun: der benötigte Speicher wäre in unserem Beispiel unendlich groß, weil jeder Mensch einen Namen und zwei Eltern hätte.

Was uns fehlt, ist die Möglichkeit, einem Menschen nicht zwei Eltern zu geben (das widerspricht jetzt zwar auf den ersten Blick der Realität, aber biologisch gesehen ist das sogar korrekt: wenn wir weit genug in die Vergangenheit gehen, werden wir ein Wesen finden, welches keine zwei Eltern hatte). Um das zu verwirklichen, müssen wir die Datenstuktur für den Human etwas anders aufbauen, da momentan immer zwei Eltern gefordert sind.

Wünschenswert wäre eine Möglichkeit, die Eltern wahlweise zu definieren oder – wenn sie nicht vorhanden sind – undefiniert zu lassen. Mit einer “normalen” Variablendeklaration lässt sich das nicht erreichen, da gewöhnliche Variablen nicht in dem Sinne undefiniert sein können; ihnen kann zwar einfach kein Wert zugewiesen werden – der für sie theoretisch benötigte Speicher muss aber dennoch immer reserviert werden. Das Stichwort zur Lösung ist aber genau die Reservierung von Speicher: wie wir uns erinnern, ging es im Kapitel über den Heap schon einmal genau darum. Das Mittel der Wahl sind dann auch die bereits in diesem Artikel erwähnten Adressverweise, sprich: die Pointer.

Wir erinnern uns: eine Variable kann als ein Pointer deklariert werden, indem vor den Variablennamen ein * geschrieben wird; Pointer-Variablen verweisen nicht auf konkrete Werte, sondern auf eine Adresse, unter welcher der gesuchte Wert im Speicher zu finden ist. Zudem hat eine Pointer-Variable eine feste Größe und benötigt zur Speicherung immer genau 4 Byte, also eine Speicherzelle (auf 64-Bit-Systemen entsprechend 8 Byte).

Möchten wir nun, dass eine Variable auf keine Adresse verweist, so weisen wir ihr einen speziellen Wert zu, nämlich die 0. An dieser Adresse werden während des Programmablaufs niemals relevante Daten stehen, weswegen sie zur Markierung von derartigen Leerverweisen benutzt wird; man spricht dementsprechend auch von Null-Pointern.

Wir können also in unserem Beispiel die Eltern eines Menschen nicht direkt als Menschen, sondern als Verweise auf Menschen deklarieren, was so aussieht:

struct Human { char* name; Human* mother; Human* father; };

Die Größe einer Human-Variable lässt sich nun eindeutig bestimmen: 4 Byte werden für den Namens-Verweis benötigt und noch einmal je 4 Byte für die Verweise auf die beiden Eltern; macht 12 Byte beziehungsweise 3 Speicherzellen insgesamt. Legen wir nun also eine Variable vom Typ Human wie folgt an

void h() { Human h; ... }

dann ergibt sich das folgende Speicherbild:

Adresse Inhalt Inhalt Inhalt Inhalt Var
123450 <– esp
123454 <– h
<– h.name
h
123458 <– h.mother
123462 <– h.father
123466 <– ebp
123490 <– bottom

Um nun einem Menschen einen Elternteil zuzuweisen, nutzen wir das aus dem vorletzten Artikel bekannte new-Schlüsselwort:

void h() { Human h; h.mother = new Human; }

Hier passiert nichts anderes, dass als durch new Human auf dem Heap der benötigte Speicherplatz für einen neuen Menschen reserviert wird und die Start-Adresse dieses reservierten Speicherbereiches an h.mother zugewiesen wird. Der Ausdruck h.mother verweist also im folgenden auf den gerade reservierten neuen Menschen.

Wollen wir dagegen ausdrücken, dass ein Mensch keine Eltern hat, weisen wir den Variablen einen Nullpointer zu. Dafür gibt es in C++ verschiedene Möglichkeiten; entweder nutzt man direkt die Zahl 0, oder – ab dem neuen Standard C++11 – das spezielle Schlüsselwort nullptr (beides drückt das gleiche aus):

void h() { Human h; h.mother = 0; h.father = nullptr; }

Jetzt stellt sich natürlich die Frage, wie man mit den Eltern eines Menschen weiterarbeiten kann – experimentierfreudige werden merken, dass etwa der Ausdruck h.mother.mother zu einer Fehlermeldung seitens des Compilers führt. Im nächsten Artikel werden wir demnach sehen, wie man mit Pointern arbeiten kann. Seid gespannt!

Kommentare (2)

  1. #1 Nicolai
    November 13, 2013

    0 und nullptr drücken nicht das selbe aus – das eine kann als integraler Wert verwendet werden, das andere nur als Zeiger-Adresse und zur true / false Abfrage. Im Gegensatz zu NULL, das meistens als #define NULL 0 implementiert ist, ist der nullptr somit nur für Zeiger-Operationen gültig.

    Danke für die ausführlichen Artikel, ich finde es klasse, dass du ein wenig auf die Technik im Speicher eingehst. 🙂

    Kleine Frage: Kannst du grob erklären, wie ein Konstruktor übersetzt wird? Ich würde es mir wie eine normale Klassenfunktion vorstellen, Aufruf mit dem this-Pointer und den Argumenten, weiß aber nicht, ob das korrekt ist..

  2. #2 Marcus Frenkel
    November 13, 2013

    @Nicolai

    0 und nullptr drücken nicht das selbe aus – das eine kann als integraler Wert verwendet werden, das andere nur als Zeiger-Adresse und zur true / false Abfrage.

    Ich dachte mir schon, dass ein Kommentar dazu kommt. 😉
    Das gleiche sind sie natürlich nicht, aber sie drücken in Bezug auf die Nullpointer-Adresse das gleiche aus. Natürlich bestehen viele Unterschiede zwischen beiden Werten, aber im Kontext dieser einfachen Zuweisung sind sie äquivalent.

    Konstruktor kommt demnächst. So ein bisschen sind das wirklich normale Klassenfunktionen, die aber ein bisschen Extramagie beim Aufruf betreiben. Insbesondere werden hierbei zu Beginn des Konstruktors der Konstruktor der Basisklasse sowie die Konstruktoren alle Klassen-Attribute aufgerufen. Wo im Falle von RTTI die Typinformation gesetzt wird, weiß ich gerade gar nicht, das könnte aber auch im Konstruktor sein.