7.
Arrays, Dictionaries & Sets
Written by Eli Ganim
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
As discussed in the introduction to this section, collections are flexible “containers” that let you store any number of values together. Before discussing these collections, you need to understand the concept of mutable vs. immutable collections.
As part of exploring the differences between the collection types, you’ll also consider performance: how quickly the collections can perform certain operations, such as adding or searching through it.
The usual way to talk about performance is with big-O notation. If you’re not familiar with it already, start reading the chapter for a brief introduction.
Big-O notation is a way to describe running time, or how long an operation takes to complete. The idea is that the exact time an operation takes isn’t as important; it’s the relative difference in scale that matters.
Imagine you have a list of names in some random order, and you have to look up the first name on the list. It doesn’t matter whether the list has a single name or a million names — glancing at the first name always takes the same amount of time. That’s an example of a constant time operation, or O(1) in big-O notation.
Now say you have to find a particular name on the list. You need to scan through the list and look at every name until you either find a match or reach the end. Again, we’re not concerned with the exact amount of time this takes, just the relative time compared to other operations.
To figure out the running time, think in terms of units of work. You need to look at every name, so consider there to be one “unit” of work per name. If you had 100 names, that’s 100 units of work. What if you double the number of names to 200? How does that change the amount of work?
The answer is it also doubles the amount of work. Similarly, if you quadruple the number of names, that quadruples the amount of work.
This increase in work is an example of a linear time operation, or O(N) in big-O notation. The input size is the variable N, which means the amount of time the process takes is also N. There’s a direct, linear relationship between the input size (the number of names in the list) and the time it will take to search for one name.
You can see why constant time operations use the number one in O(1). They’re just a single unit of work, no matter what!
You can read more about big-O notation by searching the Web. You’ll only need constant time and linear time in this book, but there are other such time complexities out there.
Big-O notation is particularly important when dealing with collection types because collections can store vast amounts of data. You need to be aware of running times when you add, delete or edit values.
For example, if collection type A has constant-time searching and collection type B has linear-time searching, which you choose to use will depend on how much searching you’re planning to do.
Mutable versus immutable collections
Like the previous types you’ve read about, such as Int or String, when you create a collection, you must declare it as either a constant or a variable.
If the collection doesn’t need to change after you’ve created it, you should make it immutable by declaring it as a constant with let. Alternatively, if you need to add, remove or update values in the collection, you should create a mutable collection by declaring it as a variable with var.
Arrays
Arrays are the most common collection type you’ll run into in Swift. Arrays are typed, just like regular variables and constants, and store multiple values like a simple list.
What is an array?
An array is an ordered collection of values of the same type. The elements in the array are zero-indexed, which means the index of the first element is 0, the index of the second element is 1, and so on. Knowing this, you can determine that the last element’s index is the number of values in the array minus one.
When are arrays useful?
Arrays are useful when you want to store your items in a particular order. You may want the elements sorted, or you may need to fetch elements by index without iterating through the entire array.
Creating arrays
The easiest way to create an array is by using an array literal. This is a concise way to provide array values. An array literal is a list of values separated by commas and surrounded by square brackets.
let evenNumbers = [2, 4, 6, 8]
var subscribers: [String] = []
let allZeros = Array(repeating: 0, count: 5) // [0, 0, 0, 0, 0]
let vowels = ["A", "E", "I", "O", "U"]
Accessing elements
Being able to create arrays is useless unless you know how to fetch values from an array. In this section, you’ll learn several different ways to access elements in an array.
Using properties and methods
Imagine creating a game of cards, and you want to store the players’ names in an array. The list will need to change as players join or leave the game, so you need to declare a mutable array:
var players = ["Alice", "Bob", "Cindy", "Dan"]
print(players.isEmpty)
// > false
if players.count < 2 {
print("We need at least two players!")
} else {
print("Let’s start!")
}
// > Let’s start!
var currentPlayer = players.first
print(currentPlayer as Any)
// > Optional("Alice")
print(players.last as Any)
// > Optional("Dan")
currentPlayer = players.min()
print(currentPlayer as Any)
// > Optional("Alice")
print([2, 3, 1].first as Any)
// > Optional(2)
print([2, 3, 1].min() as Any)
// > Optional(1)
if let currentPlayer = currentPlayer {
print("\(currentPlayer) will start")
}
// > Alice will start
Using subscripting
The most convenient way to access elements in an array is by using the subscript syntax. This syntax lets you access any value directly by using its index inside square brackets:
var firstPlayer = players[0]
print("First player is \(firstPlayer)")
// > First player is "Alice"
var player = players[4]
// > fatal error: Index out of range
Using countable ranges to make an ArraySlice
You can use the subscript syntax with countable ranges to fetch more than a single value from an array. For example, if you’d like to get the next two players, you could do this:
let upcomingPlayersSlice = players[1...2]
print(upcomingPlayersSlice[1], upcomingPlayersSlice[2])
// > "Bob Cindy\n"
let upcomingPlayersArray = Array(players[1...2])
print(upcomingPlayersArray[0], upcomingPlayersArray[1])
// > "Bob Cindy\n"
Checking for an element
You can check if there’s at least one occurrence of a specific element in an array by using contains(_:), which returns true if it finds the element in the array, and false otherwise.
func isEliminated(player: String) -> Bool {
!players.contains(player)
}
print(isEliminated(player: "Bob"))
// > false
players[1...3].contains("Bob") // true
Modifying arrays
You can make all kinds of changes to mutable arrays, such as adding and removing elements, updating existing values, and moving elements around into a different order. In this section, you’ll see how to work with the array to match up what’s going on with your game.
Appending elements
If new players want to join the game, they need to sign up and add their names to the array. Eli is the first player to join the existing four players. You can add Eli to the end of the array using the append(_:) method:
players.append("Eli")
players += ["Gina"]
print(players)
// > ["Alice", "Bob", "Cindy", "Dan", "Eli", "Gina"]
Inserting elements
An unwritten rule of this card game is that the players’ names have to be in alphabetical order. This list is missing a player that starts with the letter F. Luckily, Frank has just arrived. You want to add him to the list between Eli and Gina. To do that, you can use the insert(_:at:) method:
players.insert("Frank", at: 5)
Removing elements
During the game, the other players caught Cindy and Gina cheating. They should be removed from the game! You know that Gina is last in the players list, so you can remove her easily with the removeLast() method:
var removedPlayer = players.removeLast()
print("\(removedPlayer) was removed")
// > Gina was removed
removedPlayer = players.remove(at: 2)
print("\(removedPlayer) was removed")
// > Cindy was removed
Mini-exercise
Use firstIndex(of:) to determine the position of the element "Dan" in players.
Updating elements
Frank has decided everyone should call him Franklin from now on. You could remove the value "Frank" from the array and then add "Franklin", but that’s too much work for a simple task. Instead, you should use the subscript syntax to update the name.
print(players)
// > ["Alice", "Bob", "Dan", "Eli", "Frank"]
players[4] = "Franklin"
print(players)
// > ["Alice", "Bob", "Dan", "Eli", "Franklin"]
players[0...1] = ["Donna", "Craig", "Brian", "Anna"]
print(players)
// > ["Donna", "Craig", "Brian", "Anna", "Dan", "Eli", "Franklin"]
Moving elements
Take a look at this mess! The players array contains names that start with A to F, but they aren’t in the correct order, which violates the rules of the game.
let playerAnna = players.remove(at: 3)
players.insert(playerAnna, at: 0)
print(players)
// > ["Anna", "Donna", "Craig", "Brian", "Dan", "Eli", "Franklin"]
players.swapAt(1, 3)
print(players)
// > ["Anna", "Brian", "Craig", "Donna", "Dan", "Eli", "Franklin"]
players.sort()
print(players)
// > ["Anna", "Brian", "Craig", "Dan", "Donna", "Eli", "Franklin"]
Iterating through an array
It’s getting late, so the players decide to stop for the night and continue tomorrow. In the meantime, you’ll keep their scores in a separate array. You’ll investigate a better approach for this when you learn about dictionaries, but for now, you can continue to use arrays:
let scores = [2, 2, 8, 6, 1, 2, 1]
for player in players {
print(player)
}
// > Anna
// > Brian
// > Craig
// > Dan
// > Donna
// > Eli
// > Franklin
for (index, player) in players.enumerated() {
print("\(index + 1). \(player)")
}
// > 1. Anna
// > 2. Brian
// > 3. Craig
// > 4. Dan
// > 5. Donna
// > 6. Eli
// > 7. Franklin
func sumOfElements(in array: [Int]) -> Int {
var sum = 0
for number in array {
sum += number
}
return sum
}
print(sumOfElements(in: scores))
// > 22
Mini-exercise
Write a for-in loop that prints the players’ names and scores.
Running time for array operations
Arrays are stored as a contiguous block in memory. That means if you have ten elements in an array, the ten values are all stored one next to the other. With that in mind, here’s the performance cost of various array operations:
Dictionaries
A dictionary is an unordered collection of pairs, where each pair comprises a key and a value.
Creating dictionaries
The easiest way to create a dictionary is by using a dictionary literal. This is a list of key-value pairs separated by commas, enclosed in square brackets.
var namesAndScores = ["Anna": 2, "Brian": 2, "Craig": 8, "Donna": 6]
print(namesAndScores)
// > ["Craig": 8, "Anna": 2, "Donna": 6, "Brian": 2]
namesAndScores = [:]
var pairs: [String: Int] = [:]
pairs.reserveCapacity(20)
Accessing values
As with arrays, there are several ways to access dictionary values.
Using subscripting
Dictionaries support subscripting to access values. Unlike arrays, you don’t access a value by its index but rather by its key. For example, if you want to get Anna’s score, you would type:
namesAndScores = ["Anna": 2, "Brian": 2, "Craig": 8, "Donna": 6]
// Restore the values
print(namesAndScores["Anna"]!) // 2
namesAndScores["Greg"] // nil
Using properties and methods
Dictionaries, like arrays, conform to Swift’s Collection protocol. Because of that, they share many of the same properties. For example, both arrays and dictionaries have isEmpty and count properties:
namesAndScores.isEmpty // false
namesAndScores.count // 4
Modifying dictionaries
It’s easy enough to create dictionaries and access their contents — but what about modifying them?
Adding pairs
Bob wants to join the game.
var bobData = [
"name": "Bob",
"profession": "Card Player",
"country": "USA"
]
bobData.updateValue("CA", forKey: "state")
bobData["city"] = "San Francisco"
Mini-exercise
Write a function that prints a given player’s city and state.
Updating values
It appears that in the past, Bob was caught cheating when playing cards. He’s not just a professional — he’s a card shark! He asks you to change his name and profession so no one will recognize him.
bobData.updateValue("Bobby", forKey: "name") // Bob
bobData["profession"] = "Mailman"
Removing pairs
Bob — er, sorry — Bobby, still doesn’t feel safe, and he wants you to remove all information about his whereabouts:
bobData.removeValue(forKey: "state")
bobData["city"] = nil
Iterating through dictionaries
The for-in loop also works when you want to iterate over a dictionary. But since the items in a dictionary are pairs, you can use a tuple:
for (player, score) in namesAndScores {
print("\(player) - \(score)")
}
// > Craig - 8
// > Anna - 2
// > Donna - 6
// > Brian - 2
for player in namesAndScores.keys {
print("\(player), ", terminator: "") // no newline
}
print("") // print one final newline
// > Craig, Anna, Donna, Brian,
Running time for dictionary operations
To examine how dictionaries work, you need to understand what hashing is and how it works. Hashing is the process of transforming a value — String, Int, Double, Bool, etc. — to a numeric value, known as the hash value. This value can then be used to quickly look up the values in a hash table.
Sets
A set is an unordered collection of unique values of the same type. This can be extremely useful when you want to ensure that an item doesn’t appear more than once in your collection and when the order of your items isn’t important.
Creating sets
You can declare a set explicitly by writing Set followed by the type inside angle brackets:
let setOne: Set<Int> = [1]
Set literals
Sets don’t have their own literals. You use array literals to create a set with initial values. Consider this example:
let someArray = [1, 2, 3, 1]
var explicitSet: Set<Int> = [1, 2, 3, 1]
var someSet = Set([1, 2, 3, 1])
print(someSet)
// > [2, 3, 1] but the order is not defined
Accessing elements
You can use contains(_:) to check for the existence of a specific element:
print(someSet.contains(1))
// > true
print(someSet.contains(4))
// > false
Adding and removing elements
You can use insert(_:) to add elements to a set. If the element already exists, the method does nothing.
someSet.insert(5)
let removedElement = someSet.remove(1)
print(removedElement!)
// > 1
Running time for set operations
Sets have a very similar implementation to dictionaries, and they also require the elements to be hashable. The running time of all the operations is identical to those of dictionaries.
Challenges
Before moving on, here are some challenges to test your knowledge of arrays, dictionaries and sets. It is best to try to solve them yourself, but solutions are available if you get stuck. These came with the download or are available at the printed book’s source code link listed in the introduction.
Challenge 1: Which is valid
Which of the following are valid statements?
1. let array1 = [Int]()
2. let array2 = []
3. let array3: [String] = []
let array4 = [1, 2, 3]
4. print(array4[0])
5. print(array4[5])
6. array4[1...2]
7. array4[0] = 4
8. array4.append(4)
var array5 = [1, 2, 3]
9. array5[0] = array5[1]
10. array5[0...1] = [4, 5]
11. array5[0] = "Six"
12. array5 += 6
13. for item in array5 { print(item) }
Challenge 2: Remove the first number
Write a function that removes the first occurrence of a given integer from an array of integers. This is the signature of the function:
func removingOnce(_ item: Int, from array: [Int]) -> [Int]
Challenge 3: Remove the numbers
Write a function that removes all occurrences of a given integer from an array of integers. This is the signature of the function:
func removing(_ item: Int, from array: [Int]) -> [Int]
Challenge 4: Reverse an array
Arrays have a reversed() method that returns an array holding the same elements as the original array in reverse order. Write a function that does the same thing without using reversed(). This is the signature of the function:
func reversed(_ array: [Int]) -> [Int]
Challenge 5: Return the middle
Write a function that returns the middle element of an array. When array size is even, return the first of the two middle elements.
func middle(_ array: [Int]) -> Int?
Challenge 6: Find the minimum and maximum
Write a function that calculates the minimum and maximum values in an array of integers. Calculate these values yourself; don’t use the methods min and max. Return nil if the given array is empty.
func minMax(of numbers: [Int]) -> (min: Int, max: Int)?
Challenge 7: Which is valid
Which of the following are valid statements?
1. let dict1: [Int, Int] = [:]
2. let dict2 = [:]
3. let dict3: [Int: Int] = [:]
let dict4 = ["One": 1, "Two": 2, "Three": 3]
4. dict4[1]
5. dict4["One"]
6. dict4["Zero"] = 0
7. dict4[0] = "Zero"
var dict5 = ["NY": "New York", "CA": "California"]
8. dict5["NY"]
9. dict5["WA"] = "Washington"
10. dict5["CA"] = nil
Challenge 8: Long names
Given a dictionary with two-letter state codes as keys, and the full state names as values, write a function that prints all the states with names longer than eight characters. For example, for the dictionary ["NY": "New York", "CA": "California"], the output would be California.
Challenge 9: Merge dictionaries
Write a function that combines two dictionaries into one. If a certain key appears in both dictionaries, ignore the pair from the first dictionary. This is the function’s signature:
func merging(_ dict1: [String: String], with dict2: [String: String]) -> [String: String]
Challenge 10: Count the characters
Declare a function occurrencesOfCharacters that calculates which characters occur in a string, as well as how often each of these characters occur. Return the result as a dictionary. This is the function signature:
func occurrencesOfCharacters(in text: String) -> [Character: Int]
Challenge 11: Unique values
Write a function that returns true if all of the values of a dictionary are unique. Use a set to test uniqueness. This is the function signature:
func isInvertible(_ dictionary: [String: Int]) -> Bool
Challenge 12: Removing keys and setting values to nil
Given the dictionary:
var nameTitleLookup: [String: String?] = ["Mary": "Engineer", "Patrick": "Intern", "Ray": "Hacker"]
Key points
Sets: