std::vector

std::vector adalah struktur data paling sering dipakai di C++ modern. Implementasinya adalah array dinamis: blok memori kontigu di heap yang ukurannya dapat berubah saat runtime. Pada Chapter ini kita akan membedah dua properti kunci std::vector — size vs capacity dan amortized O(1) push_back — lalu membahas jebakan iterator invalidation yang sering menjebak pemula. Pemahaman menyeluruh tentang std::vector menjadi prasyarat untuk hampir seluruh struktur data lain di STL.

Anatomi std::vector #

std::vector secara internal menyimpan tiga penunjuk:

1. begin — alamat elemen pertama.
2. end — alamat satu posisi setelah elemen terakhir (jumlah elemen aktif = end - begin).
3. cap — alamat satu posisi setelah kapasitas yang dialokasikan (kapasitas = cap - begin).

Karena elemen aktif selalu kontigu di memori, sifat random access dan cache-friendliness std::vector sama persis dengan C-style array.

size vs capacity #

Mekanisme: Ruang Aktif vs Ruang Alokasi #

• size: jumlah elemen aktif yang saat ini disimpan. Hasil dari v.size().
• capacity: jumlah elemen yang bisa ditampung tanpa realokasi. Hasil dari v.capacity().

Selisih capacity - size adalah slack — ruang cadangan untuk operasi push_back berikutnya tanpa realokasi.

Kode: Mengamati Pertumbuhan #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    std::cout << "size=" << v.size()
              << " capacity=" << v.capacity() << '\n';

    for (int i = 1; i <= 10; ++i) {
        v.push_back(i);
        std::cout << "push_back(" << i << "): "
                  << "size=" << v.size()
                  << " capacity=" << v.capacity() << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

size=0 capacity=0
push_back(1): size=1 capacity=1
push_back(2): size=2 capacity=2
push_back(3): size=3 capacity=4
push_back(4): size=4 capacity=4
push_back(5): size=5 capacity=8
push_back(6): size=6 capacity=8
push_back(7): size=7 capacity=8
push_back(8): size=8 capacity=8
push_back(9): size=9 capacity=16
push_back(10): size=10 capacity=16

1. Baris std::vector<int> v;: vector kosong, baik size maupun capacity bernilai 0.
2. Pola pertumbuhan 1, 2, 4, 8, 16: setiap kali size melebihi capacity, vector mengalokasikan ulang dengan kapasitas 2× (faktor pertumbuhan implementasi-defined; biasanya 2 di libstdc++).
3. capacity setelah push_back(4) tetap 4: realokasi terjadi pada push_back(3) menghasilkan capacity 4. Setelah itu, push_back(4) tidak memicu realokasi karena size == capacity masih dalam batas.

Amortized O(1) push_back #

Mekanisme: Rata-Rata per Operasi #

Biaya push_back terbagi dua:

• Case biasa (capacity > size): O(1) — tulis elemen di posisi end, geser end.
• Case realokasi (capacity == size): O(n) — alokasi blok baru 2×, salin n elemen, bebaskan blok lama.

Realokasi jarang terjadi (hanya pada size = 1, 2, 4, 8, ...). Bila kita melakukan n push_back dari vector kosong, total biaya adalah:

T(n) = 1 + 2 + 1 + 4 + 1 + 1 + 1 + 8 + ... ≈ 3n

Sehingga rata-rata per operasi adalah 3n / n = 3 — konstan. Inilah yang dimaksud amortized O(1). Analisis formalnya menggunakan aggregate method — lihat Chapter analisis-kompleksitas untuk pembahasan mendetail.

Kode: Demontrasi Amortisasi #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    int realokasi = 0;
    int total_push = 0;
    std::size_t cap_lama = 0;

    for (int i = 1; i <= 1000; ++i) {
        if (v.capacity() != cap_lama) {
            cap_lama = v.capacity();
            ++realokasi;
        }
        v.push_back(i);
        ++total_push;
    }

    std::cout << "total push_back  = " << total_push << '\n';
    std::cout << "jumlah realokasi = " << realokasi  << '\n';
    std::cout << "rasio (push/relokasi) = "
              << static_cast<double>(total_push) / realokasi << '\n';
    return 0;
}

Output yang Dihasilkan:

total push_back  = 1000
jumlah realokasi = 11
rasio (push/relokasi) = 90.9091

1. Baris if (v.capacity() != cap_lama): mendeteksi perubahan kapasitas — tanda terjadi realokasi pada iterasi sebelumnya.
2. Hasil realokasi = 11: dari 1000 push_back, hanya 11 kali realokasi terjadi (kapasitas 1, 2, 4, …, 1024). Realokasi menjadi kasus langka.
3. Rasio ~91: setiap realokasi melayani ~91 push_back rata-rata. Amortisasi: O(n)/O(n) ≈ O(1) per operasi.

reserve: Mencegah Realokasi #

Mekanisme: Alokasi Sekali di Awal #

Bila kita tahu ukuran akhir std::vector (mis. dari input problem), panggil reserve(n) setelah konstruksi. Hal ini mengalokasikan blok berkapasitas n sekaligus, menghindari seluruh realokasi pertumbuhan.

Kode: Tanpa vs dengan reserve #

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

int main() {
    constexpr int N = 1'000'000;

    // Tanpa reserve
    auto t0 = std::chrono::high_resolution_clock::now();
    std::vector<int> v1;
    for (int i = 0; i < N; ++i) v1.push_back(i);
    auto t1 = std::chrono::high_resolution_clock::now();
    auto ms1 = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count();

    // Dengan reserve
    auto t2 = std::chrono::high_resolution_clock::now();
    std::vector<int> v2;
    v2.reserve(N);
    for (int i = 0; i < N; ++i) v2.push_back(i);
    auto t3 = std::chrono::high_resolution_clock::now();
    auto ms2 = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();

    std::cout << "tanpa reserve: " << ms1 << " ms, capacity=" << v1.capacity() << '\n';
    std::cout << "dengan reserve: " << ms2 << " ms, capacity=" << v2.capacity() << '\n';
    return 0;
}

