Sets

Picture a collection of numbered stickers. You put them in a bag and keep one rule: each sticker is in the bag once. When a second identical one turns up, it does not go in. The bag has no order: any sticker may end up on top.

In Swift such a collection is called a set: it stores values without repeats and without order. A set's values are listed in square brackets, like an array's, and the type is given by the annotation : Set:

var album: Set = [3, 7, 12]
album.insert(7)
album.insert(15)
print(album.count) // 4
print(album.contains(12)) // true
print(album.contains(5)) // false

Let's walk through the program line by line:

1. var album: Set = [3, 7, 12] creates a set of three stickers. Swift infers the element type itself, and the full type of album is Set<Int>, that is, a set of integers.
2. album.insert(7) changes nothing: sticker 7 is already there. There is no error either.
3. album.insert(15) adds a new sticker.
4. print(album.count) prints 4: the bag holds stickers 3, 7, 12 and 15.
5. contains checks whether a value is in the set: 12 is, and 5 is not.

Here the bag picture is inaccurate. You can put a second identical sticker into a real bag, and watching for repeats would be your job. A set watches for itself: it silently skips a repeat.

An empty set is created with its full type: var seen: Set<String> = [] or Set<String>().

Removing repeats from an array

A set is often built from an array to remove repeats. Set(pack) takes the elements of the array pack and keeps each value once:

let pack = [5, 3, 5, 9, 3]
let unique = Set(pack)
print(pack.count, unique.count) // 5 3

The pack holds five stickers, but only three of them differ: 5, 3 and 9. The array pack itself does not change: the set gets its own copy of the values.

A set has no order, so to print it in order you sort it. unique.sorted() returns the array [3, 5, 9].

Set operations

Anna and Boris collect the same sticker series and compare their albums. Sets have three operations for this, and each returns a new set:

let anna: Set = [1, 2, 5, 8]
let boris: Set = [2, 3, 5]
print(anna.union(boris).sorted()) // [1, 2, 3, 5, 8]
print(anna.intersection(boris).sorted()) // [2, 5]
print(anna.subtracting(boris).sorted()) // [1, 8]

union

anna.union(boris) is the union: every sticker that at least one of the two has. The shared 2 and 5 appear in it once each.

intersection

anna.intersection(boris) is the intersection: the stickers both of them have. Here that is 2 and 5.

subtracting

anna.subtracting(boris) is the difference: Anna's stickers that Boris does not have. Here that is 1 and 8, which Anna can offer him in a swap. The order matters in this operation: boris.subtracting(anna) gives only 3.

Why a set searches fast

Arrays have a contains method too, but it works differently. An array checks its elements in turn, from the first, until it finds the one it needs, and in a long array that takes a while. A set computes from the value itself where to look for it, and looks there instead of going through all the elements. A dictionary finds a key the same way.

That is why the elements of a set and the keys of a dictionary must be Hashable. Such a type can turn a value into a number, and the place is computed from that number. The Int, Double, String, Character and Bool you know all fit.

Interviewers like to ask how a Set differs from an Array. A good answer names three differences:

• an array keeps order and repeats, and a set keeps neither;
• an array's contains checks elements in turn, while a set looks straight in the right place;
• the elements of a set must be Hashable.

Common mistake

A set is declared without the : Set annotation:

var stickers = [3, 7, 12]
stickers.insert(15) // ✗

error: missing argument for parameter 'at' in call

Without : Set, square brackets create an array [Int]. Arrays have an insert too, but it needs a place to insert at: insert(15, at: 0). The compiler doesn't know a set was meant, so it asks for the missing place. The fix is var stickers: Set = [3, 7, 12].

Key points

• A Set stores values without repeats and without order; the square brackets need the : Set annotation, or you get an array.
• insert skips a repeat, contains checks for a value, and Set(array) collects an array's values without repeats.
• union, intersection and subtracting return a new set: everything together, what is shared, and the difference.
• The elements of a set, like the keys of a dictionary, must be Hashable, so a set's contains does not check elements in turn.