Iterator

Iterator jest uogólnioną reprezentacja procesu poruszania się po kontenerze, niezależną od typu danych przechowywanych w kontenerze, ale także od struktury danych samego kontenera.

1. Możliwość wyłuskania iteratora w celu uzyskania dostępu do wartości, na którą wskazuje. Jeśli p jest iteratorem, to jest zdefiniowane wyrażenie *p.
2. Możliwość przypisania jednego iteratora do drugiego. Jeśli p i q są iteratorami, to zdefiniowane jest p = q.
3. Możliwość porównania jednego iteratora z drugim. Jeśli p i q są iteratorami, zdefiniowane są wyrażenia p == q oraz p != q.
4. Za pomocą iteratora można odwiedzić wszystkie elementy kontenera. Dla iteratora p zdefiniowane są instrukcje p++ oraz ++p.

/* klasa wezla kontenera */
template <class Type>
struct Node
{
	Type item_;
	Node* next_;
};
 
template <class Type>
class iterator
{
private:
	Node<Type>* ptr_;
 
public:
	iterator(): ptr_(0) {}
	iterator( Node<Type>* n ): ptr_(n) {}
 
	/* operator wyluskania wartosci, na ktora wskazuje iterator */
	Type operator* () { return ptr_->item_; }
 
	/* preinkrementacja - ++iter */
	/* odwiedza nastepny element w kontenerze */
	iterator& operator++()
	{
		ptr_ = ptr_->next_;
 
		return *this;
	}
 
	/* postinkrementacja - iter++ */
	iterator& operator++(int)
	{
		iterator tmp = *this;
		ptr_ = ptr_->next_;
 
		return tmp;
	}
 
	/* operator porownania == */
	/* zwraca true jesli iteratory wskazuja na ten sam element */
	bool operator== ( const iterator& i )
	{
		if ( ptr_ == i.ptr_ )
			return true;
 
		return false;
	}
 
	/* operator nierownosci != */
	bool operator!= ( const iterator& i )
	{
		return !( *this == i );
	}
 
	/* operator przypisania = */
	iterator& operator= ( const iterator& i )
	{
		ptr_ = i.ptr_;
 
		return *this;
	}
};

Istnieje kilka typów iteratorów, w zależności od udostępnianych operacji:

• wyłuskiwanie do odczytu
• operacje ++i oraz i++

• wyłuskiwanie do zapisu
• operacje ++i oraz i++

• operacje iteratorów wejściowego oraz wyjściowego

• operacje iteratoraiteratorao
• operacje -—i oraz i-— umożliwiające poruszanie się po kontenerze w dwóch kierunkach

• operacje iteratora dwukierunkowego
• operacja i + n, czyli wskazanie na n-ty element po elemencie, na który wskazuje i
• operacja n + i (to samo co i + n)
• operacja i - n, czyli wskazanie na n-ty element przed elementem, na który wskazuje i
• i += n (to samo co i = i + n) oraz i -= n ( i = i - n )
• operator i[], czyli *(i + n)
• i - j, czyli wartość takiego n, ze i = j + n
• i < j, które jest prawdziwe gdy j - i > 0
• i > j, które jest prawdziwe gdy j < i
• i >= j (analogicznie i ⇐ j), które jest prawdziwe gdy !(i < j)

Każdy typ jest też typem niższego poziomu.

Rożne funkcje operujące na kontenerach wymagają iteratora spełniającego pewne właściwości, np. prototyp funkcji sort ma postać:

template <class RandomAccessIterator>
 void sort ( RandomAccessIterator first, RandomAccessIterator last );

czyli podawane argumenty muszą udostępniać operacje i + n, i - n itp.

W bibliotece STL każda klasa kontenerowa posiada definicję odpowiedniego iteratora klasy. Dla jednej może być to wskaźnik (który również może być iteratorem, jako że posiada wszystkie wymagane właściwości), dla innej może być to obiekt. Ponadto klasy te posiadają metody begin() oraz end(), które zwracają iteratory na pierwszy element kontenera oraz na pozycje za ostatnim elementem.

• T* (wskaznik)
• vector<T>::iterator
• vector<T>::const_iterator
• deque<T>::iterator
• deque<T>::const_iterator

• list<T>::iterator

• hash_set<T>::iterator

/* Przyklad - korzystanie z iteratorow */
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
 
int main () {
 
	using namespace std;
 
	vector<int> v;
	v.push_back ( 3 );
	v.push_back ( 2 );
	v.push_back ( 7 );
	v.push_back ( 5 );
 
	list<int> l;
	l.push_back ( 3 );
	l.push_back ( 2 );
	l.push_back ( 7 );
	l.push_back ( 5 );
 
	/* przegladanie kontenera vector za pomoca iteratora */
	vector<int>::iterator vi;
 
	cout << "vector: ";
	for ( vi = v.begin(); vi != v.end(); ++vi ){
		cout << *vi;
	}
	cout << endl;
 
	/* przegladanie kontenera list za pomoca iteratora */
	/* identycznie jak w przypadku przegladania vectora, choc implementacja kontenerow jest inna */
	list<int>::iterator li;
 
	cout << "list: ";
	for ( li = l.begin(); li != l.end(); ++li ){
		cout << *li;
	}
	cout << endl;
 
	/* iterator klasy vector jest typu RandomAccessIterator, mozna wiec uzyc ich do funkcji sort */
	sort ( v.begin(), v.end() );
 
	cout << "sorted vector: ";
	for ( vi = v.begin(); vi != v.end(); ++vi ){
		cout << *vi;
	}
	cout << endl;
 
	/* iterator klasy list jest typu dwukierunkowego, a wiec instrukcja: */
	// sort ( l.begin(), l.end() ); 
	/* wywola blad kompilacji z komunikatem, ze list<T>::iteator nie udostepnia operacji - */
 
	return 0;
}