# Sets

Source: https://codewiki.com/python/sets/

> - **what**: A `set` holds distinct hashable elements and models unique membership, membership tests, and operations such as union, intersection, and difference.
> - **trap**: Sets have no dependable iteration order, and equal objects with compatible hashes collapse into one member; converting a list to a set can lose both order and counts.
> - **fix**: Sort when output must be stable, use a list, dictionary, or `Counter` when order or counts matter, and confirm ownership before mutating a set.

## What it is and why it exists

A Python set is a collection of distinct hashable elements. A `set` is mutable and a `frozenset` is not; neither supports positional indexing or promises an iteration order. A set literal collapses duplicates automatically, but that collapse preserves only membership, not original positions or occurrence counts.

Sets solve questions about whether a value belongs to a group and how two groups of members combine. Permission names, feature flags, visited graph nodes, and the keys of two configurations are often natural sets. Order sequences, event logs, and rankings are not, because their order and repetitions carry information.

Set operators turn error-prone nested loops into explicit algebra. `required - granted` means missing permissions, `old & new` means members shared by both sides, and `left ^ right` means members present on exactly one side. The expression states the relationship and makes you decide whether the result should be unique.

The boundary between sets and other common containers looks like this. “Unordered” does not mean that iteration must change every time; it means your program cannot treat an observed order as a contract.

| Property | `set` | `frozenset` | `list` |
| --- | --- | --- | --- |
| Elements are unique | Yes | Yes | No |
| Order is promised | No | No | Yes |
| Membership is mutable | Yes | No | Yes |
| Can be a set element | No | Yes | No |

## How it works

A set organizes membership with element hashes and equality. When inserting or looking up an object, Python obtains its hash and then checks equality at possible matches. Two objects represent the same member only when they compare equal and satisfy the matching-hash requirement; a hash collision alone does not incorrectly merge distinct objects.

Create a non-empty set with `{value1, value2}` and an empty set with `set()`, because `{}` means an empty dictionary. `set(iterable)` consumes an iterable and adds its members. A set comprehension, `{transform(item) for item in source if condition(item)}`, combines transformation, filtering, and deduplication in one construction.

### Construction and copying

A set literal evaluates its element expressions and then adds members according to hashing and equality. If an element is unhashable, construction raises `TypeError` immediately and does not return a partial set. A comprehension can likewise stop when one produced value is unhashable.

`set(source)` follows ordinary iteration rules instead of guessing business meaning for each container. A string yields characters, a dictionary yields keys, and dictionary views yield keys, values, or key-value pairs according to the view. The caller must decide whether the iterated unit is actually the intended set member.

- `set(existing_set)` creates a new mutable set.
- `frozenset(existing_frozenset)` may return the same immutable object.
- `set(mapping)` collects mapping keys, not values.
- Set construction is shallow and does not copy member objects.

Shallow construction means membership in the new and old sets can change independently, while both may still reference the same member objects. Built-in mutable containers cannot be such shared members because they are unhashable; custom instances with default identity hashing can still create this aliasing relationship.

### Mutating membership

Mutation methods on `set` affect the original object. Every alias to that object observes the change, so establish ownership before choosing an in-place method.

| Operation | Meaning | Behavior when a member is absent |
| --- | --- | --- |
| `items.add(value)` | Add one member | Not applicable |
| `items.update(values)` | Add members from one or more iterables | Not applicable |
| `items.remove(value)` | Delete the specified member | Raises `KeyError` |
| `items.discard(value)` | Delete the specified member | Does nothing |
| `items.pop()` | Delete and return an arbitrary member | Raises `KeyError` on an empty set |
| `items.clear()` | Delete every member | Not applicable |

Use `remove()` when “the member must exist” is an invariant, because absence exposes a defect. Use `discard()` for idempotent cleanup, where repeated deletion should reach the same final state. `pop()` returns an arbitrary member; it is not a queue or stack operation.

### Set algebra

The four binary operations return new sets and leave both operands unchanged. Difference is directional; symmetric difference is not.

| Expression | Method form | Result |
| --- | --- | --- |
| `left | right` | `left.union(right)` | Members in either set |
| `left & right` | `left.intersection(right)` | Members shared by both sets |
| `left - right` | `left.difference(right)` | Members only on the left |
| `left ^ right` | `left.symmetric_difference(right)` | Members on exactly one side |

The corresponding `update()`, `intersection_update()`, `difference_update()`, and `symmetric_difference_update()` methods mutate their receiver. The `|=`, `&=`, `-=`, and `^=` operators also express in-place mutation. Unless a function's contract permits changing an input set, prefer returning a new one.

### Relations and operands

