Jak formatowane są wielowymiarowe tablice w pamięci?

W C wiem, że mogę dynamicznie przydzielić tablicę dwuwymiarową na stercie za pomocą następującego kodu:

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

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

Najwyraźniej tworzy to jednowymiarową tablicę wskaźników do szeregu oddzielnych jednowymiarowych tablic liczb całkowitych, a „System” może zrozumieć, co mam na myśli, gdy pytam:

someNumbers[4][2];

Ale kiedy statycznie deklaruję tablicę 2D, jak w poniższym wierszu ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

... czy na stosie tworzona jest podobna struktura, czy też ma zupełnie inną formę? (tj. czy jest to tablica wskaźników 1D? Jeśli nie, co to jest i jak się do tego odnoszą?)

Poza tym, kiedy powiedziałem „System”, co właściwie jest odpowiedzialne za to? Jądro? A może kompilator C rozwiązuje problem podczas kompilacji?

Statyczna dwuwymiarowa tablica wygląda jak tablica tablic - jest po prostu ułożona w sposób ciągły w pamięci. Tablice to nie to samo, co wskaźniki, ale ponieważ często można ich używać zamiennie, czasami może być mylące. Kompilator śledzi jednak poprawnie, co sprawia, że ​​wszystko ładnie się układa. Musisz uważać na statyczne tablice 2D, jak wspomniałeś, ponieważ jeśli spróbujesz przekazać jedną do funkcji przyjmującej int **parametr, coś złego się wydarzy. Oto szybki przykład:

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

W pamięci wygląda następująco:

0 1 2 3 4 5

dokładnie taki sam jak:

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

Ale jeśli spróbujesz przejść array1do tej funkcji:

void function1(int **a);

dostaniesz ostrzeżenie (a aplikacja nie uzyska dostępu do tablicy poprawnie):

warning: passing argument 1 of ‘function1’ from incompatible pointer type

Ponieważ tablica 2D nie jest taka sama jak int **. Można powiedzieć, że automatyczne rozkładanie tablicy na wskaźnik przechodzi tylko „na jeden poziom”. Musisz zadeklarować funkcję jako:

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

lub

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

Aby wszystko było szczęśliwe.

Ta sama koncepcja rozciąga się na tablice n- wymiarowe. Jednak korzystanie z tego rodzaju śmiesznego biznesu w twojej aplikacji sprawia, że ​​trudniej go zrozumieć. Bądź więc ostrożny.

Odpowiedź opiera się na założeniu, że C tak naprawdę nie ma tablic 2D - ma tablice tablic. Kiedy to zadeklarujesz:

int someNumbers[4][2];

Pytasz o someNumbersbycie tablicą 4 elementów, gdzie każdy element tej tablicy jest typu int [2](który sam jest tablicą 2 ints).

Inną częścią układanki jest to, że tablice są zawsze ułożone w sposób ciągły w pamięci. Jeśli poprosisz o:

sometype_t array[4];

wtedy to zawsze będzie wyglądać tak:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_tobiekty ułożone obok siebie, bez odstępów między nimi). W twojej someNumberstablicy tablic będzie to wyglądać następująco:

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

Każdy int [2]element jest tablicą, która wygląda następująco:

| int        | int        |

Więc ogólnie otrzymujesz:

| int | int  | int | int  | int | int  | int | int  |

unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

w pamięci jest równy:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};

W odpowiedzi również na: Oba, choć kompilator wykonuje większość ciężkich zadań.

W przypadku tablic przydzielanych statycznie kompilatorem będzie „System”. Zarezerwuje pamięć tak, jak dla każdej zmiennej stosu.

W przypadku tablicy malloc'd „System” będzie implementatorem malloc (zwykle jądro). Jedyny kompilator, który przydzieli, to wskaźnik podstawowy.

Kompilator zawsze będzie obsługiwał typ taki, jaki jest zadeklarowany, z wyjątkiem przykładu podanego przez Carl, w którym może on określić zastosowanie wymienne. Dlatego jeśli przekazujesz [] [] do funkcji, musisz założyć, że jest to mieszkanie przypisane statycznie, gdzie ** przyjmuje się, że jest wskaźnikiem do wskaźnika.

Załóżmy, że mamy a1i a2zdefiniowana jak poniżej i inicjalizowana (C99)

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

a1jest jednorodną tablicą 2D z prostym ciągłym układem w pamięci, a wyrażenie (int*)a1jest oceniane na wskaźnik do pierwszego elementu:

a1 --> 142 143 144 145

a2jest inicjowany z heterogenicznej tablicy 2D i jest wskaźnikiem do wartości typu int*, tzn. wyrażenie dereferencyjne *a2przekształca się w wartość typu int*, układ pamięci nie musi być ciągły:

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

Pomimo całkowicie odmiennego układu pamięci i semantyki dostępu, gramatyka języka C dla wyrażeń dostępu do tablicy wygląda dokładnie tak samo dla homogenicznej i heterogenicznej tablicy 2D:

• wyrażenie a1[1][0]pobierze wartość 144z a1tablicy
• wyrażenie a2[1][0]pobierze wartość 244z a2tablicy

Kompilator wie, że wyrażenie dostępu dla typu a1działa int[2][2], gdy wyrażenie dostępu dla typu a2działa int**. Wygenerowany kod zestawu będzie zgodny z semantyką dostępu jednorodnego lub heterogenicznego.

Kod zwykle ulega awarii w czasie wykonywania, gdy tablica typu int[N][M]jest rzutowana na typ int**, a następnie dostępna jako typ , na przykład:

((int**)a1)[1][0]   //crash on dereference of a value of type 'int'

Aby uzyskać dostęp do konkretnej tablicy 2D, rozważ mapę pamięci dla deklaracji tablicy, jak pokazano w poniższym kodzie:

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

Aby uzyskać dostęp do każdego elementu, wystarczy przekazać tablicę, którą jesteś zainteresowany, jako parametry funkcji. Następnie użyj przesunięcia dla kolumny, aby uzyskać dostęp do każdego elementu osobno.

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;
}