ArrayList

Panjang sebuah koleksi sering kali baru diketahui saat program berjalan, misalnya banyaknya nilai ujian yang melewati ambang lulus. std.ArrayList adalah koleksi yang tumbuh mengikuti kebutuhan, dan setiap pertumbuhannya dibiayai oleh allocator yang diteruskan secara eksplisit. Topik ini membahas deklarasi ArrayList pada Zig 0.17.0, operasi penambah dan penyaringan elemen, hubungan kapasitas dengan panjang, serta pengubahan daftar menjadi slice milik pemanggil.

Konsep#

Deklarasi dan pengikatan allocator#

Nilai std.ArrayList(T) dideklarasikan dengan menyebut tipe elemennya dan diawali kosong melalui .empty, seperti var lulus: std.ArrayList(u8) = .empty. Allocator tidak disimpan di dalam struct, melainkan diteruskan pada setiap metode yang membutuhkannya, misalnya lulus.append(alloc, 80). Gaya ini disebut bentuk unmanaged, karena daftar tidak mengelola sumber memorinya sendiri, dan menjadi satu-satunya gaya ArrayList pada pustaka standar 0.17.0.

Konsekuensi gaya tersebut terasa langsung pada pembacaan kode. Setiap baris yang berpotensi mengalokasikan memuat alloc secara tertulis, sehingga biaya pertumbuhan daftar terlihat pada tempatnya. Konstanta .empty menjamin daftar yang baru dideklarasikan tidak memegang memori apa pun, sehingga deklarasi yang tidak sempat dipakai tidak menimbulkan alokasi maupun pembebasan.

// tidak-dijalankan
var daftar: std.ArrayList(u32) = .empty;
defer daftar.deinit(alloc);
try daftar.append(alloc, 12);
try daftar.appendSlice(alloc, &.{ 24, 36 });

Metode append menambah satu elemen dan appendSlice menambah banyak elemen sekaligus, dan keduanya mengembalikan error alokasi yang lazim diteruskan dengan try. Pembebasan dititipkan pada deinit(alloc) yang mengembalikan seluruh kapasitas daftar ke allocator. Pasangan .empty di awal dan deinit di akhir menjadi bingkai baku setiap daftar.

Contoh Lengkap#

Menyaring nilai ke dalam daftar#

Pola pemakaian yang paling umum adalah mengumpulkan hasil penyaringan. Program berikut membaca array nilai ujian yang panjangnya tetap, lalu mengumpulkan nilai yang melewati ambang 75 ke dalam ArrayList yang jumlah akhirnya baru diketahui setelah perulangan selesai.

const std = @import("std");

pub fn main() !void {
    const alloc = std.heap.page_allocator;

    const nilai = [_]u8{ 60, 85, 74, 90, 78, 95, 69 };

    var lulus: std.ArrayList(u8) = .empty;
    defer lulus.deinit(alloc);

    for (nilai) |n| {
        if (n >= 75) {
            try lulus.append(alloc, n);
        }
    }

    const hasil = try lulus.toOwnedSlice(alloc);
    defer alloc.free(hasil);

    std.debug.print("jumlah lulus: {d}\n", .{hasil.len});
    for (hasil) |n| {
        std.debug.print("nilai lulus: {d}\n", .{n});
    }
}

jumlah lulus: 4
nilai lulus: 85
nilai lulus: 90
nilai lulus: 78
nilai lulus: 95

Setiap nilai yang memenuhi syarat ditambahkan dengan try lulus.append(alloc, n), sehingga kegagalan alokasi di tengah perulangan langsung menyebarkan error keluar dari main. Baris toOwnedSlice(alloc) mengubah daftar menjadi slice []u8 yang berdiri sendiri, dan slice itulah yang dicetak oleh perulangan berikutnya. Karena hasilnya sudah menjadi slice biasa, free dijalankan atas slice tersebut tanpa melibatkan daftar lagi.

# mengompilasi dan menjalankan program
zig run filter-lulus.zig

jumlah lulus: 4
nilai lulus: 85
nilai lulus: 90
nilai lulus: 78
nilai lulus: 95

Kapasitas dan panjang#

items.len adalah jumlah elemen yang benar-benar berisi, sedangkan kapasitas adalah banyaknya ruang yang sudah disiapkan di belakang layar. Saat panjang mencapai kapasitas dan append diminta lagi, ArrayList memperoleh blok yang lebih besar dari allocator, menyalin isinya, lalu membebaskan blok lama. Pertumbuhan berlangsung dalam lompatan, sehingga banyak panggilan append berurutan tidak menimbulkan alokasi baru pada setiap panggilan.

Program berikut mencetak kedua angka itu pada setiap penambahan, sehingga perbedaan keduanya terlihat secara langsung.

const std = @import("std");

