29.1 Iterator-kategóriák és fél-nyílt tartomány

A korábbi tárolófejezetekben már láttuk, hogy a std::vector iterátora és a std::list iterátora között lényegi különbség van: az egyik folytonos és konstans időben lépkedhető, a másik csak szekvenciálisan járható be. Az algoritmusok mégis közel azonos módon írhatók meg mindkettőn. Ezt az egységes felületet az iterator absztrakció adja, amely a C pointeraritmetikát általánosítja: egy irányított kurzor egy tároló elemére, amellyel léptetni, dereferálni és összehasonlítani lehet. Ebben az alfejezetben rögzítjük az iterator pontos fogalmát, a fél-nyílt tartomány érvényességi szerződését és azokat az iterátorkategóriákat, amelyek meghatározzák, mit lehet egy adott algoritmussal megtenni. A szabályok a Pointeraritmetika, objektumhatár és provenance (6.2) nyelvi alapjaira épülnek, és előkészítik a tárolóválasztást (Tárolóválasztási és invalidációs labor (28.6)) valamint a concepts-alapú megszorításokat (Concepts, requires és constrained overload (27.2)).

29.1.1 Az iterátor mint általánosított pointer

Definíció (iterátor). Egy It típus iterátor egy C tároló felett, ha értékszemantikával rendelkezik, it++ és ++it formában léptethető, *it dereferálással hozzáférhető, valamint it1 == it2 és it1 != it2 összehasonlítható. Egy adott It az elemek egy kitüntetett pozícióját reprezentálja, nem az elem értékét.

Az iterátor-alapú algoritmusok egyetlen, általában másfél paramétert kapnak: egy first iterátort és egy last iterátort. Az algoritmus mindaddig dolgozik, amíg first != last. Ebből három alapvető következtetés adódik. Egyrészt last nem dereferálható: nem egy elemre mutat, hanem a meglátogatandó elemek utáni pozícióra. Másrészt az algoritmus ürességet first == last esetben érzékeli, azaz nem kell külön darabszámot átadni. Harmadrészt a távolság kifejezhető last - first formában, de csak akkor, ha az It típus támogatja a kivonást – ezért a hordozható kód std::distance(first, last)-et használ.

Előfeltételek. Az [first, last) tartomány akkor érvényes, ha last elérhető first-ből ismételt ++ műveletekkel, a köztes pozíciók mindegyike dereferálható, és a bejárás során nem invalidálódik egyik iterátor sem. Az iterátor nem tárolja, hogy melyik tárolóhoz tartozik (nincs benne ownership), ezért a szerződés megszegése nem feltétlenül okoz azonnali hibát – ez a pointerekre emlékeztető, de szigorúbb élettartam-kérdés.

29.1.2 A fél-nyílt tartomány szerződése

A [first, last) fél-nyílt tartomány használatának három indoka van. Egyrészt a pointer-aritmetika a C-ben egy-past-the-end pointert is megenged, így a last kifejezhető a tömbben begin + n alakban anélkül, hogy egy elemre mutatna. Másrészt az üres tartomány természetes reprezentációja first == last, nincs szükség külön jelzőre. Harmadrészt a szomszédos tartományok összefűzése triviális: [a, b) + [b, c) = [a, c).

A last kezelésének gyakori következménye, hogy egyetlen dereferálás történik, ha az algoritmust first != last ciklus védi. Kivétel az az eset, amikor az algoritmus előfeltétele nem üres tartomány – például a maximum keresése. Ilyenkor a hívónak kell biztosítania first != last-et, és a szerződést vagy assert-tel, vagy std::optional visszatérési értékkel kell kifejezni.

29.1.3 Iterator-kategóriák

A kategóriák azt írják le, milyen műveletek érhetők el konstansidőben és milyen multiplicitással. A C++20 névterében ezek conceptek, de a mögöttes felbontás a klasszikus C++98-as címkékből származik.

