Belajar C++ - Data Structures & STL Containers

#Pendahuluan

Menulis struktur data sendiri — linked list, hash table, tree — adalah latihan akademis yang bagus, tetapi di dunia nyata kalian hampir tidak perlu melakukannya. Standard Template Library (STL) menyediakan kontainer yang sudah diuji, efisien, dan aman.

Episode 8 memperkenalkan STL secara sistematis: kontainer sequence untuk data berurutan, kontainer asosiatif untuk pencarian cepat, iterator sebagai jembatan universal, algoritma std::algorithm yang siap pakai, dan container adaptors untuk pola stack dan queue. Memilih kontainer yang tepat adalah salah satu keputusan desain paling berpengaruh pada kinerja program.

#Sequence Containers

#std::vector, std::array, dan std::deque

std::vector adalah kontainer default: array dinamis yang tumbuh otomatis dan memiliki lokasi memori kontigu. std::array adalah array ukuran tetap di stack. std::deque mendukung penyisipan dan penghapusan cepat di kedua ujung. std::list adalah doubly-linked list dengan penyisipan O(1) di posisi mana pun:

cat > sequence.cpp <<'EOF'
#include <iostream>
#include <vector>
#include <array>
#include <deque>
 
int main() {
    std::vector<int> v{1, 2, 3};
    v.push_back(4);
    std::cout << "vector: " << v.size() << " elemen\n";
 
    std::array<int, 3> a{10, 20, 30};
    std::cout << "array: " << a[1] << "\n";
 
    std::deque<int> d;
    d.push_back(5);
    d.push_front(1);
    std::cout << "deque depan: " << d.front() << "\n";
}
EOF
g++ -std=c++20 sequence.cpp -o sequence
./sequence

v.push_back(4) menambah elemen di akhir vector. std::array<int, 3> menyimpan tipe elemen dan ukuran sebagai bagian dari tipe, jadi array ini tidak membocorkan memori dan bisa dipakai seperti array biasa.

#Memilih Kontainer

Aturan praktis: default ke std::vector. vector memiliki cache locality terbaik karena elemennya bersebelahan di memori. Gunakan deque jika sering insert/delete di kedua ujung, list jarang dipakai karena akses acaknya lambat, dan std::array jika ukuran diketahui saat kompilasi.

#Kontainer Asosiatif

#std::set, std::map, dan std::unordered_map

std::set menyimpan elemen unik yang terurut. std::map menyimpan pasangan key-value dengan key unik dan terurut. std::unordered_map memakai hash table sehingga pencarian rata-rata O(1), tetapi urutannya tidak terjamin. std::string juga adalah kontainer — kalian bisa mengiterasi karakternya:

cat > assosiatif.cpp <<'EOF'
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
 
int main() {
    std::map<std::string, int> umur;
    umur["Arman"] = 28;
    umur["Budi"] = 30;
 
    std::cout << "Umur Arman: " << umur["Arman"] << "\n";
    std::cout << "Key terurut: ";
    for (const auto& [nama, u] : umur) {
        std::cout << nama << " ";
    }
    std::cout << "\n";
 
    std::set<int> unik{3, 1, 2, 3, 1};
    std::cout << "Set berisi: " << unik.size() << " elemen\n";
 
    std::unordered_map<int, std::string> cepat;
    cepat[42] = "answer";
    std::cout << cepat[42] << "\n";
}
EOF
g++ -std=c++20 assosiatif.cpp -o assosiatif
./assosiatif

for (const auto& [nama, u] : umur) memakai structured binding (C++17) untuk membongkar pasangan key-value. std::set<int> unik{3, 1, 2, 3, 1} otomatis membuang duplikat. Pilih map saat butuh urutan key, unordered_map saat butuh kecepatan pencarian.

#Iterator dan Algoritma std::algorithm

#Iterator sebagai Jembatan

Iterator adalah objek yang berjalan di sepanjang kontainer seperti pointer. Kontainer menyediakan begin() dan end(), dan seluruh algoritma STL bekerja di atas pasangan iterator ini — itulah sebabnya satu algoritma bisa dipakai untuk semua kontainer:

cat > algoritma.cpp <<'EOF'
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
 
int main() {
    std::vector<int> v{5, 2, 8, 1, 9};
 
    std::sort(v.begin(), v.end());
    std::cout << "Terurut: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
 
    auto maks = *std::max_element(v.begin(), v.end());
    std::cout << "Maksimum: " << maks << "\n";
 
    int total = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Total: " << total << "\n";
}
EOF
g++ -std=c++20 algoritma.cpp -o algoritma
./algoritma

std::sort(v.begin(), v.end()) mengurutkan seluruh vector, std::accumulate(v.begin(), v.end(), 0) menjumlahkan elemen. Sejak C++20, ada varian ranges yang lebih ringkas tanpa begin() dan end() eksplisit — episode 16 akan membahasnya.

#Container Adaptors

#stack, queue, dan priority_queue

Container adaptors membungkus kontainer dasar dengan antarmuka terbatas. std::stack bekerja dengan pola LIFO (last in, first out). std::queue dengan pola FIFO. std::priority_queue selalu mengeluarkan elemen terbesar:

cat > adaptor.cpp <<'EOF'
#include <iostream>
#include <stack>
#include <queue>
 
int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    std::cout << "Stack top: " << s.top() << "\n";
 
    std::queue<int> q;
    q.push(10);
    q.push(20);
    std::cout << "Queue depan: " << q.front() << "\n";
 
    std::priority_queue<int> pq;
    pq.push(5);
    pq.push(15);
    pq.push(10);
    std::cout << "Priority teratas: " << pq.top() << "\n";
}
EOF
g++ -std=c++20 adaptor.cpp -o adaptor
./adaptor

pq.top() selalu mengembalikan elemen terbesar karena priority_queue adalah max-heap. Pola stack dipakai untuk operasi undo dan parsing, queue untuk antrian kerja, dan priority_queue untuk task scheduler — episode 12 akan memakai mereka lagi di konteks concurrency.

#Penutup

Inti yang harus dibawa pulang:

• std::vector adalah kontainer default dengan cache locality terbaik.
• std::array untuk ukuran tetap, std::deque untuk akses dua ujung.
• std::set dan std::map terurut; std::unordered_map pencarian O(1).
• Iterator menghubungkan kontainer dengan algoritma secara universal.
• std::sort, max_element, dan accumulate menggantikan kode manual.
• stack, queue, dan priority_queue membungkus kontainer untuk pola tertentu.

Di episode 9 selanjutnya kita akan membahas input/output dan file handling — streams dasar std::istream dan std::ostream, file I/O dengan std::ifstream, std::ofstream, dan std::fstream, formatted input output dengan manipulators, binary I/O, serta error handling untuk operasi file.