Iterátorok

#include <iostream>
#include <list>

int main() {
    std::list<double> szamok = {1, 2, 3};

    /* begin, end, *, ++, != */
    std::list<double>::iterator it = szamok.begin();
    while (it != szamok.end()) {
        std::cout << *it << " ";
        ++it;
    }

    /* rövidebben */
    for (std::list<double>::iterator it = szamok.begin(); it != szamok.end(); ++it)
        std::cout << *it << " ";
}

Tárolót paraméterként átvevő változatban:

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

template <typename TAROLO>
void mindet_kiir(TAROLO const & t) {
    for (typename TAROLO::const_iterator it = t.begin(); it != t.end(); ++it)
        std::cout << *it << " ";
}

int main() {
    std::list<double> szamok_l = {1, 2, 3};
    std::vector<double> szamok_v = {1, 2, 3};

    mindet_kiir(szamok_l);
    mindet_kiir(szamok_v);
}

Mivel a tároló konstans, ezért iterator helyett const_iterator kell. A TAROLO::const_iterator elé pedig egy typename kulcsszó – ennek okai most nem lényegesek.

Az iterátorokat paraméterként átvevő változatban pedig az alábbi. Ez jobb, mert tömbökkel is tud dolgozni:

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

template <typename ITERATOR>
void mindet_kiir(ITERATOR begin, ITERATOR end) {
    for (ITERATOR it = begin; it != end; ++it)
        std::cout << *it << " ";
}

int main() {
    std::list<double> szamok_l = {1, 2, 3};
    std::vector<double> szamok_v = {1, 2, 3};
    int szamok_t[3] = {1, 2, 3};

    mindet_kiir(szamok_l.begin(), szamok_l.end());
    mindet_kiir(szamok_v.begin(), szamok_v.end());
    mindet_kiir(szamok_t, szamok_t + 3);
}

Fontos:

• A pointer is használható iterátornak, mert van * és ++ operátora.
• Az iterátorokkal megadott tartományok mindig balról zártak, jobbról nyitottak. Vagyis a begin az első elemre mutat, az end az utolsó utánira. Ezért a tömböknél tomb + meret, azaz &tomb[meret] a vége iterátor, nem pedig meret - 1.
• A pointerek esetében is ITERATOR begin, ITERATOR end a függvényparaméterek, csak ilyenkor ITERATOR = int*-gal példányosodik. Helyettesítsd be kézzel!

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

template <typename ITERATOR, typename T>
int count(ITERATOR begin, ITERATOR end, T const& elem) {
    int cnt = 0;
    for (ITERATOR it = begin; it != end; ++it)
        if (*it == elem)
            ++cnt;
    return cnt;
}

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

    std::cout << count(l.begin(), l.end(), 4) << std::endl;
    std::cout << count(v.begin(), v.end(), 2) << std::endl;
}

A függvénynek a range végére mutató iterátorral kell visszatérnie. Az már nem létező elem, tehát jelezni tudja, hogy nincs találat. A hívás helyén found == l.end() kifejezéssel ellenőrizhető, ez történt-e.

#include <iostream>
#include <list>

template <typename ITERATOR, typename T>
ITERATOR find_first(ITERATOR begin, ITERATOR end, T const& elem) {
    ITERATOR it = begin;
    while (it != end && *it != elem)
        ++it;
    return it;
}

template <typename ITERATOR, typename T>
ITERATOR find_first_2(ITERATOR begin, ITERATOR end, T const& elem) {
    for (ITERATOR it = begin; it != end; ++it)
        if (*it == elem)
            return it;
    return end;
}

int main() {
    std::list<double> l = {1, 2, 3, 4, 4, 5};

    std::list<double>::iterator found = find_first(l.begin(), l.end(), 3);
    if (found == l.end()) {
        std::cout << "Nincs ilyen." << std::endl;
    } else {
        std::cout << "Találat: " << *found << std::endl;
    }
}

A keresés fent két változatban megírva látszik. A for ciklusost talán könnyebb érteni, és a return end is kifejezőbb a végén. De az elsőnek is ugyanez az eredménye. Ha valahol *it == elem, akkor megáll a ciklus, és az iterátor aktuális értéke a visszatérési érték. Ha ez sehol nem teljesült, akkor it == end miatt áll meg, és így end a visszatérési érték.

std::list<double>::iterator found = find_first(l.begin(), l.end(), 3);
if (found != l.end()) {
    l.erase(found);
}

Ehhez az alábbi függvényeket és osztályokat kell implementálnunk:

• Verem::begin(), Verem::end(), amelyek iterátorokat adnak a verem elejére és végére.
• Verem::Iterator osztály.
• Verem::Iterator::operator++(), Verem::Iterator::operator*(), Verem::Iterator::operator!=() tagfüggvények.

Átgondolandó:

• Az iterátorban egy pointer lesz az egyik verem által lefoglalt objektumra. Kell az iterátornak destruktort, másoló konstruktort írnunk? Miért?
• Kapunk a begin()-től egy iterátort, amin sokszor meghívva a ++ operátort, olyan állapotba kell kerüljön, hogy egyenlő legyen az end()-től kapott iterátorral. Hogyan teljesül ez?
• Hogyan implementálható egyszerűen a postfix léptető operátor, vagyis it++ kifejezés hatására hívódó függvény? Miben különbözik ez ++it-től?
• Konstans tagfüggvény-e az operator*, vagy nem? Konstans referenciát ad-e vissza, vagy nem? Miért?
• Az iterátoroknak kell legyen alapértelmezett konstruktora; ha hiányozna, pótolni kell!
• Ha van !=, akkor kell == operátor is. Ha hiányozna, pótolni kell ezt is!