对NSSet的排序包装器

Question

我需要从一个NSSet数据源中填充UITableView，很明显我希望按一些标准对表进行排序。

我可以简单地使用[mySet sortedArrayUsing...]创建已排序的NSArray并将其用作我的表数据源。但是我需要更强大的功能：底层的NSSet（mySet）会随着时间的推移而改变，我希望UITableView相应地更新（当然仍然是排好序的）。

目前最好的办法是将观察器附加到NSSet上，并每次NSSet发生更改时刷新NSArray和UITableView。这涉及到相当多的代码，效率也不高。

因此，我想要的东西可能是这样的：

NSArray* sortedWrapperArray = [SortedWrapper wrapperFor:mySet sortUsing:sortCriteria];

当底层集合发生变化时，sortedWrapperArray 会自动更新。

在 Objective-C/Cocoa 的世界中是否有类似的东西呢？

- henning77

Answer 1

如果您的基础集合是NSSet，则每次集合更改时都必须从头开始进行排序，花费O(N*Log(N))的时间。我认为处理这个问题的一种更有效的方法是用NSMutableArray替换NSSet，并通过插入来保持其排序。在排序数组中添加和删除元素仍然是O(N)：虽然您可以使用二进制搜索（参见indexOfObject:inSortedRange:options:usingComparator:方法）找到位置，但插入/删除通常是O(N)（尽管常数非常低）。维护集合的唯一性属性也很容易：如果二进制搜索找到要插入的相同元素，则跳过插入。相同值检查需要O(Log(N))

- Sergey Kalinichenko

---

你说在排序数组中添加和删除元素是 O(log n)，你确定吗？-[NSMutableArray insertObject:atIndex:] 真的是 O(1) 吗？ - v1Axvw

@Ief2 你说得完全正确 - 成本将由需要将数据向上或向下移动数组来主导。我已经修正了答案，非常感谢！ - Sergey Kalinichenko

dasblinkenlight 我无法将 NSSet 更改为 NSMutableArray，因为我从具有固定接口的底层组件获取了 NSSet。所以我想我需要一种高效的 NSSet 封装器。 - henning77

我仍然喜欢你的想法，因为我可以将它融入我的解决方案中，我会将观察者附加到NSSet上。这些观察者将使用你的方法来更新NSMutableArray。 - henning77

Answer 2

如果您的应用程序仅在iOS 5.0或更高版本上运行，您可以使用NSOrderedSet

- bioffe

---

这是一个不错的方法，因为NSOrderedSet提供了一个叫做-array的方法，它返回一个代理数组，该数组会在后台排序集合被改变时不断更新。 - Mark Adams

这个与“-array”方法结合的功能正是我正在寻找的。谢谢！ - henning77

问题要求排序，而不是按插入顺序排序。 - user102008