Array dan Matriks Dinamis

Array biasa menuntut ukuran yang sudah pasti pada saat kode dikompilasi, sedangkan ukuran banyak kebutuhan nyata baru diketahui ketika program berjalan. Topik ini membahas dua pola alokasi dinamis yang paling sering dipakai untuk kebutuhan semacam itu. Pola pertama adalah array satu dimensi yang kapasitasnya dapat digandakan lewat realloc, sedangkan pola kedua adalah matriks dua dimensi berbasis int ** beserta urutan pembebasannya yang benar. Kedua pola ini menjadi bahan bangunan hampir seluruh penampung data yang ukurannya berubah-ubah.

Array dengan ukuran saat runtime#

Deklarasi int data[10]; mengikat ukuran array pada angka yang ditulis di kode, sedangkan blok heap mengikat ukurannya pada nilai yang boleh dihitung saat program berjalan. Pola dasarnya satu baris, yaitu memesan blok sebesar n * sizeof(tipe) dengan n berupa variabel, lalu memperlakukan alamat hasilnya seperti array biasa.

// tidak-dijalankan
int n = jumlah_nilai;                    /* n bisa berasal dari mana saja */
int *data = malloc((size_t)n * sizeof(int));
if (data == NULL) {
    return 1;
}

Keunggulan pola ini baru terasa penuh ketika jumlah data bertambah di tengah jalan. Array biasa tidak punya jalan keluar selain mendeklarasikan ukuran maksimumnya dari awal, sedangkan blok dinamis dapat diperbesar dengan realloc seperti pada pola berikut. Sumber nilai n sendiri bermacam-macam, mulai dari masukan pengguna, jumlah baris yang terbaca dari berkas, hingga hasil perhitungan program, dan semuanya diperlakukan sama karena malloc hanya menanyakan angkanya. Perlu diingat pula bahwa pointer yang menampung alamat blok malloc harus dijaga dengan baik, karena hilangnya alamat berarti hilangnya blok sebagaimana dibahas pada topik kebocoran memori.

Pola penggandaan kapasitas#

Menambah blok satu elemen pada setiap penambahan data menghabiskan waktu untuk alokasi dan penyalinan yang berulang. Pola yang lazim justru sebaliknya, yaitu memesan kapasitas awal, lalu menggandakannya setiap kali penuh. Dengan penggandaan, biaya perluasan yang mahal semakin jarang terjadi, sehingga penambahan satu nilai secara rata-rata hanya menuntut pekerjaan tetap atau $O(1)$ amortized. Variabel jumlah mencatat isi yang terpakai, sedangkan kapasitas mencatat ruang yang tersedia, dan keduanya harus dibedakan sejak awal.

Ukuran kapasitas awal tidak harus kecil, dan pilihannya boleh menyesuaikan perkiraan jumlah data. Nilai 2 pada contoh berikut dipilih agar penggandaannya segera terlihat, sedangkan program nyata biasanya berawal dari 10 hingga 100 elemen untuk menekan jumlah perluasan. Yang penting dari pola ini bukan angka awal, melainkan aturan pertumbuhan yang tetap, yaitu kapasitas baru selalu menjadi kelipatan kapasitas lama.

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

int main(void)
{
    int kapasitas = 2;
    int jumlah = 0;
    int *nilai = malloc((size_t)kapasitas * sizeof(int));
    if (nilai == NULL) {
        return 1;
    }

    int masukan[9] = {72, 88, 64, 91, 58, 77, 0};
    for (int i = 0; masukan[i] != 0; i = i + 1) {
        if (jumlah == kapasitas) {
            kapasitas = kapasitas * 2;
            int *sementara = realloc(nilai, (size_t)kapasitas * sizeof(int));
            if (sementara == NULL) {
                free(nilai);
                return 1;
            }
            nilai = sementara;
            printf("Kapasitas digandakan menjadi %d\n", kapasitas);
        }
        nilai[jumlah] = masukan[i];
        jumlah = jumlah + 1;
    }

    printf("Tersimpan %d nilai:", jumlah);
    for (int i = 0; i < jumlah; i = i + 1) {
        printf(" %d", nilai[i]);
    }
    printf("\n");
    free(nilai);
    return 0;
}

Kapasitas digandakan menjadi 4
Kapasitas digandakan menjadi 8
Tersimpan 6 nilai: 72 88 64 91 58 77

Perulangan mengisi enam nilai sementara blok hanya diperluas dua kali, yaitu ketika kapasitas 2 habis dan ketika kapasitas 4 habis. Perhatikan pula bahwa hasil realloc ditampung pada sementara lebih dahulu, karena apabila perluasan gagal, blok lama tetap tersimpan di nilai dan dapat dibebaskan dengan rapi. Isi lama tidak perlu disalin manual karena realloc memindahkannya sendiri ke blok baru bila pemindahan memang diperlukan.

Matriks dua dimensi dengan int **#

Matriks dinamis dibangun dari dua lapis alokasi. Lapis pertama adalah larik penunjuk baris bertipe int *, dan lapis kedua adalah satu blok untuk setiap baris. Variabel matriks bertipe int **, yaitu pointer ke pointer, sehingga ungkapan matriks[i] menghasilkan alamat baris ke-i dan matriks[i][j] menghasilkan elemen kolom ke-j pada baris tersebut. Diagram berikut menunjukkan kedua lapis itu beserta arah rujukannya.

Program berikut menyusun matriks perkalian 3 kali 4 lengkap dari awal hidupnya hingga pembebasannya. Perhatikan jalur penanganan kegagalan pada perulangan alokasi, karena baris yang sudah terbentuk harus ikut dibebaskan ketika alokasi baris berikutnya gagal.

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

#define BARIS 3
#define KOLOM 4

