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

Question

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

objective-cdesign-patternsrecursionclass-design

5

亲爱的各位：提前感谢您的时间。

最近，我决定学习Objective-C（我是长期的C语言黑客），在阅读Kochan的精美文本并深入研究苹果文档后，我仍然困惑于实现递归类的最佳方法（即一个具有相同类类型的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使用了类似的结构实现。

- SplittingField

CFTree不需要是“二进制”的。您可以在此处查看源代码http://www.opensource.apple.com/source/CF/CF-635/CFTree.c。很抱歉在这里问，有人能告诉我CFTree的目的是什么，不能使用NSDictionary和NSArray完成吗？ - Tatvamasi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Quinn Taylor · Accepted Answer

作为CHDataStructures.framework的作者，希望我可以提供一点见解。:-)

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

因为我正在实现低级数据结构，所以我选择使用结构体而不是对象，主要是出于性能考虑。对象每个实例需要更多的内存，而调用方法也需要一些开销。如果对象只有公共实例变量声明为@public，则这些开销会得到缓解，但仍然必须进行alloc/init，并且Objective-C对象变量会被零填充，而结构体则不会，除非您使用了calloc()。

Objective-C对象比结构体具有的一个优势是自动与垃圾回收（10.5+）集成，而原始C内存必须跳过一些障碍才能获得相同的好处。我同意你的看法，即对象的内存管理对Cocoa开发人员来说更加熟悉（和明显）。这就是为什么我将类用作接口，而将结构体用于存储。

请注意：第二个代码示例中的匿名联合和结构体在这种情况下是多余的。我只使用它们使编写更简洁但易读的二叉搜索树算法成为可能。（详细信息请参见http://dysart.cs.byu.edu/CHDataStructures/struct_c_h_binary_tree_node.html）我将它们注释掉，以避免混淆普通读者，但它们仍然适用于将来的参考。