Diferență între revizuiri ale paginii „SDA Lucrarea 3”

De la WikiLabs
Jump to navigationJump to search
 
(Nu s-au afișat 55 de versiuni intermediare efectuate de un alt utilizator)
Linia 16: Linia 16:
 
# ''Căutarea'' unui element în secvență (căutare care va întoarce primul index pe care apare elementul în structură).
 
# ''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.
 
# ''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 secevenț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.
+
# '''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 =
 
= Implementarea secvenței cu vectori =
  
În cazul implementării cu vectori, elementele sunt plasate într-un vector de dimensiune fixă și cunoscută. Din cauza faptului că secvența are dimensiune nelimitată, se cere ca vectorii să suporte redimensionarea dinamică pentru a acomoda elemente suplimentare în momentul când se umplu. Astfel, suntem obligați ca pentru implementarea secvențelor să folosim alocare dinamică de memorie, iar tipul de date care poate fi folosit pentru stocarea adreselor alocate este pointerul. Totuși cunoaștem din lecțiile anterioare faptul că o variabilă de tip pointer nu memorează decât o adresă de start a zonei de memorie alocată, nu și dimensiunea ei. Prin urmare vom defini o clasa numită <code>sda::vector</code> care va stoca adresa de start dar și dimensiunea zonei alocate. Mai jos este un exemplu de secvență de elemente de tip arbitrar T:
+
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">
 
<syntaxhighlight lang="cpp">
namespace sda {
+
/**
    template <class T>
+
* Constructorul aloca memorie si creeaza un nou vector cu o capacitate initiala nulă.
    class vector {
+
*/
        T * array;         // pointer la zona de memorie alocată
+
vector();
        uint32_t capacity; // dimensiunea zonei alocate
+
 
    };
+
/**
}
+
* 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>
 
</syntaxhighlight>
  
În plus față de câmpurile de mai sus, structura <code>sda::vector</code> trebuie să memoreze și numărul de elemente valide din secvență. Motivul fiind acela că inițial, chiar dacă vectorul este alocat și are o capacitate ne-nulă, el nu conține de fapt nici un element. Astfel introducem un nou câmp: <code>count</code>, care reprezintă numărul de elemente din secvență, și care este inițial 0:
+
Exemplu:
  
 
<syntaxhighlight lang="cpp">
 
<syntaxhighlight lang="cpp">
namespace sda {
+
#include <vector>
     template <class T>
+
 
     class vector {
+
using namespace std;
        T * array;         // pointer la zona de memorie alocată
+
 
        uint32_t capacity; // dimensiunea zonei alocate
+
int main() {
        uint32_t count;   // numarul de elemente valide din secventa (initial 0)
+
     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>
 
</syntaxhighlight>
  
== Crearea unui <code>sda::vector</code> ==
+
== Interogarea dimensiunii ==
  
Pentru crearea unei secvențe noi, se definește următoarea funcție:
+
Pentru interogarea dimensiunii, se definește următoarea metodă:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia aloca memorie si creeaza un nou ArrayList cu o capacitate initiala.
+
  * Metoda intoarce numarul de elemente valide din vector.
* @param initialCapacity capacitatea initiala a secventei.
+
  * @return numarul de elemente valide din vector.
  * @return pointer la o structura de tip ArrayList.  
 
 
  */
 
  */
struct ArrayList * createArrayList(unsigned initialCapacity);
+
uint32_t size();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face folosind următorul algoritm:
+
Exemplu:
# Se alocă memorie pentru o variabilă de tip <code>struct ArrayList</code>.
+
 
# Se inițializează <code>capacity</code> cu valoarea din <code>initialCapacity</code>.
+
<syntaxhighlight lang="cpp">
# Se inițializează <code>size</code> cu 0.
+
#include <vector>
# Se alocă memorie pentru un vector de <code>initialCapacity</code> elemente iar adresa alocată se memorează în <code>array</code>.
+
#include <cstdio>
# Se întoarce adresa variabilei de tip <code>struct ArrayList</code>.
+
 
 +
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>
  
== Interogarea dimensiunii ==
+
== Inserția ==
  
Pentru interogarea dimensiunii, se definește următoarea funcție:
+
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="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia intoarce numarul de elemente valide din lista specificata.
+
  * Metoda insereaza elementul value pe pozitia position in vector. Daca capacitatea este insuficienta
  * @param list lista pentru care se cere dimensinea.
+
*  se face realocare.
  * @return numarul de elemente valide din lista list.
+
  * @param position pozitia pe care se va face insertia
 +
* @param value valoarea ce trebuie inserata
 +
  * @return metoda intoarce un iterator la elementul inserat
 
  */
 
  */
unsigned arrayListSize(struct ArrayList * list);
+
iterator insert(iterator position, T value);
</syntaxhighlight>
 
  
Implementarea acestei funcții se face întorcând direct valoarea câmpului '''size''' din structură.
+
/**
 +
* 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);
  
== Inserția ==
+
/**
 +
* 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);
  
Pentru inserția unui element '''value''' pe o anumită poziție '''index''' se definește următoarea funcție:
 
 
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia inseareaza elementul value pe pozitia index in vector. Daca capacitatea este insuficienta
+
  * Metoda adauga un element la sfarsitul vectorului. Daca capacitatea este insuficienta se face realocare.
se face realocare. Se afiseaza un mesaj de eroare daca indexul este mai mare decat size.
 
* @param list lista in care se face insertia.
 
* @param index indexul pe care se va face insertia
 
 
  * @param value valoarea ce trebuie inserata
 
  * @param value valoarea ce trebuie inserata
 
  */
 
  */
void arrayListInsert(struct ArrayList * list, unsigned index, short value);
+
void push_back (T value);
 +
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Inserția unui element '''value''' pe o anumită poziție '''index''' într-o secvență implementată cu vectori, se face urmând următorul algoritm:
+
Exemplu:
# Dacă '''index''' este mai mare decat '''size''', se afișează un mesaj de eroare și funcția se încheie.
+
 
