问题标签 [chdatastructures]

为了帮助简化 Xcode 调试器窗口中一些自定义 Objective-C 对象的调试，我使用相关的 Apple 文档和 Xcode 的内置数据格式化程序作为指南，为每个对象创建了一组数据格式化程序字符串。

如果我将自定义摘要字符串与 Xcode 附带的数据格式化程序一起放在/Developer/Library/Xcode/CustomDataViews/中，我的自定义摘要字符串会很好用。但是，我宁愿不这样做，因为用户可能没有对该目录的写入权限，并且将自定义格式化程序与内置格式化程序混合可能会造成混淆。同样，将我自己的条目添加到~/Library/Application Support/Apple/Developer Tools/CustomDataViews/CustomDataViews.plist也可以，但是该文件用于覆盖默认值的用户定义值，并且它的条目被Xcode 调试器 GUI。我真正想要的是能够将带有我的数据格式化程序的文件放在一个位置，以便 Xcode 识别它们，但如果需要，用户仍然可以选择性地覆盖我的设置（在另一个文件中）。

问题是，当我创建一个包（按照这个 Apple 示例代码的示例）并安装它（在/Developer/Library/Xcode/CustomDataViews/或任何Library/Application Support/Apple/Developer Tools/CustomDataViews/路径中） , Xcode 无法识别或使用自定义格式化程序。

关于数据格式化程序包细节的文档有点少（主要是Xcode.app/Contents/PlugIns/GDBMIDebugging.xcplugin中的单个头文件），可能是因为该功能不是 Xcode 的主要功能之一。;-） 任何帮助将不胜感激。

注意：虽然我的特定上下文是 Objective-C，但我的问题实际上超越了编程语言的选择。此外，我将其标记为“主观”，因为否则肯定有人会抱怨，但我个人认为这几乎完全是客观的。另外，我知道这个相关的 SO question，但由于这是一个更大的问题，我认为最好将其作为一个单独的问题。请不要在没有完全阅读和理解的情况下批评这个问题。谢谢！

我们大多数人都熟悉存储键值关联的字典抽象数据类型，根据我们选择的语言，我们是否将其称为映射、字典、关联数组、哈希等。字典的简单定义可以概括为三个属性：

1. 通过键访问值（而不是通过索引，如数组）。
2. 每个键都与一个值相关联。
3. 每个键必须是唯一的。

任何其他属性都可以说是针对特定目的的便利或专业化。例如，某些语言（尤其是 PHP 和 Python 等脚本语言）模糊了字典和数组之间的界限，并且确实为字典提供了排序。尽管这很有用，但这样的添加并不是字典的基本特征。在纯粹意义上，字典的实际实现细节是无关紧要的。

对于我的问题，最重要的观察是未定义枚举键的顺序- 字典可以以它认为最方便的任何顺序提供键，并且由客户根据需要组织它们。

我创建了强制特定键排序的自定义字典，包括自然排序顺序（基于对象比较）和插入顺序。很明显，将前者命名为SortedDictionary上的某个变体（我实际上已经实现了），但后者的问题更大。我见过LinkedHashMap和LinkedMap (Java)、OrderedDictionary (.NET)、OrderedDictionary (Flash)、OrderedDict (Python) 和OrderedDictionary (Objective-C)。其中一些更成熟，一些更概念验证。

LinkedHashMap是根据 Java 集合传统中的实现来命名的——“linked”是因为它使用双向链表来跟踪插入顺序，而“hash”是因为它是 HashMap 的子类。除了用户不需要担心这一点之外，类名甚至没有真正表明它的作用。使用有序似乎是现有代码之间的共识，但关于这个主题的网络搜索也揭示了“有序”和“排序”之间的可以理解的混淆，我也有同感。.NET 实现甚至对明显的误称有评论，并建议它应该改为“IndexedDictionary”，因为您可以在排序的特定点检索和插入对象。

我正在设计一个框架和 API，我想尽可能智能地命名这个类。从我的角度来看，索引可能会起作用（取决于人们如何解释它，并基于字典的广告功能），排序不精确并且有太多混淆的可能性，并且链接“是正确的”（向 Monty Python 道歉）。;-)

作为用户，什么名称对您来说最有意义？是否有一个特定的名称可以准确地说明该类的功能？（如果合适的话，我不反对使用稍长一些的名称，例如 InsertionOrderDictionary。）

编辑：另一个很大的可能性（在我下面的回答中讨论）是IndexedDictionary。我不太喜欢“插入顺序”，因为如果您允许用户在特定索引处插入键、重新排序键等，这没有任何意义。

注意：以下 SO 问题是相关的，但它们和链接的资源似乎都没有完全回答我的问题，特别是与实现对象集合的相等测试有关。

• 覆盖 -isEqual: 和 -hash 的最佳实践
• 在可变 Cocoa 对象上实现 -hash 的技术

背景

