Vizualizare sursă pentru „SDA Lucrarea 3”

În acest laborator se vor implementa secvențe cu vectori și liste simplu și dublu înlănțuite.

= Secvența (lista abstractă - ''Sequence'') =

 Secvența este o structură de date abstractă care stochează datele sub forma unui șir de elemente de același fel.

Secvența are următoarele '''proprietăți''':
# Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
# Numărul de elemente ce poate fi stocat de structură este nelimitat (a nu se confunda cu infinit, există întotdeauna limita dată de memoria disponibilă).
# Elementele stocate în secvență sunt de același fel.

Secvența suportă următoarele '''operații de bază''':
# ''Interogarea numărului de elemente'' din secvență.
# ''Inserția'' unui element pe o anumită poziție în secvență.
# ''Ștergerea'' unui element de pe o anumită poziție din secvență.
# ''Căutarea'' unui element în secvență (căutare care va întoarce primul index pe care apare elementul în structură).
# ''Accesarea'' unui element de pe o anumită poziție.
# '''Dacă există o relație de ordine pe mulțimea din care fac parte elementele''', se poate defini operația de ''sortare'' a secvenței care implică mutarea elementelor pe alte poziții, astfel încât un element considerat mai mic după relația de ordine folosită să fie plasat înaintea oricărui element considerat mai mare.

= Implementarea secvenței cu vectori =

Clasa din STL care implementează secvențe folosind array-uri cu redimensionare dinamică se numește <code>std::vector</code>. Această clasă este un template care poate fi folosit pentru stocarea de elemente de diferite tipuri.

== Crearea unui <code>std::vector</code> ==

Pentru crearea unei vector nou se pot utiliza doi constructori:

<syntaxhighlight lang="cpp">
/**
 * Constructorul aloca memorie si creeaza un nou vector cu o capacitate initiala nulă.
 */
vector();

/**
 * Constructorul aloca memorie si creeaza un nou vector cu o dimensiune si o capacitate initiala.
 * Vectorul va avea "initialSize" elemente neutre (0 pentru valori numerice).
 * @param initialSize dimensiunea initiala a secventei.
 */
vector(uint32_t initialSize);
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <vector>

using namespace std;

int main() {
    vector<int> intVector;   // Foloseste primul constructor, dimensiune 0
    /* intVector[0] = 0; */  // Aici s-ar genera un Segmentation Fault pentru ca nu exista alocata memorie pentru un element (dimensiune si capacitate 0).
    intVector.push_back(10); // Aceasta linie functioneaza, pentru ca push_back adauga la sfarsitul vectorului, determinand redimensionarea acestuia.
    
    vector<float> floatVector(10); // Foloseste al doilea constructor, dimensiunea initiala e 10.
    floatVector[0] = 1;            // Linia NU genereaza un SegFault pentru ca exista capacitatea necesata pentru stocarea valorii.
     
    return 0;
}
</syntaxhighlight>

== Interogarea dimensiunii ==

Pentru interogarea dimensiunii, se definește următoarea metodă:

<syntaxhighlight lang="cpp">
/**
 * Metoda intoarce numarul de elemente valide din vector.
 * @return numarul de elemente valide din vector.
 */
uint32_t size();
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <vector>
#include <cstdio>

using namespace std;

int main() {
    vector<int> intVector;
    intVector.push_back(10);
    intVector.push_back(20);
    intVector.push_back(5);    

    printf("Vectorul are %u elemente!\n", intVector.size()); // Programul va afisa valoarea 3.

    return 0;
}
</syntaxhighlight>

== Inserția ==

Pentru inserția unui element '''value''' pe o anumită poziție '''index''' se definesc funcțiile de mai jos. Se observă că aceste funcții fac uz de iteratori. Acești iteratori sunt niște pointeri cu informații suplimentare. Există doi iteratori disponibili pentru orice vector: <code>begin()</code> și <code>end()</code>. Primul reprezintă adresa primului element din vector, iar al doilea reprezintă adresa DE DUPĂ ultimul element din vector.

