Motivasi STL berasal dari pemikiran Alexander Stepanov bahwa algoritma bisa dibuat generik jika ia hanya bergantung pada cara mengakses elemen, bukan pada struktur data spesifiknya. Tujuannya adalah membangun algoritma yang segenerik mungkin tanpa mengorbankan efisiensi.
STL adalah sebuah library komponen yang terdiri dari tiga pilar utama:
Containers: Template dari struktur data untuk menyimpan koleksi objek.
Iterators: Objek yang berperilaku seperti pointer, berfungsi sebagai jembatan untuk mengakses elemen di dalam container.
Algorithms: Fungsi generik (misalnya, sort(), find()) yang beroperasi pada container melalui iterator.
Containers: Wadah Penyimpanan Data
Container adalah objek yang mengelola koleksi elemen. Ada tiga jenis utama:
Associative Containers: Menyimpan elemen (seringkali sebagai pasangan key-value) yang dioptimalkan untuk pencarian cepat. Contoh: set, map, multiset, multimap.
Container Adapters: Memberikan antarmuka yang lebih terbatas di atas container lain untuk menyediakan perilaku spesifik. Contoh: stack, queue, priority_queue.
Iterators: Jembatan Antar Komponen
Iterator adalah konsep paling fundamental di STL. Ia adalah sebuah objek yang mengabstraksi cara mengakses elemen, memungkinkan algoritma generik untuk bekerja pada container apa pun tanpa perlu tahu detail implementasi internalnya. Ia menyediakan antarmuka yang seragam seperti pointer:
*it: Mendapatkan nilai elemen yang ditunjuk (dereference).
it++: Pindah ke elemen berikutnya.
it1 == it2: Membandingkan posisi iterator.
Setiap container menyediakan method begin() (iterator ke elemen pertama) dan end() (iterator ke posisi setelah elemen terakhir). Algoritma STL bekerja pada rentang [begin, end).
std::vector<int> numbers = {10, 20, 30};std::vector<int>::iterator it;for (it = numbers.begin(); it != numbers.end(); ++it) {std::cout << *it << " "; // Mengakses nilai melalui iterator}
Jenis-jenis Iterator
Iterator dikategorikan berdasarkan kemampuannya, dari yang paling terbatas hingga paling kuat:
Input Iterator: Hanya bisa membaca nilai secara sekuensial dan hanya bisa maju (++). Setiap elemen hanya dijamin bisa dibaca satu kali.
Output Iterator: Hanya bisa menulis nilai secara sekuensial dan hanya bisa maju (++).
Forward Iterator: Gabungan Input dan Output, bisa membaca/menulis dan maju. Bisa melewati urutan data berkali-kali (multi-pass).
Bidirectional Iterator: Seperti Forward, ditambah kemampuan untuk bergerak mundur (--). std::list, std::set, dan std::map mendukung iterator ini.
Random Access Iterator: Paling kuat. Bisa melakukan semua hal di atas ditambah akses acak (it + n, it[n]) dalam waktu konstan. std::vector dan std::deque mendukung iterator ini.
Algorithms: Prosesor Generik
Algorithm adalah fungsi global yang beroperasi pada rentang iterator, bukan pada container secara langsung.
Studi Kasus: Mengelola daftar skor pemain yang bisa bertambah kapan saja.
C++
std::vector<int> scores;
scores.push_back(100); // Tambah skor baru
scores.push_back(150);
int first_score = scores[0]; // Akses skor pertama
std::list
Deskripsi: Implementasi doubly-linked list.
Operasi Umum: push_front, pop_front, push_back, pop_back, insert, erase, sort. Tidak mendukung akses acak ([]).
Studi Kasus: Mengelola daftar urutan “undo/redo” pada editor teks, di mana penyisipan dan penghapusan di tengah daftar sering terjadi.
std::list<std::string> history;history.push_back("Ketik 'A'");history.push_back("Ketik 'B'");history.pop_back(); // Undo aksi terakhir
std::deque
Deskripsi: Singkatan dari double-ended queue. Mirip vector tetapi mendukung penambahan/penghapusan yang efisien di kedua ujung (depan dan belakang).
Operasi Umum: push_front, pop_front, push_back, pop_back, [], at.
Studi Kasus: Implementasi sebuah buffer atau antrian tugas di mana item bisa ditambahkan atau diambil dari kedua sisi.
std::deque<int> tasks;tasks.push_back(10); // Tugas biasatasks.push_front(99); // Tugas prioritas tinggi
Associative Containers (Pencarian Cepat)
std::map
Deskripsi: Menyimpan pasangan key-value unik, diurutkan secara otomatis berdasarkan key.
Operasi Umum: insert, erase, find, [] (untuk akses/penambahan), at.
Studi Kasus: Menyimpan kamus atau data konfigurasi, misalnya nama pengguna dipetakan ke ID pengguna.
std::map<std::string, int> userIDs;userIDs["alice"] = 101;userIDs["bob"] = 102;// int id = userIDs["alice"]; // id akan bernilai 101
std::set
Deskripsi: Menyimpan kumpulan elemen unik yang terurut.
Operasi Umum: insert, erase, find, count.
Studi Kasus: Mencatat daftar tag unik pada sebuah postingan blog, duplikat akan otomatis diabaikan.
std::set<std::string> tags;tags.insert("c++");tags.insert("stl");tags.insert("c++"); // Ini akan diabaikan// if (tags.count("stl")) { /* ... */ } // Cek keberadaan tag
Container Adapters (Antarmuka Terbatas)
std::stack
Deskripsi: Menyediakan antarmuka LIFO (Last-In, First-Out).
Operasi Umum: push, pop, top.
Studi Kasus: Implementasi riwayat navigasi “back” pada browser atau rekursi pada pemanggilan fungsi.
std::stack<std::string> page_history;page_history.push("google.com");page_history.push("wikipedia.org");// page_history.pop(); // Kembali ke google.com
std::queue
Deskripsi: Menyediakan antarmuka FIFO (First-In, First-Out).
Operasi Umum: push (ke belakang), pop (dari depan), front, back.
Studi Kasus: Mensimulasikan antrian cetak (print queue) atau antrian pelanggan di kasir.
STL menyediakan berbagai jenis Containers untuk kebutuhan penyimpanan yang berbeda: Sequence untuk data terurut linear, Associative untuk pencarian berbasis kunci yang cepat, dan Adapters untuk perilaku spesifik seperti LIFO/FIFO.
Setiap container memiliki serangkaian operasi umum yang dioptimalkan untuk struktur datanya, dan pemahaman karakteristik masing-masing (vector untuk akses cepat, list untuk penyisipan cepat, map untuk lookup cepat) sangat penting untuk menulis kode C++ yang efisien.
Additional Information (Optional)
Unordered Associative Containers (C++11)
Sejak C++11, ada versi “unordered” dari map dan set (std::unordered_map, std::unordered_set). Mereka menggunakan hash table di belakangnya, bukan pohon biner.
Kelebihan: Pencarian, penambahan, dan penghapusan memiliki kompleksitas rata-rata O(1), yang secara signifikan lebih cepat daripada O(log n) pada map/set biasa.
Kekurangan: Elemen tidak disimpan dalam urutan terurut. Gunakan ini saat kecepatan adalah prioritas utama dan urutan tidak penting.