In this article by Erik Azar and Mario Eguiluz Alebicto, authors of the book Swift Data Structure and Algorithms, we will learn that the Swift language is truly powerful, but a powerful language is nothing if it doesn't have a powerful standard library to accompany it. The Swift standard library defines a base layer of functionality that you can use for writing your applications, including fundamental data types, collection types, functions and methods, and a large number of protocols.

(For more resources related to this topic, see here.)

We're going to take a close look at the Swift standard library, specifically support for collection types, with a very low level examination of Arrays, Dictionaries, Sets, and Tuples.

The topics covered in this article are:

Using the Swift standard library
Implementing subscripting
Understanding immutability
Interoperability between Swift and Objective-C
Swift Protocol-Oriented Programming

Using the Swift standard library

Users often treat a standard library as part of the language. In reality, philosophies on standard library design very widely, often with opposing views. For example, the C and C++ standard libraries are relatively small, containing only the functionality that "every developer" might reasonably require to develop an application. Conversely, languages such as Python, Java, and .NET have large standard libraries that include features, which tend to be separate in other languages, such as XML, JSON, localization, and e-mail processing.

In the Swift programming language, the Swift standard library is separate from the language itself, and is a collection of classes, structures, enumerations, functions, and protocols, which are written in the core language. The Swift standard library is currently very small, even compared to C and C++. It provides a base layer of functionality through a series of generic structures and enums, which also adopt various protocols that are also defined in the library. You'll use these as the building blocks for applications that you develop.

The Swift standard library also places specific performance characteristics on functions and methods in the library. These characteristics are guaranteed only when all participating protocols performance expectations are satisfied. An example is the Array.append(), its algorithm complexity is amortized O(1), unless the self's storage is shared with another live array; O(count) if self does not wrap a bridged NSArray; otherwise the efficiency is unspecified.

We're going to take a detailed look at the implementations for Arrays, Dictionaries, Sets, and Tuples.

You'll want to make sure you have at least Xcode 8.1 installed to work with code in this section

Why Structures?

If you're coming from a background working in languages such as Objective-C, C++, Java, Ruby, Python, or other object-oriented languages, you traditionally use classes to define the structure of your types. This is not the case in the Swift standard library; structures are used when defining the majority of the types in the library. If you're coming from an Objective-C or C++ background this might seem especially odd and feel wrong, because classes are much more powerful than structures.

So why does Swift use structures, which are value types, when it also supports classes, which are reference types, that support inheritance, deinitializers, and reference counting? It's exactly because of the limited functionality of structures over classes why Swift uses structures instead of classes for the building blocks of the standard library. Because structures are value types it means they can have only one owner and are always copied when assigned to a new variable or passed to a function. This can make your code inherently safer because changes to the structure will not affect other parts of your application.

The preceding description refers to the "copying" of value types. The behavior you see in your code will always be as if a copy took place. However, Swift only performs an actual copy behind the scenes when it is absolutely necessary to do so. Swift manages all value copying to ensure optimal performance, and you should not avoid assignment to try to preempt this optimization.

Structures in Swift are far more powerful than in other C-based languages, they are very similar to classes. Swift structures support the same basic features as C-based structures, but Swift also adds support, which makes them feel more like classes.

Features of Swift structures:

In addition to an automatically generated memberwise initializer, they can have custom initializers
Can have methods
Can implement protocols

So this may leave you asking, when should I use a class over a structure? Apple has published guidelines you can follow when considering to create a structure. If one or more of the following conditions apply, consider creating a structure:

Its primary purpose is to encapsulate a few simple data values
You expect the encapsulated values to be copied rather than referenced when you pass around or assign an instance of the structure
Any properties stored by the structure are value types, which would be expected to be copied instead of referenced
The structure doesn't need to inherit properties or behavior from another existing type

In all other cases, create a class which will call instances of that class to be passed by the reference.

Apple Guidelines for choosing between classes and structures:

https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/ClassesAndStructures.html

Declaring arrays in Swift