<syntaxhighlight lang="cpp">
/**
 * Metoda insereaza elementul value pe pozitia position in vector. Daca capacitatea este insuficienta
 *  se face realocare.
 * @param position pozitia pe care se va face insertia
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la elementul inserat
 */
iterator insert(iterator position, T value);

/**
 * Metoda insereaza count elemente cu valoarea value pe pozitia position in vector. Daca capacitatea este insuficienta
 *  se face realocare.
 * @param position pozitia pe care se va face insertia
 * @param count numarul de elemente ce trebuie introduse
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert(iterator position, uint32_t count, T value);

/**
 * Metoda insereaza toate elementele dintre iteratorii first inclusiv si last exclusiv pe pozitia position in vector.
 *  Daca capacitatea este insuficienta se face realocare.
 * @param position pozitia pe care se va face insertia
 * @param first iteratorul de start
 * @param last iteratorul de final
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert(iterator position, iterator first, iterator last);

/**
 * Metoda adauga un element la sfarsitul vectorului. Daca capacitatea este insuficienta se face realocare.
 * @param value valoarea ce trebuie inserata
 */
void push_back (T value);

</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <vector>
#include <cstdio>

using namespace std;

int main() {
    vector<int> intVector;
    intVector.push_back(1);
    intVector.push_back(2);
    intVector.push_back(3);    

    // vectorul acum e: {1, 2, 3}

    intVector.insert(intVector.begin(), 0); // se insereaza inaintea primului element din vector o valoare de 0

    // vectorul acum e: {0, 1, 2, 3}

    intVector.insert(intVector.begin() + 1, 3); // se insereaza inaintea celui de-al doilea element din vector o valoare de 3

    // vectorul acum e: {0, 3, 1, 2, 3}

    intVector.insert(intVector.end(), 10); // se insereaza dupa ultimul element din vector, o valoare de 10 (echivalent cu push_back)

    // vectorul e acum: {0, 3, 1, 2, 3, 10}

    vector<int> newVector;
    newVector.push_back(-1);
    newVector.push_back(-2);
    newVector.push_back(-3);

    // newVector e acum: {-1, -2, -3}

    intVector.insert(intVector.begin(), newVector.begin(), newVector.end()); //Se insereaza inaintea primului element din intVector toate elementele din newVector

    // intVector e acum: {-1, -2, -3, 0, 3, 1, 2, 3, 10}

    return 0;
}
</syntaxhighlight>

== Ștergerea ==

Pentru ștergerea unuia sau mai multor elemente se definesc următoarele metode:

<syntaxhighlight lang="cpp">
/**
 * Metoda sterge elementul pe pozitia position din vector.
 * @param position pozitia de la care se va face stergerea
 * @return iterator la elementul ce urmeaza celui sters
 */
iterator erase(iterator position);

/**
 * Metoda sterge toate elementele dintre pozitiile first si last din vector.
 * @param first pozitia de unde incepe stergerea
 * @param last pozitia unde se termina stergerea
 * @return iterator la elementul ce urmeaza ultimului element sters
 */
iterator erase(iterator first, iterator last);

/**
 * Metoda sterge ultimul element din vector (opusul lui push_back).
 */
void pop_back();

/**
 * Metoda sterge toate elementele din vector.
 */
void clear();
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <vector>
#include <cstdio>

using namespace std;

int main() {
    vector<int> intVector;
    intVector.push_back(1);
    intVector.push_back(2);
    intVector.push_back(3);    
    intVector.push_back(4);    
    intVector.push_back(10);    

    // vectorul e acum: {1, 2, 3, 4, 10}

    intVector.pop_back(); // se sterge ultimul element

    // vectorul e acum {1, 2, 3, 4}

    intVector.erase(intVector.begin() + 2); // se sterge elementul de pe indexul 2 (a treia valoare)

    // vectorul e acum {1, 2, 4}

    intVector.erase(intVector.begin() + 1, intVector.end()); // se sterg toate valorile dintre indexul 1 si sfarsit

    // vectorul e acum {1}

    intVector.clear();

    // vectorul e acum gol: {}

    return 0;
}
</syntaxhighlight>

