3. Swift Standard Library

Written by Kelvin Lau

The Swift standard library is the framework that contains the core components of the Swift language. Inside, you’ll find a variety of tools and types to help build your Swift apps. Before you start building your own custom data structures, it is important to understand the primary data structures that the Swift standard library already provides.

In this chapter, you’ll focus on the three main data structures that the standard library provides right out of the box: Array, Dictionary, and Set.

Array

An array is a general-purpose, generic container for storing an ordered collection of elements, and it is used commonly in all sorts of Swift programs. You can create an array by using an array literal, which is a comma-separated list of values surrounded with square brackets. For example:

let people = ["Brian", "Stanley", "Ringo"]

Swift defines arrays using protocols. Each of these protocols layers more capabilities on the array. For example, an Array is a Sequence, which means that you can iterate through it at least once. It is also a Collection, which means it can be traversed multiple times, non-destructively, and it can be accessed using a subscript operator. An array is also a RandomAccessCollection, which makes guarantees about efficiency.

The Swift Array is known as a generic collection, because it can work with any type. In fact, most of the Swift standard library is built with generic code.

As with any data structure, there are certain notable traits that you should be aware of. The first of these is the notion of order.

Order

Elements in an array are explicitly ordered. Using the above people array as an example, "Brian" comes before "Stanley".

All elements in an array have a corresponding zero-based, integer index. For example, the people array from the above example has three indices, one corresponding to each element. You can retrieve the value of an element in the array by writing the following:

people[0] // "Brian"
people[1] // "Stanley"
people[2] // "Ringo"

Order is defined by the array data structure and should not be taken for granted. Some data structures, such as Dictionary, have a weaker concept of order.

Random-access

Random-access is a trait that data structures can claim if they can handle element retrieval in a constant amount of time. For example, getting "Ringo" from the people array takes constant time. Again, this performance should not be taken for granted. Other data structures such as linked lists and trees do not have constant time access.

Array performance

Aside from being a random-access collection, there are other areas of performance that are of interest to you as a developer, particularly, how well or poorly does the data structure fare when the amount of data it contains needs to grow? For arrays, this varies on two factors.

Insertion location

The first factor is one in which you choose to insert the new element inside the array. The most efficient scenario for adding an element to an array is to append it at the end of the array:

people.append("Charles")
print(people) // prints ["Brian", "Stanley", "Ringo", "Charles"]

Inserting "Charles" using the append method will place the string at the end of the array. This is a constant-time operation, meaning the time it takes to perform this operation stays the same no matter how large the array becomes. However, there may come a time that you need to insert an element in a particular location, such as in the very middle of the array.

To help illustrate why that is the case, consider the following analogy. You’re standing in line for the theater. Someone new comes along to join the lineup. What’s the easiest place to add people to the lineup? At the end, of course!

If the newcomer tried to insert himself into the middle of the line, he would have to convince half the lineup to shuffle back to make room.

And if he were terribly rude, he’d try to insert himself at the head of the line. This is the worst-case scenario, because every single person in the lineup would need to shuffle back to make room for this new person in front!

This is exactly how the array works. Inserting new elements from anywhere aside from the end of the array will force elements to shuffle backwards to make room for the new element:

people.insert("Andy", at: 0)
// ["Andy", "Brian", "Stanley", "Ringo", "Charles"]

To be precise, every element must shift backwards by one index, which takes n steps. If the number of elements in the array doubles, the time required for this insert operation will also double.

If inserting elements in front of a collection is a common operation for your program, you may want to consider a different data structure to hold your data.

The second factor that determines the speed of insertion is the array’s capacity. Underneath the hood, Swift arrays are allocated with a predetermined amount of space for its elements. If you try to add new elements to an array that is already at maximum capacity, the Array must restructure itself to make more room for more elements. This is done by copying all the current elements of the array in a new and bigger container in memory. However, this comes at a cost; Each element of the array has to be visited and copied.

This means that any insertion, even at the end, could take n steps to complete if a copy is made. However, the standard library employs a strategy that minimizes the times this copying needs to occur. Each time it runs out of storage and needs to copy, it doubles the capacity.

Dictionary

A dictionary is another generic collection that holds key-value pairs. For example, here’s a dictionary containing a user’s name and a score:

var scores: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]

Dictionaries don’t have any guarantees of order, nor can you insert at a specific index. They also put a requirement on the Key type that it be Hashable. Fortunately almost all of the standard types are already Hashable and in the more recent versions of Swift, adopting the Hashable protocol is now trivial. You can add a new entry to the dictionary with the following syntax:

scores["Andrew"] = 0

This creates a new key-value pair in the dictionary:

["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1]

The "Andrew" key is inserted somewhere into dictionary. Dictionaries are unordered, so you can’t guarantee where new entries will be put.

It is possible to traverse through the key-values of a dictionary multiple times as the Collection protocol affords. This order, while not defined, will be the same every time it is traversed until the collection is changed (mutated).

The lack of explicit ordering disadvantage comes with some redeeming traits.

Unlike the array, dictionaries don’t need to worry about elements shifting around. Inserting into a dictionary always takes a constant amount of time.

Lookup operations also take a constant amount of time, which is significantly faster than finding a particular element in an array which requires a walk from the beginning of the array to the insertion point.

Set

A set is a container that holds unique values. Imagine it being a bag that allows you to insert items into it, but rejects items that have already been inserted:

var bag: Set<String> = ["Candy", "Juice", "Gummy"]
bag.insert("Candy")
print(bag) // prints ["Candy", "Juice", "Gummy"]

Since sets enforce uniqueness, they lend themselves to a variety of interesting applications, such as finding duplicate elements in a collection of values:

let values: [String] = [...]
var bag: Set<String> = []
for value in values {
  if bag.contains(value) {
    // bag already has it, therefore it is a duplicate
  }
  bag.insert(value)
}

You won’t use sets nearly as much as arrays and dictionaries, but it is still common enough to be an important data structure to keep in your toolbelt. There is one caveat though - similar to dictionaries, values in a set have no notion of order. Keep that in mind when you use a set to aggregate data.

Key points

• Every data structure has advantages and disadvantages. Knowing them is key to writing performant software.
• Functions such as insert(at:) for Array have performance characteristics that can cripple performance when used haphazardly. If you find yourself needing to use insert(at:) frequently with indices near the beginning of the array, you may want to consider a different data structure such as the linked list.
• Dictionary trades away the ability to maintain the order of its elements for fast insertion and searching.
• Set guarantees uniqueness in a collection of values. Set is optimized for speed and abandons the ability to retain the order of the elements.