`left <= right` tests for a subset and `left < right` for a proper subset; `>=` and `>` test for a superset and proper superset. `left.isdisjoint(right)` returns `True` when the sides share no member. Sets define a partial order, so `sorted()` orders elements while `<` does not perform lexicographic comparison.

Method and operator forms accept different operands. `items.intersection(sequence)` can consume any iterable, while `items & sequence` requires another set type. This lets methods avoid an unnecessary conversion and lets operators expose code that accidentally treats a list as a set.

When a binary operation mixes `set` and `frozenset`, the result follows the left operand's type. `mutable | frozen` produces a `set`, while `frozen | mutable` produces a `frozenset`. If the result must later serve as a dictionary key or set member, put the immutable set on the left or construct a `frozenset` explicitly.

### Choosing `set` or `frozenset`

Use `set` when members need to be granted, revoked, or synchronized incrementally. Use `frozenset` when membership must not change after construction, or when the collection itself must be a dictionary key or set element. Freezing prevents membership changes but does not recursively copy or freeze member objects.

Both types support the same non-mutating operations and relation tests. Exposing public configuration as a `frozenset` can say “callers cannot add or remove members through this interface,” but it does not replace domain validation or make objects referenced by the members read-only.

## Examples

These four examples move from basic construction to difference calculation, policy checks, and immutable sets. Whenever a set's contents are displayed, the code sorts them first, so the recorded output does not depend on this process's set iteration order.

### Deduplication and membership

This example converts visit records into a set of unique customer IDs. The original list still retains request counts and arrival order; the set handles only unique membership and membership tests.

<!-- quick -->

```python
# file: unique_customers.py
visits = [
    "c-101",
    "c-102",
    "c-101",
    "c-103",
    "c-102",
    "c-104",
]

unique_customer_ids = set(visits)

# Sort output instead of depending on set iteration order.
print("requests:", len(visits))
print("unique customers:", sorted(unique_customer_ids))
print("c-103 seen:", "c-103" in unique_customer_ids)

empty_customer_ids = set()
print("empty type:", type(empty_customer_ids).__name__)
```

```text
requests: 6
unique customers: ['c-101', 'c-102', 'c-103', 'c-104']
c-103 seen: True
empty type: set
```

<!-- /quick -->

`len(visits)` is six because the list retains duplicate requests; `len(unique_customer_ids)` would be four. The containers answer different questions, so do not overwrite the original list before counting is complete.

The empty set uses `set()`. If it were written as `{}`, the final line would show `dict`, and the type error would appear only when later code first called `add()`.

### Calculating a deployment diff

Set differences model a transition between desired and current state. Putting direction in the variable names and expressions communicates the next action more clearly than retaining one symmetric difference alone.

```python
# file: deployment_diff.py
deployed = {"search", "billing", "profile"}
desired = {"billing", "profile", "reports"}

added = desired - deployed
removed = deployed - desired
unchanged = deployed & desired
changed = deployed ^ desired

# These operations return new sets and leave both inputs unchanged.
print("added:", sorted(added))
print("removed:", sorted(removed))
print("unchanged:", sorted(unchanged))
print("changed:", sorted(changed))
print("reports ready:", {"billing", "reports"} <= desired)
```

```text
added: ['reports']
removed: ['search']
unchanged: ['billing', 'profile']
changed: ['reports', 'search']
reports ready: True
```

`desired - deployed` gives services to add, while the reverse difference gives services to remove. `changed` answers “which members differ” but cannot by itself tell a deployer whether to add or remove each one.

The final `<=` tests whether a group of dependencies is included in the desired state. It allows the two sets to be equal; use the proper-subset operator `<` only when the business rule also requires the right side to contain another service.

### Checking an access policy

This function converts inputs to sets at its boundary, then computes missing and conflicting permissions separately. It returns sorted lists so logs, tests, and API responses remain stable.

```python
# file: access_policy.py
def evaluate_access(granted, required, blocked):
    granted_set = set(granted)
    required_set = set(required)
    blocked_set = set(blocked)

    missing = required_set - granted_set
    conflicts = granted_set & blocked_set
    return {
        "missing": sorted(missing),
        "conflicts": sorted(conflicts),
        "allowed": not missing and not conflicts,
    }


result = evaluate_access(
    ["invoice.read", "invoice.export", "account.suspend"],
    ["invoice.read", "invoice.refund"],
    ["account.suspend"],
)

print("missing:", result["missing"])
print("conflicts:", result["conflicts"])
print("allowed:", result["allowed"])
```

```text
missing: ['invoice.refund']
conflicts: ['account.suspend']
allowed: False
```

`required_set - granted_set` retains direction: it lists only what the caller lacks. Symmetric difference would also include extra permissions that are not forbidden, changing the policy's meaning.

