Vector de droga - Dope vector

En la programación de computadoras , un vector de droga es una estructura de datos que se utiliza para contener información sobre un objeto de datos , especialmente su diseño de memoria .

Propósito

Los vectores dope se usan más comúnmente para describir matrices , que comúnmente almacenan múltiples instancias de un tipo de datos en particular como un bloque contiguo de memoria. Por ejemplo, una matriz que contiene 100 elementos, cada uno de los cuales ocupa 32 bytes, requiere 100 × 32 bytes. Por sí mismo, dicho bloque de memoria no tiene lugar para realizar un seguimiento de qué tan grande es la matriz (u otro objeto) en general, qué tan grande es cada elemento dentro de él o cuántos elementos contiene. Un vector de drogas es un lugar para almacenar dicha información. Los vectores de drogas también pueden describir estructuras que pueden contener matrices o elementos variables.

Si dicha matriz se almacena de forma contigua, con el primer byte en la ubicación de memoria M , entonces su último byte está en la ubicación M + 3199 . Una ventaja importante de esta disposición es que la ubicación del elemento N es fácil: comienza en la ubicación M + ( N × 32) . Por supuesto, se debe conocer el valor 32 (este valor se denomina comúnmente "paso" de la matriz o "ancho" de los elementos de la matriz). Navegar por una estructura de datos de matriz utilizando un índice se denomina navegación a estima .

Sin embargo, esta disposición (sin agregar vectores de droga) significa que tener la ubicación del elemento N no es suficiente para descubrir el índice N en sí mismo; o la zancada; o si hay elementos en N - 1 o N + 1 . Por ejemplo, una función o método puede iterar sobre todos los elementos de una matriz y pasar cada uno a otra función o método, que no sabe que el elemento es parte de una matriz en absoluto, y mucho menos dónde o qué tan grande es la matriz.

Sin un vector de droga, incluso conocer la dirección de toda la matriz no te dice qué tan grande es. Esto es importante porque escribir en el elemento N + 1 en una matriz que solo contiene N elementos probablemente destruirá algunos otros datos. Debido a que muchos lenguajes de programación tratan las cadenas de caracteres como una especie de matriz, esto conduce directamente al infame problema de desbordamiento del búfer .

Un vector de droga reduce estos problemas al almacenar una pequeña cantidad de metadatos junto con una matriz (u otro objeto). Con los vectores dope, un compilador puede insertar fácilmente (y opcionalmente) código que evita escribir accidentalmente más allá del final de una matriz u otro objeto. Alternativamente, el programador puede acceder al vector de droga cuando lo desee, por seguridad u otros propósitos.

Descripción

El conjunto exacto de metadatos incluidos en un vector de droga varía de un idioma y / o sistema operativo a otro, pero un vector de droga para una matriz puede contener:

  • un puntero a la ubicación en la memoria donde comienzan los elementos de la matriz (esto normalmente es idéntico a la ubicación del elemento cero de la matriz (elemento con todos los subíndices 0). (Este podría no ser el primer elemento real si los subíndices no comienzan en cero.)
  • el tipo de cada elemento de la matriz (entero, booleano, una clase particular , etc.).
  • el rango de una matriz .
  • la extensión de una matriz (su rango de índices). (En muchos idiomas, el índice inicial de las matrices se fija en cero o uno, pero el índice final se establece cuando la matriz se (re) asigna.)
  • para matrices en las que la extensión en uso en un momento dado puede cambiar, la extensión máxima y la actual pueden almacenarse.
  • el paso de una matriz , o la cantidad de memoria ocupada por cada elemento de la matriz.

Entonces, un programa puede referirse a la matriz (u otro objeto que use vector de droga) refiriéndose al vector de droga. Esto suele ser automático en lenguajes de alto nivel . Llegar a un elemento de la matriz cuesta un poquito más (comúnmente una instrucción, que busca el puntero a los datos reales fuera del vector dope). Por otro lado, hacer muchas otras operaciones comunes es más fácil y / o más rápido:

  • Sin un vector de droga, es imposible determinar el número de elementos en la matriz. Por lo tanto, es común agregar un elemento adicional al final de una matriz, con un valor "reservado" (como NULL). La longitud se puede determinar luego escaneando hacia adelante a través de la matriz, contando elementos hasta que se alcanza este "marcador de fin". Por supuesto, esto hace que la verificación de longitud sea mucho más lenta que buscar la longitud directamente en un vector de dope.
  • Sin conocer la extensión de una matriz, no es posible liberar () (desasignar) esa memoria cuando ya no se necesita. Por lo tanto, sin vectores de drogas, algo debe almacenar esa longitud en otro lugar. Por ejemplo, pedirle a un sistema operativo en particular que asigne espacio para una matriz de 3200 bytes, podría hacer que asigne 3204 bytes en alguna ubicación M; luego almacenaría el tamaño en los primeros 4 bytes y le diría al programa solicitante que el espacio asignado comienza en M + 4 (para que la persona que llama no trate los 4 bytes adicionales como parte de la matriz propiamente dicha). Estos datos adicionales no se consideran un vector de la droga, pero logran algunos de los mismos objetivos.
  • Sin vectores de droga, también se debe mantener información adicional sobre el paso (o ancho) de los elementos de la matriz. En C , esta información la maneja el compilador, que debe realizar un seguimiento de una distinción de tipo de datos entre "puntero a una matriz de elementos de 20 bytes de ancho" y "puntero a una matriz de elementos de 1000 bytes de ancho". Esto significa que un puntero a un elemento en cualquier tipo de matriz se puede incrementar o disminuir para llegar al elemento siguiente o anterior; pero también significa que los anchos de la matriz deben fijarse en una etapa anterior.

Incluso con un vector de droga, tener (solo) un puntero a un miembro particular de una matriz no permite encontrar la posición en la matriz, o la ubicación de la matriz o el vector de droga en sí. Si se desea, dicha información se puede agregar a cada elemento dentro de la matriz. Esta información por elemento puede ser útil, pero no forma parte del vector de la droga.

Los vectores de drogas pueden ser una instalación general, compartida entre múltiples tipos de datos (no solo matrices y / o cadenas).

Ver también

Referencias

  1. ^ Pratt, T .; Zelkowitz, M. (1996). Lenguajes de programación: diseño e implementación (3ª ed.). Upper Saddle River, Nueva Jersey : Prentice-Hall . pags. 114. ISBN   978-0-13-678012-0 .
  2. ^ Claybrook, Billy G. (13 al 15 de octubre de 1976). El diseño de una estructura de plantilla para una función de definición de estructura de datos generalizada . ICSE '76: 2º congreso internacional de ingeniería de software. San Francisco, California, EE.UU .: IEEE Computer Society Press. págs. 408–413.