What is the most efficient way to sort an NSSet?

Question

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

Solution 4

NSSet is a collection of unordered objects. Looking at apple references Arrays are ordered collections.

Looking at NSArray there is a discussion with examples of sorting at http://developer.apple.com/documentation/Cocoa/Conceptual/Collections/Articles/sortingFilteringArrays ...

Example from the link:

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];

View more solutions

Comments

[Quinn Taylor]

This is not much different that the asker's suggestion, and probably roughly equivalent in speed since -allObjects returns an autoreleased NSArray, and -sortedArrayUsingDescriptors: returns a separate NSArray (both are immutable). The cost of allocating two arrays is not much less than enumerating all elements in a (moderate size) set, and requires twice as much space.

[Quinn Taylor]

Wow, that particular Apple sample code is pretty terrible. Why are they using void*, NSInteger, and int where it's simpler to use a BOOL? Why would it return NSInteger instead of NSComparisonResult? I'm sure it's for compatibility with previous API decisions, but that's frickin' ugly! I suggest using a selector (method) rather than a function for sorting Cocoa collections — it's simpler and more elegant.

[Austin]

It is good to note that sortedArrayUsingDescriptors: is a 10.6 only method. If you're targeting 10.5 or before you may want to try @QuinnTaylor's approach

[DonnaLea]

NSSet also has a sortedArrayUsingDescriptors method, so you could skip the call to allObjects and simply call [mySet sortedArrayUsingDescriptors:descriptors];

[cobbal]

@DonnaLea That does seem to be the best way to do it, but it didn't exist back when the question was asked. Updated answer, thanks.

[DiscDev]

This may be obvious, but note that sortedArrayUsingDescriptors takes an array of descriptors and not just a single descriptor. [mySet sortedArrayUsingDescriptors:[NSArray arrayWithObject:[NSSortDescriptor sortDescriptorWithKey:@"name" ascending:YES]]];

[Nico]

@QuinnTaylor I just checked and, sure enough, the documentation for sortedArrayUsingFunction:context: says that the function is expected to take two ids and a void * and return an NSInteger. In that, at least, the sample is correct. (They seem to have updated it, too—it sucks less now.)

[micnguyen]

And to add onto DiscDev's answer, remember the NSArray short @[], so you can do: [mySet sortedArrayUsingDescriptors:@[[NSSortDescriptor sortDescriptorWithKey:@"name" ascending:YES]]];

[colincameron]

This doesn't address the question, where you've got an existing NSSet and want to sort it.

[Jageen]

More important NSOrderedSet does not mean sorted NSSet.