Forward_list

Containerul forward_list reprezintă o listă simplu înlănțuită, adică o listă în care fiecare element conține un pointer către elementul următor. Pentru a folosi acest tip de listă, este necesară includerea fișierului header forward_list.

Crearea unei liste simplu înlănțuite:

std::forward_list<int> list1;                     // listă goală
std::forward_list<int> list2(5);                  // list2 are 5 elemente, fiecare cu valoarea implicită
std::forward_list<int> list3(5, 2);               // list3 este formată din 5 numere, fiecare având valoarea 2
std::forward_list<int> list4{ 1, 2, 4, 5 };       // list4 este formată din numerele 1, 2, 4, 5
std::forward_list<int> list5 = { 1, 2, 3, 4, 5 }; // list5 este formată din numerele 1, 2, 3, 4, 5
std::forward_list<int> list6(list4);              // list6 este o copie a listei list4
std::forward_list<int> list7 = list4;             // list7 este o copie a listei list4
std::forward_list<int> list8({ 1, 2, 3, 4, 5, 6 }); // list8 este formată din numerele 1, 2, 3, 4, 5, 6

Obținerea elementelor

Direct din lista forward_list poate fi obținut doar primul element. Pentru aceasta se folosește funcția front(). Pentru parcurgerea elementelor se poate folosi și un ciclu:

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> numbers { 1, 2, 3, 4, 5 };

    int first {numbers.front()};
    std::cout << "First: " << first << std::endl;

    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

De asemenea, pentru parcurgerea și obținerea elementelor se pot folosi iteratori:

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> numbers{ 1, 2, 3, 4, 5 };

    auto current = numbers.begin(); // iterator la începutul listei
    auto end = numbers.end();       // iterator la sfârșitul listei
    while (current != end)
    {
        std::cout << *current << "\t";
        current++;
    }
    std::cout << std::endl;
}

Clasa forward_list adaugă funcții suplimentare pentru obținerea de iteratori: before_begin() și cbefore_begin(). Ambele funcții returnează un iterator (a doua returnează un iterator constant const_iterator) către un element inexistent aflat chiar înaintea începutului listei. Nu se poate accesa valoarea prin acest iterator.

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> numbers{ 1, 2, 3, 4, 5 };

    auto prev = numbers.before_begin();
    auto end = numbers.end();
    while (++prev != end)
    {
        std::cout << *prev << "\t";
    }
    std::cout << std::endl;
}

Dimensiunea listei

Implicit, clasa forward_list nu definește funcții pentru obținerea dimensiunii containerului. Există doar funcția max_size(), care returnează dimensiunea maximă posibilă.

Funcția empty() permite verificarea dacă lista este goală. Dacă este goală, funcția returnează true, altfel false:

std::forward_list<int> numbers{ 1, 2, 3, 4, 5 };
if (numbers.empty())
    std::cout << "The forward_list is empty" << std::endl;
else
    std::cout << "The forward_list is not empty" << std::endl;

Pentru modificarea dimensiunii containerului se poate folosi funcția resize(), care are două forme:

resize(n): păstrează în listă primele n elemente. Dacă lista are mai multe elemente, acestea sunt eliminate. Dacă lista are mai puține, se adaugă elemente cu valoarea implicită
resize(n, value): același comportament, dar elementele adăugate vor avea valoarea value

std::forward_list<int> numbers{ 1, 2, 3, 4, 5, 6 };
numbers.resize(4);  // păstrăm primele patru elemente - numbers = {1, 2, 3, 4}

numbers.resize(6, 8);    // numbers = {1, 2, 3, 4, 8, 8}

Modificarea elementelor listei

Funcția assign() permite înlocuirea tuturor elementelor listei cu un anumit set. Are următoarele forme:

assign(il): înlocuiește conținutul cu elementele din lista de inițializare il
assign(n, value): înlocuiește conținutul cu n elemente, fiecare cu valoarea value
assign(begin, end): înlocuiește conținutul cu elementele din intervalul determinat de iteratorii begin și end

