Как работает (* prt) [N] [N] при работе с памятью выделения кучи?

Question

Сегодня коллега на работе показал мне способ объявления двумерного массива таким образом, чтобы я мог распределять его линейно, но при этом для доступа к элементам все же использовал двумерную квадратную скобку ([][]).

Например:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 2

int main () {
  int (*a)[SIZE][SIZE] = malloc (sizeof (int) * SIZE * SIZE);

  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      (*a)[i][j] = 0;
    }
  }

  (*a)[0][1] = 100;

  /* should yield:
   *   0
   *   100
   *   0
   *   0
   */
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      printf ("%d\n", (*a)[i][j]);
    }
  }

  free (a);

  return EXIT_SUCCESS;
}

Это в отличие от вычисления индекса и последующего выполнения артеметики указателя (например, *(a + (x * SIZE + y)) или более a[x * SIZE + y]) для доступа к элементу.

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

Помимо этого, хотя я не понимаю, как это работает. Что именно делает эта запись? Это синтаксический сахар? Это выглядит как динамическое выделение стека для массивов (см. Размер массива во время выполнения без динамического выделения разрешен? в качестве одного из примеров), но очевидно, что это распределение происходит в куче.

Я искал больше информации об этой записи / объявлении указателя, но не могу найти ничего другого, кроме термина тип элемента , который подходит, но я не уверен, что это связано.

РЕДАКТИРОВАТЬ # 1:

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

Answer 1

int (*a)[SIZE][SIZE]

объявляет a как указатель на массив SIZE от SIZE из int - при условии SIZE == 3, вы получите что-то вроде этого:

   +---+          +---+---+---+
a: |   | -------> |   |   |   |
   +---+          +---+---+---+
                  |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+

(на самом деле макет был бы строго линейным, но мы пока пойдем с этим представлением).

Чтобы получить доступ к любому элементу массива с указанием, мы должны написать (*a)[i][j] - нам нужно явно разыменовать a, так как мы не хотим индексировать в a, мы хотим индексировать в какие a указывает на .

Помните, что a[i] определяется как *(a + i) - учитывая адрес a, смещение i элементов (не байтов!) От этого адреса и задерживает результат. Таким образом, (*a)[i][j] эквивалентно a[0][i][j].

Теперь, если a указывает на массив 3x3 int, то a + 1 указывает на следующий массив 3x3 из int:

   +---+          +---+---+---+
a: |   | -------> |   |   |   |
   +---+          +---+---+---+
                  |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+
a + 1: ---------> |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+

, к которому мы будем обращаться как (*(a + 1))[i][j], или просто a[1][i][j].

Теперь, зачем вообще указатель на массив? В этом случае мы динамически распределяем массив, что мы будем делать, если а) мы не знаем, сколько SIZExSIZE массивов нам понадобится до времени выполнения, или б) если результирующий массив будет слишком большим для размещения в виде переменная auto, или c) если мы хотим увеличить или уменьшить количество массивов SIZExSIZE по мере необходимости.

Как работает этот метод выделения многомерного массива? Начнем с выделения массива N -элемента T:

T *arr = malloc( sizeof *arr * N );

sizeof *arr эквивалентно sizeof (T), поэтому мы выделяем пространство для N объектов типа T.

Теперь давайте заменим T типом массива, R [M]:

R (*arr)[M] = malloc( sizeof *arr * N );

sizeof *arr эквивалентно sizeof (R [M]), поэтому мы выделяем пространство для N объектов типа R [M] - IOW, N M -элементных массивов R. Мы динамически создали эквивалент R a[M][N].

Мы могли бы также написать это как

R (*arr)[M] = malloc( sizeof (R) * M * N );

хотя я предпочитаю использовать sizeof *arr; Вы поймете, почему через секунду.

Теперь мы можем заменить R на еще одним типом массива, S [L]:

S (*arr)[L][M] = malloc( sizeof *arr * N );

sizeof *arr эквивалентно sizeof (S [L][M]), поэтому мы выделяем достаточно места для N объектов типа S [L][M] или N L для M массивов S. Мы динамически создали эквивалент S arr[L][M][N].