pub fn main() !void {
    const alloc = std.heap.page_allocator;

    var daftar: std.ArrayList(u32) = .empty;
    defer daftar.deinit(alloc);

    std.debug.print("awal: panjang {d}, kapasitas {d}\n", .{ daftar.items.len, daftar.capacity });
    var i: u32 = 1;
    while (i <= 9) : (i += 1) {
        try daftar.append(alloc, i);
        std.debug.print("append {d}: panjang {d}, kapasitas {d}\n", .{ i, daftar.items.len, daftar.capacity });
    }
}

awal: panjang 0, kapasitas 0
append 1: panjang 1, kapasitas 33
append 2: panjang 2, kapasitas 33
append 3: panjang 3, kapasitas 33
append 4: panjang 4, kapasitas 33
append 5: panjang 5, kapasitas 33
append 6: panjang 6, kapasitas 33
append 7: panjang 7, kapasitas 33
append 8: panjang 8, kapasitas 33
append 9: panjang 9, kapasitas 33

Keluaran di atas memperlihatkan polanya. Kapasitas melompat dari 0 ke 33 pada append pertama dan tidak berubah sampai perulangan berakhir, sedangkan panjang menaiki satu per satu. Angka 33 sendiri bergantung pada tipe elemen dan platform, tetapi polanya tidak berubah, yaitu lompatan kapasitas terjadi lebih dahulu kemudian panjang yang mengejar.

Konsekuensi pentingnya menyangkut alamat elemen. Ketika blok lama diganti blok baru, seluruh isi berpindah tempat, sehingga pointer atau slice yang menunjuk ke dalam items menjadi tidak sah setelah daftar bertumbuh. Ambil alamat elemen hanya untuk dipakai segera, atau selesaikan seluruh pertumbuhan lebih dahulu sebelum alamat dibagikan.

# mengompilasi dan menjalankan program
zig run kapasitas.zig

awal: panjang 0, kapasitas 0
append 1: panjang 1, kapasitas 33
append 2: panjang 2, kapasitas 33
append 3: panjang 3, kapasitas 33
append 4: panjang 4, kapasitas 33
append 5: panjang 5, kapasitas 33
append 6: panjang 6, kapasitas 33
append 7: panjang 7, kapasitas 33
append 8: panjang 8, kapasitas 33
append 9: panjang 9, kapasitas 33

Mengubah daftar menjadi slice#

Dua cara menutup masa hidup daftar tersedia, dan pilihannya bergantung pada tujuan. deinit(alloc) membuang daftar beserta isinya, sedangkan toOwnedSlice(alloc) menyerahkan isi daftar kepada pemanggil dalam bentuk slice dan mengembalikan daftar menjadi .empty. Setelah toOwnedSlice, pembebasan beralih ke free atas slice hasilnya, dan daftar tidak perlu deinit lagi karena tidak memegang memori apa pun.

// tidak-dijalankan
try daftar.insert(alloc, 1, 18);
const terakhir = daftar.pop();
// pop mengembalikan ?T, bernilai null bila daftar kosong

Di luar penambahan, ArrayList menyediakan insert untuk menyisipkan elemen pada indeks tertentu dan pop untuk mengambil elemen terakhir. Nilai kembalian pop adalah optional, yaitu null bila daftar kosong, sehingga keputusan pada daftar kosong tidak dapat terlewat. Metode yang berpotensi mengalokasikan tetap menerima allocator pada setiap panggilannya, sesuai gaya 0.17.0.

Kesalahan umum#

1. Metode dipanggil tanpa argumen allocator. Kompilator menolaknya karena setiap metode yang berpotensi mengalokasikan menerima alloc secara eksplisit. Tambahkan argumen allocator pada panggilan yang ditandai error.
2. Slice lama dipakai setelah daftar bertumbuh. Isi berpindah blok sehingga slice tersebut menunjuk memori yang sudah dibebaskan. Perbarui slice dari daftar.items setelah setiap pertumbuhan.
3. Daftar lama diasumsikan masih berisi setelah toOwnedSlice. Daftar dikembalikan ke .empty oleh metode tersebut, sehingga items-nya kosong. Simpan slice hasilnya dan perlakukan daftar sebagai kosong.

Ringkasan#

• ArrayList gaya 0.17.0 diawali .empty dan meneruskan allocator pada setiap metode yang berpotensi mengalokasikan.
• append, appendSlice, dan insert menumbuhkan daftar, sedangkan pop mengembalikan elemen terakhir sebagai optional.
• Kapasitas bertumbuh dalam lompatan, dan setiap lompatan memindahkan isi sehingga alamat ke dalam items berumur pendek.
• toOwnedSlice menyerahkan isi sebagai slice dan mengosongkan daftar, sedangkan deinit membuang seluruhnya.

Referensi#

• std.ArrayList — Dokumentasi pustaka standar Zig — Deklarasi .empty, metode pengumpulan, dan toOwnedSlice.