C++/Iteratory

Z Wikibooks, biblioteki wolnych podręczników.

< C++

Spis treści

[edytuj] 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. Jest on jednak czymś więcej niż wskaźnik - w przeciwieństwie do wskaźników, korzystając z iteratora nie musimy martwić się czy przypadkiem nie przekroczyliśmy zakresu pojemnika ani czy poprawnie wskazuje nam on na element. Tym wszystkim zajmuje się sam iterator, co pozwala programiście skupić się na innych problemach w trakcie tworzenia programu.

Czym więc jest iterator? Jest on pewnego rodzaju uogólnionym wskaźnikiem. Strukturalnie iterator jest obiektem, który wskazuje na inny obiekt. Można używać gotowych iteratorów dla kontenerów z STL przez dołaczenie biblioteki <iterator> i w przestrzeni nazw std.

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* , jak i operator= dzięki któremu możemy pod iterator podstwiać inne wartości.


[edytuj] 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 // inkrementacja jest niemożliwa po przekroczeniu końca


  • 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

[edytuj] 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.

Niestety używanie metod rbegin(); i rend(); do skanowania w przód spowoduje błąd kompilacji. Problem ukazuje poniższy fragment kodu:

vector<string> tablica;
tablica.push_back("wlazł kotek ");
tablica.push_back("na płotek ");
vector<string>::reverse_iterator iter; // iterator od końca
for(iter=tablica.rend(); iter<tablica.rbegin(); iter++) //  proba skanowania w przód - zle
  {cout<<*iter<<endl;}


[edytuj] Wektor

Aby użyć 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 i;
  for(i=tab.begin(); i<tab.end(); ++i)
  {
    cout<<*i<<endl;
  }
  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 metode 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 i;
  for(i=tab.rbegin(); i<tab.rend(); ++i)
  {
    cout<<*i<<endl;
  }
  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 dekremntacji: 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<.

[edytuj] 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 liste znakow
  list<char> lista;
  lista.push_back('a');
  lista.push_back('b');
  lista.push_back('c');   
  //i wyswietlamy ja w petli do przodu
  list<char>::iterator i;
  cout<<"lista po kolei: ";
  for( i=lista.begin(); i!=lista.end(); ++i )
  {
    cout<<*i<<" ";  
  }
  //i do tylu
  cout<<endl<<"lista od tylu: ";
  for( i = lista.end(); i!=lista.begin(); --i )
  {
    cout<<*i<<" ";  
  }
  //znow wyswietlamy liste - teraz przy pomocy odworconego iteratora
  list<char>::reverse_iterator i2;
  cout<<endl<<"lista od tylu z odwroconym iteratorem: ";
  for( i2=lista.rbegin(); i2 != lista.rend(); i2++ )
  {
    cout<<*i2<<" ";  
  }
  cout<<endl; 
  return 0;
}

Wynikiem działania programu będzie:

lista po kolei: a b c
lista od tylu: � c b
lista od tylu z odwroconym iteratorem: c b a

Przykład ten pokazuje nam dlaczego do przeglądania kontenera od końca należy używać iteratora odwróconego.

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.


[edytuj] 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()
{
  int o;
  set<int> zbior;
  zbior.insert(5);
  zbior.insert(40);
  zbior.insert(1);
  zbior.insert(11);
  set<int>::iterator i; // teraz i jest wskaznikiem do zbioru
  for(i=zbior.begin();i!=zbior.end();++i)
   cout<<*i<<endl;
 return 0;
}

Wynikiem pracy programu będzie wypisanie cyfr:

1
5
11
40
Spis treści
Źródło „http://pl.wikibooks.org/wiki/C%2B%2B/Iteratory”