Iteratory¶

Iterator jest obiektem, który umożliwia iterację po elementach kontenera za pomocą interfejsu zaadoptowanego od zwykłych wskaźników
- operator++ (inkrementacji) przesuwa wskaźnik na następny element
- operator* (dereferencji) oraz operator-> pozwalają na odczytanie wskazywanej przez wskaźnik wartości
Kontenery standardowe posiadają odpowiednie grupy funkcji begin() i end(), które zwracają odpowiednie iteratory
- dla tablic natywnych dostępne są funkcje wolne begin() oraz end()

Kategorie iteratorów¶

Wejściowe (input iterator)

pozwalają na odczyt sekwencji tylko w jednym przejściu
operator inkrementacji (++) przesuwa iterator na następny element
odczyt elementów jest możliwy za pomocą operatora dereferencji (*)
element odczytany nie może być modyfikowany

Wyjściowe (output iterator)

pozwala na zapis sekwencji w jednym przejściu (implementuje tylko operator inkrementacji (++))
operator dereferencji (*) służy jedynie przypisaniu wartości elementowi

Postępujące (forward iterator)

pozwala na jednokierunkowy dostęp do elementów sekwencji
każdy element może być wielokrotnie zapisywany i odczytywany
iterator postępujący może być użyty w miejscach, gdzie wymagany jest iterator wejściowy i wyjściowy

Dwukierunkowe (bidirectional iterator)

zdefiniowane operatory inkrementacji (++) oraz dekrementacji (--)
możliwy odczyt oraz zapis

Dostępie swobodnym (random access iterator)

pozwala na swobodny dostęp do dowolnego elementu kolekcji
udostępnia operator indeksowania ([]) pozwalający na natychmiastowy dostęp do dowolnego elementu kontenera
możliwe jest dodanie lub odjęcie od iteratora liczby całkowitej, co powoduje przesunięcie go o więcej niż jedną pozycję
odejmowanie dwóch iteratorów o dostępie swobowdnym daje w wyniku odległość między nimi

Stosowanie iteratorów¶

Iterator deklaruje się przy użyciu typu, który ma podlegać przeglądaniu

std::list<string>::iterator it = lstWords.begin();
auto end_it = lstWords.end();

std::list<string>::const_iterator cit = lstWords.begin();
auto end_cit = lstWords.cbegin();

Przeglądanie elementów kontenera przy pomocy iteratora

for (auto it = lstWords.begin(); it != lstWords.end(); ++it)
    std::cout << *it << '\n';

Przeglądanie kontenera wstecz

std::list<string>::reverse_iterator rit;
for (rit = lstWords.rbegin(); rit != lstWords.rend(); ++rit)
    std::cout << *rit << '\n';

Funkcje operujące na iteratorach¶

STL posiada zbiór funkcji pomocniczych przydatnych przy implementacji algorytmów.

nagłówek <iterator>

template<typename InputIt, class Distance> void advance(InputIt &it, Distance n)¶: inkrementuje podany iterator o wartość n (przesuwa w prawo o n miejsc)

template<typename InputIt> size_t distance(InputIt first, InputIt last)¶: zwraca ilość elementów pomiędzy first a last

template<typename ForwardIt> ForwardIt next(ForwardIt it, size_t n = 1)¶: zwraca n-ty następnik iteratora it

template<typename BidirIt> BidirIt prev(BidirIt it, size_t n = 1)¶: zwraca n-ty poprzednik iteratora it

Przykład

vector<int> vec = { 1, 2, 3, 4, 5 };

auto it = vec.begin();

advance(it, 2);
cout << *it << endl; // output 3

cout << *next(it) << endl; // output 4

cout << *prev(vec.end(), 2) << endl; // output 4

cout << distance(vec.begin(), vec.end() << endl; // output 5
cout << distance(vec.end(), vec.begin() << endl; // output -5

Iteratory wstawiające¶

Iterator wstawiający (insert iterator) jest odmianą iteratora wyjściowego wstawiającą elementy do kontenera.

Iterator wstawiający nie dokonuje dereferencji wskazywanego elementu. Służy do wstawiania a nie odczytu elementów.

W przypadku iteratora wstawiającego zapis:

*iterator = obiekt;

oznacza żądanie wstawienia obiektu do pojemnika przed elementem pokazywanym iteratorem.

Przykład

// iterator wstawiający od tyłu - push_back
std::vector<int> vecData;

back_insert_iterator<vector<int> > biter(vecData);
*biter = 10;
*biter = 20;
*biter = 30;
// kontener zawiera elementy { 10, 20, 30 };

// iterator wstawiający z przodu - push_front
deque<int> deqData;

front_insert_iterator<deque<int> > fiter(deqData);
*fiter = 10;
*fiter = 20;
*fiter = 30;
// kontener zawiera elementy { 30, 20, 10 }

Szablony iteratorów wstawiających¶

Istnieją trzy szablony funkcji iteratorów wstawiających:

template<typename Container> back_insert_iterator<Container> back_inserter(Container &x)¶: tworzy iterator typu back_insert_iterator wstawiający elementy na końcu kontenera x, poprzez wywołania funkcji push_back

int data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

std::vector<int> evens;

std::copy_if(begin(data), end(data), std::back_inserter(evens), [](int x) { return x % 2 == 0; });

template<typename Container> front_insert_iterator<Container> front_inserter(Container &x)¶: tworzy iterator typu front_insert_iterator wstawiający elementy na początku kontenera x, poprzez wywołania funkcji push_front

template<typename Container> insert_iterator<Container> inserter(Container &x, Iterator pos)¶: tworzy iterator typu insert_iterator wstawiający elementy do kontenera x. Jeżeli x jest kontenerem sekwencyjnym elementy są wstawiane bezpośrednio przed element wskazywany przez iterator pos.

Iteratory strumieni wejścia - wyjścia¶

Iterator strumienia - zamiast zakresu elementów kontenera obsługuje elementy strumienia.

Iteratory strumieni pozwalają na traktowanie wejścia strumieniowego jako sekwencji elementów obsługiwanych iteratorem:

wejściowym - pozwalającym na odczyt wyłuskanej wartości i przesuwanie do następnego elementu
wyjściowym - pozwalającym na zapis wyłuskanych elementów

Do wczytywania danych ze strumienia służy std::istream_iterator

Do wypisywania danych do strumienia służy std::ostream_iterator

// iteratory strumieni we-wy
std::cout << "Podaj stringi [Enter]. Koniec wprowadzania to [Ctrl + Z] i [Enter]"
     << endl;
// wczytanie elementów typu string ze strumienia cin
std::istream_iterator<string> start(cin);
std::istream_iterator<string> end;
std::vector<std::string> words(start, end);

// wypisanie danych w cout
std::copy(words.begin(), words.end(),
        std::ostream_iterator<std::string>(std::cout, " "));