Konsep Array

Array adalah struktur data linier yang menyimpan elemen bertipe sama pada blok memori berurutan. Sifat kontigu inilah yang membuat array menjadi tulang punggung hampir seluruh algoritma klasik — sorting, searching, hingga struktur data lanjutan seperti heap dan hash table. Pada Chapter ini kita akan membedah tiga properti fundamental array: akses acak konstan, layout memori kontigu, dan ukuran tetap. Pemahaman terhadap ketiganya menjadi fondasi untuk memahami mengapa operasi insert berbiaya O(n) dan mengapa cache modern sangat menyukai pola akses array.

Tiga Properti Inti Array #

Sebelum masuk ke kode, kita perlu memetakan tiga sifat yang membedakan array dari struktur data lain:

1. Random access O(1) — Kita dapat membaca atau menulis arr[i] untuk sembarang i dalam waktu konstan, tanpa perlu menjelajah elemen sebelumnya.
2. Memory layout kontigu — Semua elemen menempati alamat memori yang berurutan tanpa celah, sehingga compiler dapat menghitung alamat elemen ke-i dengan rumus aritmetika sederhana.
3. Ukuran tetap — Jumlah elemen ditentukan saat deklarasi dan tidak dapat diubah setelahnya. Sifat inilah yang memicu kebutuhan akan std::vector.

Properti pertama dan kedua saling berkaitan: random access hanya mungkin karena layout memori kontigu. Properti ketiga adalah konsekuensi historis dari implementasi array di stack.

Layout Memori Kontigu #

Mekanisme: Aritmetika Alamat #

Compiler menyimpan array sebagai blok memori berukuran N * sizeof(T) byte, dimulai dari sebuah alamat base. Alamat elemen ke-i dihitung dengan rumus:

addr(arr[i]) = base + i * sizeof(T)

Rumus ini hanya melibatkan satu perkalian dan satu penambahan — keduanya operasi tunggal di CPU modern. Inilah alasan akses arr[i] selalu O(1), terlepas dari nilai i.

Untuk int arr[5] dengan sizeof(int) == 4, total memori yang dipakai adalah 20 byte dan setiap elemen berjarak tepat 4 byte dari tetangganya.

Kode: Mengamati Alamat Elemen #

#include <iostream>
#include <cstdint>

int main() {
    int arr[5] = {10, 20, 30, 40, 50};

    std::cout << "sizeof(int) = " << sizeof(int) << " byte\n";
    std::cout << "sizeof(arr) = " << sizeof(arr) << " byte\n\n";

    for (int i = 0; i < 5; ++i) {
        std::uintptr_t addr_i   = reinterpret_cast<std::uintptr_t>(&arr[i]);
        std::uintptr_t addr_0   = reinterpret_cast<std::uintptr_t>(&arr[0]);
        std::cout << "arr[" << i << "] offset = "
                  << (addr_i - addr_0) << " byte\n";
    }
    return 0;
}

Output yang Dihasilkan:

sizeof(int) = 4 byte
sizeof(arr) = 20 byte

arr[0] offset = 0 byte
arr[1] offset = 4 byte
arr[2] offset = 8 byte
arr[3] offset = 12 byte
arr[4] offset = 16 byte

1. Baris sizeof(arr): mengembalikan total byte yang dipakai array, yaitu 5 * sizeof(int) = 20. Hanya bekerja di scope deklarasi, bukan setelah array decay menjadi pointer.
2. Baris reinterpret_cast<std::uintptr_t>(&arr[i]): mengambil alamat elemen ke-i lalu mengonversinya menjadi bilangan bulat tanpa tanda agar bisa dikurangkan. uintptr_t menampung alamat tanpa kehilangan informasi.
3. Baris addr_i - addr_0: selisih alamat elemen ke-i dengan elemen ke-0. Hasilnya tepat i * 4 byte — bukti empiris bahwa elemen array berdiaman tepat berurutan tanpa celah.

Random Access O(1) #

Random access berarti membaca atau menulis elemen pada indeks tertentu dapat dilakukan dalam waktu konstan, terlepas dari posisi indeks. Bandingkan dengan linked list yang harus menjelajah pointer demi pointer dari head.

Mekanisme: Mengapa O(1) #

CPU menghitung alamat arr[i] dengan instruksi tunggal — perkalian dan penambahan alamat. Tidak ada loop, tidak ada traversal. Inilah properti yang membuat array menjadi struktur pilihan untuk tabel lookup, buffer, dan implementasi struktur data lain seperti heap.

Kode: Bandingkan Akses Awal vs Akhir #

#include <iostream>
#include <vector>
#include <chrono>

