Array adalah struktur data paling dasar: sekumpulan elemen bertipe sama yang diletakkan berurutan di memori. Karena berurutan, akses ke elemen ke-i bisa dilakukan langsung dengan aritmetika alamat dalam O(1) — keunggulan yang tidak dimiliki struktur data berbasis node. Kelemahannya, array “biasa” memiliki ukuran yang terkunci sejak waktu kompilasi, sementara kebutuhan nyata jarang bisa diprediksi sedemikian tepat. Chapter ini membedakan kedua dunia tersebut lalu membangun dynamic array mini kita sendiri, sehingga kita memahami persis apa yang dilakukan std::vector setiap kali ia kehabisan kapasitas.

Array Statis: Sederhana tetapi Ukurannya Kaku #

Array statis seperti int data[5] dialokasikan pada stack dengan ukuran yang harus diketahui saat kompilasi. Kelebihannya nyata: tanpa alokasi heap, tanpa manajemen memori manual, dan akses secepat mungkin. Kekurangannya menyeret dua masalah: ukuran terlalu kecil membuat program kehabisan tempat, sedangkan ukuran yang dibuat besar berlebihan memboroskan memori. Selain itu, akses data[i] dengan i di luar rentang adalah undefined behavior — compiler tidak memeriksa batas, sehingga kesalahan hanya terlihat saat program berperilaku aneh.

C++ modern juga menyediakan std::array<T, N> sebagai pembungkus aman array statis; ukurannya tetap wajib konstanta waktu kompilasi. Ketika jumlah elemen baru diketahui saat program berjalan, kita butuh struktur lain — di sinilah dynamic array masuk.

Ide Dynamic Array: Blok Memori yang Digandakan #

Dynamic array menyimpan dua informasi terpisah: size (jumlah elemen terisi) dan capacity (panjang blok memori yang sudah disiapkan). Ketika elemen baru ditambahkan dan size masih di bawah capacity, penulisan cukup diletakkan di slot kosong — murah, O(1). Begitu size mencapai capacity, struktur ini menyewa blok memori baru yang lebih besar, menyalin semua elemen lama, lalu membebaskan blok lama; proses ini disebut realokasi.

Strategi pertumbuhan yang dipakai hampir semua implementasi adalah doubling: kapasitas baru = kapasitas lama × 2. Dengan cara ini, biaya penyalinan yang mahal makin jarang terjadi, dan biaya rata-rata per push_back tetap konstan (amortized O(1)) walaupun satu operasi tertentu terasa lambat.

Implementasi Mini DynamicArray<int> #

Program berikut membangun dynamic array untuk int dari bahan mentah: pointer new[], penghitung ukuran, dan kapasitas. Pesan “Realokasi” dicetak setiap kali kapasitas naik, sehingga pola 1 → 2 → 4 → 8 terlihat jelas:

cpp 
// DynamicArray<int> mini: memahami cara std::vector tumbuh dengan doubling.
#include <cstddef>
#include <iostream>

class DynamicArray {
public:
    DynamicArray() : data_(nullptr), ukuran_(0), kapasitas_(0) {}
    ~DynamicArray() { delete[] data_; }

    // Kepemilikan pointer membuat penyalinan otomatis berbahaya (shallow copy),
    // jadi penyalinan dimatikan. Pembahasan copy constructor ada di chapter OOP.
    DynamicArray(const DynamicArray&) = delete;
    DynamicArray& operator=(const DynamicArray&) = delete;

    void push_back(int nilai) {
        if (ukuran_ == kapasitas_) {
            int kapasitasBaru = (kapasitas_ == 0) ? 1 : kapasitas_ * 2;  // doubling
            int* baru = new int[kapasitasBaru];
            for (int i = 0; i < ukuran_; ++i) {
                baru[i] = data_[i];  // salin elemen lama ke blok memori baru
            }
            delete[] data_;
            data_ = baru;
            kapasitas_ = kapasitasBaru;
            std::cout << "  Realokasi: kapasitas naik menjadi " << kapasitas_ << '\n';
        }
        data_[ukuran_] = nilai;
        ++ukuran_;
    }

