Как хранятся многомерные массивы в памяти?

Question

[hello_world42]

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

int arr[2][3] = 
{
    {1, 2, 3},
    {1, 2, 3}
}

в памяти выделяется две ячейки, каждая из которых занимает sizeof(int) * 3 и таким образом можно легко обращаться к любому элементу. Например при обращении к последней тройке arr[1][2], на уровне указателей это будет выглядеть так *(arr + (sizeof(int) * 3 * 1) + 2). Ну и памяти занимает такой массив ровно 2х3.

Но затем я увидел такую формулу на уровне указателей arr[1][2] => *(*(arr + 1) + 2) и пришел к выводу, что многомерный массив хранится в памяти следующим образом (здесь я буду обозначать память вот так 0[5], где 0 - адрес ячейки, [5] - значение, которое хранится внутри ячейки):

0[адрес 2], 1[адрес 5], 2[1], 3[2], 4[3], 5[1], 6[2], 7[3]

И при таком хранении можно легко понять почему в этой формуле *(*(*(arr + i) + j) + k) на каждом уровне идет разыменование. Однако при таком способе хранения тот же массив уже занимает 2 + 2x3.

Так как хранятся многомерные массивы и если описанный мной второй способ верный, то в чем его преимущество над первым?

Answer 1

[Wataru]

Зависит от типа массива.

int **a;
// или vector<vector<int>> a;
a[10][7];

Тут происходит 2 разименовывания указателя. Массив в памяти хранится строчками. Каждая строка может быть где угодно. При этом дополнительно хранится массив указателей на строки (длиной с длину столбца). Поэтому такой массив занимает в памяти M*(sizeof(int*))+M*N*sizeof(int). Чуть сложнее для vector, но идея такая же.

int a[10][3];
a[4][5];

Тут массив, хоть и многомерный, но фиксированного размера. Поэтому он хранится одним блоком. Компилятор знает длины всех строк и сразу вычисляет адрес конкретного элемента - сдвигаясь на (длину строки)*(номер строки)+(номер столбца). Он занимает N*M*sizeof(int).

Сравните ассемблерный код.

Кстати, именно поэтому вы не можете преобразовать int[4][5] к int**. И такой массив при передаче в функцию надо передавать по типу int[][5] (можно опустить количество строк. Ибо для адресации нужна лишь длина строк, но нестолбцов, но размер строки указать предется обязательно).

arr[1][2] => *(*(arr + 1) + 2) Это действительно работает, потому что arr имеет тип int[][3] или int*[3]. Коспилятор видя arr+1, знает, что над сместится на 1 размер int[3]. * разыменовывает это, но при этом указывает на то же место. И получает просто указатель на int начало строки. Фактически тут просто меняется тип указателя с int*[3] на int*. +2 сдвигается в строке на 2 размера int.

Answer 2

[mayton2019]

Да. Ты правильно рассуждаешь. Многомерные зубчатые массивы имеют накладные расходы в виде служебных указателей которые должны предварять вход в каждое измерение. И не просто в измерение а там получается
дерево массивов массивов массивов указателей на данные.

Но для такого твоего кейса матрицу можно линеаризовать. И разложить последовательно.

int arr[6] = { 1,2,3,1,2,3};

Формула доступа будет простая. Надо будет к базовому указателю прибавить дистанцию от начала
до нужного элемента помня о том что LINE_WIDTH у нас уже известен и это длина строки в элементах.

*(basePointer + i * LINE_WIDTH + j)

Таким-же образом можно вывести формулу для 3х, 4х и более измерений. И массив можно отобразить
на гиперкуб.

Answer 3

[res2001]

Многомерные массивы можно задавать несколькими способами:

int arr1[2][3];
int (*arr2)[3] = new int[2][3];
int *arr3 = new int[2*3];
int **arr4 = new int*[2];
arr4[0] = new int[3];
arr4[1] = new int[3];

// Следующие утверждения верны:
static_assert(sizeof(arr1) == (sizeof(int)*2*3));
static_assert(sizeof(arr2) == sizeof(int(*)[3]));
static_assert(sizeof(arr3) == sizeof(int*));
static_assert(sizeof(arr4) == sizeof(int**));

static_assert(sizeof(arr1[0]) == (sizeof(int)*3));
static_assert(sizeof(arr2[0]) == (sizeof(int)*3));
static_assert(sizeof(arr3[0]) == sizeof(int));
static_assert(sizeof(arr4[0]) == sizeof(int*));

В 1-3 варианте данные массива хранятся последовательно друг за другом по строкам. 4 вариант - это "массив массивов" (его могут называть и по другому), тут требуется отдельный массив указателей, данные строк могут хранится в разных местах памяти.
Обращаться к элементам arr1, arr2 и arr4 можно с помощью индексации: arr1[i][j] и это будет работать, но по разному для arr1/2 и arr4.
arr3 это по сути одномерный массив. То что он двумерный знаете только вы как программист. Поэтому через индексацию можно обращаться только к первой размерности. Чтоб включить и вторую размерность потребуется ее явно посчитать. Например для элемента arr2[1][2]:

*(arr2 + 1 * 3 + 2);
// или то же самое
arr2[1*3 + 2];

С точки зрения производительности 4 вариант самый плохой, т.к. для обращения к элементу требуется два чтения памяти, а так же из-за того что каждая строка хранится отдельно от других в памяти, то кэш процессора будет использоваться менее эффективно, чем для остальных вариантов. Кроме того тут используется дополнительный массив указателей (первая размерность).
Не смотря на то что 3 вариант кажется довольно многословным (особенно если константы заменить на осмысленные имена переменных), но на производительности это никак не сказывается, т.к. по сути те же самые вычисления индекса делаются и для arr1/2, только для них это делает компилятор сам неявно.