A C++20 két külön kérdést tesz fel egy iterátorról. (1) Bejárás: milyen mozgások érhetők el, és bejárható-e többször a tartomány? (2) Hozzáférés: olvasható-e (std::indirectly_readable), írható-e egy T érték rajta keresztül (std::indirectly_writable<It, T>)? A kettő független: a bejárási kategória nem mondja meg, hogy az iterátoron át írhatunk-e.

Bejárási kategória	Többször bejárható	`--`	`+ n`	Távolság	Példa
bemeneti (`input_iterator`)	nem	nem	nem	O(n)	`istream_iterator`
előre haladó (`forward_iterator`)	igen	nem	nem	O(n)	`forward_list` iterátora
kétirányú (`bidirectional_iterator`)	igen	igen	nem	O(n)	`list`, `map` iterátora
véletlen elérésű (`random_access_iterator`)	igen	igen	igen	O(1)	`deque` iterátora
folytonos (`contiguous_iterator`)	igen	igen	igen	O(1)	`vector` iterátora, `T`, `const T`

Iterátor (`V` = `std::vector<int>`)	Bejárási kategória	Olvasható	`int` írható
`V::iterator`, `int*`	folytonos	igen	igen
`V::const_iterator`, `const int*`	folytonos	igen	nem
`std::istream_iterator<int>`	bemeneti	igen	nem
`std::back_insert_iterator<V>`	nincs (csak output)	nem	igen

Az output_iterator tehát nem bejárási fokozat, hanem az „írható és léptethető” tulajdonság neve; egy back_insert_iterator nem olvasható és nem is input_iterator.

// iter_concepts.cpp — C++20: bejárási kategória és írhatóság külön kérdés
#include <forward_list>
#include <iterator>
#include <list>
#include <sstream>
#include <vector>

using CVecIt = std::vector<int>::const_iterator;
using BackIns = std::back_insert_iterator<std::vector<int>>;

// const int*: a legerősebb kategória, de nem írható
static_assert(std::contiguous_iterator<const int*>);
static_assert(!std::indirectly_writable<const int*, int>);
// const vector-iterátor: ugyanígy
static_assert(std::contiguous_iterator<CVecIt>);
static_assert(!std::indirectly_writable<CVecIt, int>);
// nem const vector-iterátor: contiguous ÉS írható
static_assert(std::indirectly_writable<std::vector<int>::iterator, int>);
// back_insert_iterator: csak output, nem olvasható, nincs bejárási kategóriája
static_assert(std::output_iterator<BackIns, int>);
static_assert(!std::input_iterator<BackIns> && !std::indirectly_readable<BackIns>);
// istream_iterator: input, nem forward
static_assert(std::input_iterator<std::istream_iterator<int>>);
static_assert(!std::forward_iterator<std::istream_iterator<int>>);
// forward_list és list
static_assert(std::forward_iterator<std::forward_list<int>::iterator>);
static_assert(!std::bidirectional_iterator<std::forward_list<int>::iterator>);
static_assert(std::bidirectional_iterator<std::list<int>::iterator>);
static_assert(!std::random_access_iterator<std::list<int>::iterator>);

int main() {}

Buildjegyzőkönyv (lab-gcc profil). g++ -std=c++20 -Wall -Wextra -Wpedantic iter_concepts.cpp figyelmeztetés nélkül fordul, tehát a fenti static_assert-ek — köztük a std::contiguous_iterator<const int*> és a !std::indirectly_writable<const int*, int> — teljesülnek.

A bejárási kategóriák egymásra épülnek: minden forward_iterator egyben input_iterator, minden contiguous_iterator egyben random_access_iterator. A contiguous_iterator C++20 újdonság: garantálja, hogy std::to_address(it + n) == std::to_address(it) + n, azaz a szomszédos elemek memóriacíme is szomszédos. Ez teszi lehetővé a std::vector adatának T*-ként való átadását C API-nak, és ezt a garanciát a std::deque – bár random access iterátorral rendelkezik – nem adja meg.