An array stores values of the same type in an ordered list. Arrays in Swift have a few important differences between arrays in Objective-C. The first is elements in Swift arrays must be of the same type. If you're used to working with Objective-C NSArrays prior to Xcode 7 you may feel this is a disadvantage, but it actually is a significant advantage as it allows you to know exactly what type you get back when working with an array, allowing you to write more efficient code that leads to less defects. However, if you find you must have dissimilar types in an array, you can define the array to be of a protocol that is common to the other types, or defines the array of type AnyObject.

Another difference is Objective-C array elements have to be a class type. In Swift, arrays are generic type collections, there are no limitations on what that type can be. You can create an array that holds any value type, such as Int, Float, String, or Enums, as well as classes.

The last difference is, unlike arrays in Objective-C, Swift arrays are defined as a structure instead of a class.

We know the basic constructs for declaring an integer array and performing operations such as adding, removing, and deleting elements from an array. Let's take a closer, more detailed examination of how arrays are implemented in the standard library.

There are three Array types available in Swift:

Array
ContiguousArray
ArraySlice

Every Array class maintains a region of memory that stores the elements contained in the array. For array element types that are not a class or @objc protocol type, the arrays memory region is stored in contiguous blocks. Otherwise, when an arrays element type is a class or @objc protocol type, the memory region can be a contiguous block of memory, an instance of NSArray, or an instance of an NSArray subclass.

If may be more efficient to use a ContiguousArray if you're going to store elements that are a class or an @objc protocol type. The ContiguousArray class shares many of the protocols that Array implements, so most of the same properties are supported. The key differentiator between Array and ContiguousArray is that ContiguousArray' do not provide support for bridging to Objective-C.

The ArraySlice class represents a sub-sequence of an Array, ContiguousArray, or another ArraySlice. Like ContiguousArray, ArraySlice instances also use contiguous memory to store elements, and they do not bridge to Objective-C. An ArraySlice represents a sub-sequence from a larger, existing Array type. Because of this, you need to be aware of the side effects if you try storing an ArraySlice after the original Array's lifetime has ended and the elements are no longer accessible. This could lead to memory or object leaks thus Apple recommends that long-term storage of ArraySlice instances is discouraged.

When you create an instance of Array, ContiguousArray, or ArraySlice, an extra amount of space is reserved for storage of its elements. The amount of storage reserved is referred to as an array's capacity, which represents the potential amount of storage available without having to reallocate the array. Since Swift arrays share an exponential growth strategy, as elements are appended to an array, the array will automatically resize when it runs out of capacity. When you amortize the append operations over many iterations, the append operations are performed in constant time. If you know ahead of time an array will contain a large number of elements, it may be more efficient to allocate additional reserve capacity at creation time. This will avoid constant reallocation of the array as you add new elements. The following code snippet shows an example of declaring an initial capacity of 500 Integer elements for the array intArray:

// Create an array using full array syntax
var intArray = Array<Int>() 

// Create an array using shorthand syntax
intArray = [Int]()

intArray.capacity					// contains 0
intArray.reserveCapacity(500)
intArray.capacity					// contains 508

You can notice from the preceding example that our reserve capacity is actually larger than 500 integer elements. For performance reasons, Swift may allocate more elements than you requests. But you can be guaranteed that at least the number of elements specified will be created.

When you make a copy of an array a separate physical copy is not made during the assignment. Swift implements a feature called copy-on-write, which means that array elements are not copied until a mutating operation is performed when more than one array instances is sharing the same buffer. The first mutating operation may cost O(n) in time and space, where n is the length of the array.

Initializing Array

The initialization phase prepares a struct, class, or enum for use through a method called init. If you're familiar with other languages such as C++, Java, or C# this type of initialization is performed in their class constructor, which is defined using the class's name.

If you're coming from Objective-C, the Swift initializers will behave a little differently from how you're used to. In Objective-C, the init methods will directly return the object they initialize, callers will then check the return value when initializing a class and check for nil to see if the initialization process failed. In Swift, this type of behavior is implemented as a feature called failable initialization, which we'll discuss shortly.

There are four initializers provided for the three types of Swift arrays implemented in the standard library.

Additionally, you can use a dictionary literal to define a collection of one or more elements to initialize the array, the elements are separated by a comma (,):

// Create an array using full array syntax
var intArray = Array<Int>()

// Create an array using shorthand syntax
intArray = [Int]()

