What is the most efficient way to sort an NSSet?

What's the most efficient way to sort objects in an NSSet/NSMutableSet based on a property of the objects in the set? Right now the way I am doing it is by iterating through each object, add them to a NSMutableArray, and sort that array with NSSortDescriptor.

Solution 1:

try using

[[mySet allObjects] sortedArrayUsingDescriptors:descriptors];

Edit: For iOS ≥ 4.0 and Mac OS X ≥ 10.6 you can directly use

[mySet sortedArrayUsingDescriptors:descriptors];

Solution 2:

The "most efficient way" to sort a set of objects varies based on what you actually mean. The casual assumption (which the previous answers make) is a one-time sort of objects in a set. In this case, I'd say it's pretty much a toss-up between what @cobbal suggests and what you came up with — probably something like the following:

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

(I say it's a toss-up because @cobbal's approach creates two autoreleased arrays, so the memory footprint doubles. This is inconsequential for small sets of objects, but technically, neither approach is very efficient.)

However, if you're sorting the elements in the set more than once (and especially if it's a regular thing) this is definitely not an efficient approach. You could keep an NSMutableArray around and keep it synchronized with the NSSet, then call -sortUsingDescriptors: each time, but even if the array is already sorted it will still require N comparisons.

Cocoa by itself just doesn't provide an efficient approach for maintaining a collection in sorted order. Java has a TreeSet class which maintains the elements in sorted order whenever an object is inserted or removed, but Cocoa does not. It was precisely this problem that drove me to develop something similar for my own use.

As part of a data structures framework I inherited and revamped, I created a protocol and a few implementations for sorted sets. Any of the concrete subclasses will maintain a set of distinct objects in sorted order. There are still refinements to be made — the foremost being that it sorts based on the result of -compare: (which each object in the set must implement) and doesn't yet accept an NSSortDescriptor. (A workaround is to implement -compare: to compare the property of interest on the objects.)

One possible drawback is that these classes are (currently) not subclasses of NS(Mutable)Set, so if you must pass an NSSet, it won't be ordered. (The protocol does have a -set method which returns an NSSet, which is of course unordered.) I plan to rectify that soon, as I've done with the NSMutableDictionary subclasses in the framework. Feedback is definitely welcome. :-)

Solution 3:

For iOS ≥ 5.0 and Mac OS X ≥ 10.7 you can directly use NSOrderedSet