Organisation des conteneurs

Les différents types de conteneurs ont leurs avantages et leurs inconvénients en terme de performance et de consommation de la mémoire. De plus, certains conteneurs sont utilisables ou non selon le domaine des objets stockés.

Une séquence (liste ou vecteur) est utilisable pour des domaines ordonnés, c'est-à-dire que les objets du domaine ont un ordre, soit une ordre naturel, soit un ordre imposé par l'application.

Un exemple de domaine naturellement ordonné est celui des nombres réels ou encore n'importe quel autre domaine dont les éléments peuvent être mis en correspondance avec les nombres réels. Le domaine des personnes, par exemple, est facile à associer aux réels, si l'on considère la taille ou le poids de la personne comme étant la clé pour déterminer l'ordre. Il faut, bien sûr, que la clé choisie soit pertinente pour l'application.

Il est aussi possible de trouver un ordre sans explicitement faire correspondre le domaine aux réels. Pour les personnes, par exemple, il est possible de trouver un ordre déterminé par l'ordre lexicographique sur les noms.

Il est possible d'imposer un ordre artificiel sur un domaine qui n'en a pas naturellement. L'utilisation de numéros de sécurité sociale ou de numéros de comptes bancaires en est un exemple. C'est aussi une façon d'introduire une clé unique utilisable pour la recherche d'éléments dans des conteneurs.

Mais une séquence n'est pas forcément utilisée pour stocker des objets d'un domaine ordonné (naturellement ou artificiellement). Avec une séquence, on peut imposer un ordre utile pour l'application. Prenons un tampon Emacs utilisé pour stocker les caractères d'un document. Ce tampon est un exemple de séquence. Alors que les caractères appartiennent à un domaine ordonné, ce n'est pas cet ordre qui est utilisé (heureusement). C'est l'ordre déterminé par la volonté de l'utilisateur de former des mots et des phrases qui est utilisé.

Un arbre est un autre type de conteneur utilisable pour des domaines ordonnés. Il y a plusieurs façons d'organiser un arbre suivant les opérations qu'on désire effectuer. Couramment, l'arbre est binaire et tel que le sous-arbre gauche contient des éléments tous de rang inférieur aux rangs des éléments du sous-arbre droit. D'autres façons existent, notamment le tas où les fils d'un nud sont de rang supérieur à celui du parent. On peut également utiliser les arbres pour des domaines non ordonnés, comme pour l'arbre union-find.