// Use array literal declaration
var intLiteralArray: [Int] = [1, 2, 3]
// [1, 2, 3]

//: Use shorthand literal declaration
intLiteralArray = [1, 2, 3]
// [1, 2, 3]

//: Create an array with a default value
intLiteralArray = [Int](count: 5, repeatedValue: 2)
// [2, 2, 2, 2, 2]

Adding and Updating Elements in an Array

To add a new element to an array you can use the append(_:) method. This will add newElement to the end of the array:

var intArray = [Int]()
intArray.append(50)
// [50]

If you have an existing collection type you can use the append(_:) method. This will append elements from newElements to the end of the array:

intArray.append([60, 65, 70, 75])
// [50, 60, 65, 70, 75]

If you want to add elements at a specific index you can use the insert(newElement:at:) method. This will add newElement at index i:

intArray.insert(newElement: 55, at: 1)
// [50, 55, 60, 65, 70, 75]

Requires i <= count otherwise you will receive a fatal error: Array index out of range message and execution will stop.

To replace an element at a specific index you can use the subscript notation, providing the index of the element you want to replace:

intArray[2] = 63
// [50, 55, 63, 65, 70, 75]

Retrieving and Removing Elements from an Array

There are several methods you can use to retrieve elements from an array. If you know the specific array index or sub-range of indexes you can use array subscripting:

// Initial intArray elements
// [50, 55, 63, 65, 70, 75]

// Retrieve an element by index
intArray[5]
// returns 75

// Retrieve an ArraySlice of elements by subRange
intArray[2..<5]

// Returns elements between index 2 and less than index 5
// [63, 65, 70]

// Retrieve an ArraySlice of elements by subRange
intArray[2…5]

// Returns elements between index 2 and index 5
// [63, 65, 70, 75]

You can also iterate over the array, examining each element in the collection:

for element in intArray {
    print(element)
}

// 50
// 55
// 63
// 65
// 70
// 75

You can also check if an array has a specific element or pass a closure that will allow you to evaluate each element:

intArray.contains(55)
// returns true

See Apples Swift documentation for a complete list of methods available for arrays:https://developer.apple.com/library/ios/documentation/Swift/Conceptual/Swift_Programming_Language/CollectionTypes.html

Unlock access to the largest independent learning library in Tech for FREE!

Get unlimited access to 7500+ expert-authored eBooks and video courses covering every tech area you can think of.

Renews at $15.99/month. Cancel anytime

Retrieving and Initializing Dictionaries

A dictionary is an unordered collection that stores associations between keys and values of the same type with no defined ordering. Each value is associated with a unique key that acts as an identifier for the value in the dictionary. A dictionary data structure works just like a real world dictionary; to retrieve a definition, reference, translation, or some other type of information for a specific word you open the dictionary and locate the word to find the information you're looking for. With a dictionary data structure, you store and retrieve values by associating them with a key.

A dictionary key type must conform to the Hashtable protocol.

Initializing a Dictionary

Just like arrays, there are two ways you can declare a dictionary using either the full or literal syntax:

// Full syntax declaration

var myDict =  Dictionary<Int, String>()


// Shorthand syntax declaration

var myDict = [Int: String]()

Additionally, you can use a dictionary literal to define a collection of one or more key-value pairs to initialize the dictionary. The key and value are separated by a colon (:) and the pairs are separated by a comma (,).

If the keys and values have consistent types you do not need to declare the type of dictionary in the declaration, Swift will infer it based on the key-value pairs used during initialization, which saves a few keystrokes allowing you to use the shorter form:

// Use dictionary literal declaration

var myDict: [Int: String] = [1: "One", 2: "Two", 3: "Three"]
// [2: "Two", 3: "Three", 1: "One"]


// Use shorthand literal declaration

var myDict = [1: "One", 2: "Two", 3: "Three"]
// [2: "Two", 3: "Three", 1: "One"]

Adding/Modifying/Removing a Key-Value Pair

To add a new key-value pair or to update an existing pair you can use the updateValue(_:forKey) method or subscript notation. If the key is does not exist a new pair will be added, otherwise the existing pair is updated with the new value:

// Add a new pair to the dictionary
myDict.updateValue("Four", forKey: 4)
$R0: String? = nil
// [2: "Two", 3: "Three", 1: "One", 4: "Four"]