# Dacă '''size''' este egal cu '''capacity''', se face realocare de memorie alocând un vector nou de '''2 * capacity''' elemente. Acest lucru se realizează folosind funcția [http://www.cplusplus.com/reference/cstdlib/realloc/ realloc].
+
<syntaxhighlight lang="cpp">
# Lui '''capacity''' i se atribuie valoarea '''2 * capacity'''.
+
#include <vector>
# Se folosește funcția [http://www.cplusplus.com/reference/cstring/memmove/ memmove] pentru a muta elementele de la poziția '''index''' la '''size - 1''' cu un element mai la dreapta.
+
#include <cstdio>
# Se atribuie elementului de pe poziția '''index''' din vector valoarea '''value'''.
+
 
# '''size''' se incrementează cu 1.
+
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 ==
 
== Ștergerea ==
  
Pentru ștergerea unui element de pe o anumită poziție '''index''' se definește următoarea funcție:
+
Pentru ștergerea unuia sau mai multor elemente se definesc următoarele metode:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia sterge elementul pe pozitia index in vector. Se afiseaza un mesaj de eroare
+
  * Metoda sterge elementul pe pozitia position din vector.
*  daca indexul este mai mare decat (size - 1).
+
  * @param position pozitia de la care se va face stergerea
  * @param list lista din care se face stergerea.
+
  * @return iterator la elementul ce urmeaza celui sters
  * @param index indexul de la care se va face stergerea
 
 
  */
 
  */
void arrayListDelete(struct ArrayList * list, unsigned index);
+
iterator erase(iterator position);
</syntaxhighlight>
 
  
Ștergerea unui element de pe o anumită poziție '''index''' dintr-o secvență implementată cu vectori, se face urmând următorul algoritm:
+
/**
# Dacă '''index''' este mai mare decat '''size - 1''', se afișează un mesaj de eroare și funcția se încheie.
+
* Metoda sterge toate elementele dintre pozitiile first si last din vector.
# Se folosește funcția [http://www.cplusplus.com/reference/cstring/memmove/ memmove] pentru a muta elementele de la poziția '''index + 1''' la '''size - 1''' cu un element mai la stânga.
+
* @param first pozitia de unde incepe stergerea
# '''size''' se decrementează cu 1.
+
* @param last pozitia unde se termina stergerea
 +
* @return iterator la elementul ce urmeaza ultimului element sters
 +
*/
 +
iterator erase(iterator first, iterator last);
  
== Căutarea ==
+
/**
 +
* Metoda sterge ultimul element din vector (opusul lui push_back).
 +
*/
 +
void pop_back();
  
Pentru căutarea unui element '''value''' într-o secvență neordonată se definește următoarea funcție:
 
 
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia cauta elementul value in vector si intoarce prima pozitie pe care apare.
+
  * Metoda sterge toate elementele din vector.
*  Se intoarce -1 daca valoarea nu exista in vector.
 
* @param list lista in care se face cautarea.
 
* @param value valoarea care se cauta.
 
* @return indexul la care apare valoarea sau -1 daca nu exista in vector.
 
 
  */
 
  */
int arrayListSearch(struct ArrayList * list, short value);
+
void clear();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Căutarea unui element '''value''' într-o secvență neordonată implementată cu vectori, se face urmând următorul algoritm:
+
Exemplu:
# Se iterează cu o variabilă '''i''' de la 0 la '''size - 1'''.
+
 
# Dacă elementul de pe poziția '''i''' din vector este egal cu '''value''', se întoarce valoarea lui '''i'''.
+
<syntaxhighlight lang="cpp">
# Se întoarce valoarea -1.
+
#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 ==
 
== Accesarea elementului de pe o anumită poziție ==
  
Pentru accesarea unui element de pe poziția '''index''' dintr-o secvență se definește următoarea funcț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);
  
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia intoarce elementul din vector de pe poziția index. Daca index este mai mare decat (size - 1) se afiseaza
+
  * Metoda intoarce elementul din vector de pe poziția index.
*  un mesaj de eroare (si se întoarce 0).
 
* @param list lista in care se face accesul.
 
 
  * @param index pozitia de la care se doreste citirea elementului.  
 
  * @param index pozitia de la care se doreste citirea elementului.  
  * @return valoarea de la pozitia index sau 0 daca index este mai mare decat (size - 1)
+
  * @return valoarea de la pozitia index
 
  */
 
  */
short arrayListGet(struct ArrayList * list, unsigned index);
+
T operator[](uint32_t index);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Accesarea unui element de pe poziția '''index''' dintr-o secvență neordonată implementată cu vectori, se face urmând următorul algoritm:
+
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.
# Dacă '''index''' este mai mare decât '''(size - 1)''' se afișează un mesaj de eroare și se întoarce 0.
 
# Se întoarce valoarea de la indexul '''index''' din vector.
 
  
== Sortarea unei secvențe implementate cu vectori - ''Bubble Sort'' ==
+
Exemplu:
  
Pentru sortarea unei secvențe se definește următoarea funcție:
+
<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);
  
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort.  
+
  * Functia cauta primul element care satisface predicatul predicateFunction intre iteratorii first inclusiv si last exclusiv și
  * @param list lista care se doreste sortata.
+
*  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.
 
  */
 
  */
void arrayListBubbleSort(struct ArrayList * list);
+
iterator std::find_if(iterator first, iterator last, Predicate predicateFunction);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Sortarea unei secvențe implementată cu vectori se face urmând următorul algoritm:
 
# Se declară o variabilă '''done'''.
 
# Se atribuie lui '''done''' valoarea 1.
 
# Se iterează cu un contor '''i''' de la 0 la '''(size - 2)'''
 
