Cara aneh mengalokasikan array dua dimensi?

110

Dalam sebuah proyek, seseorang mendorong baris ini:

double (*e)[n+1] = malloc((n+1) * sizeof(*e));

Yang seharusnya menciptakan array dua dimensi (n + 1) * (n + 1) ganda.

Seharusnya , saya katakan, karena sejauh ini, tidak seorang pun yang saya tanyai dapat memberi tahu saya apa fungsinya, tepatnya, atau dari mana asalnya atau mengapa itu harus berfungsi (yang diduga, memang demikian, tetapi saya belum membelinya).

Mungkin saya melewatkan sesuatu yang jelas, tetapi saya akan sangat menghargai jika seseorang dapat menjelaskan baris di atas kepada saya. Karena secara pribadi, saya akan merasa jauh lebih baik jika kita menggunakan sesuatu yang benar-benar kita pahami.

Pengguna1291
sumber
15
Bahkan jika berhasil, tembak pendorongnya.
Martin James
22
@MartinJames Mengapa? Bagaimana Anda mengalokasikan array 2D di memori yang berdekatan jika tidak? Array 1D yang hancur? Itu adalah pemrograman tahun 1990-an, kami memiliki VLA sekarang.
Lundin
43
Sebagai catatan, bahwa adalah satu-satunya cara untuk mengalokasikan array 2D yang sebenarnya dinamis.
Quentin
15
@Kninnug Tidak, itu akan mendeklarasikan array pointer, bukan array 2D. Jika Anda menginginkan array 2D, tidak ada alasan mengapa Anda ingin mengalokasikan array pointer. Lambat karena fragmentasi heap dan pemanfaatan memori cache yang buruk, dan tidak aman karena Anda tidak dapat menggunakannya sebagai array (dengan memcpy dll). Ditambah kodenya membengkak. Anda akan memerlukan beberapa panggilan free () dan akan mudah menyebabkan kebocoran memori. Tersebar luas seperti kode seperti itu, itu jelas buruk.
Lundin
15
Masalah ini akan lebih jelas untuk dijelaskan / dijawab seandainya sampel tidak menggunakan dimensi nilai yang sama n+1melainkandouble (*e)[rows] = malloc(columns * sizeof *e);
chux - Reinstate Monica

Jawaban:

87

Variabel eadalah penunjuk ke larik n + 1elemen tipe double.

Menggunakan operator dereferensi pada ememberi Anda tipe dasar eyang adalah "larik n + 1elemen tipe double".

The mallocpanggilan hanya mengambil basis-jenis e(dijelaskan di atas) dan mendapat ukurannya, mengalikan dengan n + 1, dan melewati ukuran yang ke mallocfungsi. Pada dasarnya mengalokasikan larik n + 1larik n + 1elemen double.

Beberapa programmer
sumber
3
@MartinJames sizeof(*e)setara dengan sizeof(double [n + 1]). Lipat gandakan dengan n + 1dan Anda mendapatkan cukup.
Beberapa programmer dude
24
@MartinJames: Apa yang salah dengan itu? Ini tidak terlalu tajam, ini menjamin bahwa baris yang dialokasikan berdekatan, dan Anda dapat mengindeksnya seperti array 2D lainnya. Saya banyak menggunakan idiom ini dalam kode saya sendiri.
John Bode
3
Ini mungkin terlihat jelas, tetapi ini hanya berfungsi untuk array persegi (dimensi yang sama).
Jens
18
@ Jens: Hanya dalam arti jika Anda menempatkan n+1untuk kedua dimensi, hasilnya akan persegi. Jika Anda melakukannya double (*e)[cols] = malloc(rows * sizeof(*e));, hasilnya akan memiliki jumlah baris dan kolom berapa pun yang Anda tentukan.
user2357112 mendukung Monica
9
@ user2357112 Sekarang saya lebih suka melihat. Bahkan jika itu berarti Anda harus menambahkan int rows = n+1dan int cols = n+1. Tuhan menyelamatkan kita dari kode pintar.
candied_orange
56

