Iteratory w C++: begin, end i rodzaje iteratorów

Czym naprawdę jest iterator

Każdy standardowy kontener, czyli vector, string, map, set, list, przechowuje elementy w środku inaczej. vector to ciągły blok, map to zrównoważone drzewo, list to połączone węzły. A jednak po każdym z nich można przejść pętlą w ten sam sposób. Umożliwia to iterator: mały obiekt, który „wskazuje” na jeden element i wie, jak przejść do następnego.

Traktuj iterator jak uogólniony wskaźnik. Dostajesz go z begin(), odczytujesz wskazywany element przez * i przesuwasz go do przodu przez ++. Te elementy układają się tak:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    vector<int>::iterator it = v.begin();
    cout << *it << "\n";   // 10: dereferencja odczytuje element

    ++it;                  // przejdź do następnego elementu
    cout << *it << "\n";   // 20
}

v.begin() zwraca iterator do pierwszego elementu; *it daje ten element; ++it przechodzi do następnego. Ta trójka, czyli dereferencja, przesunięcie i porównanie, to cały model myślowy.

begin(), end() i zakres prawostronnie otwarty

Drugą połową obrazu jest end(). Co kluczowe, end() nie wskazuje na ostatni element, tylko na miejsce tuż za ostatnim elementem. To celowo zakres „prawostronnie otwarty” [begin, end): begin jest w nim zawarte, a end to sygnał stopu.

Dzięki temu standardowa pętla jest przejrzysta: idziesz, dopóki iterator nie zrówna się z end():

#include <iostream>
#include <vector>
using namespace std;

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

    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";
}

Zwróć uwagę na it != v.end(), a nie it < v.end(). Większość iteratorów kontenerów (np. map czy list) nie obsługuje <, tylko == i !=, więc != jest wyborem przenośnym. A auto oszczędza ręcznego pisania vector<int>::iterator, bo kompilator sam wydedukuje typ.

Przypadek pustego kontenera obsługuje się sam: gdy kontener jest pusty, begin() == end(), więc ciało pętli nigdy się nie wykona. Żadna specjalna obsługa nie jest potrzebna.

Nigdy nie dereferencjonuj end()

Najczęstszy błąd z iteratorami to dereferencja end(). Skoro wskazuje on tuż za ostatni element, *v.end() czyta pamięć, która nie należy do ciebie. To niezdefiniowane zachowanie, czyli awaria albo ciche śmieci, a nie przyjazny komunikat o błędzie:

vector<int> v = {1, 2, 3};
cout << *v.end();   // NIEZDEFINIOWANE ZACHOWANIE: end() nie jest elementem

Ta sama pułapka dotyczy funkcji wyszukujących. std::find zwraca end(), gdy nie znajdzie wartości, więc przed dereferencją musisz to sprawdzić:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 4, 6, 8};

    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        cout << "Found: " << *it << "\n";
    } else {
        cout << "5 is not in the vector\n";   // to się wykona
    }
}

Zawsze porównuj zwrócony iterator z end(), zanim zrobisz dereferencję. Zapomniane if to jedno z najczęstszych źródeł awarii w kodzie STL pisanym przez początkujących.

const, cbegin i iteratory odwrotne

Kontenery udostępniają różne odmiany iteratorów, zależnie od potrzeb:

• begin() / end(): zwykłe iteratory do odczytu i zapisu (*it = ... działa).
• cbegin() / cend(): const_iteratory; przez nie możesz czytać, ale nie modyfikować elementu.
• rbegin() / rend(): iteratory odwrotne, które idą od końca do początku; ++ faktycznie przesuwa do tyłu.

Iteratory odwrotne to czysty sposób na pętlę od końca bez kłopotliwej arytmetyki indeksów:

#include <iostream>
#include <vector>
using namespace std;

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

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";   // 4 3 2 1
    }
    cout << "\n";
}

Przy iteratorach odwrotnych nadal piszesz ++it, żeby iść dalej: iterator sam obsługuje kierunek „wstecz”. Używaj cbegin()/cend() (albo referencji const do kontenera), gdy pętla ma tylko czytać, a kompilator powstrzyma cię przed przypadkowym zapisem.

Iteratory map zwracają pary

Nie każdy iterator to cienka nakładka na wskaźnik. Iterator std::map chodzi po drzewie, a jego dereferencja daje std::pair z kluczem i wartością, dostępnymi przez ->first i ->second (iterator, tak jak wskaźnik, obsługuje ->):

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages = {{"Ada", 36}, {"Grace", 85}};

    for (auto it = ages.begin(); it != ages.end(); ++it) {
        cout << it->first << " -> " << it->second << "\n";
    }
}

Pętla for po zakresie jest zbudowana bezpośrednio na begin()/end(), więc przy zwykłym przechodzeniu do przodu zwykle wybierzesz właśnie ją. Jawne iteratory przydają się, gdy potrzebujesz przejścia od końca, pozycji elementu albo przekazania zakresu do algorytmu.

Wielka pułapka: unieważnienie iteratorów

Na tę pułapkę prędzej czy później trafia każdy. Gdy zmieniasz strukturę kontenera, istniejące iteratory mogą zostać unieważnione: wskazują wtedy na pamięć zwolnioną lub przeniesioną. Użycie takiego iteratora to niezdefiniowane zachowanie.

W vector push_back może przealokować cały bufor, żeby go powiększyć, co unieważnia każdy istniejący iterator. Jeszcze bardziej osławione jest usuwanie w trakcie pętli; to klasyczna awaria:

vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0)
        v.erase(it);   // BŁĄD: erase unieważnia it, a potem ++it to UB
}

Rozwiązanie: erase zwraca poprawny iterator do elementu za usuniętym. Przesuwaj iterator tylko wtedy, gdy nic nie usunięto:

#include <iostream>
#include <vector>
using namespace std;

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

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0)
            it = v.erase(it);   // erase zwraca następny poprawny iterator
        else
            ++it;               // przesuwaj tylko, gdy nic nie usunięto
    }

    for (int x : v) cout << x << " ";   // 1 3 5
    cout << "\n";
}

Zauważ, że nagłówek for nie ma ++it: to ciało pętli decyduje, czy przesunąć iterator. (W prawdziwym kodzie idiom erase-remove albo std::erase_if z C++20 robi to w jednej linii.) Zasada do zapamiętania: każda operacja, która dodaje lub usuwa elementy, może unieważnić iteratory, więc nie trzymaj starego iteratora przez taką zmianę.

Dalej: algorytmy

Skoro umiesz opisać zakres jako parę begin/end, masz dostęp do całej biblioteki algorytmów STL. Funkcje takie jak sort, find, count i accumulate nie dbają o to, jaki masz kontener: działają na zakresach iteratorów, więc to samo wywołanie działa na vector, tablicy albo jej fragmencie. Dalej zaprzęgniemy te iteratory do pracy i pozwolimy bibliotece standardowej wykonać pętle za ciebie.