Container adapter

stack, queue, dan priority_queue di atas container yang ada.

Daftar isi

Topik ini membahas container adapter pada pustaka standar, yaitu std::stack, std::queue, dan std::priority_queue, yang membungkus container yang sudah ada di balik antarmuka yang sempit. Pembahasan mencakup konsep adapter, contoh ketiganya, serta cara memilih container dasarnya. Setelah membaca topik ini, ketiga adapter dapat digunakan untuk pola akses terbatas seperti tumpukan langkah, antrean layanan, dan antrean berprioritas tanpa salah mengira perilakunya.

Adapter sebagai antarmuka sempit#

Container adapter adalah class template yang menyimpan sebuah container utuh sebagai anggota data, lalu hanya mengekspos operasi yang cocok dengan pola akses tertentu. std::stack menerapkan pola LIFO (last in, first out) melalui push(), pop(), dan top(), sedangkan std::queue menerapkan pola FIFO (first in, first out) melalui push(), pop(), front(), dan back(). std::priority_queue berbeda keduanya, yaitu top() selalu menghasilkan elemen terbesar menurut pembandingnya, bukan elemen yang masuk lebih dulu.

Antarmuka yang sempit adalah tujuannya, bukan kekurangannya. Adapter tidak menyediakan iterator, sehingga tidak ada begin() dan end(), dan pembaca kode dapat yakin bahwa isinya tidak akan ditelusuri maupun diubah dari tengah. Kebutuhan setiap adapter terhadap container dasarnya dinyatakan presisi, dan container bawaan hanya dipilih karena memenuhi syaratnya dengan baik. Ketiganya dideklarasikan melalui header <stack> dan <queue>, sedangkan std::priority_queue berada di header <queue>.

Selain operasi khasnya, ketiga adapter menyediakan size() dan empty() untuk meninjau banyaknya elemen. Pertanyaan pemilihan adapter dijawab lebih dahulu menurut pola aksesnya, yaitu elemen mana yang masuk, elemen mana yang keluar lebih dahulu, dan bagian mana yang boleh dibaca. Container dasarnya kemudian menyusul menurut syarat teknisnya.

stack dan queue#

std::stack memasukkan dan mengeluarkan elemen pada satu ujung yang sama, sehingga polanya cocok untuk riwayat aksi yang dapat dibatalkan. Program berikut meniru tiga langkah penyuntingan teks, kemudian membatalkan satu langkah terakhir.

cpp riwayat-ketik.cpp

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> riwayat;
    riwayat.push("mengetik judul");
    riwayat.push("mengetik paragraf pembuka");
    riwayat.push("menyisipkan daftar poin");

    std::cout << "Langkah terakhir: " << riwayat.top() << '\n';
    riwayat.pop();                       // aksi batalkan (undo)

    std::cout << "Setelah undo : " << riwayat.top() << '\n';
    std::cout << "Sisa riwayat : " << riwayat.size() << " langkah\n";
    return 0;
}

text Keluaran

Langkah terakhir: menyisipkan daftar poin
Setelah undo : mengetik paragraf pembuka
Sisa riwayat : 2 langkah

std::queue mengeluarkan elemen dari ujung yang berlawanan dengan tempat masuknya, sehingga urutan kedatangan tetap dipertahankan. Contoh berikut menyimulasikan layanan tiket loket yang nomor urutnya dilayani satu per satu.

cpp antrean-tiket.cpp

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> loket;
    loket.push("tiket 101");
    loket.push("tiket 102");
    loket.push("tiket 103");

    std::cout << "Dilayani: " << loket.front() << '\n';
    loket.pop();
    std::cout << "Dilayani: " << loket.front() << '\n';
    loket.pop();
    std::cout << "Nomor berikutnya: " << loket.front() << '\n';
    std::cout << "Sisa antrean: " << loket.size() << " tiket\n";
    return 0;
}

text Keluaran

Dilayani: tiket 101
Dilayani: tiket 102
Nomor berikutnya: tiket 103
Sisa antrean: 1 tiket

Pada stack, top() membaca elemen teratas tanpa menghapusnya, dan pop() menghapusnya tanpa mengembalikan nilainya, sehingga kedua operasi tersebut dipanggil berurutan. Pada queue, front() membaca ujung yang dilayani dan back() membaca ujung tempat masuk. Semua operasi kedua adapter ini berjalan dalam $O(1)$ karena tidak ada elemen yang perlu digeser.

priority_queue dan urutan prioritas#

std::priority_queue menyimpan elemen sedemikian rupa sehingga top() selalu menghasilkan elemen terbesar menurut pembandingnya, dengan penyisipan dan penghapusan berjalan dalam $O(\log n)$ . Struktur internalnya bertumpu pada algoritma heap di atas container dasarnya, sehingga urutan penyimpanan di dalamnya memang tidak linear seperti vector. Contoh berikut mengeluarkan sekumpulan nilai dua kali, pertama dari nilai tertinggi secara bawaan, lalu dari nilai terendah dengan pembanding std::greater<int>.

