Sequence container

Topik ini membahas keluarga sequence container pada pustaka standar, yaitu std::vector, std::array, std::deque, std::list, dan std::forward_list, yang semuanya menyimpan elemen dalam urutan linear. Pembahasan mencakup karakter setiap container, contoh operasi yang khas, serta trade-off performanya. Setelah membaca topik ini, pemilihan container untuk kebutuhan akses, sisip, dan hapus tertentu dapat dilakukan berdasarkan kompleksitas operasinya, bukan sekadar mengikuti kebiasaan.

Lima sequence container dan karakternya#

std::vector menyimpan elemen dalam blok memori yang berurutan dan menjadi pilihan awal untuk hampir semua kebutuhan, sebagaimana telah dibahas pada topik esensi std::vector. std::array adalah pembungkus array ukuran tetap yang ukurannya menjadi bagian dari tipenya, sehingga tanpa alokasi dinamis sama sekali. std::deque (double-ended queue) menyimpan elemen dalam beberapa potong memori dan menawarkan penambahan serta penghapusan cepat di kedua ujungnya.

std::list adalah senarai berantai ganda, yaitu setiap elemen tersimpan dalam simpul yang memegang penunjuk ke simpul sebelum dan sesudahnya. std::forward_list adalah versi senarai berantai tunggal yang hanya dapat ditelusuri ke depan, dengan simpul yang lebih hemat satu penunjuk. Kelima container ini berada di header <vector>, <array>, <deque>, <list>, dan <forward_list>. Urutan elemennya ditentukan oleh urutan penyisipan, bukan oleh nilai kunci, sehingga berbeda dari associative container yang dibahas pada topik berikutnya.

Operasi di kedua ujung dengan deque#

std::deque menawarkan push_front() dan pop_front() di samping push_back() dan pop_back(), dan keempatnya berjalan dalam $O(1)$. Perbedaan ini penting karena std::vector tidak menyediakan push_front(), sebab penambahan di depan berarti menggeser seluruh elemen dan berjalan dalam $O(n)$. Contoh berikut menggunakan deque untuk antrean tiket loket, yaitu penumpang baru masuk dari belakang, sedangkan satu pendaftar cepat masuk dari depan.

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> antrean = {"Budi", "Citra"};

    antrean.push_back("Dewi");    // pendaftar biasa, masuk dari belakang
    antrean.push_front("Ali");    // pendaftar cepat, masuk dari depan

    std::cout << "Urutan antrean:";
    for (const std::string& nama : antrean) {
        std::cout << ' ' << nama;
    }
    std::cout << '\n';

    std::cout << "Dilayani: " << antrean.front() << '\n';
    antrean.pop_front();
    std::cout << "Dilayani: " << antrean.front() << '\n';
    antrean.pop_front();
    std::cout << "Sisa antrean:";
    for (const std::string& nama : antrean) {
        std::cout << ' ' << nama;
    }
    std::cout << '\n';
    return 0;
}

Urutan antrean: Ali Budi Citra Dewi
Dilayani: Ali
Dilayani: Budi
Sisa antrean: Citra Dewi

Elemen tidak pernah digeser selama push_front() dan pop_front() berlangsung, karena deque menata memorinya dalam potongan-potongan dan mengatur ujung depannya secara terpisah. Akses acak per indeks tetap $O(1)$, meskipun melalui perhitungan dua tingkat yang sedikit lebih berat daripada aritmetika pointer pada vector.

Sisip dan hapus pada list dan forward_list#

Kekuatan utama std::list terletak pada penyisipan dan penghapusan di posisi yang sudah ditunjuk iterator, yang keduanya berjalan dalam $O(1)$ tanpa menggeser satu elemen pun. Ketika sebuah iterator menunjuk elemen tengah daftar, insert() menambahkan elemen baru tepat sebelumnya dengan memperbaiki dua penunjuk di sekitarnya. Contoh berikut menyisipkan satu nilai di tengah daftar dan membandingkannya dengan std::forward_list. Karena penunjuk forward_list hanya menghadap ke depan, penyisipannya dikerjakan lewat insert_after() yang menempatkan elemen baru tepat setelah posisi.

#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>