29.1.4 Single-pass és multipass

A forward_iterator és erősebb kategóriák multipass tulajdonsággal rendelkeznek: ha a és b ugyanazon pozíció két másolata, akkor *a és *b ugyanazt az elemet jelöli, és ++a után a != b, de b még mindig az eredeti elemre mutat. Ezt kihasználják azok az algoritmusok, amelyek egy tartományt többször bejárnak (például bináris keresés, rendezés).

Az input_iterator és output_iterator ezzel szemben single-pass: egy ++ után a korábbi másolatok érvénytelenné válnak, mert az olvasás/írás egy megosztott pufferen keresztül történik. Ha egy input_iterator tartományon std::distance-t hívunk, a bemeneti stream elfogy, és a first iterátor a továbbiakban nem használható. Ez a klasszikus hiba, amikor egy streamet előbb megszámolunk, majd újra be akarunk járni.

29.1.5 distance és advance kategóriafüggő költsége

Az algoritmusok bonyolultsági elemzése csak akkor pontos, ha az iterátor kategóriáját is megadjuk.

Művelet	Input/Forward	Bidirectional	RandomAccess/Contiguous
`std::distance(first, last)`	O(n), fogyasztja a forrást	O(n)	O(1)
`std::advance(it, n)`	O(n), `n >= 0`	O(n), `n` negatív is lehet	O(1)
`std::next(it, n)`	O(n)	O(n)	O(1)
`std::prev(it, n)`	nem elérhető	O(n)	O(1)

A lineáris esetben a költség n = distance(first, last). Ezért egy std::list-en írt lineáris keresés összköltsége O(n), de egy „előre megszámolom a hosszát, aztán lineárisan bejárom” minta O(2n) lesz – ugyanaz az aszimptotika, de a konstans kétszeres, és ami nagyobb baj, az input_iterator esetén egyenesen hibás. A std::distance és std::advance implementációja a klasszikus C++-ban overload-feloldással, C++20-ban if constexpr-fel vagy tag dispatch-csel választja ki a kategóriát. Ez a Concepts, requires és constrained overload (27.2) mintájának egyik legrégebbi alkalmazása.

29.1.6 iterator_traits és concepts kapcsolata

A std::iterator_traits<It> egy fordítási idejű leíró, amely az iterátor tulajdonságait nevesített típusokként teszi elérhetővé: value_type, difference_type, reference, pointer, iterator_category, valamint C++20-tól iterator_concept. A T* pointerekre specializáció biztosítja, hogy a nyers pointerek is működjenek. Az algoritmusok ezeket a típusokat használják belső változók deklarálásához és a kategória-alapú döntésekhez.

A C++20 conceptek ugyanezt a hierarchiát fejezik ki std::input_iterator, std::forward_iterator stb. formában. A kapcsolat kettős. Egyrészt a conceptek teljesítéséhez végső soron az iterator_traits által kinyert típusoknak kell megfelelniük. Másrészt a contiguous_iterator bevezetésével az iterator_concept tag vette át a pontos kategória szerepét, mert egy vector<int>::iterator iterator_category-ja random_access_iterator_tag, de iterator_concept-ja contiguous_iterator_tag – ezt az eltérést a legacy kód miatt nem lehetett az iterator_category-be beírni. Új algoritmus írásakor a concepteket használjuk (template <std::forward_iterator It>), mert ezek az olvasó számára dokumentálják az előfeltételt, és a hibaüzeneteket is pontosabbá teszik.

29.1.7 Reverse iterator és a base kapcsolata

A std::reverse_iterator<It> egy It típust csomagol be úgy, hogy a ++ a ---t hívja és a dereferálás egy elemmel visszalép. Az alapgondolat az, hogy a fordított iterátor a base() által visszaadott pozíció előtti elemre mutat. A kulcsazonosság:

*\text{rit} \;=\; *\bigl(\text{rit.base()} - 1\bigr) \;=\; *\bigl(\text{std::prev}(\text{rit.base()})\bigr)

