(Fortsetzung)
Die C++-Template-Variante gegen die Kot-Explosion sähe so aus:
template <typename T>
int diff(T * arr, size_t n)
{
int result = 0;
for(size_t i = 0; i < n - 1; i++)
result += arr[i+1].member1 - arr[i].member1;
return result;
}
Probleme beim C++-Template-Gedönse gibts natürlich, wenn z.B.
Derived1
und
Derived2
jeweils einen Member
member4
hätten, mit jeweils unterschiedlichem Typ. Dann kann man mit dem
union
das auseinanderhalten, muss aber einen auf die Klasse getemplateten Getter für
member4
schreiben.
Das sind, wie gesagt, Varianten gegen die _Kot-Explosion_. Die zugrundliegende Datenstruktur sieht bei allen gleich aus.
Nun zu den drei Code-Beispielen.
>[1. Code-Beispiel]
>
Dazu die C-Anmerkung: Ohne
union
darf man das nicht, denn die "common initial sequence" für Zeiger auf Objekte, die nicht mit den zugrundeliegenden Objekt übereinstimmen, gilt nur für
union
s. Darüber hinaus verstößt es gegen die strict-aliasing-Rule, da man nun für
arr[i]
zwei Objekte (eines nur temporär) unterschiedlichen Typs hat, womit man nicht mehr mittels
*
oder
->
dereferenzieren darf, wie im Kot gemacht. Du hast aber gesagt, dass das nur Beispielcode für eine mögliche Umsetzung sein soll, deshalb hackt Felix darauf nicht weiter rum.
>Also in deinem Fall wäre die naheliegenste Lösung folgende gewesen:
Das klappt in dem einfachen Beispiel gut. Aber: Sobald die
for
-Schleife nicht mehr in der gleichen Funktion wie die Array-Definition liegt, läuft man wieder in den Fall wie oben rein. Damit wurde das Problem nur verschoben.
Und in einen solchen Fall kann man schnell kommen. Kaum macht man um die Schleife drumrum etwas Komplexeres, oder man will an einer anderen Stelle die gleiche Berechnung durchführen, refaktorisiert man die Schleife raus in eine Funktion. Dann muss man sich bereits fragen, welchen Parameter diese Funktion kriegen soll.
Base *
? Dann kann der Benutzer kein
Derived1
-Array übergeben.
Derived1 *
? Was ist, wenn der Benutzer aber ein
Derived2
-Array hat? Man ist wieder an der gleichen Stelle wie zuvor.
Der Aufrufer, der auch schon mal viele Ebenen drüber im Callstack stehen kann, muss dann wissen und mitteilen, welcher Typ ganz unten im Callstack, in der innersten Berechnungsschleife, zu verwenden sein soll. Das wurde in deinem zweiten Kot-Beispiel auch erkannt: Die Information, die man mein Array-Iterieren über den Typ braucht, nämlich die Größe, wird mit
member_size
runtergereicht.
Das Problem, nämlich das Runterreichen der Information, ist leider auch genau das, was je nach Lösung zur Kot-Explosion führt.
Wenn man nicht alle Funktionen verdoppeln will, muss man dann wohl in der Praxis zu so etwas wie Typdurchreichungen im C++-Template-Style greifen.
template <typename T>
int diff(T * a, T * b)
{
return b->parent.member1 - a->parent.member1;
}
template <typename T>
int ProcessArray(T * arr, size_t n)
{
int sum = 0;
for(size_t i = 0; i < n - 1; i++)
sum += diff(&arr[i], &arr[i+1]);
return sum;
}
int main(int argc, char ** argv)
{
size_t n = 8;
Derived1 * arr = CreateDerived1Array(n);
InitializeDerived1Array(arr, n);
int sum = ProcessArray(arr, n);
printf("%d\n", sum);
DestroyDerived1Array(arr);
return 0;
}
Und da hat man dann das Problem: Wenn
ProcessBaseArray
und
ProcessDerived1Array
zu einer Funktion zusammenfassen will, wie es bei Polymorphie der Fall ist, kann man sich nicht in der Parameterliste einfach für
Base *
entscheiden, weil man dann beim gleichen Problem wie oben ist. D.h. man hat dann wieder das gleiche Problem - nur eben bei
ProcessArray
, statt bei
diff
. Man hat damit das Problem nur verschoben.
>Stell dir vor, der Compiler ist schlau genug, das zu inlinen.
Stell dir vor, der Compiler macht es nicht, weil er es nicht durchschaut (vgl. Video unten, wo es nicht geinlined wurde).
>[2. Code-Beispiel]
>Es gäbe aber auch noch andere Möglichkeiten. Z.B. könntest du der Funktion einfach die Größe des Datentyps als weiteren Parameter übergeben:
Da würde in C erst mal das gleiche bzgl. der strict-aliasing-Rule gelten, dabei dann sogar explizit mit
arr + i
,
a
,
arr + (i + 1)
,
b
. Wieder hackt Felix nicht weiter darauf rum.
Die Größe des Datentyps zu übergeben, ist eine sehr gute Lösung, die Felix auch schon dabei in den Sinn gekommen war und Felix so natürlich von einigen APIs kennt (Klassiker: Man übergibt Null-Zeiger und Zeiger auf Größe und kriegt Größe zurück, man übergibt Nicht-Null-Zeiger mit Größe und Array wird befüllt). Felix hatte oben etwas von "bei Sprachen ohne Kompilierung: zur Allokationszeit" geschrieben, aber das kann man so natürlich auch bei kompilierten Sprachen machen. Geht auch zur Vermeidung der Kot-Explosion mit der
union
-Variante von Felix, siehe oben.
Zunächst zu dem, was Felix auch schon zum 1. Code-Beispiel geschrieben hat: Der Aufrufer, der auch schon mal viele Ebenen drüber im Callstack stehen kann, muss dann wissen und mitteilen, welcher Typ ganz unten im Callstack, in der innersten Berechnungsschleife, zu verwenden sein soll. Das ist hierbei einfach, weil wegen der Definition von
arr
im gleichen Scope das
sizeof(arr[0])
richtig ist. Das gilt aber nicht, wenn man das Array per
Base *
übergibt und dann den
sizeof
nimmt. Man muss von Allokation der Objekte im Array bis zur
for
-Schleife das
member_size
durchreichen, so wie man im ersten Beispiel den richtigen Typ durchreichen muss. Falscher Typ führt zu Undefined Behavior, falsches
member_size
führt zu Undefined Behavior.
Aber: Auch die Lösung bietet keine O(1)-Schreibzugriff mit anderem Typ - und zwar einem anderem Typ, dessen Größe erst bekannt wird, nachdem man das Array bereits befüllt hat. Das ist jedoch gerade die Erweiterbarkeit bei Vererbung im OOP-Stil: Man hat bereits ein gefülltes Array, und nun kommt noch ein Typ mit einer anderen Größe zur Vererbungshierarchie, und das Element soll mitten ins gefüllte Array geschrieben werden (und natürlich alles O(1) halten).
Deswegen hatte Felix geschrieben
>sei es der O(1)-Zugriff
weil man dann beim _Schreiben_ ins Array keinen O(1)-Schreibzugriff mehr hat, sondern erst das Array umstrukturieren muss. Und wenn dann andere Stellen im Kot keine Array-Indizes von dem Array gespeichert haben, sondern direkt Zeiger aufs Array, müssen alle diese Zeiger umgebogen werden, was ein großer Aufwand und fehleranfällig ist.
Das mit dem Schreibzugriff war natürlich auch für die Sprach-Implementierer relevant, weil die genau nicht wissen, ob der Sprach-Benutzer dann plötzlich nach der Initialisierung (was bereits ein Schreibzugriff ist) nochmal ins Array schreibt.
Das gleiche Problem gibt es auch bei Felixens
union
-Lösung, weshalb die Erweiterbarkeit bei Vererbung im OOP-Stil bei Felix unerfüllt gelassen wurde, und bei deiner Lösung auch.
Wenn das nicht vorkommt, kann man das genauso machen, wie von dir oder auch mir beschrieben. Wenn man wahlfreie Schreibzugriffe mit einem neuen, größeren Typ hat, hat man ein Problem. So langsam sollte es dämmern, warum eine solche OOP-Erweiterbarkeit in der Praxis gerade fast nie auftaucht.
Was man stattdessen sehr viel häufiger hat: Man hat eine Bibliothek, und die wird einmal geladen, und mehr Typen kommen nach der Lade-Zeit nicht mehr hinzu. Wenn man einmal die kernel32.dll geladen hat, will man nicht noch eine zweite kernel32.dll laden. Ladezeitpunkt der Bibliothek ist fast immer der Ladezeitpunkt des Programms. Dann holt man sich einmal zu Programmstart die (Maximal-)Größe von der Bibliothek und man kann damit seine Arrays erstellen und mit Objekten der Bibliothek befüllen. Das ist gerade weniger als der OOP-Stil, bei dem jederzeit weitere Bibliotheken hinzukommen können, Plugin-System-Style.
>[3. Code-Beispiel]
>Also eigentlich hast du das Polymorphismus-Problem immer noch nicht gelöst. Könntest du aber beispielsweise so lösen:
Ob das damit "nicht gelöst" ist, ist debattierbar. Aber bzgl. des Kots: Wieder keine O(1)-Schreibzugriffe. Wenn man als Funktionalität nur Hinzufügen zum Ende vom Array/Entfernen vom Ende vom Array braucht, und nicht mitten drin reinspeichern muss, klappt das vollkommen.
(Felix hat auch mal auf Godbolt bzgl. der Kot-Generierung geschaut, wenig überraschend schafft der Kompiler erst mal das Endergebnis komplett durchzurechnen und auf eine Konstante zu reduzieren. Wenn man die Array-Größe variabel macht, sieht der Kot für die Variante ohne
member_size
besser aus, weniger Berechnungen in der heißen Schleife. Aber Felix wird darauf nicht rumhacken, weil Beispielkot.)