Now serving...

set

Written by Jordan Morgan • Apr 18th, 2015

Things. Data. Models.

If ever there existed an absolute truth in programming, proclaiming that one’s code will have to store and retrieve things would be quite the worthy candidate. If we take that as gospel, then, it could only imply that the means in which we store such things is important.

Though many run straight to the array or dictionary, it would be a mistake to forget about the set. As of swift 1.2, it has returned to active duty. This week, we’ll spend time getting to know the useful and performant set collection.

Set<T>

struct Set<hashable>
A collection of unique T instances with no defined ordering.

Like all of swift’s collections, the set is defined to store instances of T. This is a universally accepted way of saying that one could store just about anything they wish within it — otherwise known as the power of generics. It also respects Objective-C, as it bridges without issue to Foundation’s NSSet.

There are a number of ways to initialize an instance of a set:

//Empty set  
let emptySet = Set()

//Empty set with a capacity defined  
let capacitySet = Set(minimumCapacity: 10)

//Set from an array literal  
let intSet = Set([1,2,3])

//Initialize from a sequence of items  
let oddNums = Set([1,3,5])  
let evenNums = Set([2,4,6])  
let allNums = Set(oddNums.union(evenNums))

As of now, there is not a way to initialize a set literal — a minor inconvience.

In Practice

A quick trip to your local Xcode’s playground file will show it’s usefulness for the visual learner:

let numArray = [1,2,3,3,2,1]  
for num in numArray  
{  
    println(num) //1,2,3,3,2,1  
}

let numSet = Set(numArray)  
for distinctNum in numSet  
{  
    println(distinctNum) //2,3,1  
}

One would be wise to notice that not only does the friendly set log out the three distinct values of each Int instance (which, if you weren’t aware, can do more than you think), it also was placed neatly on the heap with only those three distinct Ints upon initialization.

While you’re here, we might as well mention set’s slick wrapper for iteration. Calling its instance function generate will return a SetGenerator that will aid in looking things over:

//numSet from the previous code sample  
var intGenerator = numSet.generate()  
while let aNum = intGenerator.next()  
{  
    println(aNum) //2,3,1  
}

Let’s Talk Relationships

Though set contains the usual suspects for mutating or otherwise interacting with its elements (i.e. contains, insert, remove, etc.), it also has some useful functions to compare or combine data to boot.

For instance, you may have noticed the union function reveal itself earlier in this post:

//Init set with items in both this set and a finite sequence.  
func union <S : SequenceType where T == T>(sequence: S) -> Set<T>

Union is happy to combine things for you. For instance, should one be tasked with preparing the next family gathering (so sorry, by the way), union and set will dutifully sort all of your family members accordingly:

let immediateFamily = Set(["Jordan", "Jansyn", "Bennett"])  
let inlaws = Set(["Alicia","Justin","Johnny"])

//Alicia, Bennett, Jansyn, Johnny, Jordan, Justin  
println(sorted(immediateFamily.union(inlaws)))

Of course, checking for overlap, thankfully, is trivial as well. This is due in no small part to intersect:

//Init set with elements common to this set and a finite sequence  
func intersect <S : SequenceType where T == T>(sequence: S) -> Set <T>

Checking for overlap in family names has never been easier:

//[]  
println(immediateFamily.intersect(inlaws))

Another useful function set employs is the exclusiveOr:

//Init set with elements that are either in the set or a finite sequence but do not occur in both.  
func exclusiveOr<S : SequenceType where T == T>(sequence: S) -> Set<T>

In the event that your fictional family gathering includes siblings with the same names, don’t fret. Set’s exclusiveOr will bear the unique names from either family tree with ease:

//Unique names from both sets  
let firstFam = Set(["Jack","Jill","Jane"])  
let otherFam = Set(["Jack","Karl","Jane"])

//Karl, Jill  
println(firstFam.exclusiveOr(otherFam))

Comparing Membership

On the topic of comparing sets, you may find these functions particularly indispensable:

//True if the set is a subset of a finite sequence as a Set.  
func isSubsetOf<S : SequenceType where T == T>(sequence: S) -> Bool

//True if the set is a superset of a finite sequence as a Set.  
func isSupersetOf<S : SequenceType where T == T>(sequence: S) -> Bool

//True if no members in the set are in a finite sequence as a Set.  
func isDisjointWith<S : SequenceType where T == T>(sequence: S) -> Bool

The fine developers at Apple have provided a succinct and digestible code sample displaying these functions . This following example continues both their standard of providing excellent use cases and the implementation of emojis:

let houseAnimals: Set = ["🐶", "🐱"]  
let farmAnimals: Set = ["🐮", "🐔", "🐑", "🐶", "🐱"]  
let cityAnimals: Set = ["🐦", "🐭"]

//All evaluate to true  
houseAnimals.isSubsetOf(farmAnimals)  
farmAnimals.isSuperSetOf(houseAnimals)  
farmAnimals.isDisjointWith(cityAnimals)

As developers, there is no doubt that scenarios involving comparing and or combining data will occur. It’s simply a matter of when. Considering that, swift and the set have a fine array of tools to carry out such operations with both elegant syntax and efficiency out of the box functions.

Why & When

A common mistake often made as a programmer is to rely soley on what one knows. While arrays can handle most all of one’s needs, it’s important to ask yourself a series of questions before simply assigning a collection type.

For the set, it would be these two questions:

  • Do I care about the order of the items?
  • Do I want each element to be unique?

The set primarily excels over the array when it comes to looking up items. Due to its ability to utilize hash values when performing look ups, results come quickly and easily. The common array, though, must iterate to locate the element in need.

The TL;DR version? Think O(1) vs O(n).

Wrapping Up

True to its name, swift is constantly changing and evolving at a brisk pace. As developers, we know that learning is simply the cost of doing business. The set embodies a new collection that many will find several uses for, be it in languages past or new implementations in swift. Enjoy it, use it, and of course — may your weekend beJoyful.union(andProductive).

Spot any corrections or have anything to add?
Feel free to open an issue or create a pull request for this article.