== Accesarea elementului de pe o anumită poziție ==

Pentru accesarea unui element de pe poziția '''index''' dintr-o secvență se definesc următoarele metode:

<syntaxhighlight lang="cpp">
/**
 * Metoda intoarce elementul din vector de pe poziția index.
 * @param index pozitia de la care se doreste citirea elementului. 
 * @return valoarea de la pozitia index
 */
T at(uint32_t index);

/**
 * Metoda intoarce elementul din vector de pe poziția index.
 * @param index pozitia de la care se doreste citirea elementului. 
 * @return valoarea de la pozitia index
 */
T operator[](uint32_t index);
</syntaxhighlight>

Metoda <code>operator[]</code> redefinește (supraîncarcă) utilizarea parantezelor pătrate astfel încât să poată fi folosite la fel ca la array-uri. Cele două metode sunt echivalente, singura diferență este că metoda <code>at</code> face și verificarea limitelor vectorului pentru a evita un Segmentation Fault.

Exemplu:

<syntaxhighlight lang="cpp">
#include <vector>
#include <cstdio>
 
int main() {
    std::vector<int> numbers;
    numbers.push_back(2);
    numbers.push_back(4);
    numbers.push_back(6);
    numbers.push_back(8);
 
    printf("Second element: %d\n", numbers[1]); // se va afisa 4
 
    numbers.at(0) = 5; // in loc de 2, primul element devine 5
 
    printf("All numbers:");
    for (uint32_t i = 0; i < numbers.size(); i++) {
        printf(" %d", numbers.at(i)); // se va afisa 5, 4, 6, 8
    }
    printf("\n");
    return 0;
}
</syntaxhighlight>

== Căutarea ==

Pentru căutarea unui element '''value''' într-o secvență neordonată '''list''' se definește următoarea funcție din header-ul ''algorithms'' (atenție, aceasta NU este o metodă, nu face parte din clasa vector, ci se apelează ca funcție):

<syntaxhighlight lang="cpp">
/**
 * Functia cauta elementul value in vector intre iteratorii first inclusiv si last exclusiv și intoarce un iterator la elementul gasit 
 *  Se intoarce last daca elementul nu a fost gasit.
 * @param first pozitia de start pentru cautare (inclusiv)
 * @param last pozitia de final pentru cautare (exclusiv)
 * @param value valoarea cautata
 * @return indexul la care apare valoarea sau last daca nu exista in interval.
 */
iterator std::find(iterator first, iterator last, T value);

/**
 * Functia cauta primul element care satisface predicatul predicateFunction intre iteratorii first inclusiv si last exclusiv și 
 *  intoarce un iterator la elementul gasit. Se intoarce last daca elementul nu a fost gasit.
 * @param first pozitia de start pentru cautare (inclusiv)
 * @param last pozitia de final pentru cautare (exclusiv)
 * @param predicateFunction functia predicat
 * @return indexul la care apare valoarea sau last daca nu exista in interval.
 */
iterator std::find_if(iterator first, iterator last, Predicate predicateFunction);
</syntaxhighlight>


Exemplu:

<syntaxhighlight lang="cpp">
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool isOdd(int v) {
    return (v & 1) == 1;
}
 
int main() {
    vector<int> v{0, 2, 1, 5, 3, 4};

    vector<int>::iterator findThree = find(v.begin(), v.end(), 3);
    vector<int>::iterator oddResult = find_if(v.begin(), v.end(), isOdd);

    printf("Prima pozitie unde apare un 3 este: %ld\n", findThree - v.begin());    
    printf("Prima pozitie a unui element impar este: %ld (elementul este %d)\n", oddResult - v.begin(), *oddResult);
 
    return 0;
}
</syntaxhighlight>