# Dacă elementul de pe poziția '''i''' din vector este mai mare decât elementul de pe poziția '''(i + 1)''', acestea se interschimbă și lui '''done''' i se atribuie valoarea 0.
 
# După terminarea iterării peste vector, dacă '''done''' e 0, se sare la pasul 2 (se folosește o buclă ''do-while'').
 
  
== Căutarea într-o secvență sortată implementată cu vectori - ''Binary Search'' ==
+
Exemplu:
  
Căutarea într-o secvență ordonată se poate realiza mai eficient decât iterând peste toate elementele cu o buclă în O(n), deoarece avem informații suplimentare legate de poziția cea mai probabilă a elementului căutat.
+
<syntaxhighlight lang="cpp">
 +
#include <cstdio>
 +
#include <algorithm>
 +
#include <vector>
  
Algoritmul numit [https://en.wikipedia.org/wiki/Binary_search_algorithm Binary Search], care face parte din clasa Divide-et-impera, funcționează căutând elementul la mijlocul intervalului în care se realizează căutare, și în funcție de rezultat întorcând poziția sau eliminând în întregime jumătate din interval.
+
using namespace std;
  
Pentru căutarea unei valori '''value''' într-o secvență sortată implementată cu vectori, se definește următoarea funcție:
+
bool isOdd(int v) {
 +
    return (v & 1) == 1;
 +
}
 +
 +
int main() {
 +
    vector<int> v{0, 2, 1, 5, 3, 4};
  
<syntaxhighlight lang="C">
+
    vector<int>::iterator findThree = find(v.begin(), v.end(), 3);
/**
+
    vector<int>::iterator oddResult = find_if(v.begin(), v.end(), isOdd);
* Functia cauta elementul value in secventa list sortata crescator.  
+
 
*    Daca secventa nu este sortata, comportamentul nu este definit.
+
    printf("Prima pozitie unde apare un 3 este: %ld\n", findThree - v.begin());   
* @param list lista in care se cauta.
+
    printf("Prima pozitie a unui element impar este: %ld (elementul este %d)\n", oddResult - v.begin(), *oddResult);
* @param value valoarea cautata in secventa.
+
   
* @return indexul unde s-a găsit valoarea value sau -1 daca valoarea nu exista.
+
    return 0;
  */
+
}
int arrayListBinarySearch(struct ArrayList * list, short value);
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Căutarea unei valori '''value''' într-o secvență sortată implementată cu vectori se face urmând următorul algoritm:
+
== Sortarea unei secvențe implementate cu vectori ==
# Se inițializează o variabilă '''start''' cu valoarea 0 și o varibilă '''end''' cu valoarea '''(size - 1)'''.
+
 
# Cât timp '''start''' este mai mic sau egal decât '''end''' se realizează următoarele operații:
+
Pentru sortarea unui vector se definește următoarea funcție tot din header-ul <code>algorithms</code>:
# Se declară o variabilă '''middle''' și i se atribuie valoarea '''(start + end ) / 2'''.
 
# Dacă elementul din vector de pe poziția '''middle''' este egal cu '''value''', se întoarce valoarea '''middle'''.
 
# Dacă elementul din vector de pe poziția '''middle''' este mai mare decât '''value''', '''end''' va lua valoarea '''middle - 1''' altfel,
 
# Dacă elementul din vector de pe poziția '''middle''' este mai mic decât '''value''', '''start''' va lua valoarea '''middle + 1'''.
 
# Se sare la punctul 3.
 
# Aici se ajunge dacă '''start''' devine mai mare decât '''end''', în care situație se întoarce -1.
 
  
<div class="regula"><span style="color: red">'''Atenție'''</span>: Acest algoritm nu va întoarce întotdeauna prima apariție a elementului '''value''' din vector. De ce? Ce soluție propuneți pentru a rezolva această problemă?</div>
+
<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);
  
== Ștergerea unui <code>ArrayList</code> ==
+
/**
 +
* 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>
  
Pentru ștergerea unui <code>ArrayList</code> se definește următoarea funcție.
+
Funcțiile de tip Comparator sunt definite astfel:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia dezalocă memoria folosită de lista specificată.
+
  * Functia intoarce true daca first trebuie plasat in fata lui last in secventa.
* @param list lista care trebuie ștearsă.
 
 
  */
 
  */
void deleteArrayList(struct ArrayList * list);
+
bool compare (T first, T last);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Ștergerea unui <code>ArrayList</code> se realizează în doi pași:
+
Exemplu:
# Se dezalocă memoria alocată pentru vector.
+
 
# Se dezalocă memoria alocată pentru structura de tip <code>struct ArrayList</code>.
+
<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 =
 
= Implementarea secvenței cu liste simplu și dublu înlănțuite =
  
În cazul implementării cu liste simplu și dublu înlănțuite, elementele sunt plasate în zone de memorie separate, numite noduri, iar fiecare nod conține pe lângă valoarea efectivă și adresa următorului nod (în cazul listelor simplu înlănțuite), sau adresa nodului următor și a nodului anterior (în cazul listelor dublu înlănțuite). Acest tip de structurare a secvențelor respectă în mod natural contractul stabilit de lista abstractă (dimensiune nelimitată, secvențierea elementelor, etc.). Prin urmare vom defini o structură numită <code>LinkedList</code> care va stoca adresa primului și ultimului nod, dar și numărul de elemente din secvență, pentru optimizarea operației de interogare a dimensiunii. Pentru a defini un nod, ne trebuie o a doua structură numită <code>ListNode</code>. Mai jos este un exemplu de listă simplu înlănțuită de valori în virgulă mobilă cu dublă precizie:
+
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.
  
<syntaxhighlight lang="C">
+
== Crearea unor <code>std::forward_list</code> sau <code>std::list</code> ==
struct ListNode {
 
    double value;
 
