KAL
Menu

Arsitektur STL

Container, iterator, dan algoritma sebagai gagasan desain pustaka standar.

Daftar isi

Topik ini membahas arsitektur Standard Template Library (STL), yaitu gagasan desain yang mendasari bagian pustaka standar C++ untuk menyimpan dan mengolah kumpulan data. Pembahasan mencakup tiga komponen utamanya, yaitu container, iterator, dan algoritma, serta alasan ketiganya dipisahkan. Setelah membaca topik ini, program yang menggabungkan container dan algoritma generik dapat ditulis sambil memahami peran setiap komponennya, bukan sekadar menghafal pemanggilan fungsinya.

Tiga komponen utama pustaka standar#

Container adalah objek yang menyimpan sekumpulan elemen dan mengatur tata letak memorinya, dengan contoh std::vector, std::deque, std::list, dan std::map. Algoritma adalah fungsi generik yang memproses elemen, misalnya std::sort untuk mengurutkan dan std::find untuk mencari. Iterator berada di antara keduanya, yaitu objek yang menunjuk satu elemen dan dapat digeser ke elemen berikutnya, sehingga berperan sebagai perantara yang dibaca oleh algoritma.

Pemisahan tiga komponen ini adalah keputusan desain yang sengaja. Container tidak perlu menyediakan fungsi sortirnya sendiri, dan algoritma tidak perlu ditulis ulang untuk setiap jenis container. Algoritma cukup diminta bekerja atas iterator, sedangkan setiap container menyediakan iterator yang sesuai dengan struktur memorinya. Diagram berikut memperlihatkan hubungan ketiganya.

Containermenyimpan elemenIteratorpenunjuk elemenAlgoritmamemproses elemenContainer memberi iterator melalui begin() dan end(), sedangkan algoritma menelusuri melalui iterator.
Tiga komponen STL dan alur elemennya

Iterator sebagai penyambung#

Iterator merupakan generalisasi dari pointer, yakni objek yang menunjuk elemen dan mendukung operasi pergesean seperti ++ untuk maju. Setiap container menyediakan begin() yang menunjuk elemen pertama dan end() yang menunjuk posisi tepat setelah elemen terakhir. Sepasang iterator tersebut membentuk rentang setengah terbuka, yaitu menyatakan “mulai dari elemen pertama, berhenti sebelum posisi akhir”, sehingga rentang kosong dan rentang penuh tetap dinyatakan dengan rapi.

Algoritma standar tidak pernah mengenal container secara langsung, melainkan hanya menerima sepasang iterator. Ketika menulis std::sort(nilai.begin(), nilai.end()), yang dikirim kepada algoritma adalah dua iterator dari container nilai. Konsekuensinya, algoritma yang sama dapat dipanggil atas std::vector, std::deque, std::string, atau bahkan array biasa, karena semuanya menyediakan iterator.

Tidak semua iterator sama kuatnya. Iterator std::vector mendukung lompatan acak seperti it + 5, sedangkan iterator std::list hanya mendukung maju dan mundur satu langkah. Kekuatan ini dikelompokkan menjadi kategori iterator, dan setiap algoritma menyatakan kategori minimum yang dibutuhkannya. std::sort menuntut kategori akses acak, sehingga tidak dapat dipanggil atas iterator std::list. Sebaliknya, std::find cukup dengan iterator maju sehingga dapat dipakai di hampir semua container.

Kerja sama tiga komponen dalam satu program#

Program berikut menggabungkan ketiga komponen dalam satu berkas. Container std::vector menyimpan lima nilai ujian, algoritma std::sort mengurutkannya, dan algoritma std::find mencari satu nilai tertentu. Kedua algoritma bekerja sepenuhnya melalui iterator yang diberikan vector.

cpp nilai-ujian.cpp 
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nilai = {72, 95, 61, 88, 79};

    std::sort(nilai.begin(), nilai.end());

    std::cout << "Nilai setelah diurutkan:";
    for (int n : nilai) {
        std::cout << ' ' << n;
    }
    std::cout << '\n';

    auto posisi = std::find(nilai.begin(), nilai.end(), 88);
    if (posisi != nilai.end()) {
        std::cout << "Nilai 88 ditemukan pada indeks "
                  << (posisi - nilai.begin()) << '\n';
    } else {
        std::cout << "Nilai 88 tidak ada dalam daftar\n";
    }
    return 0;
}
text Keluaran 
Nilai setelah diurutkan: 61 72 79 88 95
Nilai 88 ditemukan pada indeks 3

