Programmieren Teil 10 – Strukturierte Datentypen 2

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änken¹.

^{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ötigen².

^{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):

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;
    ...
}