Bagaimana susunan multi-dimensi diformat dalam memori?

185

Di C, saya tahu saya dapat secara dinamis mengalokasikan array dua dimensi di heap menggunakan kode berikut:

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

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

Jelas, ini sebenarnya menciptakan array satu dimensi dari pointer ke sekelompok array satu dimensi yang terpisah dari integer, dan "Sistem" dapat mengetahui apa yang saya maksud ketika saya meminta:

someNumbers[4][2];

Tetapi ketika saya secara statis mendeklarasikan array 2D, seperti pada baris berikut ...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

... apakah struktur serupa dibuat pada stack, atau apakah itu dari bentuk lain sepenuhnya? (Yaitu apakah itu array 1D pointer? Jika tidak, apa itu, dan bagaimana referensi untuk itu bisa diketahui?)

Juga, ketika saya berkata, "Sistem," apa yang sebenarnya bertanggung jawab untuk mencari tahu? Kernel? Atau apakah kompiler C mengatasinya saat kompilasi?

Chris Cooper
sumber
8
Saya akan memberi lebih dari +1 jika saya bisa.
Rob Lachlan
1
Peringatan : Tidak ada array 2D dalam kode ini!
terlalu jujur ​​untuk situs ini
@toohonestforthissite Memang. Untuk memperluas itu: Looping dan panggilan malloc()tidak menghasilkan array N-dimensi. . Ini menghasilkan array pointer [ke array pointer [...]] untuk sepenuhnya memisahkan array satu dimensi . Lihat Mengalokasikan array multi-dimensi dengan benar untuk melihat bagaimana mengalokasikan array N-dimensi yang BENAR .
Andrew Henle

Jawaban:

145

Array dua dimensi yang statis terlihat seperti array array - hanya diletakkan secara berdekatan dalam memori. Array tidak sama dengan pointer, tetapi karena Anda sering dapat menggunakannya secara bergantian, terkadang membingungkan. Kompiler terus melacak dengan benar, yang membuat semuanya berbaris dengan baik. Anda harus berhati-hati dengan array 2D statis seperti yang Anda sebutkan, karena jika Anda mencoba untuk mengirimkannya ke fungsi yang mengambil int **parameter, hal-hal buruk akan terjadi. Ini contoh singkatnya:

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

Dalam memori terlihat seperti ini:

0 1 2 3 4 5

persis sama dengan:

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

Tetapi jika Anda mencoba meneruskan array1ke fungsi ini:

void function1(int **a);

Anda akan mendapatkan peringatan (dan aplikasi akan gagal mengakses array dengan benar):

warning: passing argument 1 of function1 from incompatible pointer type

Karena array 2D tidak sama dengan int **. Pembusukan otomatis array menjadi pointer hanya bisa dikatakan "sedalam level". Anda perlu mendeklarasikan fungsinya sebagai:

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

atau

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

Untuk membuat semuanya bahagia.

Konsep yang sama ini meluas ke n- dimensi array. Namun, mengambil keuntungan dari bisnis lucu semacam ini dalam aplikasi Anda hanya akan membuatnya lebih sulit untuk dipahami. Jadi berhati-hatilah di luar sana.

Carl Norum
sumber
Terima kasih untuk penjelasannya. Jadi "void function2 (int a [] [2]);" akan menerima 2D dan dinyatakan secara statis dan dinamis? Dan saya kira itu masih merupakan praktik yang baik / penting untuk meneruskan panjang array juga jika dimensi pertama dibiarkan sebagai []?
Chris Cooper
1
@ Chris Saya tidak berpikir begitu - Anda akan kesulitan membuat C memutar array yang dialokasikan secara global menjadi sekelompok pointer.
Carl Norum
6
@JasonK. - tidak. Array bukan pointer. Array "peluruhan" menjadi pointer dalam beberapa konteks, tetapi mereka sama sekali tidak sama.
Carl Norum
1
Agar lebih jelas: Ya Chris "masih merupakan praktik yang baik untuk meneruskan panjang array" sebagai parameter terpisah, jika tidak gunakan std :: array atau std :: vector (yang merupakan C ++ bukan C yang lama). Saya pikir kami setuju @CarlNorum baik secara konseptual untuk pengguna baru dan praktis, untuk mengutip Anders Kaseorg pada Quora: “Langkah pertama untuk belajar C adalah memahami bahwa pointer dan array adalah hal yang sama. Langkah kedua adalah memahami bahwa pointer dan array berbeda. ”
Jason K.
2
@JasonK. "Langkah pertama untuk belajar C adalah memahami bahwa pointer dan array adalah hal yang sama." - Kutipan ini sangat salah dan menyesatkan! Memang langkah yang paling penting untuk memahami mereka tidak sama, tetapi array dikonversi menjadi pointer ke elemen pertama untuk sebagian besar operator! sizeof(int[100]) != sizeof(int *)(kecuali jika Anda menemukan platform dengan 100 * sizeof(int)byte / int, tapi itu hal yang berbeda.
terlalu jujur ​​untuk situs ini
85

Jawabannya didasarkan pada gagasan bahwa C tidak benar - benar memiliki array 2D - ia memiliki array array. Ketika Anda menyatakan ini:

int someNumbers[4][2];

Anda meminta untuk someNumbersmenjadi array dari 4 elemen, di mana setiap elemen dari array itu adalah tipe int [2](yang merupakan array dari 2 ints).

Bagian lain dari teka-teki adalah bahwa array selalu diletakkan berdampingan dalam memori. Jika Anda meminta:

sometype_t array[4];

maka itu akan selalu terlihat seperti ini:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_tobjek diletakkan bersebelahan, tanpa spasi di antaranya). Jadi dalam someNumbersarray-of-array Anda, akan terlihat seperti ini:

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

