Collection Data Structures in Swift

Sample App Testing Results

Apple didn't outline overall expectations for set performance as they did for dictionaries and arrays, so in this case you'll just look at real-world performance.

The Swift Set documentation outlines performance characteristics for a couple of methods, but NSMutableSet does not.

The sample project has NSSetManipulator and SwiftSetManipulator objects in the SetViewController class similar to the setup in the array and dictionary view controllers, and can be swapped out the same way.

In both cases, if you're looking for pure speed, using a Set probably won't make you happy. Compare the numbers on Set and NSMutableSet to the numbers for Array and NSMutableArray, and you'll see set creation is considerably slower -- that's the price you pay for checking if every single item in a data structure is unique.

Detailed testing revealed that since Swift's Set shows that performance degradation and raw time for most operations is extremely similar to that of NSSet: Creation, removal, and lookup operations are all similar between Foundation and Swift in raw time. However, it is faster in Swift for the first time.

Creation degrades for both Swift and Foundation set types at a rate of around O(n). This is expected because every single item in the set must be checked for equality before a new item may be added. When requiring a data structure for a large sample size, a Set's initial creation time cost will be a major consideration.

Removing and looking up actions are both around O(1) performance degradations across Swift and Foundation, making set lookup considerably faster than array lookup. This is largely because set structures use hashes to check for equality, and the hashes can be calculated and stored in sorted order.

Overall, it appears that adding an object to an NSSet stays near O(1), whereas it can degrade at a rate higher than O(n) with Swift's Set structure.

Swift has seen very significant performance improvements in collection data structure performance in its short public life, and will hopefully continue to see them as Swift evolves.

Lesser-known Foundation Data Structures

Arrays, dictionaries and sets are the workhorses of data-handling. However, Cocoa offers a number of lesser-known and perhaps under-appreciated collection types. If a dictionary, array or set won't do the job, it's worth checking if one of these will work before you create something from scratch.

NSCache

Using NSCache is very similar to using NSMutableDictionary – you just add and retrieve objects by key. The difference is that NSCache is designed for temporary storage for things that you can always recalculate or regenerate. If available memory gets low, NSCache might remove some objects. They are thread-safe, but Apple's documentation warns:

…The cache may decide to automatically mutate itself asynchronously behind the scenes if it is called to free up memory.

This means that an NSCache is like an NSMutableDictionary, except that Foundation may automatically remove an object at any time to relieve memory pressure. This is good for managing how much memory the cache uses, but can cause issues if you rely on an object that may potentially be removed.

NSCache also stores weak references to keys rather than strong references.

NSCountedSet

NSCountedSet tracks how many times you've added an object to a mutable set. It inherits from NSMutableSet, so if you try to add the same object again it will only be reflected once in the set.

However, an NSCountedSet tracks how many times an object has been added. You can see how many times an object was added with countForObject().

Note that when you call count on an NSCountedSet, it only returns the count of unique objects, not the number of times all objects were added to the set.

To illustrate, at the end of your Playground take the array of names you created in your earlier NSMutableSet testing and add each one to an NSCountedSet twice:

let countedMutable = NSCountedSet()
for name in names {
    countedMutable.add(name)
    countedMutable.add(name)
}

Then, log out of the set itself and find out how many times "Ringo" was added:

let ringos = countedMutable.count(for: "Ringo")
print("Counted Mutable set: \(countedMutable)) with count for Ringo: \(ringos)")

Your log should read:

Counted Mutable set: {(
    George,
    John,
    Ronnie,
    Mick,
    Keith,
    Charlie,
    Paul,
    Ringo
)}) with count for Ringo: 2

Note that while you may see a different order for the set, you should only see "Ringo" appear in the list of names once, even though you can see that it was added twice.

NSOrderedSet

An NSOrderedSet along with its mutable counterpart, NSMutableOrderedSet, is a data structure that allows you to store a group of distinct objects in a specific order.

"Specific order" -- gee, that sounds an awful lot like an array, doesn't it? Apple succinctly sums up why you'd want to use an NSOrderedSet instead of an array (emphasis mine):

You can use ordered sets as an alternative to arrays when element order matters and performance while testing whether an object is contained in the set is a consideration -- testing for membership of an array is slower than testing for membership of a set.

Because of this, the ideal time to use an NSOrderedSet is when you need to store an ordered collection of objects that cannot contain duplicates.

NSHashTable and NSMapTable

Not this kind of Map Table. (Courtesy the Tennessee Valley Authority(!) via Flickr Creative Commons)

NSHashTable is another data structure that is similar to Set, but with a few key differences from NSMutableSet.

You can set up an NSHashTable using any arbitrary pointers and not just objects, so you can add structures and other non-object items to an NSHashTable. You can also set memory management and equality comparison terms explicitly using NSHashTableOptions enum.

NSMapTable is a dictionary-like data structure, but with similar behaviors to NSHashTable when it comes to memory management.

Like an NSCache, an NSMapTable can hold weak references to keys. However, it can also remove the object related to that key automatically whenever the key is deallocated. These options can be set from the NSMapTableOptions enum.