Ini adalah cara tipikal Anda harus mengalokasikan array 2D secara dinamis.

  • eadalah penunjuk larik ke larik bertipe double [n+1].
  • sizeof(*e)oleh karena itu memberikan tipe tipe point-at, yang merupakan ukuran satu double [n+1]array.
  • Anda mengalokasikan ruang untuk n+1array tersebut.
  • Anda mengatur penunjuk larik euntuk menunjuk ke larik pertama dalam larik larik ini.
  • Hal ini memungkinkan Anda untuk menggunakan esebagai e[i][j]akses setiap item dalam array 2D.

Secara pribadi menurut saya gaya ini jauh lebih mudah dibaca:

double (*e)[n+1] = malloc( sizeof(double[n+1][n+1]) );
Lundin
sumber
12
Jawaban bagus kecuali saya tidak setuju dengan gaya yang Anda sarankan, lebih memilih ptr = malloc(sizeof *ptr * count)gaya tersebut.
chux - Kembalikan Monica
Jawaban bagus, dan saya suka gaya yang Anda sukai. Sedikit perbaikan mungkin untuk menunjukkan bahwa Anda perlu melakukannya dengan cara ini karena mungkin ada bantalan di antara baris yang perlu diperhitungkan. (Setidaknya, saya pikir itulah alasan Anda perlu melakukannya dengan cara ini.) (Beri tahu saya jika saya salah.)
davidbak
2
@davidbak Itu hal yang sama. Sintaks array hanyalah kode yang mendokumentasikan sendiri: ia mengatakan "mengalokasikan ruang untuk array 2D" dengan kode sumber itu sendiri.
Lundin
1
@davidbak Catatan: Kerugian kecil dari komentar malloc(row*col*sizeof(double)) terjadi saat row*col*sizeof()meluap, tetapi tidak sizeof()*row*colterjadi. (misalnya baris, kolom int)
chux - Kembalikan Monica
7
@davidbak: sizeof *e * (n+1)lebih mudah dirawat; jika Anda pernah memutuskan untuk mengubah tipe dasar (dari doublemenjadi long double, misalnya), maka Anda hanya perlu mengubah deklarasi dari e; Anda tidak perlu mengubah sizeofekspresi dalam mallocpanggilan (yang menghemat waktu dan melindungi Anda dari mengubahnya di satu tempat tetapi tidak di tempat lain). sizeof *eakan selalu memberi Anda ukuran yang tepat.
John Bode
39

Idiom ini secara alami keluar dari alokasi larik 1D. Mari kita mulai dengan mengalokasikan array 1D dari beberapa tipe arbitrer T:

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

Sederhana bukan? The ekspresi *p memiliki tipe T, sehingga sizeof *pmemberikan hasil yang sama seperti sizeof (T), jadi kita mengalokasikan cukup ruang untuk Nberbagai -element dari T. Ini berlaku untuk semua tipeT .

Sekarang, mari kita gantikan Tdengan tipe array seperti R [10]. Kemudian alokasi kami menjadi

R (*p)[10] = malloc( sizeof *p * N);

Semantik di sini persis sama dengan metode alokasi 1D; semua yang berubah adalah jenis p. Alih-alih T *, sekarang R (*)[10]. Ekspresi *pmemiliki tipe Tyaitu tipe R [10], jadi sizeof *pekuivalen dengan sizeof (T)yang ekivalen dengan sizeof (R [10]). Jadi kita mengalokasikan cukup ruang untuk Noleh 10elemen array R.

Kita dapat mengambil ini lebih jauh jika kita mau; misalkan Ritu sendiri merupakan tipe array int [5]. Gantikan itu Rdan kita dapatkan

int (*p)[10][5] = malloc( sizeof *p * N);

Kesepakatan yang sama - sizeof *psama dengan sizeof (int [10][5]), dan kami akhirnya mengalokasikan sebagian besar memori yang berdekatan yang cukup besar untuk menampung Noleh 10oleh 5array int.

Jadi itulah sisi alokasi; bagaimana dengan sisi aksesnya?

Ingat bahwa []operasi subskrip didefinisikan dalam istilah aritmatika penunjuk: a[i]didefinisikan sebagai *(a + i)1 . Jadi, operator subskrip [] secara implisit merujuk sebuah pointer. Jika ppenunjuk ke T, Anda dapat mengakses nilai menunjuk ke baik dengan secara eksplisit dereferensi dengan *operator unary :

