Вектор наркотика

В компьютерном программировании вектор распределения представляет собой структуру данных, используемую для хранения информации об объекте данных , ^[1] в частности, о его структуре памяти .

Цель

Векторы допинга чаще всего используются для описания массивов , которые обычно хранят несколько экземпляров определенного типа данных в виде непрерывного блока памяти. Например, массив, содержащий 100 элементов, каждый из которых занимает 32 байта, требует 100 × 32 байта. Сам по себе такой блок памяти не имеет места для отслеживания того, насколько велик массив (или другой объект) в целом, насколько велик каждый элемент в нем или сколько элементов он содержит. Вектор допинга — это место для хранения такой информации. Векторы допинга также могут описывать структуры , которые могут содержать массивы или переменные элементы.

Если такой массив хранится непрерывно, с первым байтом в ячейке памяти M , то его последний байт находится в ячейке M + 3199 . Главным преимуществом такого расположения является то, что найти элемент N легко: он начинается в ячейке M + ( N × 32) . Конечно, значение 32 должно быть известно (это значение обычно называют «шагом» массива или «шириной» элементов массива). Навигация по структуре данных массива с использованием индекса называется точным счислением .

Однако эта компоновка (без добавления векторов допинга) означает, что наличия местоположения элемента N недостаточно для обнаружения самого индекса N; или шага; или того, есть ли элементы в N − 1 или N + 1. Например, функция или метод могут перебирать все элементы в массиве и передавать каждый из них другой функции или методу, которые вообще не знают, является ли элемент частью массива, не говоря уже о том, где и насколько велик массив.

Без dope-вектора даже знание адреса всего массива не скажет вам, насколько он большой. Это важно, поскольку запись в элемент N + 1 в массиве, содержащем только N элементов, скорее всего, уничтожит некоторые другие данные. Поскольку многие языки программирования рассматривают строки символов как своего рода массив, это напрямую приводит к печально известной проблеме переполнения буфера .

Вектор допинга уменьшает эти проблемы, сохраняя небольшое количество метаданных вместе с массивом (или другим объектом). С векторами допинга компилятор может легко (и опционально) вставлять код, который предотвращает случайную запись за пределами конца массива или другого объекта. В качестве альтернативы программист может получить доступ к вектору допинга, когда это необходимо, для безопасности или других целей.

Описание

Точный набор метаданных, включенных в dope-вектор, варьируется в зависимости от языка и/или операционной системы, но dope-вектор для массива может содержать:

указатель на местоположение в памяти, где начинаются элементы массива (обычно оно совпадает с местоположением нулевого элемента массива (элемента со всеми индексами 0). (Это может быть не первый фактический элемент, если индексы не начинаются с нуля.)
тип каждого элемента массива (целое число, логическое значение, определенный класс и т. д.).
ранг массива .
размер массива (диапазон его индексов). (Во многих языках начальный индекс для массивов фиксирован и равен нулю или единице, но конечный индекс устанавливается при (пере)распределении массива.)
для массивов, в которых используемый в данный момент экстент может изменяться, могут храниться как максимальный, так и текущий экстент.
шаг массива или объем памяти, занимаемый каждым элементом массива.

Затем программа может ссылаться на массив (или другой объект, использующий dope-вектор), ссылаясь на dope-вектор. Это обычно происходит автоматически в языках высокого уровня . Получение элемента массива стоит немного больше (обычно одна инструкция, которая извлекает указатель на фактические данные из dope-вектора). С другой стороны, выполнение многих других общих операций проще и/или быстрее:

Без dope-вектора определение количества элементов в массиве невозможно. Поэтому обычно в конец массива добавляют дополнительный элемент с «зарезервированным» значением (например, NULL). Затем длину можно определить, просканировав массив вперед, подсчитывая элементы до тех пор, пока не будет достигнут этот «конечный маркер». Конечно, это делает проверку длины намного медленнее, чем поиск длины напрямую в dope-векторе.
Не зная размер массива, невозможно free() (освободить) эту память, когда она больше не нужна. Таким образом, без dope-векторов что-то должно хранить эту длину где-то еще. Например, запрос конкретной ОС выделить место для 3200-байтового массива может привести к выделению 3204 байт в некотором месте M; затем она сохранит размер в первых 4 байтах и сообщит запрашивающей программе, что выделенное пространство начинается с M+4 (так что вызывающая программа не будет рассматривать дополнительные 4 байта как часть собственно массива). Эти дополнительные данные не считаются dope-вектором, но достигают некоторых из тех же целей.
Без dope-векторов необходимо также хранить дополнительную информацию о шаге (или ширине) элементов массива. В C эта информация обрабатывается компилятором, который должен отслеживать различие типов данных между «указателем на массив элементов шириной 20 байт» и «указателем на массив элементов шириной 1000 байт». Это означает, что указатель на элемент в любом виде массива может быть увеличен или уменьшен для достижения следующего или предыдущего элемента; но это также означает, что ширина массива должна быть зафиксирована на более раннем этапе.

Даже с dope-вектором наличие (только) указателя на конкретный элемент массива не позволяет найти позицию в массиве или местоположение массива или самого dope-вектора. Если это необходимо, такую информацию можно добавить к каждому элементу в массиве. Такая информация поэлементно может быть полезна, но не является частью dope-вектора.

Векторы допинга могут быть общим средством, общим для нескольких типов данных (не только массивов и/или строк). ^[2]

Смотрите также

Ссылки

^ Пратт, Т.; Зелковиц, М. (1996). Языки программирования: проектирование и реализация (3-е изд.). Upper Saddle River, NJ : Prentice-Hall . стр. 114. ISBN 978-0-13-678012-0.
^ Клейбрук, Билли Г. (13–15 октября 1976 г.). Проектирование шаблонной структуры для обобщенного определения структуры данных. ICSE '76: 2-я международная конференция по программной инженерии. Сан-Франциско, Калифорния, США: IEEE Computer Society Press. стр. 408–413.

Эта статья, связанная с программированием, является заглушкой . Вы можете помочь Википедии, расширив ее.

[1] Пратт, Т.; Зелковиц, М. (1996). Языки программирования: проектирование и реализация (3-е изд.). Upper Saddle River, NJ : Prentice-Hall . стр. 114. ISBN 978-0-13-678012-0.

[2] Клейбрук, Билли Г. (13–15 октября 1976 г.). Проектирование шаблонной структуры для обобщенного определения структуры данных. ICSE '76: 2-я международная конференция по программной инженерии. Сан-Франциско, Калифорния, США: IEEE Computer Society Press. стр. 408–413.