Data Structures in Swift - Part 1
Introduction
Why Data Structures?
Data structures are containers that hold data used in our programs. The efficiency of these data structures affects our software as a whole. Therefore, it is crucial that we understand the structurers available for us to use and that we choose the correct ones for our various tasks.
Structure
This is the first part of a two-part series on data structures in Swift.
In this tutorial, we’re going to talk about generics and the built-in Swift collection types. In the second part, we’ll take a look at some of the most popular data structures and how they can be implemented in Swift.
Generics
Generics are the means for writing useful and reusable code. They are also used to implement flexible data structures that are not constrained to a single data type.
Generics stand at the core of the Swift standard library. They are so deeply rooted in the language that you cannot and should not ignore them. In fact, after a while, you won’t even notice that you’re using generics.
Why do we need generics?
To illustrate the problem, let’s try to solve a simple problem: create types which hold pairs of different values.
A naive attempt might look like this:
1struct StringPair {
2 var first: String
3 var second: String
4}
5
6struct IntPair {
7 var first: Int
8 var second: Int
9}
10
11struct FloatPair {
12 var first: Float
13 var second: Float
14}Now, what if we need a type which holds pairs of Data instances? No problem, we’ll create a DataPair structure!
1struct DataPair {
2 var first: Data
3 var second: Data
4}And a type which holds different types, say a String and a Double? Here you go:
1struct StringDoublePair {
2 var first: String
3 var second: Double
4}We can now use our newly created types:
1let pair = StringPair(first: "First", second: "Second")
2print(pair)
3// StringPair(first: "First", second: “Second")
4
5let numberPair = IntPair(first: 1, second: 2)
6print(numberPair)
7// IntPair(first: 1, second: 2)
8
9let stringDoublePair = StringDoublePair(first: "First", second: 42.5)
10print(stringDoublePair)
11// StringDoublePair(first: "First", second: 42.5)Is this really the way to go? Definitely not! We must stop the type explosion before it gets out of hand.
Generic Types
Wouldn’t it be cool to have just one type which can work with any value? How about this:
1struct Pair<T1, T2> {
2 var first: T1
3 var second: T2
4}We arrived at a generic solution which can be used with any type.
Instead of providing the concrete types of the properties in the structure, we use placeholders: T1 and T2.
We can simply call our struct Pair because we don’t have to specify the supported types in the name of our structure.
Now we can write:
1let floatFloatPair = Pair<Float, Float>(first: 0.3, second: 0.5)
2print(floatFloatPair)
3// Pair<Float, Float>(first: 0.300000012, second: 0.5)We can even skip the placeholder types because the compiler is smart enough to figure out the type based on the arguments. (Type inference works by examining the provided values while compiling the code.)
1let stringAndString = Pair(first: "First String", second: "Second String")
2print(stringAndString)
3// Pair<String, String>(first: "First String", second: "Second String")
4
5let stringAndDouble = Pair(first: "I'm a String", second: 99.99)
6print(stringAndDouble)
7// Pair<String, Double>(first: "I\'m a String", second: 99.989999999999995)
8
9let intAndDate = Pair(first: 42, second: Date())
10print(intAndDate)
11// Pair<Int, Date>(first: 42, second: 2017-08-15 19:02:13 +0000)In Swift, we can define our generic classes, structures, or enumerations just as easily.
Swift Collection Types
Swift has some primary collection types to get us going. Let’s get a closer look at the built-in Array, Set, and Dictionary types.
Arrays
Arrays store values of the same type in a specific order. The values must not be unique: each value can appear multiple times. Swift implements arrays - and all other collection types - as generic types. They can store any type: instances of classes, structs, enumerations, or any built-in type like Int, Float, Double, etc.
Creating Arrays
We create an array using the following syntax:
1let numbers: Array<Int> = [0, 2, 1, 3, 1, 42]
2print(numbers)
3// Output: [0, 2, 1, 3, 1, 42]You can also use the shorthand form [Type] - this is the preferred form by the way:
1let numbers1: [Int] = [0, 2, 1, 3, 1, 42]Providing the type of the elements is optional: we can also rely on Swift’s type inference to work out the type of the array:
1let numbers = [0, 2, 1, 3, 1, 42]A zero-based index identifies the position of each element. We can iterate through the array and print the indices using the Array index(of:) instance method:
1for value in numbers {
2 if let index = numbers.index(of: value) {
3 print("Index of \(value) is \(index)")
4 }
5}The output will be:
1Index of 0 is 0
2Index of 2 is 1
3Index of 1 is 2
4Index of 3 is 3
5Index of 1 is 2
6Index of 42 is 5We can also iterate through the array using the forEach(_:) method. This method executes its closure on each element in the same order as a for-in loop:
1numbers.forEach { value in
2 if let index = numbers.index(of: value) {
3 print("Index of \(value) is \(index)")
4 }
5}Mutable Arrays
If we want to modify the array after its creation, we must assign it to a variable rather than a constant.
1var mutableNumbers = [0, 2, 1, 3, 1, 42]Then, we can use various Array instance methods like for example append(_:) or insert(_:at:) to add new values to the array.
1mutableNumbers.append(11)
2print(mutableNumbers)
3// Output: [0, 2, 1, 3, 1, 42, 11]
4
5mutableNumbers.insert(100, at: 2)
6print(mutableNumbers)
7// Output: [0, 2, 100, 1, 3, 1, 42, 11]If you use insert(at:) make sure that the index is valid, otherwise you’ll end up in a runtime error.
To remove elements from an array, we can use the remove(at:) method:
1mutableNumbers.remove(at: 2)
2print(mutableNumbers)
3// Output: [0, 2, 1, 3, 1, 42, 11]Again, if the index is invalid, a runtime error occurs. The gap is closed whenever we remove elements from the array.
To remove all the elements, call removeAll():
1mutableNumbers.removeAll()
2print(mutableNumbers)
3// Output: []I’ve mentioned some of the most frequently used Array methods. There are plenty of other methods that you can use; check out the documentation or simply start experimenting with them in a Swift playground.
Arrays store values of the same type in an ordered sequence. Use Arrays if the order of the elements is important and if the same values shall appear multiple times.
If the order or repetition of elements does not matter, you can use a set instead.
Sets
There are two fundamental differences between a set and an array:
- the set provides no defined ordering
- a value can only appear once in a set
The Set exposes useful methods that let us combine two sets using mathematical set operations like union and subtract. Let’s get started with the basic syntax for set creation.
Creating Sets
We can declare a Set using the following syntax:
1let uniqueNumbers: Set<Int> = [0, 2, 1, 3, 42]
2print(uniqueNumbers)
3// Output: [42, 2, 0, 1, 3]Note that we can’t use the shorthand form as we did for arrays. Swift’s type inference engine could not tell whether we want to instantiate a Set rather than an array if we defined it like this:
1let uniqueNumbers = [0, 2, 1, 3, 42] // this will create an Array of Int valuesWe must specify that we need a Set; however, type inference will still work for the values used in the Set. So, we can write the following:
1let uniqueNumbers: Set = [0, 2, 1, 3, 42] // creates a Set of Int valuesLet’s take a look at this example:
1let zeroes: Set<Int> = [0, 0, 0, 0]
2print(zeroes)Can you guess the output?
This is what we’ll see in the console: [0]
The set will allow only one out of the four zeroes. Whereas if we use an array, we get all our zeroes:
1let zeroesArray: Array<Int> = [0, 0, 0, 0]
2print(zeroesArray)
3// Output: [0, 0, 0, 0]Be careful when choosing the collection type, as they serve different purposes.
We can use the for-in loop or the forEach() method:
1let uniqueNumbers: Set = [0, 2, 1, 3, 42]
2for value in uniqueNumbers {
3 print(value)
4}
5
6uniqueNumbers.forEach { value in
7 print(value)
8}Hashable Values
A set cannot have duplicates. In order to check for duplicates, the set must be of a type that has a way to tell whether two instances are equal.
Swift uses a hash value for this purpose. The hash value is a unique value of type Int, which must be equal if two values are the same. In most languages, various object types have functions that produce a hashcode which determines equality. Swift’s basic built-in types are hashable. So, we can use String, Bool, Int, Float or Double values in a set.
However, if we want to use custom types, we must implement the Hashable protocol.
Hashable conformance means that your type must implement a read-only property called hashValue of type Int.
Also, because Hashable conforms to Equatable, you must also implement the equality (==) operator.
1struct MyStruct: Hashable {
2 var id: String
3
4 public var hashValue: Int {
5 return id.hashValue
6 }
7
8 public static func ==(lhs: MyStruct, rhs: MyStruct) -> Bool {
9 return lhs.id == rhs.id
10 }
11}Now we can instantiate our Set of MyStruct elements and the compiler won’t complain anymore:
1let setWithCustomType = Set<MyStruct>()Mutable Sets
We can create mutable sets by assigning the set to a variable.
1var mutableStringSet: Set = ["One", "Two", "Three"]
print(mutableStringSet)
// Output: ["One", "Three", "Two"]We can add new elements to the set via the insert() Set instance method:
1mutableStringSet.insert("Four")
print(mutableStringSet)
// Output: ["Three", "Two", "Four", "One"]To remove elements from a set, we can call the remove() method:
1mutableStringSet.remove("Three")
2print(mutableStringSet)
3// Output: ["Two", "Four", "One"]If the element we are about to remove is not in the list, the remove method has no effect:
1mutableStringSet.remove("Ten")
2print(mutableStringSet)
3// Output: ["Two", "Four", “One"]The remove() method returns the element that was removed from the list. We can use this feature to check whether the value was indeed deleted:
1if let removedElement = mutableStringSet.remove("Ten") {
2 print("\(removedElement) was removed from the Set")
3} else {
4 print("\"Ten\" not found in the Set")
5}To remove all the elements in the set call removeAll():
1mutableStringSet.removeAll()
2print(mutableStringSet)
3// Output: []Alternatively, we could check whether the element exists using the contains() Set instance method:
1if mutableStringSet.contains("Ten") {
2 mutableStringSet.remove("Ten")
3}
4print(mutableStringSet)Set Operations
We can use the following Set operations to combine two sets into a new one:
- Union - Creates a new set with all of the elements in the two sets. If the same element exists in both sets, only one instance will appear in the resulting set.
1let primeNumbers: Set = [11, 13, 17, 19, 23]
2let oddNumbers: Set = [11, 13, 15, 17]
3
4let union = primeNumbers.union(oddNumbers)
5print( union.sorted() )
6// Output: [11, 13, 15, 17, 19, 23]
7
8[11, 13, 17, 19, 23] ∪ [11, 13, 15, 17] = [11, 13, 13, 15, 17, 17, 19, 23]
9
10//After removing the duplicates, the result is [11, 13, 15, 17, 19, 23]- Intersect - The result of calling the
intersection()Set instance method is a set which holds the elements that appear in both sets.
1let intersection = primeNumbers.intersection(oddNumbers)
print(intersection.sorted)
// Output: [11, 13, 17]
2
3[11, 13, 17, 19, 23] ∩ [11, 13, 15, 17] = [11, 13, 17]- Symmetric Difference - After invoking the symmetricDifference() method, the resulting set will contain elements that are only in either set, but not both.
1let symmetricDiff = primeNumbers.symmetricDifference(oddNumbers)
2print(symmetricDiff.sorted)
3// Output: [15, 19, 23]
4
5[11, 13, 17, 19, 23] ∆ [11, 13, 15, 17] = [15, 19, 23]- Subtract - The result will contain those values which are only in the source set and not in the subtracted set. This output is known as the set difference.
1[11, 13, 17, 19, 23] ∖ [11, 13, 15, 17] = [19, 23]
2let subtractOddFromPrimes = primeNumbers.subtracting(oddNumbers)
3print(subtractOddFromPrimes)
4// Output: [19, 23]
5
6[11, 13, 15, 17] ∖ [11, 13, 17, 19, 23] = [15]
7let subtractPrimesFromOdds = oddNumbers.subtracting(primeNumbers)
8print(subtractPrimesFromOdds)
9// Output: [15]Set Membership Methods
The Set exposes methods to test for equality and membership:
- == - tests whether the values contained in both sets are all the same
- isSubset(of:) - checks whether the values from a set are contained in the other set
- isStrictSubset(of:) - returns true if the other set contains all the values from the set, but the sets are not equal
- isSuperset(of:) - checks whether the set contains all the values from the other set
- isStrictSuperset(of:) - checks whether the set has all the elements contained in the other set, but the sets are not equal
- isDisjoint(with:) - call to find out whether the two sets have no elements in common
Examples:
1let numbers: Set = [0, 1, 2, 3, 4, 5]
2let otherNumbers: Set = [5, 4, 3, 2, 1, 0]
3
4if numbers == otherNumbers {
5 print("\(numbers) and \(otherNumbers) contain the same values")
6}
7// Prints: [4, 5, 2, 0, 1, 3] and [5, 0, 2, 4, 3, 1] contain the same values
8
9let oddNumbers: Set = [1, 3, 5]
10if oddNumbers.isSubset(of: numbers) {
11 print("\(oddNumbers.sorted()) is subset of \(numbers.sorted())")
12}
13// Prints: [1, 3, 5] is subset of [0, 1, 2, 3, 4, 5]
14
15if numbers.isSuperset(of: oddNumbers) {
16 print("\(numbers.sorted()) is superset of \(oddNumbers.sorted())")
17}
18// Prints: [0, 1, 2, 3, 4, 5] is superset of [1, 3, 5]
19
20let primeNumbers: Set = [2, 3, 5]
21let otherPrimeNumbers: Set = [11, 13, 17]
22
23if primeNumbers.isDisjoint(with: otherPrimeNumbers) {
24 print("\(primeNumbers.sorted()) has no values in common with \(otherPrimeNumbers.sorted())")
25}
26// Prints: [11, 13, 17, 19, 23] has no values in common with [11, 13, 17]We discussed some of the most important capabilities of Sets. Hopefully this knowledge will make it easier to choose between a Set and an Array.
Dictionaries
Dictionaries - also known as hash maps - store key-value pairs and allow for efficient setting and reading of values based on their unique identifiers. Just like the other Swift collection types, the Dictionary is also implemented as a generic type, meaning that it can take on any data type.
Creating Dictionaries
To create a dictionary, we must specify the key and the value type.
- Using the initializer syntax
1var numbersDictionary = Dictionary<Int, String>()- Using the shorthand syntax
1var numbersDictionary = [Int: String]()- Using dictionary literals Swift can infer the type of the keys and the values based on the literals
1var numbersDictionary = [0: "Zero", 1: "One", 10: "Ten"]Heterogeneous Dictionaries
When creating a dictionary, the types of the keys and the values is supposed to be consistent - e.g., all keys are of type Int and all the values are of type String.
Type inference won't work if the type of the dictionary literals is not consistent.
However, there are cases when we do need dictionaries with different key and value types. For instance, when converting JSON payloads or property lists, a typed dictionary won't work.
Alright, let’s try the following:
1var mixedMap: [Any: Any] = [0: “Zero”, "pi": 3.14]Now, the compiler complains about something else: "Type 'Any' does not conform to protocol 'Hashable'"
The problem is that the Dictionary requires keys that are hashable - just like the values used in a Set.
AnyHashable
Starting with Swift 3, the standard library introduced a new type called AnyHashable. It can hold a value of any type conforming to the Hashable protocol.
AnyHashable can be used as the supertype for keys in heterogeneous dictionaries.
So, we can create a heterogeneous collection like this:
1var mixedMap: [AnyHashable: Any] = [0: "Zero", 1: 1.0, "pi": 3.14]AnyHashable is a structure which lets us create a type-erased hashable value that wraps the given instance. This is what happens behind the scenes:
1var mixedMap = [AnyHashable(0): "Zero" as Any, AnyHashable(1): 1.0 as Any, AnyHashable("pi"): 3.14 as Any]Actually, this version would compile just fine if we typed in Xcode - but the shorthand syntax is obviously more readable.
AnyHashable’s base property represents the wrapped value. It can be cast back to the original type using the as, as? or as! cast operators.
1let piWrapped = AnyHashable("pi")
2let piWrapped = AnyHashable("pi")
3if let unwrappedPi = piWrapped.base as? String {
4 print(unwrappedPi)
5}Accessing and Modifying the Contents of a Dictionary
We can access the value stored in a dictionary associated with a given key using the subscript syntax:
1var numbersDictionary = [0: "Zero", 1: "One", 10: "Ten"]
2if let ten = numbersDictionary[10] {
3 print(ten)
4}
5// Output: TenWe can also iterate over the key-value pairs of a dictionary using a for-in loop. Since it’s a dictionary, items are returned as a key-value touple:
1for (key, value) in numbersDictionary {
2 print("\(key): \(value)")
3}We can access the dictionary's key property to retrieve its keys:
1for key in numbersDictionary.keys {
2 print(key)
3}The value property will return the values stored in the dictionary:
1for value in numbersDictionary.values {
2 print(value)
3}To add a new item to the dictionary, use a new key as the subscript index, and assign it a new value:
1numbersDictionary[2] = "Two"
2print(numbersDictionary)
3// Prints: [10: "Ten", 2: "Two", 0: "Zero", 1: "One"]To update an existing item, use the subscript syntax with an existing key:
1numbersDictionary[2] = "Twoo"
2print(numbersDictionary)
3// Prints: [10: "Ten", 2: "Twoo", 0: "Zero", 1: "One"]You can remove a value by assigning nil for its key:
1numbersDictionary[1] = nil
2print(numbersDictionary)
3// Prints: [10: "Ten", 2: "Two", 0: "Zero"]You can achieve the same result - with a little more typing - using the removeValue(forKey:) instance method:
1numbersDictionary.removeValue(forKey: 2)
2print(numbersDictionary4)
3// Prints: [10: "Ten", 0: "Zero"]Finally, removeAll() empties our dictionary without remorse:
1numbersDictionary.removeAll()
2print(numbersDictionary)
3// Output: [:]Conclusion
In this tutorial, we've covered the built-in Swift collection types.
Stay tuned for Data Structures in Swift Part 2. We’re going to talk about some popular data structures and we’ll implement them in Swift from scratch. Hopefully this will help you pick the correct data structure when the time comes!
In the meantime, you may want to check out my Swift courses on Pluralsight.
Thanks for reading and Happy Coding!