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

185

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

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

Ясно, что на самом деле это создает одномерный массив указателей на кучу отдельных одномерных массивов целых чисел, и «Система» может понять, что я имею в виду, когда спрашиваю:

someNumbers[4][2];

Но когда я статически объявляю 2D-массив, как в следующей строке ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

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

Кроме того, когда я сказал: «Система», что на самом деле отвечает за это? Ядро? Или компилятор C разбирает его во время компиляции?

Крис Купер
источник
8
Я бы дал больше +1, если бы мог.
Роб Лахлан
1
Предупреждение : в этом коде нет двумерного массива!
слишком честно для этого сайта
@toohonestforthissite Действительно. Чтобы расширить это: цикл и вызов malloc()не приводят к N-мерному массиву. , Это приводит к массивам указателей [к массивам указателей [...]] для полного разделения одномерных массивов. См. Правильное размещение многомерных массивов, чтобы узнать, как распределить ИСТИННЫЙ N-мерный массив.
Эндрю Хенле

Ответы:

145

Статический двумерный массив выглядит как массив массивов - он просто расположен непрерывно в памяти. Массивы - это не то же самое, что указатели, но из-за того, что вы часто можете использовать их практически взаимозаменяемо, иногда это может сбивать с толку. Тем не менее, компилятор правильно отслеживает, что делает все правильно. Вы должны быть осторожны со статическими 2D-массивами, как вы упомянули, так как если вы попытаетесь передать один из них в функцию, принимающую int **параметр, произойдут плохие вещи. Вот быстрый пример:

int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};

По памяти выглядит так:

0 1 2 3 4 5

точно так же как:

int array2[6] = { 0, 1, 2, 3, 4, 5 };

Но если вы попытаетесь перейти array1к этой функции:

void function1(int **a);

вы получите предупреждение (и приложение не сможет получить доступ к массиву правильно):

warning: passing argument 1 of function1 from incompatible pointer type

Потому что 2D массив не совпадает с int **. Автоматическое затухание массива в указатель идет, так сказать, только на один уровень. Вам нужно объявить функцию как:

void function2(int a[][2]);

или

void function2(int a[3][2]);

Чтобы сделать все счастливым.

Эта та же самая концепция распространяется на n- мерные массивы. Однако использование такого рода забавных бизнесов в вашем приложении, как правило, только усложняет понимание. Так что будьте осторожны там.

Карл Норум
источник
Спасибо за объяснение. Так что "void function2 (int a [] [2]);" будет принимать как статически, так и динамически объявленные 2D? И я думаю, что это хорошая практика / важно также передавать длину массива, если первое измерение оставлено как []?
Крис Купер
1
@ Крис Я так не думаю - вам будет трудно заставить C перебирать массив из стека или глобально распределенный массив в набор указателей.
Карл Норум,
6
@JasonK. - нет Массивы не указатели. Массивы «разлагаются» на указатели в некоторых контекстах, но они абсолютно не совпадают.
Карл Норум
1
Для ясности: Да, Крис, «все еще хорошая практика передавать длину массива» в качестве отдельного параметра, в противном случае используйте std :: array или std :: vector (который является C ++, а не старым C). Я думаю, что мы согласны с @CarlNorum концептуально как для новых пользователей, так и практически, чтобы процитировать Андерса Касеорга из Quora: «Первый шаг к изучению C - это понимание того, что указатели и массивы - это одно и то же. Второй шаг - понимание того, что указатели и массивы разные ».
Джейсон К.
2
@JasonK. «Первым шагом к изучению C является понимание того, что указатели и массивы - это одно и то же». - Эта цитата очень неправильная и вводящая в заблуждение! Это действительно самый важный шаг, чтобы понять, что они не одинаковы, но для большинства операторов массивы преобразуются в указатель на первый элемент ! sizeof(int[100]) != sizeof(int *)(если вы не найдете платформу с 100 * sizeof(int)байтами / int, но это совсем другое.
слишком честно для этого сайта
85

Ответ основан на идее, что C на самом деле не имеет 2D-массивов - у него есть массивы-массивы. Когда вы заявляете это:

int someNumbers[4][2];

Вы запрашиваете someNumbersмассив из 4 элементов, где каждый элемент этого массива имеет тип int [2](который сам является массивом из 2int с).

Другая часть головоломки состоит в том, что массивы всегда располагаются непрерывно в памяти. Если вы попросите:

sometype_t array[4];

тогда это всегда будет выглядеть так:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_tобъекта расположены рядом друг с другом без пробелов между ними). Итак, в вашем someNumbersмассиве массивов это будет выглядеть так:

