Tampon d'espacement - Gap buffer

Un tampon d'espacement en informatique est un tableau dynamique qui permet des opérations d'insertion et de suppression efficaces regroupées près du même emplacement. Les tampons d'espacement sont particulièrement courants dans les éditeurs de texte , où la plupart des modifications apportées au texte se produisent à ou près de l'emplacement actuel du curseur . Le texte est stocké dans une grande mémoire tampon en deux segments contigus, avec un espace entre eux pour insérer un nouveau texte. Le déplacement du curseur implique la copie de texte d'un côté de l'espace à l'autre (parfois la copie est retardée jusqu'à l'opération suivante qui change le texte). L'insertion ajoute un nouveau texte à la fin du premier segment; la suppression le supprime.

Le texte dans un tampon d' espacement est représenté par deux chaînes , qui prennent très peu d'espace supplémentaire et qui peuvent être recherchées et affichées très rapidement, par rapport à des structures de données plus sophistiquées telles que les listes chaînées . Cependant, les opérations effectuées à différents endroits dans le texte et celles qui comblent le vide (nécessitant la création d'un nouveau vide) peuvent nécessiter la copie de la majeure partie du texte, ce qui est particulièrement inefficace pour les fichiers volumineux. L'utilisation de tampons d'écart est basée sur l'hypothèse qu'une telle recopie se produit rarement suffisamment pour que son coût puisse être amorti sur les opérations bon marché les plus courantes. Cela fait du tampon d'espacement une alternative plus simple à la corde à utiliser dans les éditeurs de texte tels qu'Emacs .

Exemple

Voici quelques exemples d'opérations avec des lacunes de tampon. L'écart est représenté par l'espace vide entre les crochets. Cette représentation est un peu trompeuse: dans une implémentation typique, les points d'extrémité de l'écart sont suivis à l'aide de pointeurs ou d'indices de tableau, et le contenu de l'écart est ignoré; cela permet, par exemple, de faire des suppressions en ajustant un pointeur sans changer le texte dans le tampon. C'est une pratique de programmation courante d'utiliser un intervalle semi-ouvert pour les pointeurs d'intervalle, c'est-à-dire que le début de l'intervalle pointe vers le caractère invalide suivant le dernier caractère du premier tampon, et la fin de l'intervalle pointe vers le premier caractère valide dans le deuxième tampon (ou de manière équivalente, les pointeurs sont considérés comme pointant "entre" les caractères).

Etat initial: 

This is the way [                     ]out.

L'utilisateur insère un nouveau texte: 

This is the way the world started [   ]out.

L'utilisateur déplace le curseur avant "commencé"; le système déplace "démarré" du premier tampon vers le deuxième tampon. 

This is the way the world [   ]started out.

L'utilisateur ajoute du texte remplissant le vide; le système crée un nouvel écart: 

This is the way the world as we know it [                   ]started out.

Voir également

Les références

Liens externes