Vector de droga

En programación informática , un vector dope es una estructura de datos utilizada para almacenar información sobre un objeto de datos , ^[1] especialmente su diseño de memoria .

Los vectores dope se utilizan con mayor frecuencia para describir matrices , que suelen almacenar 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í solo, un bloque de memoria de este tipo 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 ella o cuántos elementos contiene. Un vector dope es un lugar para almacenar dicha información. Los vectores dope también pueden describir estructuras que pueden contener matrices o elementos variables.

Si una matriz de este tipo 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 por estima .

Sin embargo, esta disposición (sin agregar vectores de dope) 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, mucho menos dónde o qué tan grande es la matriz.

Sin un vector de datos, ni siquiera conocer la dirección de toda la matriz nos dice qué tan grande es. Esto es importante porque escribir en el elemento N + 1 de una matriz que solo contiene N elementos probablemente destruirá 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 de búfer .

Un vector dope 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 impida escribir accidentalmente más allá del final de una matriz u otro objeto. Alternativamente, el programador puede acceder al vector dope cuando lo desee, por seguridad u otros fines.

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 podría contener:

• un puntero a la ubicación en la memoria donde comienzan los elementos de la matriz (normalmente es idéntica 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 lenguajes, el índice inicial de las matrices se fija en cero o uno, pero el índice final se establece cuando se (reasigna) la matriz).
• Para matrices en las que 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.

Un programa puede entonces hacer referencia a la matriz (u otro objeto que utilice el vector dope) haciendo referencia al vector dope. Esto es comúnmente 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 obtiene el puntero a los datos reales 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 referencia, es imposible determinar la cantidad de elementos de 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 entonces escaneando hacia adelante a través de la matriz, contando los elementos hasta que se alcanza este "marcador final". Por supuesto, esto hace que la verificación de longitud sea mucho más lenta que buscar la longitud directamente en un vector de referencia.
• Sin conocer la extensión de una matriz, no es posible liberar (free()) (desasignar) esa memoria cuando ya no se necesita. Por lo tanto, sin vectores dope, 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 el llamador no trate los 4 bytes adicionales como parte de la matriz propiamente dicha). Estos datos adicionales no se consideran un vector dope, pero logran algunos de los mismos objetivos.
• Sin vectores dope, también se debe mantener información adicional sobre el paso (o ancho) de los elementos de la matriz. En C , esta información es manejada por 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 decrementar para alcanzar el elemento siguiente o anterior; pero también significa que los anchos de las matrices se deben fijar en una etapa anterior.

Incluso con un vector dope, tener (solamente) 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 dope en sí. Si se desea, dicha información se puede agregar a cada elemento dentro de la matriz. Dicha información por elemento puede ser útil, pero no es parte del vector dope.

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

• Descriptor de datos
• Vector de Iliffe
• Reflexión (programación informática)