Output yang Dihasilkan (waktu bervariasi):

tanpa reserve: 14 ms, capacity=1048576
dengan reserve: 6 ms, capacity=1000000

1. Baris v2.reserve(N);: alokasi kapasitas N sekali di awal. Setiap push_back berikutnya menjadi case biasa O(1).
2. Hasil: waktu eksekusi turun signifikan (~2× lebih cepat) karena tidak ada salin elemen ulang saat realokasi.
3. capacity=1048576 vs 1000000: tanpa reserve, vector tumbuh ke kelipatan 2 (1048576 = 2²⁰). Dengan reserve, capacity tepat sesuai permintaan.

Iterator Invalidation #

Mekanisme: Kapan Iterator Valid #

Operasi std::vector tertentu membatalkan iterator, pointer, atau reference yang sudah ada. Tabel ringkas:

Pelanggaran paling umum: menyimpan iterator, lalu memanggil push_back yang memicu realokasi — iterator yang disimpan kini menunjuk ke memori yang sudah dibebaskan (dangling).

Kode: Jebakan Iterator Invalidation #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    int* p = &v[1];                  // p menunjuk ke elemen ke-1 (nilai 2)
    std::cout << "sebelum push: *p = " << *p << '\n';

    // Realokasi terjadi — p kini dangling
    for (int i = 0; i < 100; ++i) v.push_back(0);

    // Akses ulang p — perilaku tak terdefinisi (UB)
    // Untuk demo, kita cetak alamat saja (bukan dereferensi)
    std::cout << "setelah push banyak, alamat p mungkin tidak valid\n";
    std::cout << "v[1] (nilai baru) = " << v[1] << '\n';
    std::cout << "&v[1] (alamat baru) = " << &v[1] << '\n';
    std::cout << "p (alamat lama)     = " << p << '\n';
    return 0;
}

Output yang Dihasilkan (alamat bervariasi):

sebelum push: *p = 2
setelah push banyak, alamat p mungkin tidak valid
v[1] (nilai baru) = 2
&v[1] (alamat baru) = 0x55a1a2c2b2c4
p (alamat lama)     = 0x55a1a2c2a2c0

1. Baris int* p = &v[1];: menyimpan alamat elemen ke-1 vector.
2. Baris for (...) v.push_back(0);: setelah beberapa push_back, realokasi terjadi. Blok memori lama dibebaskan dan elemen disalin ke blok baru. p masih menyimpan alamat blok lama yang sudah tidak valid.
3. Alamat berbeda: &v[1] (baru) berbeda dari p (lama). Dereferensi *p akan menjadi undefined behavior — bisa membaca data acak, crash, atau tampak “benar” secara kebetulan.

Pola Idiomatik dengan std::vector #

Berikut beberapa idiom yang sering muncul di kode DSA:

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    // 1. Konstruksi langsung dengan initializer list
    std::vector<int> a = {3, 1, 4, 1, 5, 9};

    // 2. Konstruksi N elemen dengan nilai sama
    std::vector<int> b(5, 7);     // 5 elemen bernilai 7

    // 3. Konstruksi dari rentang iterator lain
    std::vector<int> c(a.begin(), a.begin() + 3);

    // 4. std::accumulate: jumlah seluruh elemen
    long long sum = std::accumulate(a.begin(), a.end(), 0LL);

    // 5. std::sort dengan komparator default
    std::sort(a.begin(), a.end());

    std::cout << "sum a = " << sum << '\n';
    std::cout << "a sorted:";
    for (int x : a) std::cout << ' ' << x;
    std::cout << '\n';

    std::cout << "b :";
    for (int x : b) std::cout << ' ' << x;
    std::cout << '\n';

    std::cout << "c :";
    for (int x : c) std::cout << ' ' << x;
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

sum a = 23
a sorted: 1 1 3 4 5 9
b : 7 7 7 7 7
c : 3 1 4

1. Baris std::vector<int> b(5, 7);: konstruksi dengan jumlah elemen dan nilai awal. Ekivalen dengan push_back(7) sebanyak 5 kali namun lebih efisien (alokasi sekali).
2. Baris std::accumulate(a.begin(), a.end(), 0LL): menjumlahkan seluruh elemen. Argumen 0LL (long long) menentukan tipe akumulasi — menghindari overflow bila jumlah melebihi INT_MAX.
3. Baris std::vector<int> c(a.begin(), a.begin() + 3);: konstruksi dari subrange. Elemen a[0..2] disalin ke c.

Ringkasan #

• std::vector adalah array dinamis: blok kontigu di heap yang ukurannya dapat berubah saat runtime.
• size adalah jumlah elemen aktif; capacity adalah ruang yang dialokasikan. Selisihnya adalah ruang cadangan untuk push_back cepat.
• push_back amortized O(1) — biaya rata-rata konstan karena realokasi jarang (faktor pertumbuhan 2× atau 1.5×).
• reserve(n) menghindari realokasi bila ukuran akhir diketahui — panggil setelah konstruksi.
• Operasi tertentu membatalkan iterator/pointer lama. Hindari menyimpan referensi lintas operasi yang dapat memicu realokasi.
• Untuk DSA, std::vector adalah pilihan default: efisien, ekspresif, dan terintegrasi penuh dengan STL.