Массив (тип данных): различия между версиями
[непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Dm (обсуждение | вклад) →Реализация: стилевые правки, дополнение |
|||
Строка 110:
== Реализация ==
Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является следующий :
# Под массив выделяется непрерывный блок памяти объёмом S*m<sub>1</sub>*m<sub>2</sub>*m<sub>3</sub>…m<sub>n</sub>, где S — размер одного элемента, а m<sub>1</sub>…m<sub>n</sub> — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
# При обращении к элементу массива A[i<sub>1</sub>, i<sub>2</sub>, i<sub>3</sub>, …, i<sub>n</sub>] адрес соответствующего элемента вычисляется как B+S*((…(i<sub>1p</sub>*m<sub>1</sub>+i<sub>2p</sub>)*m<sub>2</sub>+…+i<sub>(n-1)p</sub>)*m<sub>n-1</sub>+i<sub>np</sub>), где B — база (адрес начала блока памяти массива), i<sub>kp</sub> — значение k-го индекса, приведённое к целому с нулевым начальным смещением. Порядок следования индексов в формуле вычисления адреса может быть различным. Приведённый соответствует реализации в большинстве компиляторов языка [[Си (язык программирования)|Си]]; в [[Фортран]]е порядок индексов противоположен{{sfn|Бартеньев|2000|сс = 108-112}}).
Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково. <small> ''Примечание'':
Первый элемент массива, в зависимости от [[язык программирования|языка программирования]], может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для [[Низкоуровневый язык программирования|низкоуровневых языков программирования]],
Обычным способом реализации гетерогенных массивов является отдельное хранение самих значений элементов и размещение в блоке памяти массива (организованного как обычный гомогенный массив, описанный выше) указателей на эти элементы. Поскольку указатели на значения любых типов, как правило, имеют один и тот же размер, удаётся сохранить простоту вычисления адреса, хотя возникают дополнительные накладные расходы на размещение значений элементов и обращение к ним.
Для динамических массивов может использоваться тот же механизм размещения, что и для статических, но с выделением некоторого объёма дополнительной памяти для расширения и добавлении механизмов изменения размера и перемещения содержимого массива в памяти.
Также динамические и гетерогенные массивы могут реализовываться путём использования принципиально иных методов хранения значений в памяти, например, одно- или двухсвязных списков. Такие реализации могут быть более гибкими, но требуют, как правило, дополнительных накладных расходов. Кроме того, в них обычно не удаётся выдержать требование константного времени доступа к элементу.
== Достоинства ==
|