Collection Data Structures in Swift

Dictionaries

Dictionaries are a way of storing values that don’t need to be in any particular order and are uniquely associated with keys. You use the key to store or look up a value.

Dictionaries also use subscripting syntax, so when you write dictionary["hello"], you’ll get the value associated with the key hello.

Like arrays, Swift dictionaries are immutable if you declare them with let and mutable if you declare them with var. Similarly on the Foundation side, there are both NSDictionary and NSMutableDictionary classes for you to use.

Another characteristic that is similar to Swift arrays is that dictionaries are strongly typed, and you must have known key and value types. NSDictionary objects are able to take any NSObject as a key and store any object as a value.

You’ll see this in action when you call a Cocoa API that takes or returns an NSDictionary. From Swift, this type appears as [NSObject: AnyObject]. This indicates that the key must be an NSObject subclass, and the value can be any Swift-compatible object.

When to use Dictionaries

Chaplin still knows when to use dictionaries. Do you?

Chaplin still knows when to use dictionaries. Do you?

Dictionaries are best used when there isn’t a particular order to what you need to store, but the data has meaningful association.

To help you examine how dictionaries and other data structures in the rest of this tutorial work, create a Playground by going to File…\New\Playground, and name it DataStructures.

For example, pretend you need to store a data structure of all your friends and the names of their cats, so you can look up the cat’s name using your friend’s name. This way, you don’t have to remember the cat’s name to stay in that friend’s good graces.

First, you’d want to store the dictionary of people and cats. Add the following to the playground:

import Foundation

let cats = [ "Ellen" : "Chaplin", "Lilia" : "George Michael", "Rose" : "Friend", "Bettina" : "Pai Mei"]

Thanks to Swift type inference, this will be defined as [String: String] — a dictionary with string keys and string values.

Now try to access items within it. Add the following:

cats["Ellen"] //returns Chaplin as an optional
cats["Steve"] //Returns nil

Note that subscripting syntax on dictionaries returns an optional. If the dictionary doesn’t contain a value for a particular key, the optional is nil; if it does contain a value for that key you get the wrapped value.

Because of that, it’s a good idea to use the if let optional-unwrapping syntax to access values in a dictionary. Add the following:

if let ellensCat = cats["Ellen"] {
    print("Ellen's cat is named \(ellensCat).")
} else {
    print("Ellen's cat's name not found!")
}

Since there is a value for the key “Ellen”, this will print out “Ellen’s cat is named Chaplin” in your Playground.

Expected Performance

Once again, Apple outlines the expected performance of dictionaries in Cocoa in the CFDictionary.h header file:

1. The performance degradation of getting a single value is guaranteed to be at worst O(log n), but will often be O(1).
2. Insertion and deletion can be as bad as O(n (log n)), but typically be closer to O(1) because of under-the-hood optimizations.

These aren’t quite as obvious as the array degradations. Due to the more complex nature of storing keys and values versus a lovely ordered array, the performance characteristics are harder to explain.

Sample App Testing Results

DictionaryManipulator is a similar protocol to ArrayManipulator, and it tests dictionaries. With it, you can easily test the same operation using a Swift Dictionary or an NSMutableDictionary.

To compare the Swift and Cocoa dictionaries, use a similar procedure as you used for the arrays. Build and run the app and select the Dictionary tab at the bottom.

Run a few tests – you’ll notice that dictionaries take significantly longer to create than arrays. If you push the item slider up to 10,000,000 items, you might even be able to get a memory warning or even an out-of-memory crash!

Back in Xcode, open DictionaryViewController.swift and find the dictionaryManipulator property:

let dictionaryManipulator: DictionaryManipulator = SwiftDictionaryManipulator()

Replace it with the following:

let dictionaryManipulator: DictionaryManipulator = NSDictionaryManipulator()

Now the app will use NSDictionary under the hood. Build and run the app again, and run a few more tests. If you’re running Swift 2.1.1, your findings should be similar to the results of more extensive testing:

• In raw time, creating Swift dictionaries is roughly 6 times faster than creating NSMutableDictionaries but both degrade at roughly the same O(n) rate.
• Adding items to Swift dictionaries is roughly 100 times faster than adding them to NSMutableDictionaries in raw time, and both degrade close to the best-case-scenario O(1) rate promised by Apple’s documentation.
• Removing items from Swift dictionaries is roughly 8 times faster than removing items from NSMutableDictionaries, but the degradation of performance is again close to O(1) for both types.
• Swift is also faster at lookup, with both performing roughly at an O(1) rate. This version of Swift is the first where it beats Foundation by a significant amount.

These are amazing improvements over Swift 2.3 where both types of dictionaries performed roughly the same.

Swift 3.0 has implemented substantial improvements to dictionaries.

And now, on to the final major data structure used in iOS: Sets!

Sets

A set is a data structure that stores unordered, unique values. Unique is the key word; you won’t won’t be able to add a duplicate.

Swift sets are type-specific, so all the items in a Swift Set must be of the same type.

Swift added support for a native Set structure in version 1.2 – for earlier versions of Swift, you could only access Foundation’s NSSet.

Note that like arrays and dictionaries, a native Swift Set is immutable if you declare it with let and mutable if you declare it with var. Once again on the Foundation side, there are both NSSet and NSMutableSet classes for you to use.

When to use Sets

Sets are most useful when uniqueness matters, but order does not. For example, what if you wanted to select four random names out of an array of eight names, with no duplicates?

Enter the following into your Playground:

let names = ["John", "Paul", "George", "Ringo", "Mick", "Keith", "Charlie", "Ronnie"]
var stringSet = Set<String>() // 1
var loopsCount = 0
while stringSet.count < 4 {
    let randomNumber = arc4random_uniform(UInt32(names.count)) // 2
    let randomName = names[Int(randomNumber)] // 3
    print(randomName) // 4
    stringSet.insert(randomName) // 5
    loopsCount += 1 // 6
}

// 7
print("Loops: " + loopsCount.description + ", Set contents: " + stringSet.description)

In this little code snippet, you do the following:

1. Initialize the set so you can add objects to it. It is a set containing String objects.
2. Pick a random number between 0 and the count of names.
3. Grab the name at the selected index.
4. Log the selected name to the console.
5. Add the selected name to the mutable set. Remember, if the name is already in the set, then the set won't change since it doesn't store duplicates.
6. Increment the loop counter so you can see how many times the loop ran.
7. Once the loop finishes, print out the loop counter and the contents of the mutable set.

Since this example uses a random number generator, you'll get a different result every time. Here's an example of the log produced while writing this tutorial:

John
Ringo
John
Ronnie
Ronnie
George
Loops: 6, Set contents: ["Ronnie", "John", "Ringo", "George"]

Here, the loop ran six times in order to get four unique names. It selected Ronnie and John twice, but they only wound up in the set once.

As you're writing the loop in the Playground, you'll notice that it runs on a, well, loop, and you'll get a different number of loops each time. In this case, you'll need at least four loops, since there must always be four items in the set to break out of the loop.

Now that you've seen Set at work on a small scale, it's time to examine performance with a larger batch.