什么是对NSSet进行排序的最有效方法？

Question

如何在NSSet/NSMutableSet中根据对象的属性对对象进行高效排序？目前我的做法是遍历每个对象，将它们添加到NSMutableArray中，并使用NSSortDescriptor对该数组进行排序。

- Boon

Answer 1

尝试使用

[[mySet allObjects] sortedArrayUsingDescriptors:descriptors];

编辑: 对于 iOS ≥ 4.0 和 Mac OS X ≥ 10.6，你可以直接使用。

[mySet sortedArrayUsingDescriptors:descriptors];

- cobbal

---

这与提问者的建议并没有太大区别，而且在速度上可能差不多，因为-allObjects返回一个自动释放的NSArray，而-sortedArrayUsingDescriptors:返回一个单独的NSArray（两者都是不可变的）。分配两个数组的成本几乎不比枚举（中等大小的）集合中的所有元素少，并且需要两倍的空间。 - Quinn Taylor

需要注意的是，sortedArrayUsingDescriptors: 是一个只能在10.6及以上版本中使用的方法。如果你的目标系统是10.5或更早版本，你可能需要尝试@QuinnTaylor的方法。 - Austin

NSSet也有一个sortedArrayUsingDescriptors方法，因此您可以跳过对allObjects的调用，直接调用[mySet sortedArrayUsingDescriptors：descriptors]； - DonnaLea

@DonnaLea，这似乎是最好的方法，但在提问时它并不存在。感谢更新答案。 - cobbal

这可能很明显，但请注意，sortedArrayUsingDescriptors需要一个描述符数组，而不仅仅是单个描述符。[mySet sortedArrayUsingDescriptors:[NSArray arrayWithObject:[NSSortDescriptor sortDescriptorWithKey:@"name" ascending:YES]]]; - DiscDev

补充DiscDev的答案，记得NSArray的简写是@[]，所以你可以这样做：[mySet sortedArrayUsingDescriptors:@[[NSSortDescriptor sortDescriptorWithKey:@"name" ascending:YES]]]; - micnguyen

Answer 2

“最有效的方式”来对一组对象进行排序取决于你实际的需求。通常的假设（之前的答案已经提到）是对一组对象进行一次排序。在这种情况下，我认为 @cobbal 建议的方法和你提出的方法差不多，可能类似于以下内容：

NSMutableArray* array = [NSMutableArray arrayWithCapacity:[set count]];
for (id anObject in set)
    [array addObject:anObject];
[array sortUsingDescriptors:descriptors];

我认为这是一个抉择，因为@cobbal的方法会创建两个自动释放的数组，所以内存占用量会增加一倍。对于少量对象来说，这并不重要，但从技术上讲，这两种方法都不太高效。

然而，如果你需要多次对集合中的元素进行排序（尤其是经常性地），这绝对不是一种高效的方法。你可以保留一个NSMutableArray，并将其与NSSet同步，然后每次调用-sortUsingDescriptors:方法，但即使数组已经排序，它仍需要N次比较。

Cocoa本身并没有提供一种有效的方式来维护有序集合。Java有一个TreeSet类，每当插入或删除对象时，都会按照排序顺序维护元素，但Cocoa没有。正是这个问题促使我开发了类似的东西供自己使用。

作为我继承和改进的数据结构框架的一部分，我创建了一个protocol和一些实现来维护有序集合。任何具体的子类都将维护一个按排序顺序排列的不同对象集合。仍有待完善之处——首要问题是它基于- compare:的结果进行排序（集合中的每个对象都必须实现），还不能接受NSSortDescriptor。（解决方法是实现- compare：以比较对象上感兴趣的属性。）

一个可能的缺点是这些类（目前）不是NS（Mutable）Set的子类，因此如果您必须传递一个NSSet，它将无序。（该协议确实有一个-set方法，返回一个无序的NSSet。）我计划很快纠正这一点，就像我在框架中对NSMutableDictionary子类所做的那样。欢迎反馈。 :-)

- Quinn Taylor

Answer 3

对于 iOS ≥ 5.0 和 Mac OS X ≥ 10.7，您可以直接使用 NSOrderedSet。

- bioffe

---

这并没有解决问题，如果你已经有一个现有的 NSSet 并想要对其进行排序。 - colincameron

更重要的是，NSOrderedSet并不意味着NSSet已经排序。 - Jageen

Answer 4

NSSet是一个无序对象的集合。根据苹果公司的参考文献，数组是有序的集合。

查看NSArray，其中有一些讨论和示例可以进行排序，具体请参见http://developer.apple.com/documentation/Cocoa/Conceptual/Collections/Articles/sortingFilteringArrays ...

以下是来自链接的示例：

NSInteger alphabeticSort(id string1, id string2, void *reverse)
{
    if (*(BOOL *)reverse == YES) {
        return [string2 localizedCaseInsensitiveCompare:string1];
    }
    return [string1 localizedCaseInsensitiveCompare:string2];
}

---

// assuming anArray is array of unsorted strings

NSArray *sortedArray;

// sort using a selector
sortedArray =
    [anArray sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];

// sort using a function
BOOL reverseSort = NO;
sortedArray =
    [anArray sortedArrayUsingFunction:alphabeticSort context:&reverseSort];

- stefanB

---

哇，那个苹果的示例代码真的很糟糕。他们为什么要使用void*、NSInteger和int，而不是更简单的BOOL？为什么会返回NSInteger而不是NSComparisonResult呢？我知道这可能是为了与之前的API决策兼容，但那真的是丑爆了！我建议在对Cocoa集合进行排序时使用选择器（方法）而不是函数——这样更简单、更优雅。 - Quinn Taylor

@QuinnTaylor 我刚刚检查了一下，sortedArrayUsingFunction:context: 的文档确实说该函数应该接受两个 id 和一个 void *，并返回一个 NSInteger。至少在这方面，示例是正确的。（他们似乎也更新了它，现在看起来好多了。） - Peter Hosey

Answer 5

你不能对 NSSet 进行排序，因为 "sortedArrayUsingFunction:" 方法返回的是 NSArray 类型的结果... 而且所有的上述提示都只适用于 Array :)

NSArray *myArray = [mySet sortedArrayUsingDescriptors:descriptors];

工作得很完美，不需要其他方法 :)

- iTux

Answer 6

自从OS X 10.7和iOS 5.0以来，就有了NSOrderedSet。您可以使用它来保留集合中的对象并保持它们的顺序。NSMutableOrderedSet具有排序方法。在某些情况下，这可能会提高性能，因为您不必像NSArray一样创建单独的对象来存储排序后的项目。

- Andriy