A második alak hordozható azokra a kategóriákra is, ahol a - 1 nem értelmezett (például list). Bizonyításvázlat. Legyen it az It egy pozíciója, és tegyük fel, hogy it != begin(). A reverse_iterator belső állapota megegyezik it-vel; a v.rbegin() konstruktora v.end()-et, a v.rend() a v.begin()-et kapja. A std::reverse_iterator::operator* definíció szerint egy lokális másolatot dekramentál, majd dereferál; ezért a base() mindig egy pozícióval a logikai elem után áll. Ebből adódik a fenti azonosság. A rend().base() == begin() és rbegin().base() == end() azonosságok a konstrukcióból következnek, ezért a fordított tartomány fél-nyílt szerződése ugyanaz marad: [rbegin(), rend()).

Ez a plusz egy eltolás a gyakorlatban a leggyakoribb reverse_iterator hibaforrás. Ha a rit által mutatott elemet akarjuk törölni, nem rit.base()-ot kell átadni, hanem std::prev(rit.base())-ot (vagy (rit + 1).base()-ot). A rit.base() a következő pozíció, nem az aktuális.

29.1.8 Kidolgozott példa

Az alábbi példa egy std::forward_iterator fogadó sablonnal mutatja meg, hogy azonos algoritmus működik vector-on, list-en és forward_list-en, és hogy a distance költsége kategóriafüggő. A második rész a reverse_iterator és base() kapcsolatát ellenőrzi. A fájl önállóan fordítható C++20 alatt GCC 13 vagy Clang 17 mellett; a buildparancs a kód után szerepel.

// main.cpp
#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

template <std::forward_iterator It>
void report_distance(const char* name, It first, It last) {
    // distance kategóriafüggő: forward esetén O(n), random access esetén O(1)
    std::cout << name << ": distance = " << std::distance(first, last) << '\n';
}

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

    report_distance("vector",       v.begin(), v.end());
    report_distance("list",         l.begin(), l.end());
    report_distance("forward_list", f.begin(), f.end());

    auto rit = v.rbegin();                       // *rit == 50
    std::cout << "*rbegin() = " << *rit << '\n';
    std::cout << "rbegin().base() == end(): "
              << std::boolalpha << (rit.base() == v.end()) << '\n';
    std::cout << "*(rbegin().base()-1) == *rbegin(): "
              << (*(rit.base() - 1) == *rit) << '\n';
    std::cout << "rend().base() == begin(): "
              << (v.rend().base() == v.begin()) << '\n';
}

g++ -std=c++20 -O2 -Wall -Wextra -pedantic main.cpp -o main
./main

Érdemes megfigyelni, hogy a report_distance sablon előfeltétele std::forward_iterator, ezért istream_iterator-t nem fogad el – helyesen, hiszen a distance ott elfogyasztaná a bemenetet. A std::vector<int>::iterator contiguous_iterator, std::list<int>::iterator csak bidirectional_iterator, std::forward_list<int>::iterator pedig forward_iterator; a report_distance mindegyiket elfogadja, mert a leggyengébb közös kategóriát igényli.

29.1.9 Tipikus hibák és javításuk

Az első és legfontosabb hiba a last dereferálása, például for (auto it = v.begin(); it <= v.end(); ++it). A <= itt nem csak stíluskérdés: a v.end() dereferálása nem definiált viselkedés, és a ciklus egy extra iterációval túllép. A helyes minta < vagy != a last-tal szemben.

A második hiba az iterátor érvénytelenné válása. A vector::push_back és minden újrafoglalást okozó művelet érvényteleníti a korábbi iterátorokat; a list::erase csak a törölt elemre mutató iterátort. Ezt a Tárolóválasztási és invalidációs labor (28.6) laborban részletesen tárgyaljuk – itt annyit rögzítünk, hogy az „érvényes [first, last)” szerződés a bejárás teljes időtartamára szól.

