set & membership
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. Sets are backed by a hash table, so membership (`x in myset`) is ~O(1), whereas scanning a list is O(n) -- that's why set membership is faster. 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). Sets support mathematical operations like union `|`, intersection `&`, and difference `-`.
Sets are optimized for two things: answering 'is this item 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 lists 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 dictionary, 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 dictionary to a set raises a `TypeError`. Use tuples 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 `{}`?
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 dictionary, not an empty set.
Python uses `{}` for dictionaries. To create an empty set, you must explicitly use the `set()` constructor.
Practice tasks
Find missing scopes
The `get_missing_scopes` function takes two lists of strings. 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: Mutable vs immutable types
Previous: Slicing