Iteratori

Algoritmii generici actioneaza asupra containerelor prin intermediul iteratorilor. Astfel algoritmul copy() utilizeaza, pentru a copia o portiune din containerul cs în containerul cd, trei iteratori: un iterator pe primul element copiat din containerul sursa, un iterator dupa ultimul element copiat din containerul sursa si un iterator la prima pozitie din containerul destinatie:

copy(cs.begin(),cs.end(),cd.begin());

Iteratorii pot fi împartiti în categorii de iteratori, în functie de operatiile care se pot efectua asupra lor. (iteratori de intrare, iteratori de iesire, iteratori de avans, iteratori bidirectionali si iteratori cu acces direct). Aceste clase formeaza o ierarhie având la baza o clasa de iteratori cu posibilitati foarte limitate (iteratorii de intrare si de iesire), iar clasele derivate au posibilitati mai mari.

struct input_iterator_tag{};

struct output_iterator_tag{};

struct forward_iterator_tag : public input_iterator_tag{};

struct bidirectional_iterator_tag : public forward_iterator_tag{};

struct random_access_iterator_tag : public bidirectional_iterator_tag{};

Asa cum avem pointeri la obiecte const, putem defini iteratori la elemente const:

vector::const_iterator it;

Exista trei tipuri de adaptori ai iteratorilor: iteratori inversi (reverse iterators), iteratori de insertie (insert iterators) si iteratori pe memorie (raw storage iterators).

Iteratorii inversi inverseaza comportarea operatorilor ++ si --. Toate containerele standard asigura functiile rbegin() si rend(), asigurând pozitionarea pe ultimul element, respectiv înaintea primului element din container.

Iteratorii pe memorie realizeaza în mod eficient copierea unui container într-o zona de memorie neinitializata, folosind functiile get_temporary_buffer() si return_temporary_buffer() .

Toti iteratorii (exceptând iteratorii de iesire) asigura o functie distanta între doi iteratori, având un tip asociat difference_type.

Un iterator este minimal caracterizat prin tipul valorii elementelor containerului si tipul functiei distanta specifice containerului asociat.

Fiecarui tip de iterator i se asociaza o clasa de proprietati (sau trasaturi) iterator_traits, care contine: o serie de nume de tipuri recunoscute de iterator precum: tipul elementelor containerului (value_type), tipul distantei (difference_type), tipul dimensiunii containerului (size_type), tipul referinta (reference) si pointer (pointer) asociate elementelor containerului, categoria iteratorului (iterator_category): Clasele de proprietati servesc deci pentru exportul unor nume de tipuri din clasa iterator.

Clasa de proprietati trebuie specificata pentru fiecare tip iterator nou definit.

template <class Itor>

struct iterator_traits{

typedef typename Itor::value_type value_type;

typedef typename Itor::difference_type difference_type;

typedef typename Itor::pointer pointer;

typedef typename Itor::reference reference;

typedef typename Itor::iterator_category iterator_category;

};

În cazul în care iteratorul este un simplu pointer (pentru vectori si tablouri predefinite C), distanta între iteratori se calculeaza printr-o simpla scadere si are tipul predefinit ptrdiff_t, avem particularizarea (specializarea) clasei de proprietati:

template <class T>

struct iterator_traits<T*>{

typedef T value_type;

typedef ptrdiff_t difference_type;

typedef T* pointer;

typedef T& reference;

tzpedef size_t size_type;

typedef random_access_iterator_tag iterator_category;

};

Numele tipurilor care apar în clasa de proprietati pot fi date ca parametrii ai sablonului. În acest caz, clasa de proprietati precedenta va avea forma:

template <class Categ, class T, class Dist=ptrdiff_t,class Ptr=T*,class Ref=T& >

struct iterator_traits{

typedef T value_type;

typedef Dist difference_type;

typedef Ptr pointer;

typedef Ref reference;

typedef Categ iterator_category;

};

Vom exemplifica definirea functiei distanta între doi iteratori. În caz ca iteratorii sunt de intrare, distanta este numarul de deplasari necesar ajungerii în pozitia indicata de cel de-al doilea iterator:

template <class InItor>

typename iterator_traits<InItor>::difference_type dist(InItor i1, InItor i2,

input_iterator_tag){

typename iterator_traits<InItor>::difference_type d=0;

while(i1++ != i2)

d++;

return d;

}

În cazul iteratorilor cu acces direct, distanta se calculeaza prin simpla diferenta a iteratorilor:

template <class RAItor>

typename iterator_traits<RAItor>::difference_type dist(RAItor i1, RAItor i2,

random_acces_iterator_tag){

return i2-i1;

}

Se observa ca cel de-al treilea paramatru a fost bdat numai pentru a deosebi semnaturile celor doua functii. Cele doua functii pot fi comasate într-una singura:

template <class Itor>

typename iterator_traits<Itor>::difference_type dist(Itor i1, Itor i2){

return dist(i1, i2, iterator_traits<Itor>::iterator_category());

};

Toate containerele standard STL definesc tipurile: iterator si const_iterator si metodele begin()/end() pentru container.

Clasele container definite de utilizator pot utiliza algoritmi generici numai daca le asociem clase iteratori corespunzatoare.

Daca o clasa container definita de utilizator foloseste un container standard, atunci trebuie sa delegam containerului utilizator tipurile si metodele clasei iterator asociate containerului standard. De exemplu:

//delegarea iteratorilor clasei vector catre clasa grupa

class grupa{

typedef vector<char*> gr_stud;

gr_stud g;

public:

typedef gr_stud::iterator iterator;//preluam iterator din vector

typedef gr_stud::const_iterator const_iterator;

iterator begin(){return g.begin();};

iterator end(){return g.end();};

// alte metode

}