À retenir
- Les doublons sont autorisés.
- L'ordre des éléments n'est pas conservé.
- On s'intéresse principalement à la présence et au nombre d'exemplaires de chaque élément.
En programmation, un sac (ou multiensemble) est une structure de données qui regroupe des éléments sans aucun ordre précis, tout en autorisant les doublons. C'est comme un véritable sac de courses : peu importe l'ordre des articles à l'intérieur, et vous pouvez très bien y avoir plusieurs briques de lait identiques.
Étymologie
Le terme est une métaphore directe de l'objet physique. En informatique, il traduit l'anglais bag. Il s'oppose au concept mathématique d'« ensemble » (set) qui, lui, n'autorise chaque élément qu'une seule fois.
Exemples d'usage
- La gestion d'un inventaire dans un jeu vidéo (posséder 5 potions de soin et 2 épées).
- Le comptage des occurrences de mots dans un document (le mot "code" apparaît 12 fois).
- Une corbeille d'achats avant l'étape du paiement.
Cas d'usage
On utilise cette structure lorsqu'on a besoin de stocker une collection d'objets où la quantité de chaque élément est importante, mais où leur position ou leur ordre d'arrivée n'a aucune influence sur le traitement des données.
Bonnes pratiques
Si vous devez souvent vérifier si un élément est présent ou compter ses occurrences, privilégiez une implémentation basée sur une Table de hachage (ou Dictionnaire) où la clé est l'objet et la valeur est son nombre d'apparitions. Cela sera bien plus performant qu'une simple liste non ordonnée.
Synonymes
Antonymes
Conseil
Pour bien comprendre, visualisez le sac comme un dictionnaire où chaque clé est associée à un compteur. Si vous débutez, ne confondez pas le 'sac' en tant que structure de données abstraite avec les tableaux classiques (arrays) qui, eux, sont ordonnés.
Questions fréquentes
Quelle est la différence entre un sac et un ensemble (set) ?
Un ensemble interdit les doublons (chaque élément est unique), alors qu'un sac permet d'avoir plusieurs fois le même objet.
Quelle est la différence entre un sac et une liste ?
Une liste retient l'ordre des éléments (premier, deuxième, etc.), tandis qu'un sac ne garantit aucune organisation spatiale des données.