CITS2200 - Lecture 10

← Back to Home

CITS2200 - Lecture 9
Sets - Slides

Introduction to Sets

• A set is an unordered collection of objects $-$ no duplicates
• A multiset is a set-like container that allows duplicates
  • Also known as a bag
• A multimap $-$ associates values with keys, but the same key can be mapped to multiple values

Key Set ADT

• Common operations: add, discard, in, len, iter, remove, pop and clear

Operation	Description
S.add(e)	Add element e $-$ no effect if already present
S.discard(e)	Remove e if present — no error if missing
S.remove(e)	Remove e — raises KeyError if missing
e in S	Membership test → True / False
len(S)	Number of elements
iter(S)	Iterate over all elements
S.pop()	Remove and return an arbitrary element
S.clear()	Remove all elements

Discard vs Remove

Use discard() when you don’t care if the element exists. Use remove() when its absence should be treated as an error.

Boolean Set Operations

Operation	Description
S == T	True if S and T have identical contents
S != T	True if S and T are not equivalent
S <= T	True if S is a subset of T
S < T	True if S is a proper subset of T (S ≤ T and S ≠ T)
S >= T	True if S is a superset of T
S > T	True if S is a proper superset of T
S.isdisjoint(T)	True if S and T share no elements

Proper vs Regular Subset

A proper subset means S ⊂ T but S ≠ T — T must have at least one extra element.

Update Operations

Operation	Type	Description
S ｜ T	Returns new set	Union — all elements from S and T
S ｜= T	Modifies S	Update S to be the union of S and T
S & T	Returns new set	Intersection — elements in both S and T
S &= T	Modifies S	Update S to be the intersection of S and T
S ^ T	Returns new set	Symmetric difference — elements in exactly one of S or T
S ^= T	Modifies S	Update S to become the symmetric difference of itself and T
S - T	Returns new set	Difference — elements in S but not T
S -= T	Modifies S	Update S to remove all elements it shares with T

Quick Examples:

S = {1, 2, 3}
T = {2, 3, 4}
 
S | T   # {1, 2, 3, 4}  — union
S & T   # {2, 3}        — intersection
S ^ T   # {1, 4}        — symmetric difference (NOT in both)
S - T   # {1}           — difference (in S, not T)

In-place vs new set

S |= T modifies S directly. S | T returns a new set and leaves S unchanged.

---

CITS2200 - Lecture 11