    struct ListNode * next;
 
};
 
  
struct LinkedList {
+
Pentru crearea unei liste noi se pot utiliza următorii constructori constructori:
    struct ListNode * firstNode;
+
 
    struct ListNode * lastNode;
+
<syntaxhighlight lang="cpp">
    unsigned size;
+
/**
};
+
* Constructorul aloca memorie si creeaza o listă goală.
</syntaxhighlight>
+
*/
 +
forward_list();
  
== Crearea unui <code>LinkedList</code> ==
+
/**
 +
* Constructorul aloca memorie si creeaza o listă goală.
 +
*/
 +
list();
  
Pentru crearea unei liste noi, se definește următoarea funcție (observați lipsa parametrului ''capacity''):
+
/**
 +
* 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 lang="C">
 
 
/**
 
/**
  * Functia aloca memorie si creeaza un nou LinkedList.
+
  * Constructorul aloca memorie si creeaza o listă cu o dimensiune initiala.
  * @return pointer la o structura de tip LinkedList.  
+
* Lista va avea "initialSize" elemente neutre (0 pentru valori numerice).
 +
  * @param initialSize dimensiunea initiala a secventei.
 
  */
 
  */
struct LinkedList * createLinkedList();
+
forward_list(uint32_t initialSize);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face folosind următorul algoritm:
+
Exemplu:
# Se alocă memorie pentru o variabilă de tip <code>struct LinkedList</code>.
+
 
# Se inițializează <code>firstNode</code> și <code>lastNode</code> cu valoarea '''NULL'''.
+
<syntaxhighlight lang="cpp">
# Se inițializează <code>size</code> cu 0.
+
#include <forward_list>
# Se întoarce adresa variabilei de tip <code>struct LinkedList</code>.
+
#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 ==
 
== Interogarea dimensiunii ==
  
Pentru interogarea dimensiunii, se definește următoarea funcție:
+
Î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="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia intoarce numarul de elemente valide din lista specificata.
+
  * Funcția intoarce numarul de elemente dintre cei doi interatori
* @param list lista pentru care se cere dimensinea.
+
  * @return numarul de elemente dintre cei doi iteratori.
  * @return numarul de elemente valide din lista list.
 
 
  */
 
  */
unsigned linkedListSize(struct LinkedList * list);
+
uint32_t distance (iterator begin, iterator end);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementarea acestei funcții se face întorcând direct valoarea câmpului <code>size</code> din structură.
+
Exemplu:
  
== Inserția ==
+
<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 inserția unui element '''value''' pe o anumită poziție '''index''' se definește următoarea funcție:
+
Pentru listele dublu înlănțuite, se definește următoarea metodă:
  
<syntaxhighlight lang="C">
+
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia inseareaza elementul value pe pozitia index in lista.
+
  * Metoda intoarce numarul de elemente din lista.
  * @param list lista in care se face insertia.
+
  * @return numarul de elemente din lista.
* @param index indexul pe care se va face insertia
 
* @param value valoarea ce trebuie inserata
 
 
  */
 
  */
void linkedListInsert(struct LinkedList * list, unsigned index, double value);
+
uint32_t size();
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Inserția unui element '''value''' pe o anumită poziție '''index''' într-o secvență implementată cu liste înlănțuite, se face urmând următorul algoritm:
+
Exemplu:
# Dacă <code>index</code> este mai mare decat <code>size</code>, se afișează un mesaj de eroare și funcția se încheie.
+
 
# Se alocă memorie pentru un nod <code>newNode</code>, unde câmpul <code>newNode->next</code> este '''NULL''' și <code>newNode->value</code> este <code>value</code>.
+
<syntaxhighlight lang="cpp">
# Dacă <code>index</code> este egal cu 0, <code>newNode->next</code> va deveni <code>firstNode</code> și <code>firstNode</code> va deveni <code>newNode</code>.
+
#include <list>
# Dacă <code>size</code> nu este egal cu 0, se folosește un pointer temporar <code>tmpNode</code> cu care se avansează până la nodul de pe poziția <code>index-1</code>. Se inserează nodul <code>newNode</code> între <code>tmpNode</code> și <code>tmpNode->next</code>:
+
#include <cstdio>
#* <code>newNode->next</code> devine <code>tmpNode->next</code> și <code>tmpNode->next</code> devine <code>newNode</code>.
+
 
# Dacă <code>index</code> este egal cu <code>size</code>, <code>lastNode</code> devine <code>newNode</code>
+
using namespace std;
# <code>size</code> se incrementează cu 1.
 
  
== Ștergerea ==
+
int main() {
 +
    list<int> intList;
 +
    intList.push_back(10);
 +
    intList.push_back(20);
 +
    intList.push_back(5);   
  
Pentru ștergerea unui element de pe o anumită poziție '''index''' se definește următoarea funcție:
+
    printf("Lista are %u elemente!\n", intList.size()); // Programul va afisa valoarea 3.
  
<syntaxhighlight lang="C">
+
    return 0;
/**
+
}
* Functia sterge elementul de pe pozitia index din lista. Se afiseaza un mesaj de eroare
 
*  daca indexul este mai mare sau egal decat size.
 
* @param list lista din care se face stergerea.
 
* @param index indexul de la care se va face stergerea
 
*/
 
void linkedListDelete(struct LinkedList * list, unsigned index);
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Ștergerea unui element de pe o anumită poziție '''index''' dintr-o secvență implementată cu liste, se face urmând următorul algoritm:
+
== Inserția ==
# Dacă <code>index</code> este mai mare sau egal decât <code>size</code>, se afișează un mesaj de eroare și funcția se încheie.
 
# Dacă <code>size</code> e 1, se eiberează memoria pentru <code>firstNode</code>, <code>firstNode</code> și <code>lastNode</code> devin '''NULL''', <code>size</code> devine 0 și funcția se încheie.
 
# Se definește un pointer temporar la un nod numit <code>oldNode</code>.
 
# Dacă index este 0, <code>oldNode</code> devine <code>firstNode</code> și <code>firstNode</code> devine <code>oldNode->next</code>
 
# Dacă index NU este 0, se folosește un pointer suplimentar numit <code>tmpNode</code> pentru a avansa în listă până pe poziția <code>index - 1</code>. <code>oldNode</code> devine <code>tmpNode->next</code> și <code>tmpNode->next</code> devine <code>oldNode->next</code>.
 
# Dacă <code>index</code> este egal cu <code>size - 1</code>, <code>lastNode</code> devine <code>tmpNode</code>
 
# Se eliberează memoria pentru <code>oldNode</code>
 
# <code>size</code> se decrementează cu 1.
 
  
== Căutarea ==
+
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:
  
Pentru căutarea unui element '''value''' într-o secvență neordonată se definește următoarea funcție:
+
<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);
  
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia cauta elementul value in lista si intoarce prima pozitie pe care apare.
+
  * Exclusiv pentru std::list si std::vector, functia intoarce un iterator la elementul cu offset pozitii mai la stanga.
*  Se intoarce -1 daca valoarea nu exista in lista.
+
  * @param current iteratorul curent, care va fi decrementat cu offset
  * @param list lista in care se face cautarea.
+
  * @param offset iteratorul deplasat cu offset poziții mai la stanga. Implicit este 1
  * @param value valoarea care se cauta.
 
* @return indexul la care apare valoarea sau -1 daca nu exista in lista.
 
 
  */
 
