Deque
Deque reprezintă o coadă dublu-extremă. Pentru a utiliza acest container, trebuie inclus fișierul antet deque.
Moduri de creare a unei cozi dublu-extreme:
std::deque<int> deque1; // coadă goală
std::deque<int> deque2(5); // deque2 conține 5 numere, fiecare element are valoarea implicită
std::deque<int> deque(5, 2); // deque3 conține 5 numere, fiecare număr este 2
std::deque<int> deque4{ 1, 2, 4, 5 }; // deque4 conține numerele 1, 2, 4, 5
std::deque<int> deque5 = { 1, 2, 3, 5 }; // deque5 conține numerele 1, 2, 3, 5
std::deque<int> deque6({ 1, 2, 3, 4, 5 }); // deque6 conține numerele 1, 2, 3, 4, 5
std::deque<int> deque7(deque4); // deque7 este o copie a cozii deque4
std::deque<int> deque8 = deque7; // deque8 este o copie a cozii deque7Obținerea elementelor din coadă
Pentru a obține elemente din coadă se pot folosi operatorul [] și o serie de funcții:
- [index]: obține elementul de la indexul respectiv
- at(index): returnează elementul de la index
- front(): returnează primul element
- back(): returnează ultimul element
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers { 1, 2, 3, 4, 5 };
int first = numbers.front(); // 1
int last = numbers.back(); // 5
int second = numbers[1]; // 2
int third = numbers.at(2); // 3
std::cout << first << second << third << last << std::endl; // 1235
}Este de menționat că, dacă accesăm un index incorect, care este în afara limitelor containerului, rezultatul va fi nedefinit:
std::deque<int> numbers { 1, 2, 3, 4, 5 };
int eighth = numbers[7];În acest caz, folosirea funcției at() este de preferat, deoarece generează o excepție out_of_range la un index incorect:
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers { 1, 2, 3, 4, 5};
try
{
int n { numbers.at(7) };
std::cout << n << std::endl;
}
catch (const std::out_of_range&)
{
std::cout << "Index incorect" << std::endl;
}
}De asemenea, elementele containerului pot fi parcurse într-un ciclu sau cu ajutorul iteratorilor:
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers { 1, 2, 3, 4, 5 };
for (int n : numbers)
std::cout << n << "\t";
std::cout << std::endl;
for (unsigned i {}; i < numbers.size(); i++)
std::cout << numbers[i] << "\t";
std::cout << std::endl;
for (auto iter = numbers.begin(); iter != numbers.end(); iter++)
std::cout << *iter << "\t";
std::cout << std::endl;
return 0;
}Dimensiunea cozii
Pentru a afla dimensiunea cozii, se folosește funcția size(). Iar funcția empty() permite verificarea dacă coada conține elemente. Aceasta returnează true dacă coada este goală:
std::deque<int> numbers { 1, 2, 3, 4, 5 };
if (numbers.empty())
{
std::cout << "Deque-ul este gol" << std::endl;
}
else
{
int n {numbers.size()};
std::cout << "Deque-ul conține " << n << " elemente" << std::endl;
}Funcția resize() permite modificarea dimensiunii cozii. Aceasta are două forme:
- resize(n): păstrează primele n elemente. Dacă deque-ul conține mai multe elemente, acestea sunt eliminate. Dacă are mai puține, se adaugă elemente cu valoarea implicită
- resize(n, value): similar cu prima formă, dar elementele adăugate vor avea valoarea value
Utilizare:
std::deque<int> numbers { 1, 2, 3, 4, 5, 6 };
numbers.resize(4); // păstrează primele patru elemente - numbers = {1, 2, 3, 4}
numbers.resize(6, 8); // numbers = {1, 2, 3, 4, 8, 8}Este important de reținut că utilizarea funcției resize poate face invalide toate iterațiile, pointerii și referințele către elementele cozii.
Modificarea elementelor cozii
Funcția assign() permite înlocuirea tuturor elementelor din coadă cu un anumit set. Are următoarele forme:
- assign(il): înlocuiește conținutul containerului cu elementele din lista de inițializare il
- assign(n, value): înlocuiește conținutul containerului cu n elemente având valoarea value
- assign(begin, end): înlocuiește conținutul containerului cu elementele din intervalul delimitat de iteratorii begin și end
Utilizarea funcției:
std::deque<int> numbers { 1, 2, 3, 4, 5 };
numbers.assign({ 21, 22, 23, 24, 25 }); // numbers = { 21, 22, 23, 24, 25 }
numbers.assign(4, 3); // numbers = {3, 3, 3, 3}
std::deque<int> values { 6, 7, 8, 9, 10, 11 };
auto start = values.begin() + 2; // iteratorul indică al treilea element
auto end = values.end(); // iteratorul indică după ultimul element
numbers.assign(start, end); // numbers = { 8, 9, 10, 11 }Funcția swap() face schimb de valori între două cozi:
std::deque<int> deque1 { 1, 2, 3, 4, 5 };
std::deque<int> deque2 { 6, 7, 8, 9 };
deque1.swap(deque2); // deque1 = { 6, 7, 8, 9 };Adăugarea de elemente
Pentru a adăuga elemente într-un deque se pot folosi mai multe funcții:
- push_back(val): adaugă valoarea val la sfârșitul cozii
- push_front(val): adaugă valoarea val la începutul cozii
- emplace_back(val): adaugă valoarea val la sfârșitul cozii
- emplace_front(val): adaugă valoarea val la începutul cozii
- emplace(pos, val): inserează valoarea val la poziția indicată de iteratorul pos. Returnează iteratorul către elementul adăugat
- insert(pos, val): inserează valoarea val la poziția pos, similar cu emplace. Returnează iteratorul către elementul adăugat
- insert(pos, n, val): inserează n elemente cu valoarea val începând de la poziția pos
- insert(pos, begin, end): inserează elementele din alt container din intervalul [begin, end) începând de la poziția pos
- insert(pos, values): inserează o listă de valori values începând de la poziția pos
Funcțiile push_back(), push_front(), emplace_back() și emplace_front():
std::deque<int> numbers { 1, 2, 3, 4, 5 };
numbers.push_back(6); // { 1, 2, 3, 4, 5, 6 }
numbers.push_front(0); // { 0, 1, 2, 3, 4, 5, 6 }
numbers.emplace_back(7); // { 0, 1, 2, 3, 4, 5, 6, 7 }
numbers.emplace_front(-1); // { -1, 0, 1, 2, 3, 4, 5, 6, 7 }Adăugare în mijlocul listei cu emplace():
std::deque<int> numbers { 1, 2, 3, 4, 5 };
auto iter = ++numbers.cbegin();
numbers.emplace(iter, 8); // { 1, 8, 2, 3, 4, 5 }Adăugare în mijlocul listei cu insert():
std::deque<int> numbers1 { 1, 2, 3, 4, 5 };
auto iter1 = numbers1.cbegin(); // iteratorul indică al doilea element
numbers1.insert(iter1 + 2, 8); // adăugăm după al doilea element
//numbers1 = { 1, 2, 8, 3, 4, 5 };
std::deque<int> numbers2 { 1, 2, 3, 4, 5 };
auto iter2 = numbers2.cbegin(); // iteratorul indică primul element
numbers2.insert(iter2, 3, 4); // adăugăm la început trei valori de 4
//numbers2 = { 4, 4, 4, 1, 2, 3, 4, 5 };
std::deque<int> values { 10, 20, 30, 40, 50 };
std::deque<int> numbers3 { 1, 2, 3, 4, 5 };
auto iter3 = numbers3.cbegin(); // iteratorul indică primul element
// adăugăm la început toate elementele din values
numbers3.insert(iter3, values.begin(), values.end());
//numbers3 = { 10, 20, 30, 40, 50, 1, 2, 3, 4, 5 };
std::deque<int> numbers4 { 1, 2, 3, 4, 5 };
auto iter4 = numbers4.cend(); // iteratorul indică poziția de după ultimul element
// adăugăm după ultimul element lista { 21, 22, 23 }
numbers4.insert(iter4, { 21, 22, 23 });
//numbers4 = { 1, 2, 3, 4, 5, 21, 22, 23 };La adăugarea în containerul deque trebuie avut în vedere că această operație poate invalida toți iteratorii, pointerii și referințele către elementele containerului.
Ștergerea elementelor din containerul deque
Pentru ștergerea elementelor din containerul deque se folosesc următoarele funcții:
- clear(): șterge toate elementele
- pop_back(): șterge ultimul element
- pop_front(): șterge primul element
- erase(p): șterge elementul indicat de iteratorul p. Returnează iteratorul către elementul următor celui șters sau end() dacă a fost șters ultimul element
- erase(begin, end): șterge elementele din intervalul delimitat de iteratorii begin și end. Returnează iteratorul către elementul de după cel șters sau end() dacă a fost șters ultimul
Exemplu de utilizare:
std::deque<int> numbers{ 1, 2, 3, 4, 5 };
numbers.pop_front(); // numbers = { 2, 3, 4, 5 }
numbers.pop_back(); // numbers = { 2, 3, 4 }
numbers.clear(); // numbers = {}
numbers = { 1, 2, 3, 4, 5 };
auto iter = numbers.cbegin(); // pointer către primul element
numbers.erase(iter); // ștergem primul element
// numbers = { 2, 4, 5, 6 }
numbers = { 1, 2, 3, 4, 5 };
auto begin = numbers.begin(); // pointer către primul element
auto end = numbers.end(); // pointer către ultimul element
numbers.erase(++begin, --end); // ștergem de la al doilea până la penultimul
//numbers = {1, 5}La ștergere, trebuie avut în vedere că eliminarea elementelor din orice poziție (cu excepția primului și ultimului) invalidează toți iteratorii, pointerii și referințele la elementele din deque.
Astfel, deque, la fel ca vector și array, permite acces aleatoriu la elemente, dar spre deosebire de vector, suportă și adăugarea de elemente la începutul containerului. În plus, în implementarea internă, când dimensiunea se modifică, deque nu alocă un nou bloc de memorie pentru a găzdui toate elementele, ci lucrează cu pointeri.