    int size() const { return ukuran_; }
    int capacity() const { return kapasitas_; }
    int& operator[](int indeks) { return data_[indeks]; }
    int operator[](int indeks) const { return data_[indeks]; }

private:
    int* data_;
    int ukuran_;
    int kapasitas_;
};

int main() {
    // Array statis: ukuran tetap sejak waktu kompilasi, hidup di stack
    int statis[5] = {10, 20, 30, 40, 50};
    std::cout << "Array statis : ";
    for (int i = 0; i < 5; ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << statis[i];
    }
    std::cout << '\n';

    // Dynamic array: tumbuh sesuai kebutuhan lewat realokasi dan penyalinan
    DynamicArray dinamis;
    for (int nilai : {7, 14, 21, 28, 35}) {
        dinamis.push_back(nilai);
        std::cout << "push_back(" << nilai << ") -> ukuran=" << dinamis.size()
                  << ", kapasitas=" << dinamis.capacity() << '\n';
    }

    std::cout << "Isi akhir    : ";
    for (int i = 0; i < dinamis.size(); ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << dinamis[i];
    }
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Array statis : 10 20 30 40 50
  Realokasi: kapasitas naik menjadi 1
push_back(7) -> ukuran=1, kapasitas=1
  Realokasi: kapasitas naik menjadi 2
push_back(14) -> ukuran=2, kapasitas=2
  Realokasi: kapasitas naik menjadi 4
push_back(21) -> ukuran=3, kapasitas=4
push_back(28) -> ukuran=4, kapasitas=4
  Realokasi: kapasitas naik menjadi 8
push_back(35) -> ukuran=5, kapasitas=8
Isi akhir    : 7 14 21 28 35

Bedah baris penting:

  1. Baris 7-8: constructor memulai dengan nullptr dan ukuran nol — belum ada memori yang disewa; baris destructor delete[] data_ membebaskannya saat objek mati, sehingga tidak terjadi memory leak.
  2. Baris 12-13: copy constructor dan assignment operator sengaja di-delete. Tanpa ini, penyalinan otomatis akan menyalin pointer saja (shallow copy) dan dua objek akan menghapus blok memori yang sama dua kali.
  3. Baris 17: kunci doubling — kapasitas pertama adalah 1, lalu setiap realokasi menggandakannya.
  4. Baris 19-22: elemen lama disalin satu per satu ke blok baru sebelum blok lama dibebaskan. Inilah biaya realokasi: mahal, tetapi makin jarang terjadi.
  5. Baris 27-28: elemen baru ditulis ke slot ke-ukuran_, lalu penghitung dinaikkan — dua baris inilah seluruh pekerjaan push_back pada hari biasa.
  6. Baris 33-34: operator[] memberi akses indeks O(1), memakai aritmetika pointer di balik layar, persis seperti array statis.

Keluaran menunjukkan realokasi terjadi saat ukuran ke-1, ke-2, dan ke-5: tepat ketika kapasitas sebelumnya penuh. Setelah itu slot 5-8 tersedia tanpa kerja tambahan.

Kaitan dengan std::vector #

std::vector bekerja dengan mekanisme yang sama dan menambahkan keamanan serta fleksibilitas: size() dan capacity() terpisah, reserve(n) menyiapkan kapasitas lebih awal untuk menghindari realokasi berulang, dan realokasinya memakai move semantics agar elemen kompleks tidak disalin ulang. Bila Anda tahu akan mengisi 1.000 elemen, memanggil reserve(1000) lebih dulu menghemat lima kali proses salin yang tidak perlu.

Dynamic array unggul di ujung belakang: menambah dan menghapus di akhir itu cepat, tetapi menyisipkan di depan menuntut menggeser seluruh elemen. Struktur berikutnya, linked list, mengambil sisi sebaliknya — mahal di akses indeks, tetapi sigap saat menyambung node di mana saja.

Rujukan resmi: std::vector dan std::array .