1. Po co są kategorie iteratorów
Jeżeli dotąd postrzegaliście iterator jako „prawie wskaźnik”, to nie jesteście sami: tak myśli połowa ludzkości, w tym ja na początku mojej przygody z C++. Ale w STL iterator to nie „adres w pamięci”, a kontrakt możliwości: co dokładnie można robić z tym iteratorem i czego nie można oczekiwać.
Kategorie iteratorów służą dokładnie temu, by ustandaryzować te możliwości. Wtedy algorytm STL może uczciwie powiedzieć: „wystarczy, że potrafię robić ++it i czytać *it” — albo odwrotnie: „nie, ludzie, bez it + n i it2 - it1 nie będę sortował”.
Żeby uczynić to bardziej obrazowym: iterator to jak środek transportu. Na rowerze można jechać naprzód, czasem można ostrożnie cofnąć się, ale „teleport na 10 kilometrów naprzód” nie jest możliwy. Metro (przykładowy vector) pozwala „skoczyć” szybko na potrzebną stację.
Iterator i zakres [first, last)
Zanim podzielimy iteratory na kategorie, warto odświeżyć podstawowy model: STL niemal wszędzie używa półotwartego przedziału [first, last). To znaczy, że first wskazuje na pierwszy element zakresu, a last wskazuje na pozycję po ostatnim. Innymi słowy last nie można dereferencować — jest jak tabliczka „dalej urwisko”.
Mini-demo na naszym przykładzie edukacyjnym: załóżmy, że mamy listę zadań (użyjemy jej jako „kontekstu” w przykładach):
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> tasks{"Read", "Code", "Sleep"};
for (auto it = tasks.begin(); it != tasks.end(); ++it) {
std::cout << *it << '\n';
}
}
// Read
// Code
// Sleep
Tutaj widzicie podstawowe operacje, które niemal zawsze kojarzą się z iteratorami: porównanie !=, dereferencja *it oraz przesunięcie ++it. Ale dalej zaczyna się najciekawsze: nie każdy iterator wspiera „zaawansowane” operacje, takie jak it + 5 czy --it.
Drabina możliwości iteratorów
Kategoria iteratora to w istocie odpowiedź na pytanie: jakie operacje są gwarantowane (i co one znaczą). W standardzie to nie kaprys: to wymagania dotyczące poprawności, na których opierają się algorytmy biblioteki standardowej.
Warto trzymać w głowie „drabinę możliwości”: im wyższa kategoria, tym więcej operacji jest dozwolonych. Poniżej praktyczna ściąga (to nie formalna tabela standardu, a materiał edukacyjny).
| Kategoria | Można czytać *it | Można pisać *it = ... | Można ++it | Można --it | Można it + n, it[n] | Typowe skojarzenie |
|---|---|---|---|---|---|---|
|
tak | czasem (ale zwykle „tylko do odczytu”) | tak | nie | nie | strumień danych, czytanie „w miarę napływu” |
|
tak | zwykle tak | tak | nie | nie | wieloprzebiegowy „do przodu” |
|
tak | tak | tak | tak | nie | można wykonać krok wstecz |
|
tak | tak | tak | tak | tak | prawie jak tablica pod względem możliwości |
Sens tej tabeli nie polega na zapamiętaniu jej na pamięć, lecz na tym, by przestać pisać kod w stylu „a na vector przecież działało”. W STL bardzo ceni się myślenie w kategoriach gwarancji: co iterator obiecuję, a nie „co się udało w jednym kontenerze”.
2. Kategorie iteratorów w praktyce
input
: czytanie w miarę posuwania się i jednoprzebiegowość
inputInput-iteratory zwykle występują tam, gdzie dane nie leżą całe w kontenerze, a przychodzą sekwencyjnie: jak woda z kranu. Możesz postawić kubek (odczytać bieżącą wartość), potem przekręcić kurek na następny krok (wykonać ++it) — ale „wrócić do poprzedniej kropli wody” już nie możesz. Dlatego input-iteratory często są jednoprzebiegowe: nie można wykonać drugiego przebiegu po tych samych danych.
Klasycznym przykładem jest std::istream_iterator<T>, który czyta wartości ze strumienia. Jest dobry, bo sprawia, że „strumień” wygląda jak kontener, ale pozostaje strumieniem: odczytałeś — i koniec, nie cofasz się.
#include <iostream>
#include <iterator>
#include <sstream>
int main() {
std::istringstream in("10 20 30");
std::istream_iterator<int> it(in);
std::istream_iterator<int> end;
std::cout << *it << '\n'; // 10
++it;
std::cout << *it << '\n'; // 20
}
Zwróć uwagę na aspekt psychologiczny: istream_iterator wygląda jak zwykły iterator, ale jego natura jest bliższa „skanerowi”. Nie mówisz „daj mi element nr 5” — mówisz „daj następny”.
Jeśli spróbujesz myśleć o input-iteratorach jak o random-access („skoczę na 100 naprzód”), kompilator uczciwie powie: „nie obiecywaliśmy”.
forward
: tylko do przodu, ale można wykonać kilka przebiegów
forwardForward-iteratory przypominają input tym, że poruszają się tylko do przodu (++it), ale różnią się ważną praktyczną cechą: zwykle można je kopiować i ponownie używać do wielokrotnego przeglądu. To znaczy, że to już nie „strumień, który się spala”, a „normalna sekwencja”, tylko bez kroku wstecz.
W rzeczywistych kontenerach forward-iteratory często występują tam, gdzie struktura danych nie pozwala tanio iść wstecz. Koncepcyjnie to jak kartka z zadaniami przyklejona do ściany: czytasz z góry na dół, możesz spojrzeć z powrotem, ale nikt na poziomie interfejsu nie gwarantuje operacji --it.
Mała „weryfikacja rzeczywistości”: nawet jeśli prywatnie możesz wrócić, interfejs iteratora może tego nie umożliwiać. I to jest w porządku: STL opiera się na minimalnych gwarancjach.
W tej lekcji nie będziemy wiązać forward-iteratorów z konkretnym nowym kontenerem (aby nie zbaczać w temat następnego dnia), więc utrwalamy najważniejsze: forward = multi-pass + tylko ++. To kategoria „uczciwego krokomierza”: potrafi iść do przodu, nie umie cofać, ale trasa nie znika po pierwszym przebiegu.
bidirectional
: krok wstecz --it
bidirectionalBidirectional-iteratory to kolejny poziom wygody: oprócz ++it dostępny jest --it. W praktyce to „iterator, który potrafi cofać się”, ale za tym stoi sens praktyczny: niektóre algorytmy wymagają poruszania się z obu stron, np. „idziemy z początku i z końca na spotkanie”.
Bardzo typowym przedstawicielem bidirectional-iteratorów jest iterator std::map i std::set. To logiczne: drzewo (na którym zwykle oparty jest map) pozwala przejść do następnego i poprzedniego elementu w porządku, ale „skoczyć o +100” nadal nie można: drzewo to nie tablica.
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<int, std::string> users{{1, "Ann"}, {3, "Bob"}, {5, "Cat"}};
auto it = users.end();
--it; // krok wstecz: teraz to ostatni element
std::cout << it->first << " " << it->second << '\n'; // 5 Cat
}
Zauważcie, jak tu widać filozoficzną różnicę: w vector „ostatni element” często pobiera się przez indeksy lub back(), a w map naturalnie poruszamy się iteratorami, bo to „kontener do przeglądania”, a nie „kontener do indeksowania”.
I jeszcze jedna ważna uwaga: --users.end() jest poprawne, ponieważ end() to pozycja „po ostatnim”, a krok wstecz prowadzi do ostatniego elementu. Ale jeśli spróbujecie --users.begin(), to będzie już wyjście poza zakres (i tego nie wolno robić).
random-access
: skoki, indeksowanie i różnica
random-accessRandom-access to „premium” wśród iteratorów. Pojawia się tu wszystko, co przypomina tablicę: można szybko skoczyć o n do przodu (it + n), można użyć it[n], można porównywać „kto wcześniej w porządku” i nawet policzyć odległość jako różnicę iteratorów.
Klasyczne random-access iteratory widzieliście non stop, nawet jeśli nie nazywaliście ich tak: std::vector<T>::iterator i iteratory std::string.
#include <iostream>
#include <vector>
int main() {
std::vector<int> scores{10, 20, 30, 40};
auto it = scores.begin();
std::cout << it[2] << '\n'; // 30
std::cout << *(it + 3) << '\n'; // 40
}
Dlaczego to ważne dla STL? Ponieważ niektóre algorytmy, np. sortowanie std::sort, historycznie wymagają iteratorów random-access (w klasycznej wersji STL). To znaczy, jeśli iterator twojego kontenera nie jest random-access, nie możesz go bezpośrednio użyć z std::sort: nie z przekory, lecz dlatego, że algorytm potrzebuje szybkiego adresowania.
Kategoria to nie etykietka, lecz uczciwe ograniczenie dozwolonych operacji i zastosowalności algorytmów.
5. Przesunięcia i wymagania algorytmów
Przykład: dlaczego it + n nie działa dla map
Bardzo typowy scenariusz: napisałeś piękny kod na vector, potem postanowiłeś zamienić kontener na map (bo „tam są klucze”) — i nagle połowa operacji przestała istnieć. To nie dlatego, że map jest „zła”, lecz dlatego, że ma inną kategorię iteratorów.
Oto przykład, który działa dla vector, ale nie musi działać dla map. Celowo zostawiam „złą linię” zakomentowaną, aby kod się kompilował:
#include <map>
#include <string>
int main() {
std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.begin();
// it = it + 1; // nie można: iterator map nie jest random-access
(void)it;
}
I tutaj pojawia się dorosły nawyk: jeśli musisz „przesunąć się o n”, nie pisz it + n, dopóki nie jesteś pewien kategorii. Używaj uniwersalnego narzędzia, które działa dla różnych kategorii: std::advance.
std::advance(it, n) i koszt operacji
std::advance wygląda jak „po prostu wygodna funkcja”, ale w rzeczywistości wyraża właściwą myśl: chcę przesunąć iterator o n, ale nie chcę zakładać, że iterator jest random-access. Wtedy kompilator i biblioteka standardowa wybiorą poprawny sposób.
Na iteratorze random-access zwykle będzie to szybki skok. W słabszych kategoriach zamieni się to w n kroków ++it (i to jest normalne — trzeba pamiętać o koszcie).
#include <iostream>
#include <iterator>
#include <map>
#include <string>
int main() {
std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.begin();
std::advance(it, 2);
std::cout << it->second << '\n'; // three
}
Z punktu widzenia „myślenia algorytmami” to bardzo przydatne: nie wiążesz kodu z jednym kontenerem. Z punktu widzenia wydajności jest uczciwa cena: jeśli advance-ujesz o 1_000_000 po drzewie, rzeczywiście wykonasz milion kroków. Uniwersalność nie znosi zdrowego rozsądku — po prostu nie pozwala pisać niepoprawnego kodu.
Schemat wyboru operacji według kategorii
Aby nie trzymać wszystkiego w głowie jako „magiczne reguły”, można myśleć tak: najpierw rozpoznaj, jaki masz kontener/iterator, potem wybierz dozwolone operacje. Poniżej schemat-przypominajka.
flowchart TD
A["Jest kontener i iteratory begin/end"] --> B["Jaka kategoria iteratora?"]
B --> C["input: czytam, ++"]
B --> D["forward: czytam/piszę, ++, można kilka przebiegów"]
B --> E["bidirectional: ++ i --"]
B --> F["random-access: ++/--, it+n, it[n], it2-it1"]
F --> G["Można użyć algorytmów wymagających random-access, np. sort"]
E --> H["Można użyć algorytmów wymagających kroku wstecz, np. reverse"]
C --> I["Przypomina strumień: odczytałem i idę dalej"]
Ten schemat nie zastępuje praktyki, ale pomaga nie popełnić najczęstszego błędu początkującego: „jeśli kiedyś widziałem it[5], to znaczy, że to zawsze istnieje”.
6. Typowe błędy przy pracy z kategoriami iteratorów
Błąd nr 1: traktować dowolny iterator jak vector::iterator i oczekiwać it + n wszędzie.
To najczęściej spotykana pułapka: piszesz kod „jak dla tablicy”, a potem przenosisz go na map/set i dziwisz się, że „operatory zniknęły”. Poprawny model: to kategoria definiuje gwarancje. Jeśli potrzebujesz uniwersalnego przesunięcia, użyj std::advance, a jeśli potrzebujesz szybkiego dostępu po indeksie — wybierz kontener z iteratorami random-access.
Błąd nr 2: mylić „uniwersalne” z „szybkim”.
Po poznaniu std::advance łatwo pomyśleć: „O! Można wszędzie skakać o 10000 elementów”. Można, ale koszt jest różny. Dla random-access to zbliżone do it += 10000, a dla słabszych kategorii to wielokrotny ++it. Kod pozostaje poprawny, ale może być nieoczekiwanie wolny.
Błąd nr 3: próbować wykonać kilka przebiegów po input-iteratorze, jakby to był kontener.
std::istream_iterator i podobne iteratory często czytają dane ze strumienia: to źródło jednorazowe. Jeśli „przeszedłeś dalej”, zmieniłeś stan strumienia. Dlatego drugi przebieg po tych samych danych może być niemożliwy lub zwrócić pustkę. Jeśli potrzebujesz wielokrotnego przeglądu, najpierw zmaterializuj dane w kontenerze (np. w std::vector), a potem poruszaj się po nim ile chcesz.
Błąd nr 4: dereferencować end() lub robić kroki poza granice.
end() to nie „ostatni element”, lecz „pozycja po ostatnim”. Nie można jej dereferencować. Podobnie, --begin() i ++(--end()) w niewłaściwych miejscach łatwo prowadzą do wyjścia poza zakres. To nie jest błąd, który „zawsze od razu się sypie”: czasem objawia się dziwnymi symptomami i długo zastanawiacie się, dlaczego program drukuje „dinozaury pamięci”.
Błąd nr 5: próbować użyć algorytmu z iteratorami nieodpowiedniej kategorii i traktować to jako „błąd STL”.
Jeśli std::sort nie kompiluje się z twoimi iteratorami, to nie kaprys: algorytm ma wymagania co do możliwości iteratora. W takiej sytuacji bardziej sensowne niż „walka z kompilatorem” jest zadanie sobie pytania: „czy mój kontener jest w ogóle o dostępie losowym, czy raczej o przechowywaniu/porządkowaniu/szukaniu?” — i na tej podstawie wybór albo innego kontenera, albo innego podejścia.
GO TO FULL VERSION