NSObject 提供（返回实例的地址，如）和（除非接收者的地址和参数的地址相同，否则返回）的默认实现。这些方法被设计为在必要时被覆盖，但文档清楚地表明您应该提供两者或都不提供。此外，如果返回两个对象，则这些对象的结果必须相同。如果不是，那么当应该相同的对象（例如返回的两个字符串实例）被添加到 Cocoa 集合或直接比较时，就会出现问题。-hash(NSUInteger)self-isEqual:NO-isEqual:YES-hash-compare:NSOrderedSame

语境

我开发了 CHDataStructures.framework，这是一个 Objective-C 数据结构的开源库。我已经实现了许多集合，目前正在改进和增强它们的功能。我想添加的功能之一是能够将集合与另一个集合进行比较。

这些比较应该考虑两个集合中存在的对象（包括排序，如果适用），而不是只比较内存地址。这种方式在Cocoa中有相当的先例，一般采用单独的方式，包括以下几种：

• -[NSArray isEqualToArray:]
• -[NSDate isEqualToDate:]
• -[NSDictionary isEqualToDictionary:]
• -[NSNumber isEqualToNumber:]
• -[NSSet isEqualToSet:]
• -[NSString isEqualToString:]
• -[NSValue isEqualToValue:]

我想让我的自定义集合对相等性测试具有鲁棒性，因此它们可以安全地（并且可预测地）添加到其他集合中，并允许其他集合（如 NSSet）确定两个集合是否相等/等价/重复。

问题

一个-isEqualTo...:方法本身就可以很好地工作，但是如果参数与接收者属于同一类（或者可能是子类），或者其他情况下，定义这些方法的类通常也会覆盖-isEqual:以调用。这意味着该类还必须定义为，它将为具有相同内容的不同实例返回相同的值。[self isEqualTo...:][super isEqual:]-hash

此外，Apple 的文档-hash规定如下：（强调我的）

“如果将可变对象添加到使用哈希值确定对象在集合中的位置的集合中，则该对象的哈希方法返回的值在对象在集合中时不得更改。因此，无论是哈希方法不得依赖任何对象的内部状态信息，或者您必须确保对象在集合中时对象的内部状态信息不会改变。因此，例如，可以将可变字典放入哈希表中，但您必须当它在那里时不要更改它。（请注意，很难知道给定对象是否在集合中。）“

编辑： 我完全理解为什么这是必要的，并且完全同意这个推理——我在这里提到它是为了提供额外的背景，并为了简洁而避开了为什么会这样的话题。

我所有的集合都是可变的，并且哈希必须至少考虑一些内容，所以这里唯一的选择是认为改变存储在另一个集合中的集合是一个编程错误。（我的收藏都采用了NSCopying，所以像 NSDictionary 这样的收藏可以成功地制作副本作为密钥等）

-isEqual:实现and对我来说是有意义的-hash，因为（例如）我的一个类的间接用户可能不知道-isEqualTo...:要调用的具体方法，甚至不关心两个对象是否是同一个类的实例。他们应该能够调用-isEqual:或调用-hash任何类型的变量id并获得预期的结果。

与-isEqual:（可以访问被比较的两个实例）不同，-hash必须“盲目地”返回结果，只能访问特定实例中的数据。由于它无法知道哈希的用途，因此对于所有应该被视为相等/相同的可能实例，结果必须一致，并且必须始终与-isEqual:. （编辑：这已经被下面的答案揭穿了，它确实让生活更轻松。）此外，编写好的散列函数并非易事——保证唯一性是一个挑战，尤其是当你只有一个 NSUInteger（32/64 位）时在其中代表它。

问题

1. 为集合实施相等比较 时是否有最佳实践？-hash
2. 在 Objective-C 和 Cocoa 风格的集合中是否有任何特殊需要计划？
3. -hash是否有任何具有合理置信度的单元测试的好方法？
4. 关于实施-hash以同意-isEqual:包含任意类型元素的集合的任何建议？我应该知道哪些陷阱？（编辑：不像我最初想的那样有问题——正如@kperryua指出的那样，“相等的-hash值并不意味着-isEqual:”。）

编辑： 我应该澄清一下，我对如何实现 -isEqual: 或 -isEqualTo...: 对于集合并不感到困惑，这很简单。我认为我的困惑主要源于（错误地）认为如果 -isEqual: 返回 NO，则 -hash 必须返回不同的值。过去做过密码学，我认为不同值的散列必须不同。然而，下面的答案让我意识到一个“好的”散列函数实际上是关于最小化桶冲突和链接使用-hash. 虽然唯一的哈希是可取的，但它们并不是严格的要求。

我是 iPhone 编程的新手，我正在尝试在我的项目中使用CHDataStructures。但我遇到了一些问题：

1. 当我在下载后直接尝试构建它时，我收到错误“Foundation/Foundation.h”没有这样的文件或目录。Active SDK 是“Use Base SDK”，活动架构是 x86_64。我相信我应该将 Active SDK 设置为 iPhone SDK，但它没有在那里列出；