  */
int linkedListSearch(struct LinkedList * list, double value);
+
iterator std::prev (iterator current, int32_t offset = 1);
</syntaxhighlight>
 
  
Căutarea unui element '''value''' într-o secvență neordonată implementată cu liste, se face urmând următorul algoritm:
+
/**
# Se folosește un pointer suplimentar <code>tmpNode</code> cu care se iterează peste elementele din listă până când acesta devine '''NULL'''.
+
* Metoda insereaza elementul value pe pozitia de dupa position in lista.
# Dacă elementul din nodul <code>tmpNode</code> din listă este egal cu <code>value</code>, se întoarce valoarea din nod.
+
* @param position pozitia de dinaintea celei pe care se va face insertia
# Se întoarce valoarea -1.
+
* @param value valoarea ce trebuie inserata
 +
* @return metoda intoarce un iterator la elementul inserat
 +
*/
 +
iterator insert_after(iterator position, T value);
  
== Accesarea elementului de pe o anumită poziție ==
+
/**
 +
* 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);
  
Pentru accesarea unui element de pe poziția '''index''' dintr-o secvență se definește următoarea funcție:
+
/**
 +
* 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);
  
<syntaxhighlight lang="C">
 
 
/**
 
/**
  * Functia intoarce elementul din lista de pe poziția index. Daca index este mai mare sau egal decat size
+
  * Metoda adauga un element la inceputul listei.
*  se afiseaza un mesaj de eroare (si se întoarce 0).
+
  * @param value valoarea ce trebuie inserata
  * @param list lista in care se face accesul.
 
* @param index pozitia de la care se doreste citirea elementului.
 
* @return valoarea de la pozitia index sau 0 daca index este mai mare sau egal decat size
 
 
  */
 
  */
short linkedListGet(struct LinkedList * list, unsigned index);
+
void push_front (T value);
 +
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Accesarea unui element de pe poziția '''index''' dintr-o secvență neordonată implementată cu liste, se face urmând următorul algoritm:
+
Exemplu:
# Dacă <code>index</code> este mai mare sau egal decât <code>size</code> se afișează un mesaj de eroare și se întoarce 0.
 
# Se folosește un pointer la nod temporar numit <code>tmpNode</code> și folosind o buclă se avansează în listă până la poziția <code>index</code>.
 
# Se întoarce valoarea din nodul <code>tmpNode</code>.
 
  
== Sortarea unei secvențe implementate cu liste - ''Bubble Sort'' ==
+
<syntaxhighlight lang="cpp">
 +
#include <forward_list>
 +
#include <cstdio>
 +
#include <iterator>
  
Pentru sortarea unei secvențe se definește următoarea funcție:
+
using namespace std;
  
<syntaxhighlight lang="C">
+
int main() {
/**
+
    forward_list<int> intList;
* Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort.  
+
    intList.push_front(3);
* @param list lista care se doreste sortata.
+
    intList.push_front(2);
*/
+
    intList.push_front(1);   
void linkedListBubbleSort(struct LinkedList * list);
+
 
</syntaxhighlight>
+
    // lista e acum: {1, 2, 3}
 +
 
 +
    intList.insert_after(intList.begin(), 0); // se insereaza dupa primul element din lista o valoare de 0
  
Sortarea unei secvențe implementată cu vectori se face urmând următorul algoritm:
+
    // lista e acum: {1, 0, 2, 3}
# Se declară o variabilă <code>done</code>.
 
# Se atribuie lui <code>done</code> valoarea 1.
 
# Se folosește un pointer temporar la un nod <code>tmpNode</code> și se parcurge lista de la <code>firstNode</code> la nodul anterior lui <code>lastNode</code>
 
# Dacă elementul din nodul <code>tmpNode</code> din listă este mai mare decât elementul din nodul <code>tmpNode->next</code>, acestea se interschimbă și lui '''done''' i se atribuie valoarea 0.
 
# După terminarea iterării peste listă, dacă <code>done</code> e 0, se sare la pasul 2 (se folosește o buclă ''do-while'').
 
  
== Căutarea într-o secvență sortată implementată cu liste ==
+
    intList.insert_after(next(intList.begin()), 3); // se insereaza dupa cel de-al doilea element din lista o valoare de 3
  
Deoarece listele simplu și dublu înlănțuite nu suportă acces aleator, <span style="color: red; font-weight: bold">PE ACESTEA NU SE POATE IMPLEMENTA CĂUTAREA BINARĂ.</span>.
+
    // lista e acum: {1, 0, 3, 2, 3}
  
== Ștergerea unui <code>LinkedList</code> ==
+
    intList.push_front(-1); // se insereaza pe prima pozitie o valoare de -1
  
Pentru ștergerea unui <code>LinkedList</code> se definește următoarea funcție.
+
    // lista e acum: {-1, 1, 0, 3, 2, 3}
  
<syntaxhighlight lang="C">
+
    forward_list<int> newList;
/**
+
    newList.push_front(-1);
* Functia dezalocă memoria folosită de lista specificată.
+
    newList.push_front(-2);
* @param list lista care trebuie ștearsă.
+
    newList.push_front(-3);
*/
 
void deleteLinkedList(struct LinkedList * list);
 
</syntaxhighlight>
 
  
Ștergerea unui <code>LinkedList</code> se realizează în doi pași:
+
    // newList e acum: {-3, -2, -1}
# Se dezalocă nodurile din listă.
 
# Se dezalocă memoria alocată pentru structura de tip <code>struct LinkedList</code>.
 
  
= Exerciții =
+
    intList.insert_after(intList.begin(), newList.begin(), newList.end()); //Se insereaza dupa primul element din intList toate elementele din newList
  
== Săptămâna 1 ==
+
    // intList e acum: {-1, -3, -2, -1, 1, 0, 3, 2, 3}
  
<ol>
+
    return 0;
<li>
+
}
Se dă următorul header file <code>arrayList.h</code>:
+
</syntaxhighlight>
<syntaxhighlight lang="C">
 
#ifndef ARRAY_LIST_H
 
#define ARRAY_LIST_H
 
  
struct ArrayList {
+
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:
    short * array;    // pointer la zona de memorie alocată
 