T x = *p;

atau dengan menggunakan []operator subskrip:

T x = p[0]; // identical to *p

Jadi, jika pmenunjuk ke elemen pertama dari sebuah array , Anda dapat mengakses elemen apa pun dari array itu dengan menggunakan subskrip pada penunjuk p:

T arr[N];
T *p = arr; // expression arr "decays" from type T [N] to T *
...
T x = p[i]; // access the i'th element of arr through pointer p

Sekarang, mari kita lakukan operasi substitusi lagi dan ganti Tdengan tipe array R [10]:

R arr[N][10];
R (*p)[10] = arr; // expression arr "decays" from type R [N][10] to R (*)[10]
...
R x = (*p)[i];

Satu perbedaan yang langsung terlihat; kami secara eksplisit mendereferensi psebelum menerapkan operator subskrip. Kami tidak ingin subskrip ke p, kami ingin subskrip ke p poin apa (dalam hal ini, array arr[0] ). Sejak unary *memiliki hak lebih rendah dari subscript []operator, kita harus menggunakan tanda kurung secara eksplisit kelompok pdengan *. Tapi ingat dari atas itu *psama dengan p[0], jadi kita bisa menggantinya dengan

R x = (p[0])[i];

atau hanya

R x = p[0][i];

Jadi, jika pmenunjuk ke larik 2D, kita bisa mengindeks ke larik itu melalui pseperti ini:

R x = p[i][j]; // access the i'th element of arr through pointer p;
               // each arr[i] is a 10-element array of R

Mengambil kesimpulan yang sama seperti di atas dan menggantinya Rdengan int [5]:

int arr[N][10][5];
int (*p)[10][5]; // expression arr "decays" from type int [N][5][10] to int (*)[10][5]
...
int x = p[i][j][k];

Ini berfungsi sama jika pmenunjuk ke array biasa, atau jika menunjuk ke memori yang dialokasikan malloc.

Idiom ini memiliki manfaat sebagai berikut:

  1. Sederhana - hanya satu baris kode, sebagai lawan dari metode alokasi sedikit demi sedikit
    T **arr = malloc( sizeof *arr * N );
    if ( arr )
    {
      for ( size_t i = 0; i < N; i++ )
      {
        arr[i] = malloc( sizeof *arr[i] * M );
      }
    }
  2. Semua baris dari array yang dialokasikan adalah * bersebelahan *, yang tidak terjadi dengan metode alokasi sepotong-sepotong di atas;
  3. Mendelokasi array semudah dengan satu panggilan ke free. Sekali lagi, tidak benar dengan metode alokasi sedikit demi sedikit, di mana Anda harus membatalkan alokasi masing-masing arr[i]sebelum Anda dapat membatalkan alokasi arr.

Terkadang metode alokasi sedikit demi sedikit lebih disukai, seperti saat heap Anda terfragmentasi dengan buruk dan Anda tidak dapat mengalokasikan memori sebagai potongan yang berdekatan, atau Anda ingin mengalokasikan larik "bergerigi" di mana setiap baris dapat memiliki panjang yang berbeda. Tetapi secara umum, ini adalah cara yang lebih baik untuk pergi.


1. Ingat bahwa array bukanlah pointer - sebaliknya, ekspresi array diubah menjadi ekspresi pointer jika perlu.

John Bode
sumber
4
+1 Saya suka cara Anda menyajikan konsep: mengalokasikan serangkaian elemen dimungkinkan untuk semua jenis, bahkan jika elemen itu adalah array itu sendiri.
logo_writer
1
Penjelasan Anda sangat bagus, tetapi perhatikan bahwa alokasi memori yang berdekatan bukanlah manfaat sampai Anda benar-benar membutuhkannya. Memori yang berdekatan lebih mahal daripada yang tidak bersebelahan. Untuk larik 2D sederhana, tidak ada perbedaan dalam tata letak memori untuk Anda (kecuali jumlah baris untuk alokasi dan pelepasan alokasi), jadi lebih suka menggunakan memori yang tidak bersebelahan.
Oleg Lokshyn