Iteratorii
Iteratorii oferă acces la elementele unui container și reprezintă o implementare a tiparului binecunoscut în programarea orientată pe obiecte numit „Iterator”. Cu ajutorul iteratorilor este foarte comod să parcurgem elementele. În C++, iteratorii oferă o interfață comună pentru diferite tipuri de containere, ceea ce permite utilizarea unei abordări unificate pentru accesul la elementele acestora.
Este important de menționat că doar containerele au iteratori. Adaptatorii de containere – tipurile std::stack, std::queue și std::priority_queue – nu dispun de iteratori.
Un iterator este descris de tipul iterator. Pentru fiecare container, tipul concret de iterator va fi diferit. De exemplu, iteratorul pentru un list<int> este de tipul list<int>::iterator, iar pentru un vector<int> este vector<int>::iterator și așa mai departe. Totuși, funcționalitatea de bază pentru accesarea elementelor este similară.
Pentru obținerea iteratorilor, containerele din C++ dispun de funcțiile begin() și end(). Funcția begin() returnează un iterator care indică spre primul element al containerului (dacă există elemente). Funcția end() returnează un iterator care indică poziția de după ultimul element – practic, finalul containerului. Dacă containerul este gol, atunci begin() și end() vor returna același iterator. Dacă begin este diferit de end, atunci containerul are cel puțin un element.
Ambele funcții returnează un iterator specific tipului containerului:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers{ 1, 2, 3, 4 };
std::vector<int>::iterator iter = numbers.begin(); // obținem iteratorul
}În acest exemplu, este creat un vector de tip vector<int> ce conține valorile {1, 2, 3, 4}. Cu ajutorul metodei begin() obținem un iterator pentru acest container. Acest iterator indică către primul element.
Operații cu iteratori:
- *iter: obține elementul indicat de iterator
- ++iter: avansează iteratorul către următorul element
- --iter: deplasează iteratorul înapoi (nu este suportat de forward_list)
- iter1 == iter2: cei doi iteratori sunt egali dacă indică același element
- iter1 != iter2: iteratorii sunt diferiți dacă indică elemente diferite
- iter + n: returnează un iterator deplasat cu n poziții înainte
- iter - n: returnează un iterator deplasat cu n poziții înapoi
- iter += n: deplasează iteratorul cu n poziții înainte
- iter -= n: deplasează iteratorul cu n poziții înapoi
- iter1 - iter2: returnează numărul de poziții dintre cei doi iteratori
- >, >=, <, <=: comparații – un iterator este „mai mare” dacă este mai aproape de sfârșitul containerului
Este de reținut că nu toți iteratorii suportă toate aceste operații.
Iteratorii pentru tipurile std::forward_list, std::unordered_set și std::unordered_map nu acceptă operațiile --, -= și -. (deoarece std::forward_list este o listă înlănțuită unidirecțional, unde fiecare element stochează un pointer doar către elementul următor)
Iteratorii pentru tipul std::list acceptă operațiile de incrementare și decrementare, dar nu sunt acceptate operațiile +=, -=, + și -. Aceleași limitări le au și iteratorii containerelor std::map și std::set.
Operațiile +=, -=, +, -, <, <=, >, >= și <=> sunt acceptate doar de iteratorii cu acces aleatoriu (iteratorii containerelor std::vector, array și deque)
Obținerea și modificarea elementului unui container
Deoarece iteratorul, în esență, reprezintă un pointer către un anumit element, prin acest pointer putem obține elementul curent indicat de iterator și îi putem modifica valoarea:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers{ 1,2,3,4 };
auto iter { numbers.begin() }; // obținem iteratorul
// obținem elementul indicat de iterator
std::cout << *iter << std::endl; // 1
// modificăm elementul
*iter = 125;
// verificăm modificarea elementului
std::cout << numbers[0] << std::endl; // 125
}După obținerea iteratorului, acesta va indica spre primul element al containerului. Astfel, expresia *iter va returna primul element al vectorului.
Adunând sau scăzând o anumită valoare, putem deplasa iteratorul înainte sau înapoi cu un anumit număr de elemente:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers{ 10, 20, 30, 40 };
auto iter { numbers.begin() }; // obținem iteratorul
// trecem un element înainte, spre al doilea element
++iter;
std::cout << *iter << std::endl; // 20
// trecem două elemente înainte, spre al patrulea element
iter += 2;
std::cout << *iter << std::endl; // 40
// mergem înapoi cu trei elemente, spre primul element
iter = iter - 3;
std::cout << *iter << std::endl; // 10
}Reamintim că nu toate operațiile sunt suportate de toți iteratorii tuturor containerelor.
Parcurgerea containerului
De exemplu, putem folosi iteratorii pentru a parcurge elementele unui vector:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers{ 10, 20, 30, 40 };
auto iter { numbers.begin() }; // obținem iteratorul
while(iter != numbers.end()) // până ajungem la final
{
std::cout << *iter << std::endl; // obținem elementele prin iterator
++iter; // ne deplasăm înainte cu un element
}
// exemplu echivalent cu bucla for
for(auto start {numbers.begin()}; start != numbers.end(); start++)
{
std::cout << *start << std::endl;
}
}Când lucrăm cu containere, trebuie avut în vedere că adăugarea sau ștergerea elementelor dintr-un container poate face ca toți iteratorii curenți pentru acel container, precum și referințele și pointerii către elementele sale, să devină invalizi. Prin urmare, după adăugarea sau eliminarea elementelor din container, în general nu ar trebui să se mai folosească iteratorii existenți pentru acel container.
Iteratori constanți
Dacă un container este declarat ca constant, atunci pentru a accesa elementele acestuia pot fi folosiți doar iteratori constanți (tipul const_iterator). Un astfel de iterator permite citirea elementelor, dar nu și modificarea acestora:
const vector<int> numbers{1, 2, 3, 4, 5};
for(auto iter {numbers.begin()}; iter != numbers.end(); ++iter)
{
std::cout << *iter << std::endl;
// acest lucru nu este permis
//*iter = (*iter) * (*iter);
}În acest caz, iteratorul iter va avea tipul std::vector<int>::const_iterator.
Pentru a obține un iterator constant se pot folosi funcțiile cbegin() și cend(). Chiar dacă containerul nu este constant, dar la parcurgerea lui se utilizează un iterator constant, atunci valorile elementelor nu pot fi modificate:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers { 1, 2, 3, 4, 5 };
for (auto iter {numbers.cbegin()}; iter != numbers.cend(); ++iter)
{
std::cout << *iter << std::endl;
// modificarea nu este permisă
//*iter = (*iter) * (*iter);
}
}Este de menționat că pentru tipurile std::set și std::map sunt disponibili doar iteratori constanți.
Iteratori inversați
Iteratorii inversați permit parcurgerea elementelor containerului în ordine inversă. Pentru obținerea unui iterator inversat se folosesc funcțiile rbegin() și rend(), iar tipul iteratorului este reverse_iterator:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers { 1, 2, 3, 4, 5 };
for (auto iter {numbers.rbegin()}; iter != numbers.rend(); ++iter)
{
std::cout << *iter << "\t";
}
std::cout << std::endl;
}În acest caz, iteratorul este de tip std::vector<int>::reverse_iterator. Ieșirea în consolă:
5 4 3 2 1Pentru a proteja valorile containerului împotriva modificării, putem folosi un iterator inversat constant, reprezentat prin tipul const_reverse_iterator și obținut cu ajutorul funcțiilor crbegin() și crend():
#include <iostream>
#include <vector>
int main()
{
std::vector<int> numbers { 1, 2, 3, 4, 5 };
for (auto iter {numbers.crbegin()}; iter != numbers.crend(); ++iter)
{
std::cout << *iter << std::endl;
// modificarea nu este permisă
//*iter = (*iter) * (*iter);
}
}Iteratori pentru tablouri
Pentru tablouri (array-uri) în C++ există suport pentru iteratori. În biblioteca standard C++ sunt definite funcțiile std::begin() (returnează iteratorul de început) și std::end() (returnează iteratorul de final):
int data[]{4, 5, 6, 7, 8};
// obținem iteratorul de început
auto iter = std::begin(data);
// obținem iteratorul de final
auto end = std::end(data);La fel ca în cazul containerelor, și tablourile pot fi parcurse folosind iteratori:
#include <iostream>
int main()
{
int data[]{4, 5, 6, 7, 8};
for(auto iter {std::begin(data)}; iter != std::end(data); iter++)
{
std::cout << *iter << std::endl;
}
}Totuși, parcurgerea unui tablou se poate realiza și în alte moduri – prin indici sau pointeri simpli. Însă iteratorii pot fi utili atunci când manipulăm containere. De exemplu, funcția insert() disponibilă în unele containere permite adăugarea unei porțiuni dintr-un alt container. Pentru a delimita această porțiune pot fi folosiți iteratorii. Astfel, putem adăuga într-un container (de exemplu, un vector) o porțiune dintr-un alt container:
#include <iostream>
#include <vector>
int main()
{
int data[]{4, 5, 6, 7, 8};
std::vector<int> numbers { 1, 2, 3, 4 };
// adăugăm la sfârșitul vectorului numbers elementele de la al doilea la penultimul din data
numbers.insert(numbers.end(), std::begin(data) + 1, std::end(data) - 1);
for (auto iter {numbers.begin()}; iter != numbers.end(); ++iter)
{
std::cout << *iter << "\t";
}
std::cout << std::endl;
}Aici linia:
numbers.insert(numbers.end(), std::begin(data) + 1, std::end(data)-1);Adaugă în vectorul numbers, începând de la poziția indicată de numbers.end() (adică la sfârșit), elementele din intervalul definit de std::begin(data) + 1 (al doilea element) și std::end(data) - 1 (penultimul element). Ieșirea în consolă:
1 2 3 4 5 6 7