    unsigned capacity; // dimensiunea zonei alocate
 
    unsigned size;    // numarul de elemente valide din secventa
 
};
 
  
 +
<syntaxhighlight lang="cpp">
 
/**
 
/**
  * Functia aloca memorie si creeaza un nou ArrayList cu o capacitate initiala.
+
  * Metoda insereaza elementul value pe pozitia position in lista.
  * @param initialCapacity capacitatea initiala a secventei.
+
  * @param position pozitia pe care se va face insertia
  * @return pointer la o structura de tip ArrayList.
+
* @param value valoarea ce trebuie inserata
 +
  * @return metoda intoarce un iterator la elementul inserat
 
  */
 
  */
struct ArrayList * createArrayList(unsigned initialCapacity);
+
iterator insert(iterator position, T value);
  
 
/**
 
/**
  * Functia intoarce numarul de elemente valide din lista specificata.
+
  * Metoda insereaza count elemente cu valoarea value pe pozitia position in lista.
  * @param list lista pentru care se cere dimensinea.
+
  * @param position pozitia pe care se va face insertia
  * @return numarul de elemente valide din lista list.
+
  * @param count numarul de elemente ce trebuie introduse
 +
* @param value valoarea ce trebuie inserata
 +
* @return metoda intoarce un iterator la primul element inserat
 
  */
 
  */
unsigned arrayListSize(struct ArrayList * list);
+
iterator insert(iterator position, uint32_t count, T value);
  
 
/**
 
/**
  * Functia inseareaza elementul value pe pozitia index in vector. Daca capacitatea este insuficienta
+
  * Metoda insereaza toate elementele dintre iteratorii first inclusiv si last exclusiv pe pozitia position in lista.
  * se face realocare. Se afiseaza un mesaj de eroare daca indexul este mai mare decat size.
+
  * @param position pozitia pe care se va face insertia
  * @param list lista in care se face insertia.
+
  * @param first iteratorul de start
  * @param index indexul pe care se va face insertia
+
  * @param last iteratorul de final
  * @param value valoarea ce trebuie inserata
+
  * @return metoda intoarce un iterator la primul element inserat
 
  */
 
  */
void arrayListInsert(struct ArrayList * list, unsigned index, short value);
+
iterator insert(iterator position, iterator first, iterator last);
  
 
/**
 
/**
  * Functia sterge elementul pe pozitia index in vector. Se afiseaza un mesaj de eroare
+
  * Metoda adauga un element la sfarsitul listei.
*  daca indexul este mai mare decat (size - 1).
+
  * @param value valoarea ce trebuie inserata
  * @param list lista din care se face stergerea.
 
* @param index indexul de la care se va face stergerea
 
 
  */
 
  */
void arrayListDelete(struct ArrayList * list, unsigned index);
+
void push_back (T value);
  
 
/**
 
/**
  * Functia cauta elementul value in vector si intoarce prima pozitie pe care apare.
+
  * Metoda adauga un element la inceputul listei.
*  Se intoarce -1 daca valoarea nu exista in vector.
+
  * @param value valoarea ce trebuie inserata
* @param list lista in care se face cautarea.
 
  * @param value valoarea care se cauta.
 
* @return indexul la care apare valoarea sau -1 daca nu exista in vector.
 
 
  */
 
  */
int arrayListSearch(struct ArrayList * list, short value);
+
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">
 
/**
 
/**
  * Functia intoarce elementul din vector de pe poziția index. Daca index este mai mare decat (size - 1) se afiseaza
+
  * Metoda sterge elementul de dupa pozitia position din lista.
*  un mesaj de eroare (si se întoarce 0).
+
  * @param position pozitia de dinaintea celei de la care se va face stergerea
* @param list lista in care se face accesul.
+
  * @return iterator la elementul ce urmeaza celui sters
  * @param index pozitia de la care se doreste citirea elementului.
 
  * @return valoarea de la pozitia index sau 0 daca index este mai mare decat (size - 1)
 
 
  */
 