// Add a new pair using subscript notation
myDict[5] = "Five"
// [5: "Five", 2: "Two", 3: "Three", 1: "One", 4: "Four"]

Unlike the subscript method, the updateValue(_:forKey:) method will return the value that was replaced, or nil if a new key-value pair was added.

To remove a key-value pair you can use the removeValue(forKey:) method, providing the key to delete or setting the key to nil using subscript notation:

// Remove a pair from the dictionary – returns the removed pair
let removedPair = myDict.removeValue(forKey: 1)
removedPair: String? = "One"
// [5: "Five", 2: "Two", 3: "Three", 4: "Four"]

// Remove a pair using subscript notation
myDict[2] = nil
// [5: "Five", 3: "Three", 4: "Four"]

Unlike the subscript method, the removeValue(forKey:) method will return the value that was removed, or nil if the key doesn't exist.

Retrieving Values from a Dictionary

You can retrieve specific key-value pairs from a dictionary using subscript notation. The key is passed to the square bracket subscript notation; it's possible the key may not exist so subscripts will return an Optional. You can use either optional binding or forced unwrapping to retrieve the pair or determine if it doesn't exist. Do not use forced unwrapping though unless you're absolutely sure the key exists or a runtime exception will be thrown:

// Example using Optional Binding

var myDict = [1: "One", 2: "Two", 3: "Three"]
if let optResult = myDict[4] {
    print(optResult)
}
else {
    print("Key Not Found")
}

// Example using Forced Unwrapping – only use if you know the key will exist

let result = myDict[3]!
print(result)

If instead of getting a specific value, you can iterate over the sequence of a dictionary and return a (key, value) tuple, which can be decomposed into explicitly named constants. In this example, (key, value) are decomposed into (stateAbbr, stateName):

// Dictionary of state abbreviations to state names
let states = [ "AL" : "Alabama", "CA" : "California", "AK" : "Alaska", "AZ" : "Arizona", "AR" : "Arkansas"]

for (stateAbbr, stateName) in states {
    print("The state abbreviation for (stateName) is (stateAbbr)")
}

// Output of for...in
The state abbreviation for Alabama is AL
The state abbreviation for California is CA
The state abbreviation for Alaska is AK
The state abbreviation for Arizona is AZ
The state abbreviation for Arkansas is AR

You can see from the output that items in the dictionary are not output in the order they were inserted. Recall that dictionaries are unordered collections, so there is no guarantee that the order pairs will be retrieved when iterating over them.

If you want to retrieve only the keys or values independently you can use the keys or values properties on a dictionary.

These properties will return a LazyMapCollection instance over the collection. The elements of the result will be computed lazily each time they are read by calling the transform closure function on the base element. The key and value will appear in the same order as they would as a key-value pair, .0 member and .1 member, respectively:

for (stateAbbr) in states.keys {
    print("State abbreviation: (stateAbbr)")
}

//Output of for...in
State abbreviation: AL
State abbreviation: CA
State abbreviation: AK
State abbreviation: AZ
State abbreviation: AR

for (stateName) in states.values {
    print("State name: (stateName)")
}

//Output of for...in
State name: Alabama
State name: California
State name: Alaska
State name: Arizona
State name: Arkansas

You can read more about the LazyMapCollection structure on Apple's developer site at https://developer.apple.com/library/prerelease/ios/documentation/Swift/Reference/Swift_LazyMapCollection_Structure/

There may be occasions when you want to iterate over a dictionary in an ordered manner. For those cases, you can make use of the global sort(_:) method. This will return an array containing the sorted elements of a dictionary as an array:

// Sort the dictionary by the value of the key
let sortedArrayFromDictionary = states.sort({ $0.0 < $1.0 })

// sortedArrayFromDictionary contains...
// [("AK", "Alaska"), ("AL", "Alabama"), ("AR", "Arkansas"), ("AZ", "Arizona"), ("CA", "California")]

for (key) in sortedArrayFromDictionary.map({ $0.0}) {
    print("The key: (key)")
}

//Output of for...in
The key: AK
The key: AL
The key: AR
The key: AZ
The key: CA


