Vecteurs avec trou

Le vecteur avec trou permet souvent de combiner les avantages de la liste (insertion et suppression au milieu) et ceux du vecteur (accès direct, peu de surcoût de stockage). C'est ce qu'utilise l'éditeur Emacs pour stocker les caractères d'un tampon (en Anglais : buffer).

Comme la liste et le vecteur, ce conteneur est utile pour stocker des éléments dont l'ordre est déterminé explicitement par des requêtes d'insertion et de suppression (et non par le fait que le domaine est ordonné par exemple). L'exemple typique est le tampon Emacs qui contient une suite d'éléments (caractères) dont l'ordre est fixé par l'utilisateur.

Pour qu'un vecteur avec trou soit rentable, il faut que les opérations d'insertion et de suppression d'un élément aient une distribution particulière. La probabilité que deux opérations consécutives soient proches (la différence des indices concernés par les opérations faible) doit être assez élevée. C'est évidemment le cas de Emacs : l'utilisateur travaille souvent dans une petite région du tampon. Il est relativement rare d'effectuer une insertion ou une suppression d'un caractère, puis d'en faire une autre à un endroit totalement différent du texte.

L'idée de base du vecteur avec trou est de diviser les éléments du conteneur en deux parties : les éléments qui précèdent le point probable de travail (insertion, suppression) et ceux qui lui succèdent. La première partie est stockée au début du vecteur et la deuxième partie à la fin du vecteur. Ceci laisse un trou dans le vecteur entre la première et la deuxième partie (voir figure 23.7).

Figure 23.7: Vecteur avec trou

Les opérations d'insertion et suppression se font toujours soit au début, soit à la fin du trou. En fait, après l'une de ces opérations, le trou représente la position actuelle d'insertion et de suppression (le point de Emacs). Si une opération d'insertion ou de suppression est souhaitée à un autre endroit que celui où se trouve le trou, celui-ci est d'abord déplacé. Cela nécessite un déplacement de tous les éléments entre la position actuelle du trou et la position souhaitée. Au pire, il s'agit de l'ensemble des éléments du vecteur. Cette opération peut donc coûter $O(n)$ où $n$ est le nombre d'éléments du vecteur. C'est la raison pour laquelle la probabilité que le trou nécessite un déplacement, doit être faible.

Le vecteur avec trou est un exemple de structure de données dont l'efficacité est probabiliste, c'est-à-dire que le comportement au pire des cas est relativement mauvais, mais en moyenne très bon. Un comportement probabiliste est souvent incompatible avec les systèmes temps-réel. Ce type de systèmes nécessite souvent de pouvoir borner le temps d'une opération par une valeur relativement faible.

L'analyse de la complexité asymptotique des opérations sur une structure de données probabiliste donne souvent des valeurs de complexité beaucoup trop pessimistes. Pour le vecteur avec trou, l'insertion et la suppression coûtent $O(n)$ (où $n$ est le nombre d'éléments du vecteur) au pire et la recherche d'un élément d'une table de hachage coûte $O(n)$ alors qu'en pratique elle ne coûte que $O(1)$. Il faut donc être prudent en ce qui concerne l'utilisation de la complexité asymptotique.