Vecteur de dopage - Dope vector

En programmation informatique , un vecteur de dopage est une structure de données utilisée pour contenir des informations sur un objet de données , en particulier sa disposition de mémoire .

Objectif

Les vecteurs Dope sont les plus couramment utilisés pour décrire les tableaux , qui stockent généralement plusieurs instances d'un type de données particulier sous la forme d'un bloc de mémoire contigu. Par exemple, un tableau contenant 100 éléments, dont chacun occupe 32 octets, nécessite 100 × 32 octets. En soi, un tel bloc de mémoire n'a pas de place pour garder une trace de la taille globale du tableau (ou d'un autre objet), de la taille de chaque élément qu'il contient ou du nombre d'éléments qu'il contient. Un vecteur de dopage est un endroit pour stocker ces informations. Les vecteurs dopés peuvent également décrire des structures qui peuvent contenir des tableaux ou des éléments variables.

Si un tel tableau est stocké de manière contiguë, avec le premier octet à l'emplacement de mémoire M , alors son dernier octet est à l'emplacement M + 3199 . Un avantage majeur de cette disposition est que la localisation de l'élément N est facile: elle commence à l'emplacement M + ( N × 32) . Bien entendu, la valeur 32 doit être connue (cette valeur est communément appelée la "foulée" du tableau ou la "largeur" ​​des éléments du tableau). La navigation dans une structure de données de tableau à l'aide d'un index s'appelle l' estime .

Cette disposition, cependant (sans ajouter de vecteurs de dopage) signifie que le fait d'avoir l'emplacement de l'item N ne suffit pas pour découvrir l'index N lui-même; ou la foulée; ou s'il y a des éléments à N - 1 ou N + 1 . Par exemple, une fonction ou une méthode peut parcourir tous les éléments d'un tableau et passer chacun d'eux à une autre fonction ou méthode, qui ne sait pas du tout que l'élément fait partie d'un tableau, encore moins où ou quelle est la taille du tableau.

Sans vecteur de dopage, même connaître l'adresse de l'ensemble du tableau ne vous dit pas quelle est sa taille. Ceci est important car l'écriture dans l' élément N + 1 dans un tableau qui ne contient que N éléments, détruira probablement d'autres données. Étant donné que de nombreux langages de programmation traitent les chaînes de caractères comme une sorte de tableau, cela conduit directement au tristement célèbre problème de dépassement de tampon .

Un vecteur de dopage réduit ces problèmes en stockant une petite quantité de métadonnées avec un tableau (ou un autre objet). Avec les vecteurs dope, un compilateur peut facilement (et éventuellement) insérer du code qui empêche l'écriture accidentelle au-delà de la fin d'un tableau ou d'un autre objet. En variante, le programmeur peut accéder au vecteur de dopage lorsqu'il le souhaite, pour des raisons de sécurité ou à d'autres fins.

La description

L'ensemble exact de métadonnées inclus dans un vecteur de dopage varie d'une langue et / ou d'un système d'exploitation à l'autre, mais un vecteur de dopage pour un tableau peut contenir:

  • un pointeur vers l'emplacement en mémoire où les éléments du tableau commencent (c'est normalement identique à l'emplacement de l'élément zéro du tableau (élément avec tous les indices 0). (Cela peut ne pas être le premier élément réel si les indices ne commencent pas à zéro.)
  • le type de chaque élément du tableau (entier, booléen, une classe particulière , etc.).
  • le rang d'un tableau .
  • l'étendue d'un tableau (sa plage d'indices). (Dans de nombreuses langues, l'index de départ des tableaux est fixé à zéro, ou à un, mais l'index de fin est défini lorsque le tableau est (ré) alloué.)
  • pour les tableaux où l'étendue utilisée à un moment donné peut changer, l'étendue maximale et l'étendue actuelle peuvent être toutes deux stockées.
  • la foulée d'un tableau , ou la quantité de mémoire occupée par chaque élément du tableau.

Un programme peut alors faire référence au tableau (ou à un autre objet utilisant un vecteur de dopage) en se référant au vecteur de dopage. Ceci est généralement automatique dans les langages de haut niveau . Accéder à un élément du tableau coûte un tout petit peu plus (généralement une instruction, qui récupère le pointeur vers les données réelles à partir du vecteur de dopage). D'un autre côté, effectuer de nombreuses autres opérations courantes est plus facile et / ou plus rapide:

  • Sans un vecteur de dopage, il est impossible de déterminer le nombre d'éléments dans le tableau. Ainsi, il est courant d'ajouter un élément supplémentaire à la fin d'un tableau, avec une valeur "réservée" (telle que NULL). La longueur peut ensuite être déterminée en balayant vers l'avant le réseau, en comptant les éléments jusqu'à ce que ce "marqueur de fin" soit atteint. Bien sûr, cela rend la vérification de la longueur beaucoup plus lente que la recherche de la longueur directement dans un vecteur de dopage.
  • Sans connaître l'étendue d'un tableau, il n'est pas possible de libérer () (désallouer) cette mémoire lorsqu'elle n'est plus nécessaire. Ainsi, sans vecteurs de dopage, quelque chose doit stocker cette longueur ailleurs. Par exemple, demander à un système d'exploitation particulier d'allouer de l'espace pour un tableau de 3200 octets peut l'amener à allouer 3204 octets à un emplacement M; il stockerait alors la taille dans les 4 premiers octets, et indiquerait au programme demandeur que l'espace alloué commence à M + 4 (de sorte que l'appelant ne traite pas les 4 octets supplémentaires comme faisant partie du tableau proprement dit). Ces données supplémentaires ne sont pas considérées comme un vecteur de dopage, mais atteignent certains des mêmes objectifs.
  • Sans vecteurs de dopage, des informations supplémentaires doivent également être conservées sur la foulée (ou la largeur) des éléments du tableau. En C , ces informations sont gérées par le compilateur, qui doit garder une trace d'une distinction de type de données entre "pointeur vers un tableau d'éléments de 20 octets" et "pointeur vers un tableau d'éléments de 1000 octets". Cela signifie qu'un pointeur vers un élément dans l'un ou l'autre type de tableau peut être incrémenté ou décrémenté afin d'atteindre l'élément suivant ou précédent; mais cela signifie également que les largeurs de tableau doivent être fixées à un stade antérieur.

Même avec un vecteur de dopage, le fait d'avoir (seulement) un pointeur vers un membre particulier d'un tableau ne permet pas de trouver la position dans le tableau, ni l'emplacement du tableau ou le vecteur de dopage lui-même. Si cela est souhaité, ces informations peuvent être ajoutées à chaque élément du tableau. Ces informations par élément peuvent être utiles, mais ne font pas partie du vecteur de dopage.

Les vecteurs dopés peuvent être une fonction générale, partagée entre plusieurs types de données (pas seulement des tableaux et / ou des chaînes).

Voir également

Références

  1. ^ Pratt, T .; Zelkowitz, M. (1996). Langages de programmation: conception et mise en œuvre (3e éd.). Upper Saddle River, NJ : Prentice-Hall . p. 114. ISBN   978-0-13-678012-0 .
  2. ^ Claybrook, Billy G. (13-15 octobre 1976). La conception d'une structure modèle pour une installation de définition de structure de données généralisée . ICSE '76: 2e conférence internationale sur le génie logiciel. San Francisco, Californie, États-Unis: IEEE Computer Society Press. pp. 408–413.