int main() {
    std::list<int> nilai = {70, 80, 90};

    auto posisi = nilai.begin();
    std::advance(posisi, 1);          // posisi bergeser menunjuk elemen 80
    nilai.insert(posisi, 75);         // menyisip tepat sebelum 80

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

    std::forward_list<int> stok = {10, 20, 30};
    auto awal = stok.begin();
    stok.insert_after(awal, 15);      // menyisip tepat setelah elemen pertama

    std::cout << "forward_list :";
    for (int n : stok) {
        std::cout << ' ' << n;
    }
    std::cout << '\n';
    return 0;
}

std::list    : 70 75 80 90
forward_list : 10 15 20 30

Fungsi std::advance() menggeser iterator sebanyak langkah yang diminta, dan untuk list pergesean itu berjalan satu simpul demi satu simpul sehingga mencari posisi sendiri tetap $O(n)$. Keunggulan $O(1)$ list baru terwujud apabila posisinya sudah ada di tangan, misalnya saat iterasi berlangsung. Untuk forward_list, versi insert_after() dipilih agar penyisipan dapat dikerjakan dengan satu penunjuk, dan fungsi before_begin() menyediakan posisi sebelum elemen pertama bila penyisipan di depan diperlukan.

Trade-off kompleksitas dan memori#

Tabel berikut merangkum kompleksitas operasi penting kelima container. Notasi “tidak tersedia” berarti operasi itu tidak disediakan oleh container tersebut.

Kompleksitas asimptotik tidak selalu bercerita utuh tentang kecepatan sebenarnya. Elemen vector tersimpan berdampingan dalam memori, sehingga penelusurannya menguntungkan cache perangkat keras dan berjalan cepat pada ukuran yang lazim. Simpul list dan forward_list tersebar di memori karena dialokasikan satu per satu, dan setiap simpulnya membawa tambahan dua penunjuk untuk list atau satu penunjuk untuk forward_list, sehingga memakai lebih banyak memori dan lebih sering memicu akses cache yang lambat.

Istilah amortisasi pada baris push_back() vector berarti biaya rata-rata per operasinya konstan, meskipun sesekali terjadi realokasi yang menyalin seluruh elemen. Biaya sesekali itu tetap lebih murah daripada penyisipan di depan yang menggeser elemen setiap kali, dan kebiasaan menyiapkan kapasitas dengan reserve() menghilangkan realokasi yang tersisa.

Kesalahan umum#

Tiga kesalahan berikut paling sering muncul ketika memilih sequence container.

1. Memilih list hanya karena ada penyisipan di tengah. Tanpa iterator yang sudah menunjuk posisinya, pencarian posisi sendiri berjalan $O(n)$, sehingga keunggulan $O(1)$ list hilang dan biaya penyebaran memorinya tetap terbayar. Ukur pola aksesnya lebih dahulu sebelum memutuskan.
2. Mengakses elemen list lewat indeks. std::list dan std::forward_list tidak menyediakan operator[], dan penggantinya seperti std::advance(posisi, k) berjalan $O(n)$. Apabila akses per indeks mendominasi, vector atau deque adalah pilihan yang benar.
3. Memegang iterator sebuah vector selama push_back(). Realokasi yang sesekali terjadi membatalkan iterator, referensi, dan pointer yang menunjuk elemen vector, sedangkan iterator list tidak pernah dibatalkan oleh penyisipan. Peraturan invalidasi setiap container perlu dibaca pada topik pendalaman iterator.

Ringkasan#

• Lima sequence container standar adalah vector, array, deque, list, dan forward_list, yang tersusun dari keputusan tata letak memori yang berbeda, yaitu blok berurutan, potongan memori, atau simpul berantai.
• std::deque unggul pada operasi $O(1)$ di kedua ujungnya, sedangkan list dan forward_list unggul pada penyisipan $O(1)$ di posisi iterator yang sudah diketahui.
• Trade-off performanya dinilai dari kompleksitas pada tabel beserta efek cache: vector justru paling ramah cache, sedangkan container berbasis simpul membayar biaya alokasi dan penunjuk per elemen.

Referensi#

• std::vector — cppreference.com — Dokumentasi vector beserta jaminan kompleksitas tiap operasinya.
• std::deque — cppreference.com — Dokumentasi deque dan operasi kedua ujungnya.
• std::list — cppreference.com — Dokumentasi senarai berantai ganda dan penyisipan berbasis iterator.
• std::forward_list — cppreference.com — Dokumentasi senarai berantai tunggal beserta insert_after.
• std::array — cppreference.com — Dokumentasi container ukuran tetap yang ukurannya bagian dari tipe.