递归类设计模式：选项和最佳实践

Question

亲爱的大家： 提前，感谢您的时间。

最近，我决定学习 Objective-C（我是 C-hacker 的老手），在阅读了 Kochan 优美的文字并深入研究 Apple 文档后，我仍然对实现递归类的最佳方法感到困惑（即. 一个类，其中 ivar 具有相同类的类型）。为了具体起见，假设我们希望实现一个二叉树类。首先，我们有一个基本的节点类，我已将其简化为：

@interface MMNode : NSObject {
    NSString *label;
}

---

现在我们可以用两种不同的方式实现我们的树。第一个（也是我认为更明显的方法）是将递归放在类本身中。

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

---

第二种方法，在美妙的CHDataStructures.framework 中使用，实现这个数据结构如下：

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


@interface MMTreeStruct : NSObject {
    MMTreeNode *root;
}

这里的解决方案更“指针重复”，将递归推入结构中。（正如评论中提到的，匿名结构和联合不是必需的。但是，由于许多应用程序需要每个节点的附加信息，我将保留代码原样）。

---

我已经实施了这两种解决方案，并且它们运行良好。前者看起来更直白，更“OO”；后者更“以 C 为中心”，来源稍微复杂一些。

后一种技术是首选吗？如果有，客观原因是什么？我所能确定的可能是后者对内存更友好，因为结构具有固定大小。

再次感谢 StackOverflow 和 CocoaHeads。

更新： 我应该补充一点，CoreFoundation 对象CFTree似乎 使用了类似的结构实现。

Answer 1

作为 CHDataStructures.framework 的作者，希望我能补充一点。:-)

我的经验法则是使用对象，除非有明显的理由使用结构。

由于我正在实现低级数据结构，我选择使用结构而不是对象，主要是出于性能原因。对象不仅每个实例需要更多的内存，而且调用方法也有一些开销。如果对象只有声明为@public 的实例变量，这会得到缓解，但您仍然必须分配/初始化，并且Objective-C 对象变量是零填充的，而结构则不是，除非您使用calloc().

Objective-C 对象相对于结构的一个优势是自动与垃圾收集 (10.5+) 集成，而原始 C 内存必须跳过几个环节才能获得相同的好处。我同意您的观点，Cocoa 开发人员更熟悉（和明显）对象的内存管理。这就是为什么我使用类作为接口，使用结构作为存储。

注意：第二个代码示例中的匿名联合和结构对于这种特殊情况是无关紧要的。我使用它们只是为了让编写更精简但更易读的二叉搜索树算法成为可能。（详情见http://dysart.cs.byu.edu/CHDataStructures/struct_c_h_binary_tree_node.html）我将它们注释掉，希望避免让普通读者感到困惑，但它们仍供将来参考。