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, a comma-separated list of values surrounded by 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 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, other performance areas 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 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 backward to make room for the new element:

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

To be precise, every element must shift backward 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 the 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 that 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.

The Swift Collections package

The Swift standard library only implements the three most important data structures: Array, Set, and Dictionary. For additional data structures, you can check out the Swift Collections package. This package allows new collection types to be developed and tested by the community before they become part of the official standard library.

In the next section, you’ll take a deeper look at one of the data structures from this package.

Deque

Earlier, you learned that inserting elements in the front of an Array causes a shuffle of all the elements.

At first glance, the Deque (pronounced “deck”) data structure seems to serve the same purpose as the Array. You can use it as a general-purpose container that holds values in order. Just like the Array, you can call append to add elements to the Deque, or remove(at:) to remove a specific element at some index.

In fact, the interface is nearly identical since both Array and Deque implement the same collection protocols. So why use a Deque over an Array? The tradeoffs are hard to see until you consider time complexity.

A Deque is a double-ended queue. Therefore, Deque optimizes for modifications from both the front and the back of the collection. Unlike Array, inserting or removing an element from the front of a Deque is a cheap O(1) operation.

Great - so what are the downsides? In programming, everything is about tradeoffs. For Deque, it’s about improving modifications in the front for the cost of slightly degraded performance on everything else. As a programmer, it’s your job to weigh the options and pick the best tool for the job. If your app requires frequent modifications to the front of a collection, a Deque will perform much better than an Array. That could translate to a better user experience - one that could make the difference between a snappy and sluggish app.

The Swift Collections package contains additional data structures, such as OrderedDictionary and OrderedSet. As the prefix suggests, these are variants of Dictionary and Set that retain the order of the elements. Like Deque, these data structures have some performance tradeoffs. You can learn more about them at https://swift.org/blog/swift-collections/.

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.
• The Swift Collections package contains specialized data structures that perform better in certain scenarios.