The function does not mutate any of its three inputs. Even when a caller passes a set, `set(...)` at the boundary creates a shallow copy, so later internal mutation would not leak back to the caller.

### Modeling an unordered combination with `frozenset`

An undirected combination has no first and second member. A `frozenset` expresses unordered, unique, immutable membership and can therefore serve directly as a mapping key.

```python
# file: frozen_groups.py
route_owners = {
    frozenset({"billing", "exports"}): "finance-platform",
    frozenset({"search", "catalog"}): "discovery",
}

requested_route = frozenset({"exports", "billing"})
print("owner:", route_owners[requested_route])

mutable_group = {"billing"}
frozen_group = frozenset(mutable_group)
mutable_group.add("audit")

print("frozen:", sorted(frozen_group))
print("mutable:", sorted(mutable_group))
print("mixed type:", type(frozen_group | {"audit"}).__name__)
print("equivalent count:", len({True, 1, 1.0}))
```

```text
owner: finance-platform
frozen: ['billing']
mutable: ['audit', 'billing']
mixed type: frozenset
equivalent count: 1
```

Constructing `frozen_group` copies membership at that point, so changing `mutable_group` later does not affect it. The mixed operation has a `frozenset` left operand, so its result remains a `frozenset`.

The final line shows that sets depend on equality and hashing, not type names. `True == 1 == 1.0`, and these numeric values satisfy the equal-hash requirement, so the set retains only one member.

## Pitfalls

### Creating an empty set with `{}`

> **Pitfall:** `{}` always creates a dictionary. Code may survive initialization and fail only when it first calls a set method.

**Fix:** use `set()` and test empty input when the type affects control flow. A non-empty `{member}` is a set literal; a dictionary literal contains a colon, as in `{"id": 1}`.

### Treating “immutable” as “hashable”

> **Pitfall:** “Only immutable objects can enter a set” is a rough mnemonic, not Python's rule. A tuple containing a list is still unhashable, while a user-defined class instance may be hashable by default even when its attributes can change.

**Fix:** apply the hashability protocol: an object's hash must remain stable over its lifetime, and equal objects must have equal hashes. Use `frozenset` for nested member sets; for structured records, choose an explicit, stable immutable key instead of wrapping the outer value in a tuple blindly.

### Treating iteration order as an output contract

> **Pitfall:** Small sets often display in an apparently stable order, so generated code writes `list(a_set)` directly to JSON, snapshots, or test expectations. The language contract does not promise that order.

**Fix:** use `sorted(a_set)` for comparable elements and supply an explicit key when elements are not directly comparable. When first-occurrence order matters, traverse the original sequence while tracking seen keys in a helper set; do not convert the whole sequence first.

### Reversing a difference or mutating in place

> **Pitfall:** `current - desired` and `desired - current` answer opposite questions, while `current -= desired` also changes the original set that a caller may share. Short variable names hide both mistakes.

**Fix:** use directional names such as `added = desired - current` and `removed = current - desired`. Default to non-mutating operators for externally supplied sets; use an update operation only when the contract transfers ownership or permits mutation.

### Changing set size during iteration

> **Pitfall:** Calling `add()`, `remove()`, or `discard()` on `members` inside `for member in members` changes the same set's size and raises `RuntimeError`. Mechanically replacing `remove()` with `discard()` does not repair invalidated iteration.

**Fix:** build a new result with a set comprehension, calculate members to delete before a difference update, or iterate over `members.copy()`. Keep `remove()` when unexpected absence should surface; use `discard()` only when absence is valid.

### Losing counts and equal types

> **Pitfall:** `set(records)` does more than delete duplicate rows. It also discards occurrence counts and can merge equal values such as `True`, `1`, and `1.0` into one member.

**Fix:** state the uniqueness key and required output first. Use `collections.Counter` for counts; traverse the source and maintain `seen_keys` to retain the first record by a business key; include a type tag in the key when equal cross-type values must remain distinct.

<!-- deep -->

## Hashing and equality

A hashable object supplies a hash value that stays unchanged during its lifetime and can participate in equality comparisons. Objects that compare equal must return the same hash, but the converse is not true: distinct objects may have a hash collision. Sets continue with equality checks after hash-based location to distinguish them.

“Immutable built-ins are usually hashable” is more accurate than “immutable means hashable.” Numbers, strings, and tuples containing only hashable members can enter a set; mutable containers such as lists and dictionaries cannot. A tuple has no mutating methods, but it is still unhashable when it contains a list.

User-defined classes add another constraint. Instances normally start with identity-based hashing and equality; once a class implements field-based `__eq__()`, it must design a consistent `__hash__()` with it. Never mutate fields involved in hashing or equality after an object has become a set member, or lookup and removal may no longer find an object that is logically still present.