cpp prioritas.cpp

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> tertinggi;
    for (int n : {40, 90, 60, 20, 80}) {
        tertinggi.push(n);
    }
    std::cout << "Pop dari nilai tertinggi:";
    while (!tertinggi.empty()) {
        std::cout << ' ' << tertinggi.top();
        tertinggi.pop();
    }
    std::cout << '\n';

    std::priority_queue<int, std::vector<int>, std::greater<int>> terendah;
    for (int n : {40, 90, 60, 20, 80}) {
        terendah.push(n);
    }
    std::cout << "Pop dari nilai terendah :";
    while (!terendah.empty()) {
        std::cout << ' ' << terendah.top();
        terendah.pop();
    }
    std::cout << '\n';
    return 0;
}

text Keluaran

Pop dari nilai tertinggi: 90 80 60 40 20
Pop dari nilai terendah : 20 40 60 80 90

Parameter template kedua dan ketiga pada deklarasi kedua, yaitu std::vector<int> dan std::greater<int>, menentukan container dasarnya sekaligus pembandingnya. Dengan pembanding std::greater, urutan “terbesar” dibalik sehingga nilai terkecil yang keluar lebih dahulu, dan pola ini dipakai ketika elemen paling mendesak justru yang angkanya paling kecil.

Dibandingkan dengan mengurutkan ulang seluruh data setiap kali ada elemen baru, yang berjalan $O(n \log n)$ , priority_queue mempertahankan kandidat terbaik dengan $O(\log n)$ per penyisipan. Pola ini berguna pada antrean yang elemennya datang secara bertahap, misalnya tugas yang diselesaikan lebih dahulu menurut tingkat urgensinya, dan jumlah datanya tidak diketahui sejak awal. Apabila seluruh data sudah tersedia sejak awal dan hanya perlu diurutkan sekali, std::sort pada container linear tetap lebih sederhana.

Memilih container dasar#

Setiap adapter menyatakan container dasarnya sebagai parameter template, dan bawaannya dipilih menurut syarat operasi yang dibutuhkan.

Adapter	Container bawaan	Syarat container dasar
`std::stack`	`std::deque`	`push_back()`, `pop_back()`, `back()`
`std::queue`	`std::deque`	`push_back()`, `pop_front()`, `front()`, `back()`
`std::priority_queue`	`std::vector`	`push_back()`, `pop_back()`, `front()`, akses acak

Syarat tersebut diisi dengan member function yang dipakai adapter pada operasinya, sehingga container yang tidak menyediakannya ditolak saat dikompilasi. std::stack<int, std::vector<int>> misalnya sah karena vector menyediakan ketiga operasi yang dibutuhkan stack, sedangkan std::stack di atas std::forward_list gagal dikompilasi karena forward_list tidak punya back().

Pemilihan yang berbeda dari bawaan perlu alasan yang jelas. Stack di atas std::vector menguntungkan pada tata letak memori yang rapat, dan priority_queue di atas std::deque juga sah karena deque menyediakan akses acak. Apabila pilihan bawaan tidak menyebabkan masalah terukur, mempertahankannya menjaga kode tetap sederhana dan mudah dibaca orang lain.

Kesalahan umum#

Tiga kesalahan berikut sering muncul pada pemakaian container adapter.

Berharap pop() mengembalikan elemen. Pada ketiga adapter, pop() hanya menghapus dan tidak mengembalikan apa pun, sedangkan pembacaannya dikerjakan top() atau front() sebelum menghapus. Kebalikan urutan ini membaca elemen yang sudah terhapus dan berujung pada undefined behavior.
Mencoba begin() dan end() pada adapter. Ketiganya tidak menyediakan iterator, sehingga kode perulangannya gagal saat dikompilasi. Pindahkan kebutuhan penelusuran itu ke container dasarnya atau ubah pola desainnya.
Mengira priority_queue melayani sesuai urutan kedatangan. top() menghasilkan elemen terbesar menurut pembanding, bukan yang masuk lebih dulu, sehingga antrean berprioritas memerlukan kunci prioritas yang eksplisit, misalnya sepasang tingkat prioritas dan nomor urut sebagai elemennya.

Ringkasan#

Container adapter membungkus container yang ada dengan antarmuka sempit, yaitu stack untuk pola LIFO, queue untuk pola FIFO, dan priority_queue yang selalu memunculkan elemen terbesar menurut pembandingnya.
Setiap adapter menetapkan syarat member function bagi container dasarnya, dengan bawaan std::deque untuk stack dan queue serta std::vector untuk priority_queue.
Adapter tidak memiliki iterator, pop() tidak mengembalikan nilai, dan penyisipan serta penghapusan pada priority_queue berjalan dalam $O(\log n)$ melalui algoritma heap.

Referensi#

std::stack — cppreference.com — Dokumentasi stack beserta syarat container dasarnya.
std::queue — cppreference.com — Dokumentasi queue beserta operasi kedua ujungnya.
std::priority_queue — cppreference.com — Dokumentasi priority_queue beserta parameter pembandingnya.
std::greater — cppreference.com — Objek fungsi perbandingan yang membalik urutan prioritas.