  */
short arrayListGet(struct ArrayList * list, unsigned index);
+
iterator erase_after(iterator position);
  
 
/**
 
/**
  * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort.  
+
  * Metoda sterge toate elementele dintre pozitiile first si last din lista, exclusiv.
  * @param list lista care se doreste sortata.
+
  * @param first pozitia de unde incepe stergerea
 +
* @param last pozitia unde se termina stergerea
 +
* @return iterator la elementul ce urmeaza ultimului element sters
 
  */
 
  */
void arrayListBubbleSort(struct ArrayList * list);
+
iterator erase_after(iterator first, iterator last);
  
 
/**
 
/**
  * Functia cauta elementul value in secventa list sortata crescator.
+
  * Metoda sterge primul element din lista (opusul lui push_front).
*    Daca secventa nu este sortata, comportamentul nu este definit.
 
* @param list lista in care se cauta.
 
* @param value valoarea cautata in secventa.
 
* @return indexul unde s-a găsit valoarea value sau -1 daca valoarea nu exista.
 
 
  */
 
  */
int arrayListBinarySearch(struct ArrayList * list, short value);
+
void pop_front();
  
 
/**
 
/**
  * Functia dezalocă memoria folosită de lista specificată.
+
  * Metoda sterge toate elementele din lista.
* @param list lista care trebuie ștearsă.
 
 
  */
 
  */
void deleteArrayList(struct ArrayList * list);
+
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}
  
#endif
+
    intList.erase_after(next(intList.begin(), 2)); // se sterge elementul de pe indexul 3 (a patra valoare)
</syntaxhighlight>
 
  
Implementați într-un fișier sursă C funcțiile definite în header.
+
    // lista e acum {2, 3, 4}
</li>
 
<li>Folosind structura și funcțiile definite în header, scrieți un program simplu care să efectueze următoarele operații:
 
* definiți un <code>ArrayList</code> de capacitatea initiala 3.
 
* adăugați 7 elemente: 6, 10, 0, -5, 4, 16, 20 (utilizați arrayListInsert cu indexul 0 de fiecare dată).
 
* căutați valoarea 4 și afișați indexul pe care apare.
 
* inserați valoarea 9 la indexul 5.
 
* afișați valoarea de la indexul 5.
 
* sortați vectorul.
 
* căutați valoarea 16 și afișați indexul la care apare.
 
* afișați conținutul secvenței.
 
* ștergeți secvența.
 
</li>
 
</ol>
 
  
== Săptămâna 2 ==
+
    intList.erase_after(intList.begin(), intList.end()); // se sterg toate valorile dintre indexul 1 si sfarsit (exclusiv)
  
<ol>
+
    // lista e acum {2}
<li>
 
Se dă următorul header file <code>linkedList.h</code>:
 
<syntaxhighlight lang="C">
 
#ifndef LINKED_LIST_H
 
#define LINKED_LIST_H
 
  
struct ListNode {
+
     intList.clear();
     double value;
 
    struct ListNode * next;
 
};
 
  
struct LinkedList {
+
    // lista e acum goala: {}
    struct ListNode * firstNode;
 
    struct ListNode * lastNode;
 
    unsigned size;
 
};
 
  
 +
    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">
 
/**
 
/**
  * Functia aloca memorie si creeaza un nou LinkedList.
+
  * Metoda sterge elementul pe pozitia position din lista.
  * @return pointer la o structura de tip LinkedList.
+
* @param position pozitia de la care se va face stergerea
 +
  * @return iterator la elementul ce urmeaza celui sters
 
  */
 
  */
struct LinkedList * createLinkedList();
+
iterator erase(iterator position);
  
 
/**
 
/**
  * Functia intoarce numarul de elemente valide din lista specificata.
+
  * Metoda sterge toate elementele dintre pozitiile first si last din lista.
  * @param list lista pentru care se cere dimensinea.
+
  * @param first pozitia de unde incepe stergerea
  * @return numarul de elemente valide din lista list.
+
* @param last pozitia unde se termina stergerea
 +
  * @return iterator la elementul ce urmeaza ultimului element sters
 
  */
 
  */
unsigned linkedListSize(struct LinkedList * list);
+
iterator erase(iterator first, iterator last);
  
 
/**
 
/**
  * Functia insereaza elementul value pe pozitia index in lista. Se afiseaza un
+
  * Metoda sterge ultimul element din lista (opusul lui push_back).
*  mesaj de eroare daca indexul este mai mare decat size.
 
* @param list lista in care se face insertia.
 
* @param index indexul pe care se va face insertia
 
* @param value valoarea ce trebuie inserata
 
 
  */
 
  */
void linkedListInsert(struct LinkedList * list, unsigned index, double value);
+
void pop_back();
  
 
/**
 
/**
  * Functia sterge elementul de pe pozitia index din lista. Se afiseaza un mesaj de eroare
+
  * Metoda sterge primul element din lista (opusul lui push_front).
*  daca indexul este mai mare sau egal decat size.
 
* @param list lista din care se face stergerea.
 
* @param index indexul de la care se va face stergerea
 
 
  */
 
  */
void linkedListDelete(struct LinkedList * list, unsigned index);
+
void pop_front();
  
 
/**
 
/**
  * Functia cauta elementul value in lista si intoarce prima pozitie pe care apare.
+
  * Metoda sterge toate elementele din lista.
*  Se intoarce -1 daca valoarea nu exista in lista.
 
* @param list lista in care se face cautarea.
 
* @param value valoarea care se cauta.
 
* @return indexul la care apare valoarea sau -1 daca nu exista in lista.
 
 
  */
 
  */
int linkedListSearch(struct LinkedList * list, double value);
+
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 intoarce elementul din lista de pe poziția index. Daca index este mai
+
  * Functia cauta elementul value in lista intre iteratorii first inclusiv si last exclusiv și intoarce un iterator la elementul gasit
  * mare sau egal decat size se afiseaza un mesaj de eroare (si se întoarce 0).
