Iterators

Iterator adalah jenderal dari pointer C++: objek yang bisa dereference (*it), di-increment (++it), dan dibandingkan (it != end). Container STL menyediakan iterator dengan kemampuan berbeda — dari yang hanya bisa maju (forward_list) hingga random-access (vector). Banyak algoritma STL (std::sort, std::copy, std::find) ditulis generik berbasis iterator, sehingga satu algoritma bekerja untuk semua container yang kategorinya cocok. Pada Chapter ini kita akan memetakan lima kategori iterator, operasi advance/next/prev, serta aturan iterator invalidation yang krusial untuk kode yang benar.

Lima Kategori Iterator #

Algoritma STL mensyaratkan kategori tertentu — std::sort butuh random-access, std::reverse butuh bidirectional, std::find cukup input.

Mekanisme: begin/end dan Ranges #

Setiap container menyediakan pasangan fungsi:

• begin() / end(): iterator maju, dengan end adalah past-the-end (satu setelah elemen terakhir). end tidak boleh di-dereference.
• rbegin() / rend(): reverse iterator — mengiterasi dari belakang ke depan.
• cbegin() / cend(): versi const_iterator — elemen read-only.

Fungsi bebas std::begin(c) dan std::end(c) bekerja untuk array C-style juga, bukan hanya container STL.

Kode: Operasi Iterator Umum #

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

template <typename It>
void print_range(It first, It last, const char* label) {
    std::cout << label;
    for (; first != last; ++first) std::cout << *first << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 1) begin/end, rbegin/rend
    std::cout << "forward : ";
    for (auto it = v.begin(); it != v.end(); ++it) std::cout << *it << ' ';
    std::cout << '\n';
    std::cout << "reverse : ";
    for (auto it = v.rbegin(); it != v.rend(); ++it) std::cout << *it << ' ';
    std::cout << '\n';

    // 2) cbegin/cend — const_iterator
    auto cit = v.cbegin();
    // *cit = 99;  // ERROR — const iterator, elemen read-only
    std::cout << "cbegin  : " << *cit << '\n';

    // 3) advance, distance, next, prev
    auto it = v.begin();
    std::advance(it, 3);   // pindah 3 langkah maju
    std::cout << "*advance(begin, 3) = " << *it << '\n';
    std::cout << "distance(begin, it) = " << std::distance(v.begin(), it) << '\n';
    std::cout << "*prev(it) = " << *std::prev(it) << '\n';
    std::cout << "*next(it, -1) = " << *std::next(it, -1) << '\n';

    // 4) Iterator kategori berbeda
    std::list<int> L = {1, 2, 3, 4, 5};
    auto lit = L.begin();
    std::advance(lit, 2);   // list punya bidirectional — advance O(n) di sini O(2)
    std::cout << "list advance(begin, 2) = " << *lit << '\n';

    std::forward_list<int> fl = {1, 2, 3, 4, 5};
    auto fit = fl.begin();
    std::advance(fit, 2);   // forward_list hanya forward iterator
    std::cout << "forward_list advance(begin, 2) = " << *fit << '\n';

    // 5) inserter / back_inserter — output iterator
    std::vector<int> dst;
    std::copy(v.begin(), v.end(), std::back_inserter(dst));
    print_range(dst.begin(), dst.end(), "dst     : ");

    // 6) Iterator invalidation — vektor setelah insert
    std::vector<int> w = {1, 2, 3};
    auto wit = w.begin();
    w.push_back(4);          // kemungkinan realokasi -> wit mungkin invalid
    (void)wit;               // sengaja tidak dibaca: mungkin dangling
    std::cout << "w setelah push_back: ";
    for (int x : w) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Output yang Dihasilkan:

forward : 1 2 3 4 5 
reverse : 5 4 3 2 1 
cbegin  : 1
*advance(begin, 3) = 4
distance(begin, it) = 3
*prev(it) = 3
*next(it, -1) = 3
list advance(begin, 2) = 3
forward_list advance(begin, 2) = 3
dst     : 1 2 3 4 5 
w setelah push_back: 1 2 3 4 

Bedah Kode Baris-per-Baris #

1. v.begin() / v.end(): begin mengembalikan iterator ke elemen pertama; end adalah past-the-end — bukan elemen valid. Loop for (it = begin; it != end; ++it) adalah idiom iterasi.
2. v.rbegin() / v.rend(): reverse iterator. Increment maju mundur — dari elemen terakhir ke pertama. Output 5 4 3 2 1 untuk vector {1,2,3,4,5}.
3. v.cbegin(): mengembalikan const_iterator. Mencoba *cit = 99 gagal kompilasi — elemen read-only. Gunakan bila container tidak boleh dimutasi (mis. parameter fungsi const std::vector<T>&).
4. std::advance(it, 3): memajukan iterator n langkah. Pada random-access iterator (vector), operasi ini O(1) (pointer arithmetic). Pada forward/bidirectional iterator, ia memanggil ++it sebanyak n kali — O(n).
5. std::distance(begin, it): jumlah increment yang diperlukan untuk mencapai it dari begin. Pada random-access iterator O(1) (pengurangan pointer); pada kategori lain O(n).
6. std::prev(it) / std::next(it): mengembalikan iterator baru yang telah digeser — tidak mengubah iterator asli. next(it, -1) setara dengan prev(it) untuk random-access iterator.
7. std::advance(lit, 2) pada std::list: list adalah bidirectional iterator — advance memanggil ++it dua kali. Tetap O(n) walau n kecil di sini.
8. std::forward_list::advance: forward_list hanya punya forward iterator. advance hanya bisa maju (atau mundur dengan n negatif pada random-access — pada forward_list, n negatif adalah compile error).
9. std::back_inserter(dst): mengembalikan output iterator yang, saat ditulis *it = x, memanggil dst.push_back(x). Pola idiomatik untuk algoritma yang menulis ke container.
10. w.push_back(4) setelah auto wit = w.begin(): bila vector harus realokasi, wit menjadi dangling. Walaupun tidak crash di sini, mengakses *wit setelah push adalah undefined behavior. Aturan praktis: anggap semua iterator vector invalid setelah operasi yang mungkin realokasi (insert, push_back, resize).

Aturan Iterator Invalidation #

Setiap container memiliki aturan berbeda kapan iterator valid setelah operasi mutasi:

Inserter Iterator #

Tiga jenis inserter untuk output iterator:

• std::back_inserter(c) → memanggil c.push_back(x).
• std::front_inserter(c) → memanggil c.push_front(x) (butuh push_front — tidak ada di vector).
• std::inserter(c, it) → memanggil c.insert(it, x).

Ketiganya memudahkan komposisi dengan algoritma STL:

std::copy(src.begin(), src.end(), std::back_inserter(dst));     // append ke dst
std::transform(src.begin(), src.end(), std::back_inserter(dst),
               [](int x) { return x * 2; });                     // dst = 2*src

Ringkasan #

• Lima kategori iterator: input, output, forward, bidirectional, random-access — menentukan algoritma mana yang bisa dipakai.
• begin/end, rbegin/rend, cbegin/cend menyediakan iterasi maju, mundur, dan const.
• std::advance, std::distance, std::next, std::prev — operasi generik yang efisien untuk kategori tinggi, O(n) untuk kategori rendah.
• Aturan invalidation berbeda per container — paling ketat pada deque (semua invalid), paling longgar pada list (hanya yang di-erase).
• back_inserter/front_inserter/inserter adalah idiom output iterator untuk komposisi dengan algoritma STL.