Sets: Beginner

Distinguish sets from lists

Lists preserve order and allow duplicates. When you add items to a list, they stay in the order you added them. You can access items by their position using indexing: list[0] gives you the first item, list[1] gives you the second, and so on. Lists allow the same value to appear multiple times. A list like [1, 1, 2, 2, 3] is perfectly valid and maintains all five elements.

The notation O(n) means that checking if an item is in a list takes time proportional to the list size. If the list has n items, you might need to check all n items in the worst case. A list with a million items requires up to a million comparisons. The notation O(1) means that checking if an item is in a set takes constant time regardless of set size. Whether the set has ten items or ten million items, the lookup takes approximately the same amount of time.

The O(1) membership test is the defining advantage of sets. It comes from hashing: Python converts each element into a number that directly points to its storage location, so no scanning is needed. This makes sets the right tool for membership checks in any performance-sensitive code.

Build sets from any iterable

The type() function confirms that these objects are sets. Python's set type is a built-in type, meaning it is always available without importing anything. Sets are as fundamental to Python as lists, dictionaries, and tuples.

There is one critical exception to the curly brace syntax that trips up many Python programmers. You cannot create an empty set with empty curly braces. When Python sees {}, it interprets this as an empty dictionary, not an empty set. This behavior exists for historical reasons: dictionaries were added to Python before sets, and {} was already established as the dictionary literal syntax.

This quirk catches even experienced Python developers. If you write code that initializes a variable with {} and later tries to use set methods like add(), you will get an AttributeError because dictionaries do not have an add() method. The error message might be confusing because you thought you had a set.

The set() constructor is versatile. It can convert any iterable object into a set. An iterable is anything you can loop over: lists, tuples, strings, ranges, and even other sets. This conversion automatically removes any duplicate values, which is often exactly what you want.

Strings are iterable in Python, meaning you can loop over their characters. When you pass a string to set(), Python treats it as a sequence of characters and creates a set containing each unique character. The string "mississippi" has eleven characters total, but only four unique letters: m, i, s, and p. The set contains exactly these four characters.

The constructor you choose determines everything about the resulting collection: whether it keeps duplicates, whether it maintains order, and whether it supports fast membership checks. set() is unique in that it both removes duplicates and provides O(1) lookups.

A common pattern is to convert a list to a set and back: list(set(my_list)). This deduplicates a list in one step, though the output order may differ from the input since sets do not guarantee ordering.

Deduplicate data with add and update

This approach iterates through the original list once. For each item, it checks whether the item has been seen before by checking the set. If not seen, it adds the item to both the seen set (for fast future lookups) and the unique_ordered list (to preserve order). If already seen, it skips the item. The first occurrence of each item is preserved in its original position.

In Python 3.7 and later, dictionaries preserve insertion order. The dict.fromkeys() method creates a dictionary where each item becomes a key (with None as the value). Since dictionary keys must be unique, duplicates are automatically eliminated while order is preserved. Converting back to a list gives you the deduplicated, ordered result.

Sets are mutable, meaning you can add elements after creation. Python provides two methods for adding elements: add() for single elements and update() for adding multiple elements at once. Understanding when to use each method helps you write cleaner, more efficient code.

The .add() method inserts exactly one element into the set. If the element already exists, the set remains unchanged and no error is raised. The .add() method modifies the set in place and returns None (not the modified set).

The .update() method adds multiple elements from any iterable (list, tuple, string, set, or other iterable). This is more concise and often more efficient than calling add() repeatedly in a loop.

Sets silently ignore duplicate insertions. Calling add() with a value that already exists is a no-op: the set remains unchanged and no error is raised. This makes sets ideal for collecting unique items in a loop without explicit duplicate checking.

For bulk additions, update() accepts any iterable: a list, tuple, another set, or even a string, which adds each character individually. If you need to add a list as a single element, convert it to a tuple first since lists are unhashable and cannot be stored in a set.

Remove elements and test membership

Python provides several methods for removing elements from sets: remove(), discard(), pop(), and clear(). Each behaves differently and is suited for different situations. Understanding these differences helps you choose the right method and avoid unexpected errors.

Both remove() and discard() delete a specific element from the set. The critical difference is what happens when the element does not exist. The remove() method raises a KeyError exception if the element is not found, while discard() silently does nothing.

In this example, discarding "mango" had no effect because mango was not in the set. No error was raised, and the set remained unchanged. If we had used remove("mango") instead, Python would have raised a KeyError exception, potentially crashing our program if we did not handle it.

The .pop() method removes and returns an arbitrary element from the set. Because sets are unordered, you cannot predict which element will be removed. This method is useful when you need to process elements one by one and do not care about the order, or when you need to empty a set while examining each element.

Calling pop() on an empty set raises a KeyError. Always ensure the set is not empty before popping, either by checking its length or using a while loop as shown above.

The .clear() method removes all elements from a set, leaving it empty. This is useful when you want to reset a set for reuse without creating a new set object.

The in operator checks whether an element exists in a set. This operation is one of the primary reasons to use sets: membership testing in sets is extremely fast, with O(1) time complexity. This makes sets ideal for situations where you need to check existence frequently.

The expression "alice" in allowed_users returns True because "alice" is a member of the set. The expression "eve" in allowed_users returns False because "eve" is not in the set. The not in operator returns the logical opposite: True if the element is absent, False if present.

A common optimization pattern is to convert a list to a set when you need to perform many membership tests against it. The conversion has a one-time cost proportional to the list size, but each subsequent lookup is O(1). If you perform enough lookups, the time saved far exceeds the conversion cost.

In real applications, valid_codes_list might contain thousands or millions of entries loaded from a database or configuration file. If you needed to validate millions of user inputs against this list, using a set instead of a list could reduce validation time from hours to seconds.

The code below has a bug related to membership testing. The developer tried to use the in operator with a list literal instead of a set, losing the O(1) performance advantage. Fix it to use a set.

Converting a list to a set is one of the most common and impactful performance optimizations in Python. The change is a single word in the source code, but it can reduce the time complexity of membership checks from O(n) to O(1), making code that scanned thousands of items per check effectively instant.

Sets work for membership testing because hashing gives each element a predictable storage address. When you check item in my_set, Python computes the hash of the item and checks one location directly, without scanning any other elements.

Identify which types sets accept

Mutable types like lists, dictionaries, and regular sets cannot be set elements because their hash values would change if modified. Python raises a TypeError if you try to add an unhashable type to a set.

Notice that True was "added" but the set size did not change. This is because Python considers True and 1 to be equal (and they have the same hash). Since 42 is already in the set and True equals 1 not 42, True just maps to the same slot. Mutable types like lists trigger a TypeError immediately.

The most common set mistake is trying to create an empty set with empty curly braces {}. Python interprets this as an empty dictionary, not an empty set. This mistake often leads to AttributeError exceptions later when you try to use set methods.

You cannot access set elements by index. Sets have no concept of "first element" or "element at position 2" because they have no order. Trying to index a set with square brackets raises a TypeError.

Using sorted() gives you a predictable ordering every time, unlike converting to an unsorted list where the order could vary. If you need indexed access often, store your data in a list instead of a set.

Adding or removing elements from a set while iterating over it can cause unexpected behavior or RuntimeError exceptions. If you need to modify a set based on its contents, iterate over a copy instead.