Aplicarea funcției:

std::forward_list<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::list<int> values{ 6, 7, 8, 9, 10, 11 };
auto start = ++values.begin();  // iteratorul indică al doilea element din values
auto end = values.end();
numbers.assign(start, end); // numbers = { 7, 8, 9, 10, 11 }

Funcția swap() schimbă valorile a două liste:

std::forward_list<int> list1{ 1, 2, 3, 4, 5 };
std::forward_list<int> list2{ 6, 7, 8, 9 };
list1.swap(list2);
// list1 = { 6, 7, 8, 9 };
// list2 = { 1, 2, 3, 4, 5 };

Adăugarea elementelor

Pentru a adăuga elemente într-un forward_list se folosesc următoarele funcții:

push_front(val): adaugă obiectul val la începutul listei
emplace_front(val): adaugă obiectul val la începutul listei
emplace_after(p, val): inserează obiectul val după elementul indicat de iteratorul p. Returnează iteratorul către elementul inserat. Dacă p indică poziția de după sfârșitul listei, rezultatul este nedefinit
insert_after(p, val): inserează obiectul val după elementul indicat de iteratorul p. Returnează iteratorul către elementul inserat
insert_after(p, n, val): inserează n obiecte val după elementul indicat de iteratorul p. Returnează iteratorul către ultimul element inserat
insert_after(p, begin, end): inserează după elementul indicat de iteratorul p un set de obiecte dintr-un alt container, al cărui început și sfârșit sunt definite de iteratorii begin și end. Returnează iteratorul către ultimul element inserat
insert_after(p, il): inserează după elementul indicat de iteratorul p o listă de inițializare il. Returnează iteratorul către ultimul element inserat

Aplicarea funcțiilor:

#include <iostream>
#include <list>
#include <forward_list>

int main()
{
    std::forward_list<int> numbers{ 7, 8 };
    numbers.push_front(6);  // adăugăm la început numărul 6
    // numbers = { 6, 7, 8 }

    numbers.emplace_front(-3);  // adăugăm la început numărul -3
    // numbers = { -3, 6, 7, 8 }

    auto iter = numbers.begin();
    iter = numbers.emplace_after(iter, -2); // adăugăm după iterator numărul -2
    // numbers = { -3, -2, 6, 7, 8 }

    iter = numbers.insert_after(iter, -1);
    // numbers = { -3, -2, -1, 6, 7, 8 }

    iter = numbers.insert_after(iter, 3, 0); // adăugăm trei zerouri
    // numbers = { -3, -2, -1, 0, 0, 0, 6, 7, 8 }

    std::list<int> values{ 1, 2, 3 };
    iter = numbers.insert_after(iter, values.begin(), values.end()); // adăugăm toate elementele din values
    // numbers = { -3, -2, -1, 0, 0, 0, 1, 2, 3, 6, 7, 8 }

    numbers.insert_after(iter, { 4, 5 }); // adăugăm lista { 4, 5 }
    // numbers = { -3, -2, -1, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8 }

    for(int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Ștergerea elementelor

Pentru a șterge un element din containerul forward_list, se pot folosi următoarele funcții:

clear(): șterge toate elementele
pop_front(): șterge primul element
erase_after(p): șterge elementul de după elementul indicat de iteratorul p. Returnează iteratorul către elementul de după cel șters
erase_after(begin, end): șterge un interval de elemente, începutul și sfârșitul fiind indicate de iteratorii begin și end. Returnează iteratorul către elementul de după ultimul șters

Exemplu de utilizare:

std::forward_list<int> numbers{ 1, 2, 3, 4, 5, 6, 7 };

numbers.pop_front();
// numbers = { 2, 3, 4, 5, 6, 7 };

auto iter = numbers.erase_after(numbers.begin());
// numbers = { 2, 4, 5, 6, 7 };
// iter indică elementul 4

numbers.erase_after(iter, numbers.end());
// numbers = { 2, 4 };