for (value) in sortedArrayFromDictionary.map({ $0.1}) {
    print("The value: (value)")
}

//Output of for...in
The value: Alaska
The value: Alabama
The value: Arkansas
The value: Arizona
The value: California

Let's walk through what is happening here. For the sort method, we are passing a closure that will compare if the first arguments key from the key-value pair, $0.0 against the second arguments key from the key-value pair, $1.0, if the first argument is less than the second it will be added to the new array. When the sort method has iterated over and sorted all of the elements, a new array of [(String, String)] containing the key-value pairings is returned.

Next, we want to retrieve the list of keys from the sorted array. On the sortedArrayFromDictionary variable we call map({ $0.0}), the transform passed to the map method will add the .0 element of each array element in sortedArrayFromDictionary to the new array returned by the map method.

The last step is to retrieve a list of values from the sorted array. We are performing the same call to the map method as we did to retrieve the list of keys, this time we want the .1 element of each array element in sortedArrayFromDictionary, though. Like the preceding example, these values will be added to the new array returned by the map method.

But what if you wanted to base your sorting order on the dictionary value instead of the key? This is simple to do; you would just change the parameter syntax that is passed to the sort method. Changing it to states.sort({ $0.1 < $1.1 }) will now compare the first arguments value from the key-value pair, $0.1, against the second arguments value from its key-value pair, $1.1, and adding the lesser of the two to the new array that will be returned.

Declaring Sets

A Set is an unordered collection of unique, non-nil elements with no defined ordering. A Set type must conform to the Hashtable protocol to be stored in a set. All of Swift's basic types are hashable by default. Enumeration case values that do not use associate values are also hashable by default. You can store a custom type in a Set, you'll just need to ensure that it conforms to the Hashable protocol, as well as the Equatable protocol since Hashtable conforms to it.

Sets can be used anywhere you would use an array when ordering is not important and you want to ensure only unique elements are stored. Additionally, access time has the potential of being more efficient over arrays. With an array, the worst case scenario when searching for an element is O(n) where n is the size of the array. Whereas accessing an element in a Set is always constant time O(1), regardless of its size.

Initializing a Set

Unlike the other collection types, Sets cannot be inferred from an array literal alone and must be explicitly declared by specifying the Set type:

// Full syntax declaration

var stringSet =  Set<String>()

Because of Swift's type inference, you do not have to specify the type of the Set that you're initializing, it will infer the type based on the array literal it is initialized with. Remember though that the array literal must contain the same types:

// Initialize a Set from an array literal

var stringSet: Set = ["Mary", "John", "Sally"]
print(stringSet.debugDescription)

// Out of debugDescription shows stringSet is indeed a Set type
"Set(["Mary", "John", "Sally"])"

Modifying and Retrieving Elements of a Set

To add a new element to a Set use the insert(_:) method. You can check if an element is already stored in a Set using the contains(_:) method. Swift provides several methods for removing elements from a Set, if you have an instance of the element you want to remove you can use the remove(_:) method, which takes an element instance. If you know the index of an element in the Set you can use the remove(at:) method, which takes an instance of SetIndex<Element>. If the Set count is greater than 0 you can use the removeFirst() method to remove the element and the starting index. Lastly, if you want to remove all elements from a Set, use the removeAll() method or removeAll(keepCapacity) method, if keepCapacity is true the current capacity will not decrease:

var stringSet: Set = ["Erik", "Mary", "Michael", "John", "Sally"]
// ["Mary", "Michael", "Sally", "John", "Erik"]


stringSet.insert("Patrick")
// ["Mary", "Michael", "Sally", "Patrick", "John", "Erik"]


if stringSet.contains("Erik") {
    print("Found element")
}
else {
    print("Element not found")
}
// Found element


stringSet.remove("Erik")
// ["Mary", "Sally", "Patrick", "John", "Michael"]


if let idx = stringSet.index(of: "John") {
    stringSet.remove(at: idx)
}
// ["Mary", "Sally", "Patrick", "Michael"]


stringSet.removeFirst()
// ["Sally", "Patrick", "Michael"]


stringSet.removeAll()
// []

You can iterate over a Set the same as you would the other collection types by using the for…in loop. The Swift Set type is unordered, so you can use the sort method like we did for the Dictionary type if you want to iterate over elements in a specific order:

