Pendalaman iterator

Topik ini memperdalam penggunaan iterator pustaka standar melampaui pasangan begin() dan end() yang sudah dikenal. Pembahasan mencakup lima kategori iterator beserta operasi yang membedakannya, iterator terbalik untuk penyusuran dari akhir, iterator konstan untuk pembacaan saja, dan aturan invalidasi yang menjaga perulangan tetap aman ketika container berubah. Setelah membacanya, pemilihan jenis iterator dan penanganan penghapusan elemen di tengah iterasi dapat dilakukan dengan dasar yang jelas.

Lima kategori iterator#

Kategori iterator adalah jenjang kemampuan yang menentukan operasi mana yang sah dilakukan pada sebuah iterator. Jenjangnya berlapis, karena setiap kategori yang lebih tinggi mewarisi seluruh operasi kategori di bawahnya. Pustaka standar membaginya menjadi lima kategori, yaitu input, output, forward, bidirectional, dan random access.

Kategori menentukan algoritma apa saja yang dapat menerima iterator tersebut. std::find hanya berjalan maju sehingga bisa diberi iterator dari hampir semua container, sedangkan std::sort menuntut random access karena harus menukar elemen yang jauh terpisah. Akibatnya, std::sort tidak dapat menerima iterator std::list, dan list menyediakan member function sort() sendiri yang mengurutkan isinya dengan cara yang sesuai untuk struktur berantai.

Perbedaan biaya antarkategori juga terlihat pada std::advance dan std::distance. Pada iterator random access, std::advance menghitung lompatan dengan aritmetika secara langsung, sedangkan pada iterator bidirectional pergeserannya berjalan satu demi satu. Program berikut menampilkan keduanya pada vector dan list yang isinya sama.

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

int main() {
    std::vector<int> nilai = {70, 85, 90, 60, 75};
    std::list<int> urutan = {70, 85, 90, 60, 75};

    // iterator vector mendukung lompatan bebas (random access)
    std::vector<int>::iterator vn = nilai.begin();
    std::advance(vn, 3);
    std::cout << "Elemen ke-4 vector: " << *vn << '\n';

    // iterator list hanya maju satu demi satu (bidirectional)
    std::list<int>::iterator ln = urutan.begin();
    std::advance(ln, 3);
    std::cout << "Elemen ke-4 list  : " << *ln << '\n';

    std::cout << "Jarak begin-end vector: "
              << std::distance(nilai.begin(), nilai.end()) << '\n';
    return 0;
}

Elemen ke-4 vector: 60
Elemen ke-4 list  : 60
Jarak begin-end vector: 5

Keluarannya identik, tetapi jalannya tidak. Pada vector, pemanggilan std::advance(vn, 3) berpindah tiga posisi sekaligus karena aritmetika iterator tersedia. Pada list, perpindahan yang sama harus menyusuri tiga simpul karena setiap simpul hanya mengenal tetangganya. Perbedaan ini tidak terasa pada data kecil, tetapi menjadi faktor desain ketika jumlah elemennya besar.

Reverse iterator#

Reverse iterator adalah pembungkus iterator bidirectional yang arah majunya dibalik, sehingga penyusuran dapat dimulai dari elemen terakhir tanpa perulangan tambahan. Member function rbegin() mengembalikan iterator yang menunjuk elemen terakhir, sedangkan rend() menandai posisi sebelum elemen pertama. Operasi ++it yang biasa bergerak maju kini bergerak mundur. Karena antarmukanya sama, algoritma yang biasa berjalan maju dapat dipakai ulang untuk menyusuri container dari arah sebaliknya.

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

int main() {
    std::vector<int> stok = {12, 7, 20, 5};
    std::vector<int> dariAkhir;

    // salin dengan urutan terbalik lewat rbegin dan rend
    std::copy(stok.rbegin(), stok.rend(), std::back_inserter(dariAkhir));

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

5
20
7
12

Program di atas menyalin isi vector dengan std::copy, tetapi rentang yang diberikan adalah rbegin() sampai rend(), sehingga hasilnya terbalik. Pola yang sama berlaku untuk std::find yang dipasangkan dengan rbegin(), dan pola itu berguna untuk mencari kemunculan terakhir tanpa membalik container terlebih dahulu. Penyusuran terbalik hanya membutuhkan kategori bidirectional, sehingga berlaku pula untuk list, map, dan set.

Const iterator#

Const iterator adalah iterator yang melarang perubahan pada elemen yang ditunjuknya, sedangkan perpindahannya tetap normal. Bentuknya const_iterator, diperoleh lewat cbegin() dan cend(), dan berguna untuk menyatakan niat membaca lewat tipe sebagaimana konvensi const pada parameter fungsi. Bentuk ini perlu dibedakan dari deklarasi const std::vector<int>::iterator, yang mengunci posisi iteratornya tetapi tetap membolehkan perubahan elemen. Keduanya bertujuan berbeda, sehingga penulisan yang tepat menghindari kebingungan.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> suhu = {28, 31, 27};

    // iterator biasa: elemen yang ditunjuk boleh diubah
    for (std::vector<int>::iterator it = suhu.begin(); it != suhu.end(); ++it) {
        *it += 1;
    }

    // const_iterator: elemen hanya dibaca
    for (std::vector<int>::const_iterator it = suhu.cbegin(); it != suhu.cend(); ++it) {
        std::cout << "Suhu: " << *it << '\n';
    }
    return 0;
}