Dua hal pada program tersebut layak digarisbawahi. Pertama, std::find selalu mengembalikan iterator, dan pembandingan terhadap nilai.end() adalah cara standar menyatakan “tidak ditemukan”, bukan dengan nilai khusus seperti -1. Kedua, pengurangan posisi - nilai.begin() hanya sah karena iterator vector mendukung akses acak, dan hasilnya menjadi indeks elemen yang dicari.

Pemisahan data dan operasi#

Keuntungan arsitektur ini paling jelas terasa dari banyaknya algoritma yang dapat dipakai ulang. Pustaka standar menyediakan lebih dari seratus algoritma, antara lain std::sort, std::find, std::count, std::transform, dan std::accumulate. Tanpa pemisahan ini, setiap container harus menyediakan versi masing-masing sehingga jumlah fungsinya berlipat lima atau enam kali, dan container buatan pengguna tidak akan mendapatkan apa pun. Dengan desain sekarang, container baru cukup menyediakan iterator, lalu seluruh algoritma yang cocok dengan kategorinya langsung dapat digunakan.

Pemisahan ini juga memberi jaminan yang dapat diandalkan saat membaca dokumentasi. Setiap algoritma mencantumkan kategori iterator yang dibutuhkan beserta kompleksitasnya, sehingga kelayakan pemakaiannya dapat dinilai tanpa mencoba kodenya. std::find misalnya berjalan dalam O(n)O(n) karena menelusuri elemen satu per satu, sedangkan std::sort berjalan dalam O(nlog⁡n)O(n \log n). Jaminan tersebut berlaku untuk semua container yang iteratornya memenuhi syarat, dari std::vector hingga std::array.

Konsekuensi desainnya perlu dipahami juga. Karena algoritma tidak mengenal container, algoritma tidak dapat mengubah ukurannya. Algoritma hanya menggeser dan memproses elemen pada rentang yang diberikan, sedangkan penambahan dan penghapusan elemen tetap pekerjaan container itu sendiri. Pembagian tanggung jawab ini membuat perilaku algoritma konsisten, tetapi juga menuntut penulis program memahami mana yang menjadi urusan algoritma dan mana yang menjadi urusan container.

Kesalahan umum#

Tiga kesalahan berikut sering muncul ketika arsitektur STL baru dipelajari.

  1. Menganggap setiap container cocok dengan setiap algoritma. std::sort menuntut iterator akses acak, sehingga pemanggilan std::sort atas std::list gagal saat dikompilasi. Solusinya menggunakan member function sort() milik std::list, yang menyesuaikan diri dengan struktur senarai tersebut.
  2. Menggabungkan iterator dari dua container berbeda dalam satu rentang, misalnya std::find(v.begin(), deque_lain.end(), x). Rentang yang diberikan tidak lagi menunjuk memori yang sama, sehingga perjalanannya menjadi undefined behavior. Pastikan kedua iterator berasal dari container yang sama.
  3. Berharap algoritma menambah atau menghapus elemen. std::sort dan std::find hanya menggerakkan isi elemen pada rentang yang ada, sehingga pengurangan elemen dikerjakan lewat erase() milik container, sebagaimana dibahas pada idiom erase-remove di topik algoritma esensial.

Ringkasan#

  • STL dibangun dari tiga komponen yang dipisahkan, yaitu container untuk menyimpan elemen, iterator untuk menunjuknya, dan algoritma untuk memprosesnya.
  • Algoritma standar bekerja sepenuhnya melalui sepasang iterator begin() dan end(), sehingga satu fungsi seperti std::sort melayani semua container yang iteratornya memenuhi syaratnya.
  • Kategori iterator menentukan algoritma mana yang dapat dipanggil, dan setiap algoritma mencantumkan kategori minimum beserta kompleksitasnya, misalnya O(n)O(n) untuk std::find dan O(nlog⁡n)O(n \log n) untuk std::sort.

Referensi#