Sets

A set is an unordered collection of unique elements. It can very efficiently add, remove, or check if it contains a specific element (on average O(1), meaning it takes the same time regardless of the size of the set), in contrast to an unsorted array, where these operations take O(n) (the array may need to access and/or move most of its element).

Sets can be used for tracking which part of a custom view should be hidden, like which parts of an outline view are collapsed. When displaying the view, you would only show the children of those nodes which are not in the collapsed set. So, you are in a sense adding a Bool property to types you do not control. Sets can also be used for removing duplicates; you just add a sequence to an empty set and all duplicates will be gone.

Have a look at the following diagram to get a view on sets:

• Equatable means you can check if instances are equal with a == b or not equal with a != b. Each type defines for itself what equal means, and it doesn't necessarily mean identical.
• Hashable types have an integer property hashValue, which dictionaries and sets (among others) use to quickly find instances. Values that are equal always have the same hashValue.
• SetAlgebra has some mathematical set operations such as intersection, union, and subtraction.

Note

A Set is a Collection which has its own index type, but since Set is unordered, we hardly ever have a need for it.

All types used in a set have to conform to the Hashable protocol:

A lot of other types conform to Hashable as well (https://developer.apple.com/documentation/swift/hashable#adopted-by).

Working with Sets

Let's look at working with sets by following these steps:

1. To create a set, we can do this:

   var numbers: Set = [0,1,2,3,10,2.75,-3,-3.125,-14]

2. We can then print it like this:

   // order is not preserved
   print(numbers) // [-3.125, 10.0, 2.75, 2.0, -3.0, 3.0, -14.0, 0.0, 1.0]

3. To insert a value if nothing equal is already there, we can do this:

   // insert if nothing equal is already there
   numbers.insert(4)

4. To insert a value and replace it if something equal is already there, we can do this:

   // insert, and replace it if something equal is already there
   numbers.update(with: 4)

5. Here are some more common operations with sets:

   numbers.remove(4)
   numbers.contains(3)
   numbers.isEmpty
   
   for n in numbers {
     // ...
   }

Combining Sets

Have a look at the following code:

extension Double {
  var isInteger: Bool { return self.truncatingRemainder(dividingBy: 1) == 0 }
}

let negativenumbers = numbers.filter { $0 < 0 }
let positivenumbers = numbers.subtracting(negativenumbers.union([0]))

let integers = numbers.filter { $0.isInteger }
let negativeintegers = integers.intersection(negativenumbers)
print(negativeintegers) // [-3.0, -14.0]

Here's what this code does:

• union combines two sets
• intersection returns the elements both sets have in common
• symmetricDifference returns elements that are in either of the two sets, but not in both
• subtracting returns elements of the first set that do not occur in the second set

All of these have mutating versions that change the first set in-place (they all start with form, except for subtract. For more information, check out: https://swift.org/documentation/api-design-guidelines/#name-according-to-side-effects.)

Comparing Sets

Have a look at the following code:

// all of the following return "true"
numbers.isSuperset(of: negativeintegers)
integers.isSubset(of: numbers)
positivenumbers.isStrictSubset(of: numbers)
numbers.isStrictSuperset(of: negativenumbers)
negativenumbers.isDisjoint(with: positivenumbers)

Set A is a superset of set B if every member of B is also a member of A. This also makes B a subset of A. These are strict supersets/subsets if A contains at least one element that is not a member of B. In other words: a strict superset or subset means that the two sets are not equal. Disjoint means the two sets have no elements in common.

In this section, we have looked at sets in detail. Sets are useful in various situations, for example, removing duplicates. We'll see this in an activity next.

Activity B: Removing Duplicates from a Sequence

The most common method of removing duplicates from a sequence is to just add the entire sequence to a set, and then create a new sequence from the set. However, this might re-order the remaining elements. Here, we will use filter to keep the original order, and use a set to keep track of which values are already in the sequence.

By adding the method as an extension to Sequence, it can be used by any collection type, including Array, Dictionary, and Set (though it would be rather pointless to use it on dictionaries and sets, as they are already duplicate-free).

To use an Xcode playground to create a method which removes duplicates from a sequence while preserving the order of the remaining values.

1. Open the CollectionsExtra Xcode project we used earlier, and go to Set.swift.
2. Paste the following code here:

   extension Sequence where Element: Hashable {
     /// Returns an array containing each element in `self` only once, in the same order.
     public func removeDuplicates () -> [Element] {
       var originals = Set<Element>(minimumCapacity: underestimatedCount)
       return self.filter { x in
         if originals.contains(x) {
           return false
         }
         originals.insert(x)
         return true
       }
     }
   }

   filter is a method of Sequence, which takes a function, Element -> Bool, and returns an array with only those elements for which the function returns true. In this function, we check if the element is already in the originals set. If it is, we return false (meaning the element will be dropped). If it is not in the set, we add it to it and return true, so the element will be included in the resulting array.

3. Go to SetTests.swift, uncomment the unit test, and run it.