Sets
A Set is a data structure representing an unordered collection that contains any elements at maximum once. Elements can be any type (Int, String, Objects, …) but must be hashable (all primitive types implement this protocol). Sets don’t guarantee the ordering.
You will use a set when you don’t care about duplicates and are only interested in efficiently finding elements.
Internally, a set or HashSet is based on a dictionary; the key is the element and the value a Boolean. Then, you get all features of a dictionary plus the one specific to sets:
Insert: To add an element to the set call insert:
Remove: You can also remove an element that will be returned if present:
Iterate: Like all collections, you can easily iterate it:
Count: You can get the number of elements:
One of the great powers of the set is to compare with other sets.
Union: Returns a new set with the elements of both sets without duplicates.
Intersection: Returns a new set with the elements present in both sets.
Subtraction: Returns a new set with the elements from the first set which are not present in the second set.
Symmetric difference: Returns a new set with the unique elements from the first and second set but not the common ones.
Subset: Returns a Boolean indicating if all elements of the first set are present in the second set.
Equal: return a Boolean that indicates if the first set has the same elements as the second set.
Time complexity: (m quantity of first set and n quantity of the second set):
- Union: O(m+n) ,
- Intersection: O(m) // could also be O(min(n, m)),
- Subtraction: O(m),
- Symmetric difference: O(m+n),
- isSubset: O(m).
