C++/Iteratory

Wstęp

Idea iteratorów opiera się na tym, by ułatwić i usprawnić pracę na kontenerach. Daje możliwość dotarcia do danego składnika pojemnika bez konieczności znajomości jego struktury. Słusznie używanie iteratora przypomina pracę przy pomocy zwykłych wskaźników. Iterator umożliwia wygodny dostęp sekwencyjny do wszystkich elementów kontenera.

Można używać gotowych iteratorów dla kontenerów z STL przez dołączenie biblioteki <iterator>.

Istnieją pewne analogie między iteratorem a wskaźnikiem. Przede wszystkim znajomo wyglądają wyrażenia:

*nasz_iterator   // wartością jest element pojemnika wskazywany przez iterator nasz_iterator
wart = *nasz_iter   // podstawienie wartości elementu pod zmienną wart
*nasz_iterator = wart   // podstawienie wartości zmiennej w miejsce pojemnika wskazane przez nasz_iterator

Umożliwia nam to przeciążony operator*, dzięki któremu mamy dostęp do obiektu wskazywanego przez iterator jak również możliwość modyfikowania jego zawartości.

Podział iteratorów

• Iteratory wejścia:

Taki iterator może odczytać wartość elementu, na który wskazuje, o ile nie wskazuje przekroczenia zakresu – end(). Musi posiadać domyślny konstruktor, konstruktor kopiujący oraz operatory =, ==, !=, ++. Odczytać wartość można:

wart = *iterator;    // poprawne użycie iteratora wejścia
*iterator = wartosc;    // niepoprawne użycie iteratora wejścia- nie może zapisywać

Można inkrementować iterator – aby wskazywał następny składnik:

iterator++  lub  ++iterator

• Iteratory wyjścia:

Ten typ iteratora umożliwia tylko zapis wartości do danego składnika – odczyt jest niemożliwy. Musi posiadać domyślny konstruktor, konstruktor kopiujący oraz operatory =, ++. np.

*iterator = wartosc;  // poprawnie
wartosc = *iterator;  // błędnie – próbujemy odczytać

• Iteratory przejścia w przód:

Jest to połączenie operatora wejścia i wyjścia, posiada domyślny konstruktor, konstruktor kopiujący oraz operatory =, ==, != ,++. Możliwy jest zarówno zapis jak i odczyt. Przesuwanie się po kolejnych składnikach tak jak poprzednio jest możliwe tylko w przód poprzez inkrementacje iteratora.

• Iteratory dwukierunkowe:

Różnią się tylko możliwością dekrementacji iteratora od iteratorów przejścia w przód.

• Iteratory bezpośredniego dostępu:

Można powiedzieć, że ten typ z kolei dziedziczy wszystko po iteratorach dwukierunkowych, przy czym posiada możliwość dostępu bezpośrednio do wybranego składnika bez potrzeby skanowania struktury (w najgorszym wypadku całej). Z racji tego, że można przeskoczyć o większą liczbę składników niż jeden, iteratory te posiadają operatory: +, +=, -, -=, []. A także dodatkowo operatory <, >, <=, >=.

Sposób użycia iteratora bezpośredniego dostępu: (załóżmy ze nasz iterator wskazuje już składnik n-ty)

iterator += 5;   // teraz wskazuje (n+5)-ąty składnik
iterator++;   // teraz wskazuje (n+6)-ty składnik 
*iterator[n] = wartosc;   // przypisujemy n-temu składnikowi wartosc

Użycie w poszczególnych kontenerach (z przykładami)

Przedstawimy teraz metody poszczególnych kontenerów, które umożliwiają operowanie na iteratorach. Należy podkreślić, że nazwy niektórych metod powtarzają się w różnych pojemnikach a także pełnią te same funkcje, dlatego nie będziemy ich za każdym razem dokładnie opisywać - podobnie jak przeładowanych operatorów.

Poruszanie się za pomocą iteratorów

Poruszanie się za pomocą iteratorów po kolejnych składowych może odbywać się na dwa sposoby:
1) w przód - czyli od początku do końca np.:

kontener<typ kontenera>::iterator iter;   // iterator do przodu

początek struktury wyznacza metoda begin(); zaś koniec end();

2) od końca - czyli od końca do początku np.:

kontener<typ kontenera>::reverse_iterator iter;   // iterator od końca

skanować możemy od rbegin(); do rend();, co można utożsamiać z odwróconym początkiem i odwróconym końcem.

Użycie zostanie zobrazowane na przykładzie kontenera vector.

Wektor

Przed użyciem iteratora należy najpierw nadać mu wartość. Dlatego gdy chcemy powtarzać pewną operacje w pętli dla każdego elementu wektora – od początku do końca – inicjujemy iterator wartością bezparametrowej funkcji begin(). Metoda ta zwraca iterator wskazujący na pierwszy element pojemnika wektor. Jest to iterator bezpośredniego dostępu. Nie mamy jednak możliwości porównywania iteratora z wartością NULL (bo iterator zwykłym wskaźnikiem nie jest) musi istnieć metoda która pokazuje koniec naszego wektora. Tak też jest – metoda end() zwraca iterator za ostatnim elementem. To także jest iterator bezpośredniego dostępu.

Przykład:

#include <iostream>
#include <vector>
using namespace std;
int main ()
{
   vector<int> tab;

   // inicjujemy wektor kolejnymi liczbami naturalnymi
   tab.push_back(1);
   tab.push_back(2);
   tab.push_back(3);
  
   // wyswietlenie skladnikow wektora tab w petli przy pomocy iteratora
   vector<int>::iterator it;
   for( it=tab.begin(); it!=tab.end(); ++it )
   {
     cout<< *it <<'\n';
   }
   return 0;
}

