Вектор допинга

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

Цель

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

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

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

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

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

Описание

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

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

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

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

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

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

См. также

Ссылки

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

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

[1] Пратт, Т.; Зелковиц, М. (1996). Языки программирования: проектирование и реализация (3-е изд.). Река Аппер-Сэддл, Нью-Джерси : Прентис-Холл . п. 114. ИСБН 978-0-13-678012-0 .

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

[1]

[2]