Vector de droga

En programación de computadoras , un vector de droga es una estructura de datos utilizada para contener información sobre un objeto de datos , ^[1] especialmente su diseño de memoria .

Objetivo

Los vectores Dope se usan más comúnmente para describir matrices , que comúnmente almacenan múltiples instancias de un tipo de datos particular como un bloque de memoria contiguo. Por ejemplo, una matriz que contiene 100 elementos, cada uno de los cuales ocupa 32 bytes, requiere 100 × 32 bytes. Por sí solo, dicho bloque de memoria no tiene lugar para realizar un seguimiento del tamaño total de la matriz (u otro objeto), del tamaño de cada elemento dentro de él o de 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 localizar el elemento N es fácil: comienza en la ubicación M + ( N × 32) . Por supuesto, se debe conocer el valor 32 (este valor se llama comúnmente "zancada" de la matriz o "ancho" de los elementos de la matriz). Navegar por una estructura de datos de matriz utilizando un índice se llama 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í; o el paso; 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 en absoluto que el elemento es parte de una matriz, 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 indica 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 vectores de droga, un compilador puede insertar fácilmente (y opcionalmente) código que evite 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 fines.

Descripción

El conjunto exacto de metadatos incluidos en un vector dope varía de un idioma y/o sistema operativo a otro, pero un vector dope 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 donde la extensión en uso en un momento dado puede cambiar, se pueden almacenar tanto la extensión máxima como la actual.
el paso de una matriz , o la cantidad de memoria ocupada por cada elemento de la matriz.

Luego, un programa puede hacer referencia a la matriz (u otro objeto que utilice un vector de droga) haciendo referencia al vector de droga. Esto suele ser automático en lenguajes de alto nivel . Llegar a un elemento de la matriz cuesta un poco más (comúnmente una instrucción, que recupera el puntero a los datos reales desde el vector de droga). Por otro lado, realizar muchas otras operaciones habituales es más fácil y/o rápido:

Sin un vector de droga, es imposible determinar el número de elementos de la matriz. Por tanto, es común agregar un elemento extra al final de una matriz, con un valor "reservado" (como NULL). Luego, la longitud se puede determinar escaneando hacia adelante a través de la matriz, contando elementos hasta alcanzar este "marcador final". Por supuesto, esto hace que la verificación de la longitud sea mucho más lenta que buscar la longitud directamente en un vector de droga.
Sin conocer la extensión de una matriz, no es posible liberar () (desasignar) esa memoria cuando ya no es necesaria. Por lo tanto, sin vectores de droga, 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 drogas, 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 anterior o siguiente; pero también significa que los anchos de las matrices deben fijarse en una etapa anterior.

Incluso con un vector de droga, tener (sólo) 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 droga.

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

Ver también

Referencias

^ Pratt, T.; Zelkowitz, M. (1996). Lenguajes de programación: diseño e implementación (3ª ed.). Upper Saddle River, Nueva Jersey : Prentice-Hall . pag. 114.ISBN 978-0-13-678012-0.
^ 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: 2da conferencia internacional sobre ingeniería de software. San Francisco, California, EE.UU.: IEEE Computer Society Press. págs. 408–413.