+
*  Se intoarce last daca elementul nu a fost gasit.
  * @param list lista in care se face accesul.
+
  * @param first pozitia de start pentru cautare (inclusiv)
  * @param index pozitia de la care se doreste citirea elementului.
+
  * @param last pozitia de final pentru cautare (exclusiv)
  * @return valoarea de la pozitia index sau 0 daca index este mai mare sau egal decat size
+
  * @param value valoarea cautata
 +
  * @return indexul la care apare valoarea sau last daca nu exista in interval.
 
  */
 
  */
double linkedListGet(struct LinkedList * list, unsigned index);
+
iterator std::find(iterator first, iterator last, T value);
  
 
/**
 
/**
  * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort.  
+
  * Functia cauta primul element care satisface predicatul predicateFunction intre iteratorii first inclusiv si last exclusiv și
  * @param list lista care se doreste sortata.
+
*  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.
 
  */
 
  */
void linkedListBubbleSort(struct LinkedList * list);
+
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">
 
/**
 
/**
  * Functia dezalocă memoria folosită de lista specificată.
+
  * Metoda sorteaza crescator elementele din lista.  
* @param list lista care trebuie ștearsă.
 
 
  */
 
  */
void deleteLinkedList(struct LinkedList * list);
+
void std::sort();
  
#endif
+
/**
 +
* Metoda sorteaza elementele din lista conform comparatorului comp.
 +
* @param comp comparatorul folosit pentru sortare (implementeaza relatia de ordine)
 +
*/
 +
void std::sort(Comparator comp);
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Implementați într-un fișier sursă C funcțiile definite în header.
+
Funcțiile de tip Comparator sunt definite astfel:
</li>
+
 
<li>Folosind structura și funcțiile definite în header, scrieți un program simplu care să efectueze următoarele operații:
+
<syntaxhighlight lang="cpp">
* definiți un <code>LinkedList</code>.
+
/**
* adăugați 7 elemente: 6, 10, 0, -5, 4, 16, 20 (utilizați linkedListInsert cu indexul 0 de fiecare dată).
+
* Functia intoarce true daca first trebuie plasat in fata lui last in secventa.
* căutați valoarea 4 și afișați indexul pe care apare.
+
*/
* inserați valoarea 9 la indexul 5.
+
bool compare (T first, T last);
* afișați valoarea de la indexul 5.
+
</syntaxhighlight>
* sortați vectorul.
+
 
* căutați valoarea 16 și afișați indexul la care apare.
+
Exemplu:
* afișați conținutul secvenței.
+
 
* ștergeți secvența.
+
<syntaxhighlight lang="cpp">
</li>
+
#include <algorithm>
</ol>
+
#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>

Versiunea curentă din 20 octombrie 2023 09:57

Î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:

  1. Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
  2. 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ă).
  3. Elementele stocate în secvență sunt de același fel.

Secvența suportă următoarele operații de bază:

  1. Interogarea numărului de elemente din secvență.
  2. Inserția unui element pe o anumită poziție în secvență.
  3. Ștergerea unui element de pe o anumită poziție din secvență.
  4. Căutarea unui element în secvență (căutare care va întoarce primul index pe care apare elementul în structură).
  5. Accesarea unui element de pe o anumită poziție.
  6. 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 std::vector. Această clasă este un template care poate fi folosit pentru stocarea de elemente de diferite tipuri.

Crearea unui std::vector

Pentru crearea unei vector nou se pot utiliza doi constructori:

/**
 * 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);

Exemplu:

#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;
}

Interogarea dimensiunii

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

/**
 * Metoda intoarce numarul de elemente valide din vector.
 * @return numarul de elemente valide din vector.
 */
uint32_t size();

Exemplu:

#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;
}

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: begin() și end(). Primul reprezintă adresa primului element din vector, iar al doilea reprezintă adresa DE DUPĂ ultimul element din vector.

/**
 * 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);

Exemplu:

#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;
}

Ștergerea

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

/**
 * 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();

Exemplu:

#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;
}

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:

/**
 * 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);

Metoda operator[] 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 at face și verificarea limitelor vectorului pentru a evita un Segmentation Fault.

Exemplu:

#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;
}

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):

/**
 * 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);


Exemplu:

#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;
}

Sortarea unei secvențe implementate cu vectori

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

/**
 * 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);

Funcțiile de tip Comparator sunt definite astfel:

/**
 * Functia intoarce true daca first trebuie plasat in fata lui last in secventa.
 */
bool compare (T first, T last);

Exemplu:

#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");
}

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 std::forward_list, iar cea pentru liste dublu înlănțuite este std::list. 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 std::forward_list sau std::list

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

/**
 * 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);

Exemplu:

#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;
}

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ă std::distance, 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ță: begin() și end(). 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.

/**
 * 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);

Exemplu:

#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;
}

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

/**
 * Metoda intoarce numarul de elemente din lista.
 * @return numarul de elemente din lista.
 */
uint32_t size();

Exemplu:

#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;
}

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, std::next și std::prev, definite în header-ul iterator care întorc acest iterator deplasat:

/**
 * 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);

Exemplu:

#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;
}

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:

/**
 * 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);

Exemplu:

#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;
}

Ș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:

/**
 * 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();

Exemplu:

#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;
}

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

/**
 * 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();

Exemplu:

#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;
}

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:

#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;
}

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):

/**
 * 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);


Exemplu:

#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;
}

Sortarea unei secvențe implementate cu liste

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

/**
 * 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);

Funcțiile de tip Comparator sunt definite astfel:

/**
 * Functia intoarce true daca first trebuie plasat in fata lui last in secventa.
 */
bool compare (T first, T last);

Exemplu:

#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");
}