Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 146 ยท Collections

Sets

Learn Swift Set - unique values, fast membership, insert and remove, union, intersection, subtracting, symmetric difference, subset tests, Hashable elements and custom types.

A set is a collection where every value appears at most once, and where the order of the values does not matter. That sounds like a restriction, but it is exactly what many problems ask for: the distinct tags on a blog post, the ids of users who are online, the letters already guessed in a word game, the permissions a user holds. In return for giving up order and duplicates, a set answers "is this value in here?" in roughly constant time, and it comes with a full set of mathematical operations: union, intersection, difference and subset tests.

This lesson covers creating sets, adding and removing, membership, the set algebra operations, comparing sets, and making your own types usable as set elements. If you have not read it yet, Collections Overview explains how Set relates to Array and Dictionary.

Creating a set

A set literal looks like an array literal, so Swift needs a hint that you want a Set: give the variable a type annotation, or call the initializer.

Swift Creating sets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Passing a sequence to Set(...) is the standard way to remove duplicates: the number of distinct letters in "mississippi" is four. The printed order of a set is unspecified and can change between runs, so the examples call sorted() before printing; do the same whenever your output must be reproducible.

Elements must be Hashable. The standard value types are: Int, String, Character, Bool and Double, and arrays or sets of hashable elements are hashable too. Tuples do not conform to Hashable, so wrap a pair of values in a small struct before putting it in a set.

Adding, removing and testing membership

insert adds a value and tells you whether it was new. remove returns the removed value or nil. contains is the membership test that sets are built for.

Swift insert, remove, contains

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

insert returns a tuple (inserted: Bool, memberAfterInsert: Element), and it is marked @discardableResult, so you can ignore it. The inserted flag is handy for detecting duplicates in one pass:

Swift Finding the first duplicate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

This does one hash lookup per element, O(n) overall, whereas comparing every pair in an array would be O(n squared).

Iterating

You can loop over a set with for ... in, and use map, filter and the rest of the sequence toolbox. Just remember that the order is arbitrary:

Swift Looping over a set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Note the difference: filter on a set returns a set, while map returns an array (the mapped values might collide, and a set of results would silently lose some).

Set algebra

This is what makes Set special. Four operations combine two sets, and each has a non-mutating form and a mutating form... form.

Operation Method Result
In either set a.union(b) everything from both
In both a.intersection(b) only the shared values
In a but not b a.subtracting(b) a without b's members
In exactly one a.symmetricDifference(b) values not shared
Swift The four set operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Read these as sentences. "Skills that both a frontend and a backend developer have" is intersection. "Skills only the frontend developer has" is subtracting. "Skills that exactly one of them has" is symmetricDifference. Writing the intent as a set operation is shorter and clearer than a nested loop with contains.

Comparing sets

Two sets are equal (==) when they contain the same elements, regardless of order. The relationship tests ask how two sets sit relative to each other:

Swift Subsets, supersets and disjoint sets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

isSubset allows equality; isStrictSubset demands that the other set has at least one extra element. Permission checks, feature flags and "has the user filled all required fields?" are all isSubset in disguise.

Using your own types in a set

A custom type can be a set element when it conforms to Hashable. For structs and enums whose stored properties are all hashable, the compiler writes the conformance for you: just add : Hashable.

Swift A struct in a Set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Visited-cell sets like this are the backbone of grid searches and graph traversals. If you forget the conformance, the error is explicit:

Swift A type that is not Hashable (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The compiler reports type 'Tag' does not conform to protocol 'Hashable'. Add : Hashable to the struct and the program compiles.

Writing hash(into:) by hand

When equality should ignore some properties, implement == and hash(into:) yourself. The rule is that equal values must produce equal hashes: hash exactly the properties == compares, or a subset of them.

Swift Custom equality and hashing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

If you violate the rule (equal values with different hashes), lookups fail in confusing ways: the set looks in the wrong bucket and misses an element it really contains. Also never use a mutable property in the hash of an object that lives inside a set: changing it afterwards strands the object in the wrong bucket.

Performance and when to choose a set

  • insert, remove and contains are O(1) on average; worst case O(n) with pathological hashes.
  • Sets use more memory than arrays and have no index, no first-in-order and no sorting in place.
  • Converting an array to a set costs O(n). Do it once if you will ask many membership questions, not once per question.
  • Use Set when uniqueness or membership is the point. Use Array when order or position matters; use Dictionary (Dictionaries) when each member needs an associated value.

For an ordered set (unique and in insertion order), the standard library has no type. Keep an array plus a set of seen values, as in firstDuplicate above, or use the array alone with contains for small sizes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does Set([1, 2, 2, 3, 3, 3]).count return?

    A set stores each distinct value once, so only 1, 2 and 3 remain.
  2. 2. Which method returns the elements that are in exactly one of two sets?

    symmetricDifference excludes values found in both sets; union includes everything, intersection only the shared values.
  3. 3. What must be true of a type used as a Set element?

    Hashing places each element in a bucket, which is how membership is checked in near constant time.
  4. 4. What does insert return when the value is already in the set?

    The result is (inserted: false, memberAfterInsert: the existing element).
  5. 5. What is the result type of someSet.map { $0 * 2 }?

    map always returns an Array. Use filter (which returns a Set) or build a Set from the result when needed.

Summary

  • A Set holds unique Hashable values in no particular order; sort before printing.
  • Create one with a type annotation or Set(sequence), which is also the quickest way to remove duplicates.
  • insert, remove and contains are O(1) on average; insert reports whether the value was new.
  • union, intersection, subtracting and symmetricDifference combine sets; each has a form... or mutating counterpart.
  • isSubset(of:), isSuperset(of:), isStrictSubset(of:) and isDisjoint(with:) compare sets.
  • Custom types need Hashable; equal values must have equal hashes.

Next: Dictionaries