== Sortarea unei secvențe implementate cu vectori ==

Pentru sortarea unui vector se definește următoarea funcție tot din header-ul <code>algorithms</code>:

<syntaxhighlight lang="cpp">
/**
 * Functia sorteaza crescator elementele dintre iteratorii first si last. 
 * @param first pozitia de start pentru sortare
 * @param last pozitia de final pentru sortare
 */
void std::sort(iterator first, iterator last);

/**
 * Functia sorteaza crescator elementele dintre iteratorii first si last. 
 * @param first pozitia de start pentru sortare
 * @param last pozitia de final pentru sortare
 * @param comp comparatorul folosit pentru sortare (implementeaza relatia de ordine)
 */
void std::sort(iterator first, iterator last, Comparator comp);
</syntaxhighlight>

Funcțiile de tip Comparator sunt definite astfel:

<syntaxhighlight lang="cpp">
/**
 * Functia intoarce true daca first trebuie plasat in fata lui last in secventa.
 */
bool compare (T first, T last);
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stdint.h>
 
using namespace std;
 
bool reverseSorter(int a, int b) {
    return a > b;
}
 
int main() {
    vector<int> v{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; 
 
    // sort using the default operator<
    sort(v.begin(), v.end());
    for (uint32_t i = 0; i < v.size(); i++) {
        printf("%d ", v[i]);
    }   
    printf("\n");

 
    sort(v.begin(), v.end(), reverseSorter);
    for (uint32_t i = 0; i < v.size(); i++) {
        printf("%d ", v[i]);
    }   
    printf("\n");
}
</syntaxhighlight>

= Implementarea secvenței cu liste simplu și dublu înlănțuite =

Clasa din STL care implementează secvențe folosind liste simplu înlănțuite se numește <code>std::forward_list</code>, iar cea pentru liste dublu înlănțuite este <code>std::list</code>. Aceaste clase sunt template-uri care pot fi folosite pentru stocarea de elemente de diferite tipuri. Diferența fundamentală între aceste două clase este că prima suporta parcurgere eficientă doar de la început la final, pe când cea din urmă se poate parcurge eficient în ambele sensuri.

== Crearea unor <code>std::forward_list</code> sau <code>std::list</code> ==

Pentru crearea unei liste noi se pot utiliza următorii constructori constructori:

<syntaxhighlight lang="cpp">
/**
 * Constructorul aloca memorie si creeaza o listă goală.
 */
forward_list();

/**
 * Constructorul aloca memorie si creeaza o listă goală.
 */
list();

/**
 * Constructorul aloca memorie si creeaza o listă cu o dimensiune initiala.
 * Lista va avea "initialSize" elemente neutre (0 pentru valori numerice).
 * @param initialSize dimensiunea initiala a secventei.
 */
forward_list(uint32_t initialSize);

/**
 * Constructorul aloca memorie si creeaza o listă cu o dimensiune initiala.
 * Lista va avea "initialSize" elemente neutre (0 pentru valori numerice).
 * @param initialSize dimensiunea initiala a secventei.
 */
forward_list(uint32_t initialSize);
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <forward_list>
#include <list>

using namespace std;

int main() {
    forward_list<int> intList;   // Foloseste primul constructor, dimensiune 0
    intList.push_front(10); // push_front adauga elementul la inceputul listei
    
    list<float> floatList(10); // Foloseste al doilea constructor, dimensiunea initiala e 10.
    printf("Primul element din lista este: %f\n", floatList.front());
     
    return 0;
}
</syntaxhighlight>

== Interogarea dimensiunii ==

În cazul listelor simplu înlănțuite, dimensiunea nu se poate interoga în timp constant. Pentru acest motiv, dimensiunea unei liste se poate obține apelând o funcție din header-ul algorithm numită <code>std::distance</code>, ce calculează distanța (numărul de elemente) dintre doi '''iteratori'''. Acești iteratori sunt niște pointeri cu informații suplimentare. Există doi iteratori disponibili pentru orice secvență: <code>begin()</code> și <code>end()</code>. Primul reprezintă adresa primului element din secvență, iar al doilea reprezintă adresa DE DUPĂ ultimul element din secvență. În cazul listelor simplu înlănțuite, timpul de calcul depinde liniar de numărul de elemente. 

<syntaxhighlight lang="cpp">
/**
 * Funcția intoarce numarul de elemente dintre cei doi interatori
 * @return numarul de elemente dintre cei doi iteratori.
 */
uint32_t distance (iterator begin, iterator end);
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <forward_list>
#include <cstdio>

using namespace std;

int main() {
    forward_list<int> intList;
    intList.push_front(10);
    intList.push_front(20);
    intList.push_front(5);    

    printf("Lista are %u elemente!\n", distance(intList.begin(), intList.end())); // Programul va afisa valoarea 3.

    return 0;
}
</syntaxhighlight>

Pentru listele dublu înlănțuite, se definește următoarea metodă:

<syntaxhighlight lang="cpp">
/**
 * Metoda intoarce numarul de elemente din lista.
 * @return numarul de elemente din lista.
 */
uint32_t size();
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <list>
#include <cstdio>

using namespace std;

int main() {
    list<int> intList;
    intList.push_back(10);
    intList.push_back(20);
    intList.push_back(5);    

    printf("Lista are %u elemente!\n", intList.size()); // Programul va afisa valoarea 3.

    return 0;
}
</syntaxhighlight>

== Inserția ==

Pentru inserția într-o listă '''''simplu înlănțuită''''' a unui element '''value''' pe o anumită poziție de după un iterator '''position''', se definesc metodele de mai jos. '''Atenție''': pentru a obține un iterator cu '''''n''''' poziții mai la dreapta, iteratorii listelor nu se pot incrementa cu '''''n'''''. În schimb, există două funcții, <code>std::next</code> și <code>std::prev</code>, definite în header-ul <code>iterator</code> care întorc acest iterator deplasat:

<syntaxhighlight lang="cpp">
/**
 * Functia intoarce un iterator la elementul cu offset pozitii mai la dreapta.
 * @param current iteratorul curent, care va fi incrementat cu offset
 * @param offset iteratorul deplasat cu offset poziții mai la dreapta. Poate fi 
 *  negativ pentru std::list sau std::vector dar nu si pentru std::forward_list. Implicit este 1.
 */
iterator std::next (iterator current, int32_t offset = 1);

/**
 * Exclusiv pentru std::list si std::vector, functia intoarce un iterator la elementul cu offset pozitii mai la stanga.
 * @param current iteratorul curent, care va fi decrementat cu offset
 * @param offset iteratorul deplasat cu offset poziții mai la stanga. Implicit este 1
 */
iterator std::prev (iterator current, int32_t offset = 1);

/**
 * Metoda insereaza elementul value pe pozitia de dupa position in lista.
 * @param position pozitia de dinaintea celei pe care se va face insertia
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la elementul inserat
 */
iterator insert_after(iterator position, T value);

/**
 * Metoda insereaza count elemente cu valoarea value pe pozitia de dupa position in lista.
 * @param position pozitia de dinaintea celei pe care se va face insertia
 * @param count numarul de elemente ce trebuie introduse
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert_after(iterator position, uint32_t count, T value);

/**
 * Metoda insereaza toate elementele dintre iteratorii first inclusiv si last exclusiv 
 *  pe pozitia de dupa position in lista.
 * @param position pozitia de dinaintea celei pe care se va face insertia
 * @param first iteratorul de start
 * @param last iteratorul de final
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert_after(iterator position, iterator first, iterator last);

/**
 * Metoda adauga un element la inceputul listei.
 * @param value valoarea ce trebuie inserata
 */
void push_front (T value);

</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <forward_list>
#include <cstdio>
#include <iterator>

using namespace std;

int main() {
    forward_list<int> intList;
    intList.push_front(3);
    intList.push_front(2);
    intList.push_front(1);    

    // lista e acum: {1, 2, 3}

    intList.insert_after(intList.begin(), 0); // se insereaza dupa primul element din lista o valoare de 0

    // lista e acum: {1, 0, 2, 3}

    intList.insert_after(next(intList.begin()), 3); // se insereaza dupa cel de-al doilea element din lista o valoare de 3

    // lista e acum: {1, 0, 3, 2, 3}

    intList.push_front(-1); // se insereaza pe prima pozitie o valoare de -1

    // lista e acum: {-1, 1, 0, 3, 2, 3}

    forward_list<int> newList;
    newList.push_front(-1);
    newList.push_front(-2);
    newList.push_front(-3);

    // newList e acum: {-3, -2, -1}

    intList.insert_after(intList.begin(), newList.begin(), newList.end()); //Se insereaza dupa primul element din intList toate elementele din newList

    // intList e acum: {-1, -3, -2, -1, 1, 0, 3, 2, 3}

    return 0;
}
</syntaxhighlight>

Pentru inserția unui element '''value''' pe o anumită poziție '''index''' într-o listă '''''dublu înlănțuită''''', se definesc funcțiile de mai jos:

<syntaxhighlight lang="cpp">
/**
 * Metoda insereaza elementul value pe pozitia position in lista.
 * @param position pozitia pe care se va face insertia
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la elementul inserat
 */
iterator insert(iterator position, T value);

/**
 * Metoda insereaza count elemente cu valoarea value pe pozitia position in lista.
 * @param position pozitia pe care se va face insertia
 * @param count numarul de elemente ce trebuie introduse
 * @param value valoarea ce trebuie inserata
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert(iterator position, uint32_t count, T value);

/**
 * Metoda insereaza toate elementele dintre iteratorii first inclusiv si last exclusiv pe pozitia position in lista.
 * @param position pozitia pe care se va face insertia
 * @param first iteratorul de start
 * @param last iteratorul de final
 * @return metoda intoarce un iterator la primul element inserat
 */
iterator insert(iterator position, iterator first, iterator last);

/**
 * Metoda adauga un element la sfarsitul listei.
 * @param value valoarea ce trebuie inserata
 */
void push_back (T value);

/**
 * Metoda adauga un element la inceputul listei.
 * @param value valoarea ce trebuie inserata
 */
void push_front (T value);

</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <list>
#include <forward_list>
#include <cstdio>
#include <iterator>

using namespace std;

int main() {
    list<int> intList;
    intList.push_back(1);
    intList.push_back(2);
    intList.push_back(3);

    // lista acum e: {1, 2, 3}

    intList.insert(intList.begin(), 0); // se insereaza inaintea primului element din lista o valoare de 0

    // lista acum e: {0, 1, 2, 3}

    intList.insert(next(intList.begin()), 3); // se insereaza inaintea celui de-al doilea element din lista o valoare de 3

    // lista acum e: {0, 3, 1, 2, 3}

    intList.insert(intList.end(), 10); // se insereaza dupa ultimul element din lista, o valoare de 10 (echivalent cu push_back)

    // lista e acum: {0, 3, 1, 2, 3, 10}

    forward_list<int> newList;
    newList.push_front(-3);
    newList.push_front(-2);
    newList.push_front(-1);

    // newList e acum: {-1, -2, -3}

    intList.insert(intList.begin(), newList.begin(), newList.end()); //Se insereaza inaintea primului element din intList toate elementele din newList

    // intList e acum: {-1, -2, -3, 0, 3, 1, 2, 3, 10}

    return 0;
}
</syntaxhighlight>

== Ștergerea ==

Pentru ștergerea unuia sau mai multor elemente de după un alt element dintr-o listă '''''simplu înlănțuită''''', se definesc următoarele metode:

<syntaxhighlight lang="cpp">
/**
 * Metoda sterge elementul de dupa pozitia position din lista.
 * @param position pozitia de dinaintea celei de la care se va face stergerea
 * @return iterator la elementul ce urmeaza celui sters
 */
iterator erase_after(iterator position);

/**
 * Metoda sterge toate elementele dintre pozitiile first si last din lista, exclusiv.
 * @param first pozitia de unde incepe stergerea
 * @param last pozitia unde se termina stergerea
 * @return iterator la elementul ce urmeaza ultimului element sters
 */
iterator erase_after(iterator first, iterator last);

/**
 * Metoda sterge primul element din lista (opusul lui push_front).
 */
void pop_front();

/**
 * Metoda sterge toate elementele din lista.
 */
void clear();
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <forward_list>
#include <cstdio>
#include <iterator>

using namespace std;

int main() {
    forward_list<int> intList;
    intList.push_front(10);
    intList.push_front(4);
    intList.push_front(3);
    intList.push_front(2);
    intList.push_front(1);

    // lista e acum: {1, 2, 3, 4, 10}

    intList.pop_front(); // se sterge primul element

    // lista e acum {2, 3, 4, 10}

    intList.erase_after(next(intList.begin(), 2)); // se sterge elementul de pe indexul 3 (a patra valoare)

    // lista e acum {2, 3, 4}

    intList.erase_after(intList.begin(), intList.end()); // se sterg toate valorile dintre indexul 1 si sfarsit (exclusiv)

    // lista e acum {2}

    intList.clear();

    // lista e acum goala: {}

    return 0;
}
</syntaxhighlight>

Pentru ștergerea unuia sau mai multor elemente dintr-o listă dublu înlănțuită, se definesc următoarele metode:

<syntaxhighlight lang="cpp">
/**
 * Metoda sterge elementul pe pozitia position din lista.
 * @param position pozitia de la care se va face stergerea
 * @return iterator la elementul ce urmeaza celui sters
 */
iterator erase(iterator position);

/**
 * Metoda sterge toate elementele dintre pozitiile first si last din lista.
 * @param first pozitia de unde incepe stergerea
 * @param last pozitia unde se termina stergerea
 * @return iterator la elementul ce urmeaza ultimului element sters
 */
iterator erase(iterator first, iterator last);

/**
 * Metoda sterge ultimul element din lista (opusul lui push_back).
 */
void pop_back();

/**
 * Metoda sterge primul element din lista (opusul lui push_front).
 */
void pop_front();

/**
 * Metoda sterge toate elementele din lista.
 */
void clear();
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <list>
#include <cstdio>

using namespace std;

int main() {
    list<int> intList;
    intList.push_back(1);
    intList.push_back(2);
    intList.push_back(3);    
    intList.push_back(4);    
    intList.push_back(10);    

    // lista e acum: {1, 2, 3, 4, 10}

    intList.pop_back(); // se sterge ultimul element

    // lista e acum {1, 2, 3, 4}

    intList.erase(next(intList.begin(), 2)); // se sterge elementul de pe indexul 2 (a treia valoare)

    // lista e acum {1, 2, 4}

    intList.erase(next(intList.begin()), intList.end()); // se sterg toate valorile dintre indexul 1 si sfarsit

    // lista e acum {1}

    intList.clear();

    // lista e acum goala: {}

    return 0;
}
</syntaxhighlight>

== Accesarea elementului de pe o anumită poziție ==

Deoarece lista nu este o structură cu acces aleator, accesarea elementelor se face exclusiv prin iteratori.

Exemplu:

<syntaxhighlight lang="cpp">
#include <list>
#include <cstdio>
#include <iterator>

int main() {
    std::list<int> numbers;
    numbers.push_back(2);
    numbers.push_back(4);
    numbers.push_back(6);
    numbers.push_back(8);

    printf("First element: %d\n", *numbers.begin()); // se va afisa 2

    *numbers.begin() = 5; // in loc de 2, primul element devine 5
    *std::next(numbers.begin(), 2) = -6; // in loc de 6, al treilea element devine -6

    printf("All numbers:");
    for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); it++) {
        printf(" %d", *it); // se va afisa 5, 4, -6, 8
    }
    printf("\n");
    return 0;
}
</syntaxhighlight>

