Qu'est-ce qu'un set et quels problèmes résout-il ?

Question

Accepted Answer

Un **set** est une collection non ordonnée d'éléments **uniques**. Sa puissance principale est de répondre à "X est-il ici ?" en **O(1) en moyenne**, et il rejette automatiquement les doublons.

## Exemple

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

La plupart des sets sont implémentés comme des **hash sets** (une table de hachage stockant uniquement les clés), donc :

| Opération | Moyenne |
|---|---|
| add | O(1) |
| remove | O(1) |
| membership (`in`) | O(1) |

## Utilisations courantes

- **Déduplication** — supprimer les répétitions d'une liste en une ligne.
- **Appartenance rapide** — "ai-je déjà vu ceci ?"
- **Relations** — intersection/union/différence entre groupes.

## Pourquoi c'est important

Les sets rendent l'unicité et l'appartenance triviales et rapides, remplaçant les boucles imbriquées lentes sur les listes.

Une astuce courante lors d'entretiens — détecter les doublons ou les nœuds visités — se réduit à quelques opérations sur les sets.