2. 在某些时候（我不记得如何）我设法对其进行了调整，并且在活动 SDK 中获得了 iPhone SDK（模拟器），但是当我尝试构建它时，出现以下错误：“目标指定产品类型 'com. apple.product-type.framework'，但 'iphonesimulator' 平台没有这样的产品类型”；

现在我被困住了。我究竟做错了什么？

在此先感谢，努诺

我下载了CHDataStructures源代码（r709），尝试在xCode 4下编译iOS静态库，编译时报错：

谁能给我一些想法如何编译它？

我需要一个优先级队列，我猜在框架中，CHMutableArrayHeap 和 CHBinaryHeap 可以完成这项工作，对吧？

但是，如果我将具有相同优先级的对象发送到队列，CHMutableArrayHeap 和 CHBinaryHeap 都无法维持它们的添加顺序。

例如，我有对象 obj1 到 obj10，它们的优先级是相同的。我把这10个对象从1到10一个一个加入队列后，它们的位置和加入顺序不一样，obj4可能排在obj1前面。

那么，Quinn，如果我想要一个优先级队列来保持添加顺序，如果优先级相同，你有什么建议？

谢谢

我想使用CHDataStructures作为框架：https ://github.com/davedelong/CHDataStructures 。但是，该项目没有二进制文件。

所以我假设我必须使用 xcode 自己构建 .a 文件。我如何在 xcode 4 中做到这一点？我阅读了文档，但它非常混乱......

有任何想法吗？

对于我的游戏 iOS 项目，我需要一个环形缓冲区。它的工作方式应该类似于元素出入的队列，但缓冲区中的元素总数应该保持不变。

我使用java成功实现了环形缓冲区，但我对objective-c不太熟悉。我在网上找到了一个名为 CHCircularBuffer 的环形缓冲区实现：https ://bitbucket.org/devartum/chdatastructures/src/4d6d7194ee94/source/CHCircularBuffer.m但是我未能正确实现它。

循环缓冲区是一个名为TerrainManager的类的属性，它执行所有数学地形生成。

这是在 TerrainManager 的实现中如何初始化环形缓冲区

这将创建缓冲区的一个实例并将 size 属性设置为部件。现在我使用 addObject 方法将对象添加到缓冲区：

有时这一行会收到错误“exec_bad_access”。例如，当我初始化容量为 15 的缓冲区时，一切都很好，而 20 则出现错误。

我现在尝试从进行绘图的地形类访问缓冲区。但每当我尝试访问对象时，我都会收到“bad_access”错误。

例如，这一行会产生错误。

所以我的代码有问题。也许我不理解缓冲区并以错误的方式添加对象。我不知道。有什么想法或建议吗？

在很长很长时间（20 多年）没有编程之后，我正试图重新开始。我的第一次真正尝试是拼字游戏/Words With Friends 求解器/作弊器（选择你的定义）。我已经构建了一个非常好的引擎，但它通过蛮力而不是效率或优雅来解决问题。经过大量研究，很明显，这个问题的最佳答案是 DAWG 或 CDWAG。我在那里找到了一些 C 实现并且能够利用它们（对于相同的数据集，搜索时间从 1.5 秒变为 0.005 秒）。

但是，我试图弄清楚如何在纯 Objective-C 中做到这一点。在那，我也在努力使其符合ARC。并且对于 iPhone 来说足够高效。我看了很多，发现了几个数据结构库（即CHDataStructures），但它们大多是 C/Objective-C 混合体，或者它们不符合 ARC。它们非常依赖结构并将对象嵌入到结构中。ARC并不真正关心这一点。

所以 - 我的问题是（对不起，我明白这是否是 tl;博士，如果这似乎完全是一个新问题 - 只是无法理解这个对象的东西）你如何编程经典数据结构（树等）在 Objective-C 中从头开始？我不想依赖 NS[Mutable]{Array,Set,etc}。有没有人有一个简单/基本的树或类似的东西，我可以在创建我的 DAWG 时使用？

我正在尝试在我的 Xcode 项目中使用 iPhone 的CHDataStructures静态库。我将它包含# import "CHDataStructures.h"在我的班级标题中。但是，当我编译我的项目时，我得到了错误：

d：在 /Users/sam/Desktop/Apps/libCHDataStructures.a(Util.o) 和 /Users/sam/Desktop/Apps/build/Apps.build/Debug-iphonesimulator/Apps.build/Objects-normal 中重复符号 _kCHPointerSize /i386/AppsAppDelegate.o collect2: ld 返回 1 退出状态命令 /Developer/Platforms/iPhoneSimulator.platform/Developer/usr/bin/g++-4.2 失败，退出代码为 1

我正在使用 GCC-4.2 编译器，并且我也尝试过 LLVM GCC 4.2。我还尝试在构建设置中设置 、 和标志，但它没有-ObjC编译-all_build。-force_build我还尝试清理目标，并确保目标二进制文件中是否包含静态库。但我无法弄清楚问题所在。任何人都可以帮忙吗？