Jak formatowane są wielowymiarowe tablice w pamięci?

185

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?

Chris Cooper
źródło
8
Dałbym więcej niż +1, gdybym mógł.
Rob Lachlan
1
Ostrzeżenie : w tym kodzie nie ma tablicy 2D!
zbyt uczciwy dla tej strony
@toohonestforthissite Rzeczywiście. Aby rozwinąć tę kwestięmalloc() : zapętlanie i wywoływanie nie powoduje utworzenia macierzy N-wymiarowej. . Wynikiem tego są tablice wskaźników [do tablic wskaźników [...]], aby całkowicie oddzielić tablice jednowymiarowe . Zobacz Prawidłowe przydzielanie tablic wielowymiarowych, aby zobaczyć, jak przydzielić PRAWDZIWĄ tablicę N-wymiarową.
Andrew Henle,

Odpowiedzi:

145

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.

Carl Norum
źródło
Dziękuję za wyjaśnienie. Więc „void function2 (int a [] [2]);” zaakceptuje statycznie i dynamicznie zadeklarowane 2D? I myślę, że nadal dobrą praktyką / koniecznością jest podanie długości tablicy, jeśli pierwszy wymiar pozostanie jako []?
Chris Cooper
1
@Chris Nie sądzę - trudno ci będzie zmienić C w zamianę tablicy alokowanej na stosie lub globalnie w zestaw wskaźników.
Carl Norum
6
@JasonK. - nie Tablice nie są wskaźnikami. Tablice „rozkładają się” na wskaźniki w niektórych kontekstach, ale absolutnie nie są takie same.
Carl Norum,
1
Żeby było jasne: Tak Chris „Nadal dobrą praktyką jest przekazywanie długości tablicy” jako osobny parametr, w przeciwnym razie użyj std :: array lub std :: vector (który to C ++ nie jest starym C). Myślę, że zgadzamy się @CarlNorum zarówno koncepcyjnie dla nowych użytkowników, jak i praktycznie, cytując Andersa Kaseorga na Quora: „Pierwszym krokiem do nauki języka C jest zrozumienie, że wskaźniki i tablice są tym samym. Drugim krokiem jest zrozumienie, że wskaźniki i tablice są różne. ”
Jason K.,
2
@JasonK. „Pierwszym krokiem do nauki języka C jest zrozumienie, że wskaźniki i tablice są tym samym.” - Ten cytat jest bardzo błędny i wprowadza w błąd! Jest to rzeczywiście najważniejszy krok, aby zrozumieć, że nie są takie same, ale dla większości operatorów tablice są konwertowane na wskaźnik do pierwszego elementu ! sizeof(int[100]) != sizeof(int *)(chyba że znajdziesz platformę z 100 * sizeof(int)bajtami / int, ale to inna sprawa.
zbyt uczciwa jak na tę stronę
85

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  |
caf
źródło
1
patrząc na ostateczny układ, myślę, że int [] [] można uzyskać jako int * ... prawda?
Narcisse Doudieu Siewe
2
@ user3238855: Typy nie są kompatybilne, ale jeśli otrzymasz wskaźnik do pierwszego intw tablicy tablic (np. poprzez ocenę a[0]lub &a[0][0]), to tak, możesz to zrównoważyć, aby uzyskać dostęp sekwencyjny do każdego int).
caf
28
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};
kangaj
źródło
5

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.

Jon L.
źródło
@Jon L. Nie powiedziałbym, że malloc jest implementowany przez jądro, ale przez libc na prymitywach jądra (takich jak brk)
Manuel Selva
@ManuelSelva: Miejsce i sposób mallocimplementacji nie są określone przez standard i pozostawione implementacji, odpowiednio. środowisko. W środowiskach wolnostojących jest on opcjonalny, podobnie jak wszystkie części standardowej biblioteki wymagające funkcji łączenia (właśnie to powodują wymagania, a nie dosłownie to, co określają standardowe). W niektórych współczesnych środowiskach hostowanych, faktycznie opiera się on na funkcjach jądra, albo kompletnych rzeczach, albo (np. Linux), jak pisałeś, używając zarówno stdlib, jak i jąder-prymitywów. W przypadku systemów jednoprocesowych z pamięcią inną niż wirtualna może to być tylko stdlib.
zbyt uczciwy dla tej strony
2

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'
sqr163
źródło
1

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;
}
AlphaGoku
źródło