int main() {
    constexpr int N = 10'000'000;
    std::vector<int> arr(N, 1);

    auto t0 = std::chrono::high_resolution_clock::now();
    volatile long long sum = 0; // volatile: cegah optimasi hapus loop
    for (int i = 0; i < N; ++i) sum += arr[i];
    auto t1 = std::chrono::high_resolution_clock::now();

    auto mikro = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
    std::cout << "sum        = " << sum << '\n';
    std::cout << "waktu loop = " << mikro << " mikrodetik\n";
    return 0;
}

Output yang Dihasilkan (nilai waktu bervariasi):

sum        = 10000000
waktu loop = 4823 mikrodetik

1. Baris std::vector<int> arr(N, 1);: membuat std::vector berisi N elemen, semua bernilai 1. std::vector menggunakan array dinamis sebagai backbone, sehingga properti random access sama persis dengan C-style array.
2. Baris volatile long long sum: volatile mencegah compiler menghapus loop saat optimasi -O2. Tanpa volatile, compiler menyadari hasilnya konstan dan menyederhanakan menjadi sum = N langsung.
3. Hasil: total waktu untuk 10 juta akses adalah beberapa milidetik — sekitar 0,5 nanodetik per elemen. Inilah bukti bahwa akses array benar-benar O(1) per elemen.

Cache-Friendly: Mengapa Array Cepat #

CPU modern tidak membaca memori byte-per-byte. CPU membaca data dalam chunk 64 byte (satu cache line) sekaligus. Saat kita mengakses arr[0], CPU otomatis memuat arr[0..15] (untuk int) ke cache L1. Akses berikutnya ke arr[1], arr[2], dst. menjadi cache hit — jauh lebih cepat daripada membaca dari RAM.

Mekanisme: Spasial Lokalitas #

Properti kontigu array menghasilkan spatial locality yang tinggi: elemen yang berdekatan secara logis juga berdekatan secara fisik di memori. Inilah alasan traversal array dengan for berurutan bisa 5–10 kali lebih cepat dibanding traversal linked list dengan pointer acak, meski keduanya secara teori O(n).

Kode: Pola Akses Sekuensial vs Acak #

#include <iostream>
#include <vector>
#include <random>
#include <chrono>

int main() {
    constexpr int N = 1'000'000;
    std::vector<int> arr(N, 1);
    std::vector<int> idx(N);
    for (int i = 0; i < N; ++i) idx[i] = i;

    // Acak urutan indeks
    std::mt19937 rng(42);
    std::shuffle(idx.begin(), idx.end(), rng);

    volatile long long sum1 = 0;
    auto t0 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) sum1 += arr[i];            // sekuensial
    auto t1 = std::chrono::high_resolution_clock::now();

    volatile long long sum2 = 0;
    auto t2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) sum2 += arr[idx[i]];       // acak
    auto t3 = std::chrono::high_resolution_clock::now();

    auto sekuensial = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
    auto acak       = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    std::cout << "sekuensial = " << sum1 << " dalam " << sekuensial << " mikrodetik\n";
    std::cout << "acak       = " << sum2 << " dalam " << acak       << " mikrodetik\n";
    return 0;
}

Output yang Dihasilkan (waktu bervariasi):

sekuensial = 1000000 dalam 412 mikrodetik
acak       = 1000000 dalam 1623 mikrodetik

1. Baris std::shuffle(idx.begin(), idx.end(), rng);: mengacak urutan indeks sehingga traversal pada loop kedua membaca elemen array dalam urutan non-sekuensial.
2. Loop pertama (arr[i]): akses berurutan dari indeks 0 sampai N-1. Setiap cache line yang dimuat langsung dimanfaatkan penuh sebelum diganti.
3. Loop kedua (arr[idx[i]]): akses melompat-lompat. Setiap akses baru kemungkinan cache miss sehingga CPU harus membaca dari RAM. Meski total iterasi sama, waktu eksekusi ~4× lebih lambat.

Ukuran Tetap: Konsekuensi Historis #

C-style array dialokasikan di stack dengan ukuran yang ditentukan saat kompilasi. Ukuran ini tidak bisa diubah saat runtime — sebuah array int arr[10] selamanya berisi 10 elemen. Keterbatasan inilah yang melahirkan kebutuhan akan std::vector.

Ringkasan #

• Array menempati blok memori kontigu sehingga alamat elemen ke-i dapat dihitung dengan rumus aritmetika sederhana.
• Random access arr[i] selalu O(1) terlepas dari nilai i, asalkan indeks berada dalam batas [0, N).
• Layout kontigu menghasilkan spatial locality yang dimanfaatkan cache modern — traversal sekuensial jauh lebih cepat daripada acak.
• Ukuran array C-style bersifat tetap dan ditentukan saat kompilasi, sebuah keterbatasan yang diatasi std::vector.
• Pemahaman properti-properti ini menjadi dasar untuk memilih array atau alternatif lain (linked list, dynamic array) pada masalah DSA.