Sets: operations and use cases
Overview
A `set` is an unordered collection of unique, hashable (having a hash value which never changes during its lifetime) elements. It is defined using curly braces `{1, 2, 3}` or the `set()` constructor. Unlike a `list`, a `set` automatically discards duplicate values and cannot be accessed by index. Think of a `set` like a VIP guest list: someone is either on the list or they aren't, but their exact position in line doesn't matter (unordered). Because sets are backed by a hash table, membership checks (`x in myset`) execute in `O(1)` time. This makes them significantly faster than scanning a `list` in `O(n)` time. Sets support powerful mathematical operations for comparing collections: - `|` (Union): Returns a new `set` containing all unique elements from both sets. - `&` (Intersection): Returns a new `set` containing only elements present in both sets. - `-` (Difference): Returns a new `set` containing elements in the first set but not the second. When removing elements, you must choose how to handle missing values. Sets provide two distinct methods: - `remove(x)`: Removes `x` from the `set`. Returns `None`. Raises a `KeyError` if `x` is missing. - `discard(x)`: Removes `x` from the `set` if present. Returns `None`. Never raises an exception if `x` is missing. This presents a common edge case where `remove()` crashes on missing elements: active_users = {"alice", "bob"} active_users.remove("charlie") # KeyError: 'charlie' active_users.discard("charlie") # Does nothing, succeeds Sets only accept hashable objects, meaning you cannot store mutable types like a `list` or `dict`: invalid_set = {[1, 2], [3, 4]} # TypeError: unhashable type: 'list' The relationship between mutability and hashing is covered fully in `collection-complexity`. Another dangerous edge case is attempting to modify a `set` while iterating over it. This will immediately crash your program: active_users = {"alice", "bob", "charlie"} for user in active_users: if user == "bob": active_users.remove(user) # RuntimeError: Set changed size during iteration To safely remove items during iteration, you must iterate over a copy of the collection instead.
Sets are optimized for two things: answering whether an item is in the collection instantly, and guaranteeing uniqueness. When you need to check if a user has a specific permission out of thousands, a `set` makes that check extremely fast compared to scanning a `list`.
Where used: API scope validation, Deduplicating database rows, Feature flags
Why learn this
- Deduplicating `list`s of IDs or tags automatically
- Fast permission and role checks (e.g., `if required_role in user_roles`)
- Finding commonalities or differences between two datasets using intersections and differences
Code walkthrough
user_roles = ['user', 'admin', 'user']
unique_roles = set(user_roles)
print(unique_roles)Focus: Notice how passing the `list` into `set()` instantly strips out the duplicate `'user'` entry.
Common mistakes
- Using {} for an empty set: `{}` creates an empty `dict`, not an empty `set`. To create an empty `set`, you must explicitly use `set()`.
- Trying to add mutable items: Set elements must be hashable. Trying to add a `list` or `dict` to a `set` raises a `TypeError`. Use `tuple` or `frozenset` instead.
- Assuming order is preserved: Sets do not preserve the order of elements you add to them. If you iterate over a `set`, the items will appear in an arbitrary order.
Glossary
- unordered collection
- A group of items that do not have a specific sequence or position, meaning you can't rely on their order. Example: `{3, 1, 2}`.
- deduplicating
- The process of removing duplicate or repeated items from a dataset so that only unique items remain. Example: `set([1, 1, 2])` gives `{1, 2}`.
Recall questions
- What happens if you try to add a duplicate element to a `set`?
- Why is it faster to check if an item exists in a `set` compared to a `list`?
- How do you create an empty `set`, and why can't you use `{}`?
- What is the difference between `remove()` and `discard()` when removing an item from a `set`?
- Why will your program crash if you remove items from a `set` during a standard `for` loop over it?
Understanding checks
What is the output of this code?
2
Sets automatically discard duplicate values. The resulting `set` is `{'user', 'admin'}`.
A developer writes `empty_set = {}` to initialize an empty `set`. Why is this incorrect?
Because `{}` creates an empty `dict`, not an empty `set`.
Python uses `{}` for `dict`ionaries. To create an empty `set`, you must explicitly use the `set()` constructor.
Practice tasks
Find missing scopes
The `get_missing_scopes` function takes two `list`s of `str`s. Modify it to return a `set` of scopes that are in `required_scopes` but NOT in `user_scopes`.
Challenge
Validate user permissions
You are building an API middleware that checks if a user has access to an endpoint. Write a function `has_access(user_roles, required_roles)` that takes two iterables. Return `True` if the user has ALL of the required roles, and `False` otherwise. Additionally, verify you don't use `list` operations.
Continue learning
Previous: Primitive types: int, float, bool, str
Previous: Mutable vs immutable objects
Previous: Lists: indexing, slicing, methods
Next: Time Complexity of Collection Operations