A harmadik hiba a distance és advance költségének figyelmen kívül hagyása. Egy list-en írt „előre megszámolom, aztán advance-dzsel a közepére ugrok” minta O(n) helyett véletlenül O(n) marad, de a konstans kétszeres; forward_list-en pedig a std::prev egyáltalán nem fordul le.

A negyedik a reverse_iterator base() off-by-one hibája, amelyet fent részleteztünk.

29.1.10 Összefoglaló

Az iterátor a C pointer általánosítása: egy kurzor, amely dereferálható, léptethető és összehasonlítható. Az algoritmusok [first, last) fél-nyílt tartományon dolgoznak, ahol last egy-past-the-end és nem dereferálható. A kategóriák (input, output, forward, bidirectional, random access, contiguous) azt rögzítik, milyen műveletek érhetők el, milyen multiplicitással és milyen költséggel; a distance és advance lineáris vagy konstans ideje ebből következik. Az iterator_traits és a C++20 conceptek ugyanezt a hierarchiát fejezik ki, a reverse_iterator pedig a base() egy pozícióval eltolt szerződésén keresztül illeszkedik a fél-nyílt modellbe.

29.1.11 Feladatok

1. feladat (magyarázó). Sorolja be kategóriába a következő iterátorokat, és adja meg, hogy std::distance(first, last) konstans vagy lineáris-e rajtuk: std::istream_iterator<int>, std::ostream_iterator<int>, std::forward_list<int>::iterator, std::list<int>::iterator, std::deque<int>::iterator, std::vector<int>::iterator, int*.

2. feladat (kódolási). Írjon template <std::forward_iterator It> It find_max(It first, It last) sablont, amely a legnagyobb elemre mutató iterátort adja vissza, üres tartomány esetén last-et. A sablon működjön vector, list és forward_list felett is. Adja meg az előfeltételt, a visszatérési érték érvényességi tartományát és a buildparancsot.

3. feladat (diagnosztikai). Az alábbi kódrészlet nem fordul le, illetve futásidőben hibás:

std::list<int> l{1, 2, 3};
auto pit = l.end() - 1;             // (a)

std::forward_list<int> f{1, 2, 3};
int x = *f.end();                    // (b)

std::vector<int> v{1, 2, 3};
auto rit = v.rbegin();
v.erase(rit.base());                // (c)

29.1.12 Megoldások

29.1.12.1 1. feladat megoldása

istream_iterator és ostream_iterator: input_iterator, illetve output_iterator, single-pass; a distance lineáris, és az istream_iterator bejárása elfogyasztja a bemenetet. forward_list::iterator: forward_iterator, distance lineáris. list::iterator: bidirectional_iterator, distance lineáris. deque::iterator: random_access_iterator, distance konstans – de nem contiguous_iterator, mert a deque blokkos tárolású. vector::iterator és int*: contiguous_iterator, distance konstans. Az ellenőrzés feltétele: a válasz minden esetben tartalmazza a kategóriát és a distance-re vonatkozó állítást; a deque és a vector megkülönböztetése akkor helyes, ha a contiguous hiányát indokolja.

29.1.12.2 2. feladat megoldása

#include <iterator>

template <std::forward_iterator It>
It find_max(It first, It last) {
    if (first == last) return last;      // üres tartomány: a last nem dereferálható
    It best = first;
    ++first;                             // az első elemet már megvizsgáltuk
    for (; first != last; ++first) {
        if (*best < *first) best = first;
    }
    return best;
}

Az előfeltétel csak std::forward_iterator, tehát multipass és ==/!=; ---ra és <-ra nincs szükség. A visszatérési érték vagy maga a last (üres bemenet), vagy egy érvényes elemre mutató iterátor, amely a bejárás végéig érvényes marad, feltéve hogy a tárolót nem módosítjuk. Az It best = first; ++first; mintázat elkerüli azt a hibát, hogy az üres tartomány esetén is dereferáljunk. Build: g++ -std=c++20 -O2 -Wall -Wextra -pedantic -c main.cpp.