== Căutarea ==

Pentru căutarea unui element '''value''' într-o secvență neordonată se definește următoarea funcție din header-ul ''algorithms'' (atenție, aceasta NU este o metodă, nu face parte din clasa list sau forward_list, ci se apelează ca funcție):

<syntaxhighlight lang="cpp">
/**
 * Functia cauta elementul value in lista intre iteratorii first inclusiv si last exclusiv și intoarce un iterator la elementul gasit 
 *  Se intoarce last daca elementul nu a fost gasit.
 * @param first pozitia de start pentru cautare (inclusiv)
 * @param last pozitia de final pentru cautare (exclusiv)
 * @param value valoarea cautata
 * @return indexul la care apare valoarea sau last daca nu exista in interval.
 */
iterator std::find(iterator first, iterator last, T value);

/**
 * Functia cauta primul element care satisface predicatul predicateFunction intre iteratorii first inclusiv si last exclusiv și 
 *  intoarce un iterator la elementul gasit. Se intoarce last daca elementul nu a fost gasit.
 * @param first pozitia de start pentru cautare (inclusiv)
 * @param last pozitia de final pentru cautare (exclusiv)
 * @param predicateFunction functia predicat
 * @return indexul la care apare valoarea sau last daca nu exista in interval.
 */
iterator std::find_if(iterator first, iterator last, Predicate predicateFunction);
</syntaxhighlight>


