Container Sequence

STL menyediakan lima container sequence utama yang menyimpan elemen dalam urutan linier: vector, deque, list, array, dan forward_list. Kelimanya menyediakan antarmuka mirip (iterasi, size, front/back) tetapi menggunakan representasi internal yang sangat berbeda — array kontigu, rangkaian chunk, atau linked list. Pemilihan container yang tepat menentukan apakah operasi insert di tengah berjalan dalam O(1) atau O(n). Pada Chapter ini kita akan memetakan kapan memakai masing-masing container dan bagaimana cara kerja internalnya memengaruhi kompleksitas operasi.

Lima Container Sequence #

Mekanisme Internal: Vector vs Deque vs List #

• std::vector: memori kontigu seperti array C. Saat push_back dan kapasitas penuh, vector mengalokasikan blok baru 2× lipat, menyalin elemen lama, lalu membebaskan blok lama. Akibatnya push_back bersifat O(1) amortisasi — sebagian besar operasi cepat, sesekali ada realokasi mahal. Iterasi sangat cache-friendly karena elemen bersebelahan secara fisik.
• std::deque (double-ended queue): menyimpan elemen dalam rangkaian chunk berukuran tetap (mis. 512 byte per chunk). Tambah di depan dan belakang sama-sama O(1). Akses acak O(1) tetapi lebih lambat dari vector karena butuh dua indirection (chunk pointer + offset dalam chunk).
• std::list: setiap elemen dibungkus node yang menyimpan pointer ke node berikutnya dan sebelumnya. Insert/erase pada iterator yang sudah dimiliki adalah O(1) — tidak perlu menggeser elemen lain. Tetapi iterasi tidak cache-friendly dan setiap node menambah overhead 16 byte untuk pointer.

Kode: Lima Container Berdampingan #

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <array>
#include <forward_list>
#include <algorithm>

int main() {
    // 1) vector — push_back O(1) amortized
    std::vector<int> v;
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) v.push_back(x);
    std::cout << "vector  : ";
    for (int x : v) std::cout << x << ' ';
    std::cout << "(size=" << v.size() << ", cap=" << v.capacity() << ")\n";

    // Random access O(1)
    std::cout << "v[3]    = " << v[3] << '\n';
    v.pop_back();
    std::cout << "after pop_back: size=" << v.size() << '\n';

    // 2) deque — push_front O(1)
    std::deque<int> dq;
    for (int x : {3, 1, 4, 1, 5}) dq.push_front(x);
    dq.push_back(99);
    std::cout << "deque   : ";
    for (int x : dq) std::cout << x << ' ';
    std::cout << "(front=" << dq.front() << ", back=" << dq.back() << ")\n";

    // 3) list — doubly linked list, O(1) splice di iterator
    std::list<int> L = {10, 20, 30, 40};
    auto it = std::next(L.begin());  // iterator ke 20
    L.insert(it, 15);                 // sisipkan 15 sebelum 20 -> O(1)
    std::cout << "list    : ";
    for (int x : L) std::cout << x << ' ';
    std::cout << '\n';
    L.remove(20);                     // hapus semua elemen bernilai 20 -> O(n)
    std::cout << "list    : ";
    for (int x : L) std::cout << x << ' ';
    std::cout << '\n';

    // 4) array — fixed size di stack
    std::array<int, 5> arr = {5, 4, 3, 2, 1};
    std::sort(arr.begin(), arr.end());
    std::cout << "array   : ";
    for (int x : arr) std::cout << x << ' ';
    std::cout << "(size=" << arr.size() << ")\n";

    // 5) forward_list — singly linked list
    std::forward_list<int> fl = {1, 2, 3, 4};
    fl.push_front(0);
    fl.insert_after(fl.begin(), 99);
    std::cout << "fwd_list: ";
    for (int x : fl) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

vector  : 3 1 4 1 5 9 2 6 (size=8, cap=8)
v[3]    = 1
after pop_back: size=7
deque   : 5 1 4 1 3 99 (front=5, back=99)
list    : 10 15 20 30 40 
list    : 10 15 30 40 
array   : 1 2 3 4 5 (size=5)
fwd_list: 0 99 1 2 3 4 

Bedah Kode Baris-per-Baris #

1. std::vector<int> v; lalu v.push_back(x) delapan kali: vector tumbuh otomatis. Kapasitas awal 0, lalu tumbuh ke 1, 2, 4, 8 — di akhir kapasitas sama dengan size (8) karena realokasi terakhir tepat menampung delapan elemen.
2. v[3]: akses acak langsung lewat pointer arithmetic — O(1). Index 3 dari {3,1,4,1,5,9,2,6} adalah 1.
3. v.pop_back(): hapus elemen terakhir. Size turun ke 7 tetapi kapasitas tetap 8 (tidak menyusut otomatis).
4. dq.push_front(x): deque menambah chunk baru di depan bila chunk depan penuh. Lima elemen dimasukkan dari depan sehingga urutan terbalik: {5,1,4,1,3}. Lalu push_back(99) menambah di belakang — total {5,1,4,1,3,99}.
5. L.insert(it, 15): it menunjuk node bernilai 20. Insert 15 sebelum it adalah O(1) — cukup susun ulang pointer dua node. List menjadi {10,15,20,30,40}.
6. L.remove(20): menghapus semua node bernilai 20. Operasi ini O(n) karena harus scan seluruh list untuk mencari elemen bernilai 20.
7. std::sort(arr.begin(), arr.end()): std::array menyediakan random-access iterator sehingga std::sort dapat dipakai langsung. Urutan {5,4,3,2,1} menjadi {1,2,3,4,5}.
8. fl.push_front(0); fl.insert_after(fl.begin(), 99);: forward_list hanya bisa insert setelah iterator tertentu (karena node tidak menyimpan pointer ke predecessor). Setelah push_front(0) list menjadi {0,1,2,3,4}. Setelah insert_after(begin, 99) menjadi {0,99,1,2,3,4}.

Kapan Memakai Apa #

Ringkasan #

• Lima container sequence STL: vector (array dinamis), deque (array of chunks), list (doubly linked), array (statis), forward_list (singly linked).
• vector adalah pilihan default — cepat, kontigu, dan cache-friendly.
• deque untuk operasi dua arah di ujung; list/forward_list untuk insert/erase O(1) pada iterator yang dimiliki.
• array menyimpan elemen di stack; cocok untuk buffer berukuran kecil dan tetap.
• Hindari linked list untuk DSA kecuali profil operasi benar-benar menuntutnya — cache locality vector sering membuatnya lebih cepat dalam praktik.