int main(void)
{
    int **matriks = malloc((size_t)BARIS * sizeof(int *));
    if (matriks == NULL) {
        return 1;
    }

    for (int i = 0; i < BARIS; i = i + 1) {
        matriks[i] = malloc((size_t)KOLOM * sizeof(int));
        if (matriks[i] == NULL) {
            /* bebaskan baris yang sudah terbentuk sebelum keluar */
            for (int j = 0; j < i; j = j + 1) {
                free(matriks[j]);
            }
            free(matriks);
            return 1;
        }
    }

    for (int i = 0; i < BARIS; i = i + 1) {
        for (int j = 0; j < KOLOM; j = j + 1) {
            matriks[i][j] = (i + 1) * (j + 1);
        }
    }

    for (int i = 0; i < BARIS; i = i + 1) {
        for (int j = 0; j < KOLOM; j = j + 1) {
            printf("%3d", matriks[i][j]);
        }
        printf("\n");
    }

    for (int i = 0; i < BARIS; i = i + 1) {
        free(matriks[i]);
    }
    free(matriks);
    return 0;
}

  1  2  3  4
  2  4  6  8
  3  6  9 12

Struktur ini punya satu keunggulan yang tidak dimiliki array dua dimensi biasa, yaitu setiap baris boleh berbeda panjangnya karena masing-masing dipesan terpisah. Ukuran baris dan kolom juga boleh ditentukan saat runtime, bukan hanya lewat konstanta seperti #define pada contoh. Harganya adalah jumlah alokasi yang lebih banyak, yaitu satu untuk larik penunjuk ditambah satu untuk setiap baris, sehingga pembebasannya juga lebih banyak.

Pembebasan dan alternatif satu blok#

Urutan pembebasan adalah kebalikan urutan alokasi, yaitu setiap baris terlebih dahulu, baru larik penunjuknya. Apabila larik penunjuk dibebaskan lebih dulu, akses matriks[i] berikutnya terjadi melalui alamat yang sudah tidak sah. Baris yang terlupa juga membuat seluruh isinya bocor meskipun larik penunjuknya sudah dibebaskan. Pola yang aman cukup dua perulangan, satu untuk membebaskan tiap baris dan satu pemanggilan free untuk larik penunjuknya.

Ada alternatif yang menghemat jumlah alokasi, yaitu memesan satu blok sebesar BARIS * KOLOM elemen lalu menghitung posisinya secara manual. Indeks dua arah diganti dengan aritmetika seperti pada contoh berikut.

// tidak-dijalankan
int *matriks = malloc((size_t)BARIS * KOLOM * sizeof(int));
matriks[i * KOLOM + j] = (i + 1) * (j + 1);   /* satu blok, satu free */

Alternatif ini dibebaskan dengan satu pemanggilan free. Seluruh data berdekatan di memori sehingga aksesnya ramah cache, dan siklus hidupnya lebih sederhana. Kekurangannya terletak pada sintaksnya, karena matriks[i][j] tidak dapat dipakai pada int * polos dan setiap akses harus menghitung i * KOLOM + j sendiri. Pilih bentuk int ** ketika baris perlu diperlakukan terpisah, dan pilih satu blok ketika matriksnya rapat serta diakses berurutan.

Kesalahan umum#

Kesalahan pada matriks dinamis hampir selalu berupa urutan atau ukuran yang salah, dan keduanya tidak terdeteksi saat kompilasi. Empat butir berikut perlu diperiksa setiap kali kode sejenis ditulis.

• Membebaskan hanya larik penunjuknya. Pemanggilan free(matriks); tanpa perulangan pembebasan baris menyisakan seluruh isi baris terpasang tanpa pencatat alamat. Tambahkan perulangan yang membebaskan matriks[i] satu per satu sebelum larik penunjuknya.
• Membalik urutan pembebasan. Membebaskan matriks lebih dahulu membuat akses matriks[i] pada perulangan berikutnya membaca alamat yang sudah dikembalikan. Ikuti urutan terbalik dari alokasi, yaitu baris terdalam dulu, larik penunjuk belakangan.
• Menukar ukuran tipe saat memesan lapis pertama. Lapis pertama menampung pointer, sehingga ukuran yang benar adalah sizeof(int *), bukan sizeof(int). Idiom malloc(BARIS * sizeof *matriks) membuat ukurannya mengikuti tipe penampung secara otomatis.
• Menganggap matriks int ** sama dengan array dua dimensi biasa. Array int a[3][4] menyimpan seluruh datanya dalam satu blok berurutan, sedangkan int ** menyimpan larik alamat baris, sehingga keduanya tidak dapat saling dipertukarkan pada parameter fungsi. Sesuaikan tipe parameternya dengan struktur yang benar-benar dipakai.

Ringkasan#

• Blok heap memungkinkan ukuran array ditentukan saat runtime, berbeda dari array biasa yang ukurannya harus tetap saat kompilasi.
• Penggandaan kapasitas lewat realloc membuat penambahan satu elemen berbiaya $O(1)$ amortized, dengan jumlah dan kapasitas dibedakan sejak awal.
• Matriks int ** terdiri atas larik penunjuk baris dan satu blok per baris, sehingga pembebasannya dilakukan baris demi baris sebelum larik penunjuknya.
• Alternatif satu blok dengan indeks i * KOLOM + j menghemat alokasi dan lebih ramah cache, dengan konsekuensi aritmetika indeks manual.

Referensi#

• malloc(3) — Linux man-pages project — Kontrak realloc saat blok diperbesar, termasuk isi yang dipertahankan dan kemungkinan pemindahan blok.
• Array — cppreference.com — Batasan array biasa yang ukuran dimensinya harus diketahui pada waktu kompilasi.