Suhu: 29
Suhu: 32
Suhu: 28

Putaran pertama menggunakan iterator biasa dan menaikkan setiap suhu satu derajat, sedangkan putaran kedua menggunakan cbegin() dan cend() untuk membaca hasilnya. Percobaan menulis melalui const_iterator langsung ditolak compiler, seperti pada potongan berikut.

// tidak-dijalankan (error kompilasi: elemen yang ditunjuk bersifat konstan)
std::vector<int> nilai = {70, 85};
auto cit = nilai.cbegin();
*cit = 99;   // error: assignment of read-only location

Pesan errornya menyebut read-only location, karena compiler memperlakukan elemen hasil dereference const_iterator sebagai nilai konstan. Fungsi yang menerima parameter const std::vector<int>& otomatis hanya mendapat const_iterator dari container tersebut, sehingga kebiasaan ini juga melindungi kode peminjam dari perubahan yang tidak disengaja.

Aturan invalidasi#

Invalidasi iterator adalah keadaan ketika iterator tidak lagi menunjuk elemen yang sah karena strukturnya berubah. Perubahannya bisa berupa penambahan, penghapusan, atau realokasi memori internal. Iterator yang sudah tidak sah tidak boleh dibaca, ditulis, atau digeser, dan pemakaiannya termasuk undefined behavior. Aturan rincinya berbeda untuk setiap jenis container.

Kesalahan yang paling sering muncul adalah menghapus elemen sambil mengiterasi. Pola berikut tampak masuk akal, tetapi erase() menggugurkan iterator yang sedang dipakai, sehingga ++it pada putaran berikutnya membaca iterator yang tidak sah.

// tidak-dijalankan (undefined behavior: iterator gugur dipakai kembali)
std::vector<int> nilai = {70, 55, 85, 60};
for (auto it = nilai.begin(); it != nilai.end(); ++it) {
    if (*it < 70) {
        nilai.erase(it);   // it gugur di sini
    }
}

Pola yang benar memanfaatkan nilai kembalian erase(), yaitu iterator sah yang menunjuk elemen setelah yang baru dihapus. Iterator tersebut dipakai untuk melanjutkan perulangan, sedangkan pemanggilan ++it hanya dilakukan ketika elemen dipertahankan.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> nilai = {70, 55, 85, 60, 90, 50};

    auto it = nilai.begin();
    while (it != nilai.end()) {
        if (*it < 70) {
            it = nilai.erase(it);   // erase mengembalikan iterator sah berikutnya
        } else {
            ++it;
        }
    }

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

70
85
90

Penghapusan berdasarkan nilai secara menyeluruh juga dapat diringkas menjadi idiom erase-remove yang memadukan std::remove dan erase dalam satu ekspresi. Apa pun polanya, aturan pokoknya tetap sama, yaitu jangan pernah memakai iterator setelah operasi yang mengubah struktur container, kecuali iterator itu diperbarui dari nilai kembalian operasinya.

Ringkasan#

• Lima kategori iterator membentuk jenjang kemampuan, dan kategori sebuah iterator menentukan algoritma yang dapat menerimanya serta biaya operasinya.
• rbegin() dan rend() membalik arah penyusuran lewat reverse iterator, sedangkan cbegin() dan cend() menegaskan pembacaan saja lewat const_iterator.
• Setiap container memiliki aturan invalidasinya sendiri, dan penghapusan di tengah iterasi pada vector wajib ditangani dengan it = nilai.erase(it) agar iterator yang dipakai tetap sah.

Referensi#

• Iterator library — cppreference.com — Definisi lima kategori iterator dan operasi khasnya.
• std::reverse_iterator — cppreference.com — Perilaku reverse iterator dan hubungannya dengan iterator dasar.
• std::vector — cppreference.com — Catatan invalidasi iterator pada push_back, insert, dan erase.
• Introduction to iterators — LearnCpp — Pengantar iterator dan kebiasaan perulangannya yang aman.