Exemplu:

<syntaxhighlight lang="cpp">
#include <cstdio>
#include <algorithm>
#include <forward_list>

using namespace std;

bool isOdd(int v) {
    return (v & 1) == 1;
}
 
int main() {
    list<int> v{0, 2, 1, 5, 3, 4};

    list<int>::iterator findThree = find(v.begin(), v.end(), 3);
    list<int>::iterator oddResult = find_if(v.begin(), v.end(), isOdd);

    printf("Prima pozitie unde apare un 3 este: %ld\n", distance(v.begin(), findThree));    
    printf("Prima pozitie a unui element impar este: %ld (elementul este %d)\n", distance(v.begin(), oddResult), *oddResult);
 
    return 0;
}
</syntaxhighlight>

== Sortarea unei secvențe implementate cu liste ==

Pentru sortarea unui liste se definește următoarea metodă din clasele <code>std::list</code> și <code>std::forward_list</code>:

<syntaxhighlight lang="cpp">
/**
 * Metoda sorteaza crescator elementele din lista. 
 */
void std::sort();

/**
 * Metoda sorteaza elementele din lista conform comparatorului comp. 
 * @param comp comparatorul folosit pentru sortare (implementeaza relatia de ordine)
 */
void std::sort(Comparator comp);
</syntaxhighlight>

Funcțiile de tip Comparator sunt definite astfel:

<syntaxhighlight lang="cpp">
/**
 * Functia intoarce true daca first trebuie plasat in fata lui last in secventa.
 */
bool compare (T first, T last);
</syntaxhighlight>

Exemplu:

<syntaxhighlight lang="cpp">
#include <algorithm>
#include <cstdio>
#include <list>
#include <stdint.h>
 
using namespace std;
 
bool reverseSorter(int a, int b) {
    return a > b;
}
 
int main() {
    list<int> v{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; 
 
    // sort using the default operator<
    v.sort();
    for (list<int>::iterator it = v.begin(); it != v.end(); it++) {
        printf("%d ", *it);
    }   
    printf("\n");

 
    v.sort(reverseSorter);
    for (list<int>::iterator it = v.begin(); it != v.end(); it++) {
        printf("%d ", *it);
    }  
    printf("\n");
}
</syntaxhighlight>