Dan setiap int [2]elemen itu sendiri merupakan array, yang terlihat seperti ini:

| int        | int        |

Jadi secara keseluruhan, Anda mendapatkan ini:

| int | int  | int | int  | int | int  | int | int  |
kaf
sumber
1
melihat tata letak akhir membuat saya berpikir bahwa int [] [] dapat diakses sebagai int * ... kan?
Narcisse Doudieu Siewe
2
@ user3238855: Jenis tidak kompatibel, tetapi jika Anda mendapatkan pointer ke yang pertama intdalam array array (mis. dengan mengevaluasi a[0]atau &a[0][0]) maka ya, Anda dapat mengimbangi itu untuk mengakses secara berurutan setiap int).
caf
28
unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

dalam memori sama dengan:

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

Sebagai jawaban untuk Anda juga: Keduanya, meskipun kompiler melakukan sebagian besar tugas berat.

Dalam hal array yang dialokasikan secara statis, "Sistem" akan menjadi kompiler. Ini akan menyimpan memori seperti halnya untuk variabel tumpukan apa pun.

Dalam kasus array malloc'd, "Sistem" akan menjadi pelaksana malloc (biasanya kernel). Semua kompiler akan mengalokasikan adalah pointer dasar.

Compiler selalu akan menangani tipe seperti apa yang mereka nyatakan kecuali pada contoh yang diberikan Carl di mana ia dapat mengetahui penggunaan yang dapat dipertukarkan. Inilah sebabnya mengapa jika Anda meneruskan sebuah [] [] ke suatu fungsi, ia harus mengasumsikan bahwa itu adalah flat yang dialokasikan secara statis, di mana ** diasumsikan sebagai pointer ke pointer.

Jon L
sumber
@Jon L. Saya tidak akan mengatakan bahwa malloc diimplementasikan oleh kernel, tetapi oleh libc di atas kernel primitif (seperti brk)
Manuel Selva
@ManuelSelva: Di mana dan bagaimana mallocpenerapannya tidak ditentukan oleh standar dan diserahkan kepada implementasi, resp. lingkungan Hidup. Untuk lingkungan yang berdiri bebas itu opsional seperti semua bagian dari perpustakaan standar yang membutuhkan fungsi penautan (itulah yang sebenarnya dihasilkan persyaratan, bukan literal apa yang dinyatakan standar). Untuk beberapa lingkungan yang di-host modern, itu memang bergantung pada fungsi kernel, baik hal-hal yang lengkap, atau (misalnya Linux) ketika Anda menulis menggunakan keduanya, stdlib dan kernel-primitif. Untuk sistem proses tunggal memori non-virtual, itu bisa saja stdlib.
terlalu jujur ​​untuk situs ini
2

Misalkan, kita memiliki a1dan a2mendefinisikan dan menginisialisasi seperti di bawah ini (c99):

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

a1adalah array 2D homogen dengan tata letak kontinu polos dalam memori dan ekspresi (int*)a1dievaluasi menjadi penunjuk ke elemen pertama:

a1 --> 142 143 144 145

a2diinisialisasi dari array 2D yang heterogen dan merupakan penunjuk ke nilai tipe int*, yaitu ekspresi dereferensi *a2dievaluasi menjadi nilai tipe int*, tata letak memori tidak harus kontinu:

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

Meskipun tata letak memori dan semantik aksesnya sangat berbeda, tata bahasa C untuk ekspresi akses-array terlihat persis sama untuk array 2D homogen dan heterogen:

  • ekspresi a1[1][0]akan mengambil nilai 144dari a1array
  • ekspresi a2[1][0]akan mengambil nilai 244dari a2array

Compiler tahu bahwa ekspresi akses untuk a1beroperasi pada tipe int[2][2], ketika ekspresi akses untuk a2beroperasi pada tipe int**. Kode rakitan yang dihasilkan akan mengikuti semantik akses yang homogen atau heterogen.

Kode biasanya macet saat run-time ketika array int[N][M]tipe dicor tipe dan kemudian diakses sebagai tipe int**, misalnya:

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

Untuk mengakses array 2D tertentu, pertimbangkan peta memori untuk deklarasi array seperti yang ditunjukkan pada kode di bawah ini:

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

Untuk mengakses setiap elemen, cukup lewati saja array yang Anda minati sebagai parameter untuk fungsi tersebut. Kemudian gunakan offset untuk kolom untuk mengakses setiap elemen secara individual.

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
sumber