Iteratori

Un iterator este un obiect care “pointează” către un element dintr-o structură de date STL. Gândește-te la el ca la un cursor care se poate deplasa de la un element la altul.

Iteratorii sunt limba comună a STL-ului: toate structurile de date (vector, set, map, deque) și toate algoritmii (sort, find, lower_bound) comunică prin iteratori.

De ce avem nevoie de iteratori?

La un vector clasic, accesăm elementele prin indice: v[0], v[1], v[2].

Dar un set nu are indici. Un map nu are indici. Cum parcurgem aceste structuri?

Răspunsul: prin iteratori - un mecanism universal care funcționează pe orice structură de date.

Primul exemplu

#include <vector>
using namespace std;

int main()
{
    vector<int> v = {3, 7, 2, 9, 4};

    vector<int>::iterator it = v.begin();  // iterator la primul element

    cout << *it;     // 3 (valoarea la care pointează)
    it++;            // avansează la următorul
    cout << *it;     // 7
    it++;
    cout << *it;     // 2

    return 0;
}

Ce se întâmplă?

• v.begin() returnează un iterator care pointează la primul element
• *it - dereferențiere - ne dă valoarea (ca la pointeri)
• it++ - avansează la elementul următor

begin() și end()

Fiecare structură STL are:

• begin() - iterator la primul element
• end() - iterator după ultimul element (nu la ultimul, ci după el)

v = {3, 7, 2, 9, 4}

begin()                              end()
  ↓                                    ↓
 [3]  [7]  [2]  [9]  [4]             (nimic)

end() nu pointează la niciun element valid - e doar un marker care spune “am terminat”.

Parcurgerea cu iteratori

for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    cout << *it << " ";
// Output: 3 7 2 9 4

Condiția e it != v.end() - parcurgem cât timp nu am ajuns la final.

auto - simplificare

Tipul complet (vector<int>::iterator) e lung de scris. Cu auto, compilatorul îl deduce singur:

for (auto it = v.begin(); it != v.end(); it++)
    cout << *it << " ";

Mult mai scurt. auto funcționează cu orice structură STL.

Legătura cu range-based for

for (int x : v)
    cout << x << " ";

Aceasta e de fapt o prescurtare pentru:

for (auto it = v.begin(); it != v.end(); it++) {
    int x = *it;
    cout << x << " ";
}

Compilatorul generează exact acest cod în spate.

Iteratori pe diferite structuri

Pe vector

vector<int> v = {3, 7, 2};
auto it = v.begin();
cout << *it;       // 3
cout << *(it + 2); // 2  (acces direct la al 3-lea element)

Vectorul are random access iterators - putem sări direct la orice poziție cu it + k.

Pe set

set<int> s = {5, 3, 8, 1};
auto it = s.begin();
cout << *it;   // 1  (cel mai mic - set e sortat)
it++;
cout << *it;   // 3
it++;
cout << *it;   // 5

Set-ul are bidirectional iterators - putem merge înainte (it++) și înapoi (it--), dar nu putem sări (it + 5 nu funcționează).

Pe map

map<string, int> m;
m["Ana"] = 15;
m["Bob"] = 16;

auto it = m.begin();
cout << it->first << " " << it->second;  // Ana 15
it++;
cout << it->first << " " << it->second;  // Bob 16

La map, iteratorul pointează la un pair. Accesăm cu it->first (cheia) și it->second (valoarea). E echivalent cu (*it).first.

Operații pe iteratori

Iteratori și algoritmi STL

Algoritmii din <algorithm> lucrează cu iteratori, nu cu indici. De aceea primesc begin() și end():

vector<int> v = {3, 7, 2, 9, 4};

sort(v.begin(), v.end());                        // sortare
reverse(v.begin(), v.end());                     // inversare
auto it = find(v.begin(), v.end(), 7);           // căutare
auto it2 = lower_bound(v.begin(), v.end(), 5);   // primul >= 5
int cnt = count(v.begin(), v.end(), 3);           // numărare

Toți primesc doi iteratori: unde începe și unde se termină intervalul.

Sortare parțială

Putem sorta doar o porțiune:

sort(v.begin() + 2, v.begin() + 5);  // sortează doar v[2], v[3], v[4]

Calculul indexului dintr-un iterator

vector<int> v = {3, 7, 2, 9, 4};
auto it = find(v.begin(), v.end(), 9);

int index = it - v.begin();  // 3
cout << "9 se afla pe pozitia " << index;

it - v.begin() = distanța de la început = indexul.

Pe set și map, it - s.begin() nu funcționează (nu sunt random access). Folosim distance:

set<int> s = {1, 3, 5, 8};
auto it = s.find(5);
int poz = distance(s.begin(), it);  // 2 (al treilea element, indexat de la 0)

distance e O(n) pe set/map, O(1) pe vector.

Iteratori reverși

Parcurgere de la final la început:

for (auto it = v.rbegin(); it != v.rend(); it++)
    cout << *it << " ";
// Output: 4 9 2 7 3 (invers)

rbegin() = ultimul element, rend() = înainte de primul.

Modificarea elementelor prin iterator

for (auto it = v.begin(); it != v.end(); it++)
    *it = *it * 2;  // dublează fiecare element

Ștergerea prin iterator

auto it = v.begin() + 2;  // al treilea element
v.erase(it);               // îl șterge

Pe set:

auto it = s.find(5);
if (it != s.end())
    s.erase(it);

Exemplu complet: intersecția a două mulțimi

#include <fstream>
#include <set>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n, m;
    set<int> a, b;

    fin >> n;
    for (int i = 0; i < n; i++) { int x; fin >> x; a.insert(x); }

    fin >> m;
    for (int i = 0; i < m; i++) { int x; fin >> x; b.insert(x); }

    // Intersecția: elementele comune
    for (auto it = a.begin(); it != a.end(); it++)
        if (b.count(*it))
            fout << *it << " ";

    return 0;
}

Greșeli frecvente

1. Dereferențierea lui end()

auto it = v.end();
cout << *it;  // EROARE! end() nu pointează la un element valid

end() e doar un marker. Mereu verifică it != v.end() înainte de *it.

2. it + k pe set/map

set<int> s = {1, 3, 5};
auto it = s.begin() + 2;  // EROARE! Set nu suportă + pe iteratori

Pe set, doar it++ și it--. Pentru a avansa k poziții, folosește advance(it, k).

3. Iterator invalidat după modificare

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); it++)
    if (*it == 3)
        v.erase(it);  // iteratorul devine INVALID după erase!

Soluție: it = v.erase(it) - erase returnează iteratorul la elementul următor.

for (auto it = v.begin(); it != v.end(); )
    if (*it == 3)
        it = v.erase(it);
    else
        it++;

4. Confuzia *it vs it

• it = iteratorul (poziția)
• *it = valoarea la acea poziție

cout << it;   // afișează adresa (nu ce vrem)
cout << *it;  // afișează valoarea (ce vrem)

Ce să reții

• Un iterator e un cursor care pointează la un element dintr-o structură STL.
• begin() = primul element, end() = după ultimul.
• *it = valoarea, it++ = avansare, it->member = acces membru.
• auto simplifică declararea: auto it = v.begin().
• Algoritmii STL (sort, find, lower_bound) lucrează cu iteratori.
• Pe vector: it + k, it - it2 funcționează (random access).
• Pe set/map: doar it++ și it-- (bidirectional).
• Nu dereferenția end() și nu folosi iteratori invalidați.