| int [2]    | int [2]    | int [2]    | int [2]    |

И каждый int [2]элемент сам по себе является массивом, который выглядит так:

| int        | int        |

В общем, вы получите это:

| int | int  | int | int  | int | int  | int | int  |
кафе
источник
1
глядя на окончательный макет, я думаю, что к int [] [] можно получить доступ как int * ... верно?
Нарцисс Дудье Сью
2
@ user3238855: типы несовместимы, но если вы получаете указатель на первый intв массиве массивов (например, путем оценки a[0]или &a[0][0]), тогда да, вы можете сместить его, чтобы последовательно обращаться к каждому int).
Кафе
29
unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

в памяти равно:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};
kanghai
источник
5

В ответ на ваш также: оба, хотя компилятор делает большую часть тяжелой работы.

В случае статически размещенных массивов, «Система» будет компилятором. Он зарезервирует память, как для любой переменной стека.

В случае с массивом malloc, «Система» будет исполнителем malloc (обычно ядра). Все, что выделит компилятор, это базовый указатель.

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

Джон Л
источник
@Jon L. Я бы не сказал, что malloc реализован ядром, но libc поверх примитивов ядра (таких как brk)
Мануэль Сельва
@ManuelSelva: Где и как mallocреализовано, не указано в стандарте и оставлено для реализации, соответственно. Окружающая среда. Для автономных сред это необязательно, как и для всех частей стандартной библиотеки, требующих связывания функций (это то, к чему фактически приводят требования, а не буквально то, что заявляет стандарт). Для некоторых современных размещенных сред он действительно полагается на функции ядра, либо весь материал, либо (например, Linux), как вы писали с использованием обоих, stdlib и kernel-примитивов. Для однопроцессных систем с не виртуальной памятью это может быть только stdlib.
слишком честно для этого сайта
2

Предположим, мы a1и a2определили и инициализировали, как показано ниже (c99):

int a1[2][2] = {{142,143}, {144,145}};
int **a2 = (int* []){ (int []){242,243}, (int []){244,245} };

a1 представляет собой однородный двумерный массив с простой непрерывной компоновкой в ​​памяти и выражением (int*)a1 вычисляется до указателя на его первый элемент:

a1 --> 142 143 144 145

a2инициализируется из гетерогенного двумерного массива и является указателем на значение типа int*, то есть выражение разыменования *a2переходит в значение типа int*, расположение в памяти не должно быть непрерывным:

a2 --> p1 p2
       ...
p1 --> 242 243
       ...
p2 --> 244 245

Несмотря на совершенно разную структуру памяти и семантику доступа, грамматика языка C для выражений доступа к массиву выглядит одинаково как для однородного, так и гетерогенного двумерного массива:

  • выражение a1[1][0]будет извлекать значение 144из a1массива
  • выражение a2[1][0]будет извлекать значение 244из a2массива

Компилятор знает, что выражение доступа для a1действует на типint[2][2] , когда выражение доступа для a2оперирует типом int**. Сгенерированный ассемблерный код будет следовать гомогенной или гетерогенной семантике доступа.

Код обычно дает сбой во время выполнения, когда массив типа int[N][M]приведен к типу и затем доступен как тип int**, например:

((int**)a1)[1][0]   //crash on dereference of a value of type 'int'
sqr163
источник
1

Чтобы получить доступ к определенному 2D массиву, рассмотрите карту памяти для объявления массива, как показано в коде ниже:

    0  1
a[0]0  1
a[1]2  3

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

int a[2][2] ={{0,1},{2,3}};

void f1(int *ptr);

void f1(int *ptr)
{
    int a=0;
    int b=0;
    a=ptr[0];
    b=ptr[1];
    printf("%d\n",a);
    printf("%d\n",b);
}

int main()
{
   f1(a[0]);
   f1(a[1]);
    return 0;
}
AlphaGoku
источник