Sets ask whether values are equal, not whether their types match. `bool` is a subclass of `int`, so `True` compares equal to `1`; integer `1` also compares equal to floating-point `1.0`. They satisfy the same-hash requirement and therefore form one member in a set. If the domain must distinguish these inputs, a composite key such as `(type(value), value)` can do so, after confirming that type objects are the intended domain tags.

The immutability of `frozenset` covers only membership: no member can be added or removed after construction. Every member must still be hashable. A custom instance that uses identity hashing may have mutable attributes, so a `frozenset` does not guarantee deep immutability of an object graph.

Set equality compares only members, not mutability. A `set` and `frozenset` with the same members can compare equal, but only the `frozenset` can be a mapping key or set member. Choose between them based on ownership and later use, not because they represent different mathematical values.

## Set-shaped data boundaries

Sets work best as an internal model of relationships, while external inputs and outputs are usually sequences or objects. Boundary code must decide how to handle duplicates, order, errors, and ownership; calling `set(...)` is an implementation choice, not a complete data contract.

### Normalizing input

Validating before deduplication and deduplicating first produce different results. If duplicate permissions indicate a configuration error upstream, immediate set conversion hides that defect; if repeated events contribute to a count, conversion permanently loses it. Deduplicate at the boundary only when repetition truly has no domain meaning.

Normalization should also happen before building the set. Email addresses, file extensions, or case-insensitive identifiers may need whitespace removal and case normalization first. Otherwise, syntactically different but domain-equivalent inputs become distinct members.

- State whether empty input is a valid empty set or missing configuration.
- State whether duplicates are merged, counted, or rejected.
- State rules for case, whitespace, and Unicode normalization.
- Report unhashable or malformed members before conversion.

An error should identify the original input position instead of forwarding only `unhashable type`. Enumerating and validating records before set construction usually gives better diagnostics than parsing, transforming, and deduplicating inside one comprehension.

### Stable external representations

JSON has no native set representation because JSON arrays are ordered and permit duplicates. When exposing a set as an array, an API must add an ordering rule: sort by value, sort by a domain key, or preserve first occurrence in a separate source sequence. Clients should not infer the rule from one response.

| Boundary need | Suitable representation |
| --- | --- |
| Membership only | Internal `set` |
| Stable, comparable output | `sorted(members)` |
| First-occurrence order | Source sequence plus a `seen` set |
| Occurrence counts | `Counter` or an explicit mapping |
| Unordered combination as a key | Internal `frozenset` |

Cache keys need the same precision. A `frozenset` is a suitable in-process key when members are already hashable and an unordered combination is the business meaning; for cross-process storage, use a stable serialized form with explicit sorting and encoding rules, not Python's displayed set text.

### Return values and ownership

Returning an internal `set` gives the caller mutation capability. If the caller runs `clear()` or `|=`, it may also change the object that owns that internal set. Return a copy for snapshot semantics, or a `frozenset` for a read-only, hashable membership snapshot.

A returned copy isolates only outer membership; it does not copy member objects. When members have mutable attributes, the caller may still change shared state through those objects. An API must describe ownership of the set and ownership of member objects separately.

- Whether an argument will be mutated in place.
- Whether a return value aliases the internal set object.
- Whether the caller continues to own member objects.
- Which layer coordinates concurrent access.

Annotations such as `set[str]` and `frozenset[str]` communicate member types and mutability intent, but ordinary Python calls do not enforce them at runtime. External data still needs explicit validation, and internal interfaces still need aliasing and mutation tests.

### Choosing a uniqueness key

A whole record is often unhashable, and whole-record equality is rarely the business definition of a duplicate. A customer may be unique by normalized email, an order by order ID, or a file by content digest. When selecting a key, state which fields participate in equality and which record survives a conflict.

Order-preserving deduplication normally maintains a key set and a result list. For each record, compute and validate its key; when the key is new, add it to both `seen_keys` and the result. This shape retains first occurrence and leaves an explicit place to implement “keep last” or “reject duplicates” instead.

Do not verify uniqueness code only with ordinary strings. Empty strings, missing keys, case differences, collisions after normalization, and equality across Python types can all change the final member count. Tests should assert the conflict policy directly, not merely the result length.

<!-- /deep -->

[Checkpoint: python/sets](https://codewiki.com/python/sets/#checkpoint)

## Further reading

These are the Python 3.14 documentation pages used to verify this topic.

- [`set` and `frozenset` in the standard types reference](https://docs.python.org/3.14/library/stdtypes.html#set-types-set-frozenset)
- [Sets in the Python tutorial](https://docs.python.org/3.14/tutorial/datastructures.html#sets)
- [`hashable` in the Python glossary](https://docs.python.org/3.14/glossary.html#term-hashable)