Kategori Iterator

Tidak semua iterator sama kuat. Iterator pada std::vector bisa melompat ke elemen ke-1000 dalam satu langkah, sedangkan iterator pada std::list harus berjalan node demi node. C++ mengelompokkan kemampuan ini ke dalam lima kategori iterator: input, output, forward, bidirectional, dan random access. Setiap algoritma di <algorithm> menuntut kategori minimum tertentu, sehingga memahami kategori membantu kita memilih algoritma yang cocok dengan container yang kita pakai. Pada Chapter ini kita melihat masing-masing kategori, tabel pemetaan container ke kategori, dan demonstrasi std::advance, std::next, dan std::prev.

Lima Kategori Iterator #

Kategori iterator membentuk jenjang kemampuan: kategori di bawahnya selalu bisa melakukan apa yang bisa dilakukan kategori di atasnya. Semakin tinggi jenjang, semakin banyak operasi yang tersedia.

Kategori	Kemampuan khas	Contoh pemilik
Input Iterator	baca elemen, maju satu langkah, satu kali jalan (single-pass)	`std::istream_iterator`
Output Iterator	tulis elemen, maju satu langkah, satu kali jalan	`std::ostream_iterator`, `std::back_inserter`
Forward Iterator	baca dan tulis, maju, boleh diulang (multi-pass)	`std::forward_list`, `std::unordered_map`
Bidirectional Iterator	forward + mundur satu langkah (`--`)	`std::list`, `std::map`, `std::set`
Random Access Iterator	bidirectional + lompat `it + n`, selisih `it2 - it1`, bandingkan `it < it2`	`std::vector`, `std::array`, `std::deque`, pointer C-style

Dua kategori pertama adalah iterator minimalis untuk alur data satu arah, misalnya membaca dari stream atau menulis ke stream. Forward iterator sudah layak dipakai berulang: kita bisa menyimpan posisi, maju, lalu kembali ke posisi simpanan tadi. Bidirectional menambah kemampuan mundur, dan random access — kemampuan tertinggi — memberi perilaku seperti pointer array.

Kategori yang Diberikan Tiap Container #

Pemetaannya bisa diringkas sesuai struktur memori container. Container berbasis array (vector, array, string, deque) memberi random access karena perhitungan posisi ke-n hanya aritmetika alamat. Container berbasis node (list, map, set beserta variannya) berhenti di bidirectional karena antar-node hanya terhubung lewat pointer maju-mundur. Container hash (unordered_map, unordered_set) memberi forward iterator, dan forward_list — list satu arah — bahkan hanya forward.

Pemetaan ini punya konsekuensi praktis yang sering mengagetkan pemula: std::sort menuntut random access iterator, sehingga std::sort(myList.begin(), myList.end()) tidak bisa dikompilasi untuk std::list. Solusinya, list menyediakan member function myList.sort() yang dirancang khusus untuk struktur berantai. Sebaliknya, std::find hanya butuh input iterator, sehingga bisa dipakai di hampir semua container.

Demonstrasi advance, next, dan prev #

Header <iterator> menyediakan tiga helper yang menunjukkan beda perilaku kategori secara nyata: std::advance menggeser iterator yang sudah ada, sedangkan std::next dan std::prev mengembalikan iterator baru tanpa menyentuh iterator lama.

cpp

#include <iostream>
#include <iterator>
#include <list>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::list<int> l = {10, 20, 30, 40, 50};

    // std::advance: menggeser iterator sejauh n langkah
    auto itV = v.begin();
    std::advance(itV, 3);   // random access: lompat langsung, O(1)
    std::cout << "Vector maju 3x: " << *itV << "\n";

    auto itL = l.begin();
    std::advance(itL, 3);   // bidirectional: maju satu-satu, O(n)
    std::cout << "List maju 3x  : " << *itL << "\n";

    // std::next dan std::prev: iterator BARU, iterator lama tetap
    auto berikut = std::next(v.begin());
    auto sebelum = std::prev(v.end());
    std::cout << "next(begin)   : " << *berikut << "\n";
    std::cout << "prev(end)     : " << *sebelum << "\n";
    std::cout << "begin tetap   : " << *v.begin() << "\n";
    return 0;
}

Output yang Dihasilkan:

text
Vector maju 3x: 40
List maju 3x  : 40
next(begin)   : 20
prev(end)     : 50
begin tetap   : 10

Bedah baris penting:

Baris 10-12 (std::advance(itV, 3)): pada std::vector yang memberi random access, advance tiga langkah dihitung langsung dengan aritmetika, sehingga biayanya O(1).
Baris 15-16 (std::advance(itL, 3)): pada std::list yang bidirectional, advance maju ++ tiga kali melewati node-node, sehingga biayanya O(n). Fungsi yang sama, biaya berbeda — inilah kategori bekerja di balik layar.
Baris 20-21 (std::next, std::prev): keduanya tidak mengubah v.begin() atau v.end(); hasilnya iterator baru. std::prev(v.end()) adalah cara idiomatik mendapatkan elemen terakhir, karena end() sendiri menunjuk posisi setelah elemen terakhir.
Baris 22 (begin tetap : 10): bukti bahwa next dan prev tidak memindahkan iterator asalnya.

Satu kehati-hatian: std::prev(v.end()) hanya sah bila rentang tidak kosong. Pada container kosong, end() sama dengan begin() dan mundur satu langkah dari sana adalah undefined behavior.

Chapter berikutnya membahas titik-titik ujung penelusuran itu secara khusus: begin() dan end(), hubungannya dengan array C-style, serta makna “satu langkah setelah elemen terakhir”.

Rujukan resmi: iterator tags , std::advance , dan std::next / std::prev .