var stringSet: Set = ["Erik", "Mary", "Michael", "John", "Sally"]
// ["Mary", "Michael", "Sally", "John", "Erik"]

for name in stringSet {
    print("name = (name)")
}


// name = Mary
// name = Michael
// name = Sally
// name = John
// name = Erik

for name in stringSet.sorted() {
    print("name = (name)")
}

// name = Erik
// name = John
// name = Mary
// name = Michael
// name = Sally

Set Operations

The Set type is modeled after the mathematical Set Theory and it implements methods that support basic Set operations for comparing two Sets, as well as operations that perform membership and equality comparisons between two Sets.

Comparison Operations

The Swift Set type contains four methods for performing common operations on two sets. The operations can be performed either by returning a new set, or using the operations alternate InPlace method to perform the operation in place on the source Set.

The union(_:) and formUnion(_:) methods create a new Set or update the source Set with all the values from both Sets, respectively.

The intersection(_:) and formIntersection(_:) methods create a new Set or update the source Set with values only common to both Sets, respectively.

The symmetricDifference(_:) or formSymmetricDifference(_:) methods create a new Set or update the source Set with values in either Set, but not both, respectively.

The subtracting(_:) or subtract(_:) methods create a new Set or update the source Set with values not in the specified Set:

let adminRole: Set = [ "READ", "EDIT", "DELETE", "CREATE", "SETTINGS", "PUBLISH_ANY", "ADD_USER", "EDIT_USER", "DELETE_USER"]

let editorRole: Set = ["READ", "EDIT", "DELETE", "CREATE", "PUBLISH_ANY"]

let authorRole: Set = ["READ", "EDIT_OWN", "DELETE_OWN", "PUBLISH_OWN", "CREATE"]

let contributorRole: Set = [ "CREATE", "EDIT_OWN"]

let subscriberRole: Set = ["READ"]

// Contains values from both Sets
let fooResource = subscriberRole.union(contributorRole)
// "READ", "EDIT_OWN", "CREATE"

// Contains values common to both Sets
let commonPermissions = authorRole.intersection(contributorRole)
// "EDIT_OWN", "CREATE"

// Contains values in either Set but not both
let exclusivePermissions = authorRole.symmetricDifference(contributorRole)
// "PUBLISH_OWN", "READ", "DELETE_OWN"

Membership and Equality Operations

Two sets are said to be equal if they contain precisely the same values, and since Sets are unordered, the ordering of the values between Sets does not matter.

Use the == operator, which is the "is equal" operator, to determine if two Sets contain all of the same values:

// Note ordering of the sets does not matter
var sourceSet: Set = [1, 2, 3]
var destSet: Set = [2, 1, 3]

var isequal = sourceSet == destSet

// isequal is true

Use the isSubset(of:) method to determine if all of the values of a Set are contained in a specified Set.

Use the isStrictSubset(of:) method to determine if a Set is a subset, but not equal to the specified Set.

Use the isSuperset(of:) method to determine if a Set contains all of the values of the specified Set.

Use the isStrictSuperset(of:) method to determine if a Set is a superset, but not equal to the specified Set.

Use the isDisjoint(with:) method to determine if two Sets have the same values in common:

let contactResource = authorRole
// "EDIT_OWN", "PUBLISH_OWN", "READ", "DELETE_OWN", "CREATE"

let userBob = subscriberRole
// "READ"

let userSally = authorRole
// "EDIT_OWN", "PUBLISH_OWN", "READ", "DELETE_OWN", "CREATE"

if userBob.isSuperset(of: fooResource){
    print("Access granted")
}
else {
    print("Access denied")
}
// "Access denied"

if userSally.isSuperset(of: fooResource){
    print("Access granted")
}
else {
    print("Access denied")
}
// Access granted

authorRole.isDisjoint(with: editorRole)
// false

editorRole.isSubset(of: adminRole)
// true

Summary

In this article, we've learned about the difference between classes and structures and when you would use one type over another, as well as characteristics of value types and reference types and how each type is allocated at runtime. We went into some of the implementation details for the Array, Dictionary, and Set collection types that are implemented in the Swift standard library.