Entwurfsmuster für rekursive Klassen: Optionen und bewährte Praktiken

Question

Sehr geehrte Damen und Herren, ich danke Ihnen im Voraus für Ihre Zeit.

Kürzlich habe ich beschlossen, Objective-C zu lernen (ich bin ein langjähriger C-Hacker) und nach dem Lesen des schönen Textes von Kochan und dem Eintauchen in die Apple-Dokumentation bin ich immer noch verwirrt, wie man am besten eine rekursive Klasse implementiert (d. h. eine Klasse, in der ein ivar den Typ von der gleichen Klasse hat). Nehmen wir einmal an, wir wollen eine Binärbaumklasse implementieren. Zunächst haben wir eine grundlegende Knotenklasse, die ich vereinfacht habe:

@interface MMNode : NSObject {
    NSString *label;
}

---

Jetzt können wir unseren Baum auf zwei verschiedene Arten implementieren. Die erste (und meines Erachtens die naheliegendere) ist, die Rekursion in der Klasse selbst zu platzieren.

@interface MMTree : NSObject {
    MMNode *root;
    MMTree *leftTree;
    MMTree *rightTree;
}
@property (nonatomic, copy) MMNode *root;
@property (nonatomic, retain) MMTree *leftTree;
@property (nonatomic, retain) MMTree *rightTree;

---

Die zweite Methode, die in der wunderbaren CHDataStructures.framework implementiert diese Datenstruktur wie folgt:

typedef struct MMTreeNode {
    MMNode *node;
//  union { 
//      struct { 
            struct MMTreeNode *leftTree;
            struct MMTreeNode *rightTree;
//      };
//  };
} MMTreeNode;

@interface MMTreeStruct : NSObject {
    MMTreeNode *root;
}

Hier ist die Lösung eher "pointer-riffic", wobei die Rekursion in die die Struktur verschoben. (Wie in den Kommentaren erwähnt, sind die anonymen Strukturen und Unions nicht erforderlich. Da jedoch viele Anwendungen zusätzliche Informationen zusätzliche Informationen an jedem Knoten benötigen, werde ich den Code so lassen, wie er ist).

---

Ich habe beide Lösungen implementiert und sie funktionieren gut. Die erste scheint einfacher, mehr "OO"; die zweite, mehr "C-zentrisch" mit etwas komplizierteren Quellen.

Ist die letztere Technik vorzuziehen? Wenn ja, was ist ein objektiver Grund? Ich kann nur feststellen, dass letzteres vielleicht speicherfreundlicher ist, da die Struktur eine feste Größe hat.

Nochmals vielen Dank an StackOverflow und an die CocoaHeads.

UPDATE: Ich sollte hinzufügen, dass es scheint, dass das CoreFoundation-Objekt CFTree verwendet eine ähnliche Strukturimplementierung.

Answer 1

Als Autor von CHDataStructures.framework kann ich hoffentlich einen kleinen Einblick geben :-)

Meine Faustregel ist, Objekte zu verwenden, es sei denn, es gibt einen nachweisbaren Grund, Structs zu verwenden.

Da ich Datenstrukturen auf niedriger Ebene implementiere, habe ich mich für eine Struktur anstelle eines Objekts entschieden, vor allem aus Leistungsgründen. Objekte benötigen nicht nur etwas mehr Speicher pro Instanz, sondern es entsteht auch ein gewisser Overhead beim Aufruf von Methoden. Dies wird gemildert, wenn das Objekt nur Instanzvariablen hat, die als @public deklariert sind, aber man muss immer noch alloc/init durchführen, und Objective-C-Objektvariablen sind mit Nullen gefüllt, während Structs das nicht sind, es sei denn, man verwendet calloc() .

Ein Vorteil von Objective-C-Objekten gegenüber Structs ist die automatische Integration in die Garbage Collection (10.5+), während man bei C-Speicher einige Hürden überwinden muss, um denselben Vorteil zu erhalten. Ich stimme Ihnen zu, dass die Speicherverwaltung mit Objekten für Cocoa-Entwickler vertrauter (und offensichtlicher) ist. Deshalb verwende ich Klassen als Schnittstelle und Structs für die Speicherung.

Nota: Die anonyme Union und die Struktur in Ihrem zweiten Codebeispiel sind für diese spezielle Situation irrelevant. Ich verwende sie nur, um schlankere und dennoch lesbare Algorithmen für binäre Suchbäume schreiben zu können. (Einzelheiten unter http://dysart.cs.byu.edu/CHDataStructures/struct_c_h_binary_tree_node.html ) Ich habe sie auskommentiert, um hoffentlich zu vermeiden, dass sie den Gelegenheitsleser verwirren, aber sie bleiben als Referenz für die Zukunft erhalten.