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