Семантика для динамического выделения 1D, 2D и 3D массивов точно такая же - все, что изменилось, это тип. Используя sizeof *arr каждый раз, мне нужно только отслеживать, сколько элементов мне нужно для этого типа.

Answer 2

int (*a)[SIZE][SIZE] - это указатель массива на массив типа int[SIZE][SIZE]. Это специальный вид указателя, который используется для указания целых массивов, но в остальном работает как любой другой указатель. Поэтому, когда вы пишете (*a)[i][j], вы говорите «дайте мне содержимое указателя (двумерный массив), а затем в этом содержимом дайте мне номер элемента [i] [j]».

Но так как указатели массива ведут себя как другие указатели, вы можете использовать его для указания первого элемента вместо всего 2D-массива. (Точно так же, как вы можете использовать int*, чтобы указать на первый элемент массива int[n].) Это делается с помощью трюка с пропуском самого левого измерения: int (*a)[SIZE] = .... Теперь это указывает на первый одномерный массив в массиве массивов. И теперь вы можете использовать его как a[i][j], что гораздо удобнее для чтения и удобнее.

Указатели на массив, описанный выше трюк и способы их использования для динамического выделения 2D-массивов в виде одного фрагмента памяти - все это описано в моем ответе на Правильное распределение многомерных массивов .

Answer 3

Это не так, но не более обычным (и идиоматическим способом). Чтобы объявить динамический массив размера N, вы используете: int *arr = malloc(N * sizeof(int));. Фактически это объявляет arr как указатель на первый элемент массива N int . 2D-массив - это массив массивов, поэтому для объявления 2D-массива N * N наиболее распространенным способом является:

int (*arr)[N] = malloc(N * N * sizeof(int));

Это фактически объявляет arr как указатель на первый элемент из N массивов N int. Затем вы можете обычно использовать arr[i][j].

Так что же это за удивительный int (*a)[SIZE][SIZE] = malloc (sizeof (int) * SIZE * SIZE);?

Вы объявляете arr как указатель на первый (и единственный) элемент массива двумерных массивов NxN целых чисел. Хорошей новостью является то, что объявление явно для размера всех измерений, но недостатком является то, что вы должны постоянно разыменовывать его: (*arr)[i][j], который не отличается для определения оператора [] в C от arr[0][i][j].

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

Answer 4

Что делает int (*a)[SIZE][SIZE] = malloc (sizeof (int) * SIZE * SIZE);, так это объявляет указатель на двумерный массив целых чисел. Это было бы полезно, только если вы намеренно хотите выделить пространство в куче, а не в стеке (например, если размеры массива неизвестны во время компиляции). Затем вы бы разыменовали указатель и получили к нему доступ, как если бы нормальный двумерный массив.

Вы можете пропустить шаг разыменования, объявив вашу переменную как массив указателей, каждый из которых указывает на стандартный массив целых чисел int *a[SIZE] или даже как int **a. В обоих случаях вы можете получить доступ к любому значению, используя скобочную запись a[x][y] без необходимости разыменования a перед.

Если вы знаете размеры массива ранее во время компиляции, и вам не нужно выделять его в куче, вы можете просто объявить массив следующим образом:

int a[SIZE][SIZE];

, который является более коротким и более эффективным, поскольку он выделяет пространство в стеке.

Вы всегда можете получить доступ к массиву, используя [][]. Вы должны иметь в виду, что все в C работает со смещением адресов памяти. Если у вас есть целочисленный массив, объявленный как int a[4], и вы обращаетесь к нему с помощью квадратных скобок, подобных этому a[3], вы указываете процессору взять адрес памяти a и применить смещение 3 * sizeof(int). Вы можете получить доступ к одному и тому же элементу, используя *(&a + 3) или даже 3[a], так как взятие адреса и добавление смещения аналогично взятию смещения и добавлению адреса.

Так что, когда вы используете a[2][3], компилятор делает то же самое, что и выше, только с большим количеством измерений. Так что вам не нужно делать a[x * SIZE + y], потому что это именно то, что компилятор делает для вас, когда вы делаете a[x][y].

РЕДАКТИРОВАТЬ: как отмечалось в комментариях, на самом деле указатели не обязательно хранят ссылку на память, хотя это определенно самая распространенная реализация.

Надеюсь, мое объяснение было ясным.