Program spowoduje wyświetlenie kolejnych elementów pojemnika:

1
2 
3

Metody begin() i end() skonstruowane są do przeglądania wektora od początku do końca. Co jeśli chcemy działać na składowych wektora w odwrotnej kolejności? Nie ma problemu. Istnieje bowiem metoda rbegin(), która zwraca odwrócony iterator wskazujący na ostatni element pojemnika (mówi się także, że jest to odwrócony początek). Odwołuje się on do elementu bezpośrednio poprzedzającego iterator wskazywany przez end. Jest to odwrócony iterator bezpośredniego dostępu. Mamy także metodę rend(), która zwraca odwrócony iterator do elementu odwołującego się do elementu bezpośrednio poprzedzającego pierwszy element kontenera wector (zwany także odwróconym końcem). rend() wskazuje miejsce bezpośrednio poprzedzające składnik do którego odwoływałby się begin(). Oto przykład:

#include <iostream>
#include <vector>
using namespace std;
int main ()
{
   vector<int> tab;
   // inicjujemy wektor kolejnymi liczbami naturalnymi
   tab.push_back(1);
   tab.push_back(2);
   tab.push_back(3);
  
   // wyświetlenie skladników wektora tab w pętli przy pomocy odwróconego iteratora
   vector<int>::reverse_iterator it;
   for( it=tab.rbegin(); it!=tab.rend(); ++it )
   {
      cout<<*it<<'\n';
   }
   return 0;
}

Wykonanie programu spowoduje wyświetlenie składników kontenera w odwrotnej kolejności:

3
2
1

Należy jeszcze podkreślić, że przy użyciu odwróconego iteratora, by przejrzeć wszystkie elementy pojemnika nie używamy -– a ++! Rzeczywiście, chcemy przejrzeć wektor od końca do początku i właśnie ku temu służy odwrócony iterator – zdefiniowany w nim porządek strukturalny jest odwrotny do porządku w zwykłym iteratorze.

Powyższe przykłady pokazują jak dużym ułatwieniem dla korzystania z iteratorów są przeładowane operatory inkrementacji i dekrementacji: operator++ i operator--, których używamy tu jak na zwykłej liczbie int. Mamy tu także operator= podstawienia, jak i porównanie iteratorów - operator!=.

Listy jedno- i dwukierunkowe

Na liście dwukierunkowej działamy bardzo podobnie jak na wektorze. Tu także dysponujemy metodami begin() i end() zwracającymi wartość iteratora odpowiednio: na początek listy i tuż za koniec. Jest to iterator dwukierunkowy i możemy na nim działać zarówno do przodu (dzięki ++) jak i do tyłu (przez --). Mamy także analogiczne rbegin() i rend() zwracające odwrócony iterator do listy.

Przykład:

#include <iostream>
#include <list>
using namespace std;
 
int main ()
{
   // tworzymy i inicjujemy nowa listę znaków
   list<char> lista;
   lista.push_back('a');
   lista.push_back('b');
   lista.push_back('c');

   // i wyświetlamy ja w pętli do przodu
   list<char>::iterator it;
   cout<<"lista po kolei: ";
   for( it=lista.begin(); it!=lista.end(); ++it )
   {
      cout<<*it<<" ";  
   }

   // oraz do tylu (ale czy poprawnie?)
   cout<<"\nLista od tylu: ";
   for( it=lista.end(); it!=lista.begin(); --it )
   {
      cout<<*it<<" ";  
   }

   // znow wyświetlamy listę - teraz przy pomocy odwróconego iteratora
   list<char>::reverse_iterator it2;
   cout<<"\nLista od tylu z odwróconym iteratorem: ";
   for( it2=lista.rbegin(); it2!=lista.rend(); it2++ )
   {
      cout<<*it2<<" ";  
   }
   cout<<'\n'; 
   return 0;
}

Wynikiem działania programu będzie:

lista po kolei: a b c
lista od tylu: � c b
lista od tylu z odwróconym iteratorem: c b a

Przykład ten pokazuje nam dlaczego do przeglądania kontenera od końca należy używać iteratora odwróconego. Wyświetlenie elementu równego lista.end() przyniosło niespodziewany skutek - losowy symbol spoza naszej listy.

W liście jednokierunkowej nie mamy już tak szerokiego zakresu działania na iteratorach. Funkcje begin() i end() zwracają wartości iteratora (jednokierunkowego) „do przodu”, zaś odwrotny iterator wcale nie istnieje.

Zbiory

Iterator w zbiorach działa jak w innych kontenerach. Iterator działający na zbiorze jest dwukierunkowy – możemy więc korzystać ze wszystkich operatorów przeciążonych dla iteratora dwukierunkowego. Dodatkowo (jak z własności zbioru wynika) należy wspomnieć, że metoda begin() daje dostęp iteratorowi do pierwszego elementu zbioru, który równocześnie posiada najniższy klucz. W zbiorach możemy także korzystać z odwróconych iteratorów.

#include<iostream>
#include<set>
using namespace std;
int main()
{
   set<int> zbior;
   zbior.insert(5);
   zbior.insert(40);
   zbior.insert(1);
   zbior.insert(11);

   set<int>::iterator it;   // teraz it jest wskaznikiem do zbioru
   for( it=zbior.begin(); it!=zbior.end(); ++it )
      cout<<*it<<'\n';

   return 0;
}

Wynikiem pracy programu będzie wypisanie cyfr:

1
5
11
40