Etichete: nicio etichetă

Descriere Generală

Listele din STL sunt liste alocate dinamic dublu înlănțuite și circulare. Acestea au avantajul că ștergerile și inserările se fac în O(1) ÎNSĂ ele nu sunt secvențiale astfel încât nu se pot accesa la o poziție oarecare (random-access), fiind nevoie să se parcurgă până la acea poziție.

Declarare și caracteristici specific

Ca și celelalte containăre STL, sunt vide inițial dacă nu cumva se inițializează.

list<int> v;
  • Adăugarea în coada și stergerea se realizează cu tradiționalele v.push_back() și v.pop_back()
list<int> v;
v.push_back(5);
// v={5};
v.pop_back();
// v={};
  • Parcurgerea unei liste

Parcurgerea se realizează cu un iterator specific.

list<tip_de_date>::iterator it;
  • Iteratorul Stergere Si Inserare

Diferența dintre iteratorii de la alte containăre unde iteratorii se devalizează în momentul alterări conținutului din interiorul containerului, în momentul inserării pe poziția iteratorului, el rămâne pe elementul care avea inițial poziția unde s-a inserat.

list<int> v={2,4,6};
list<int>::iterator it=v.begin();
//*it=2
it++; //incrementez | avansez advance(it,1);
//*it=4
v.insert(it,10);
//v={2,10,4,6}, *it=4

IAR În cazul ștergerii iteratorul se invalidează fiind nevoie reparcurgerea pana la acea pozitie SAU folosirea unui iterator secundar care va fi folosit pentru reținerea adresei imediat anterioare sau următoare.

  • În exemplul de mai jos vom șterge toate elementele pare.
list<int> v={2,4,6,5,9,21,34,35,74,101};
list<int>::iterator it=v.begin(),itt=v.begin();
for(;it!=v.end();it++)
//*it=2
if(*it%2==0)
{
    itt=it,itt++,v.erase(it);
    //it==NULL
    it=itt;
}
// v={5,9,21,34,101}

Atentie v.end() este ultima pozitie din listă, care este nullă ASTFEL ÎNCÂT nu se consideră element v.end() deși când it=v.end() și se incerementează ajunge înapoi la v.begin() deci este un caz particular.

Liste cu mai multe valori într-un element:

Exemple de liste:

list<pair<int,int>> v={{1,2},{2,10}};
list<pair<int,int>>::iterator it=v.begin();

Se acesează cu:

it->first, it->second;

SAU

struct data
{
    string s;
    int n;
}
list<data> v;
list<data>::iterator it;
it->s,it->n;

Algoritmi și Funcții

.front() - primul element
.back() - ultimul element
.clear() - golește lista
.emplace() - membru vechi depreciate datorita aparitiei make_pair()
.splice() - membru care transferă elementele dintr-o listă în alta, le șterge din sursa și le adauăgă la poziția x în cealaltă listă.
.remove() - elimină elementele cu o anumită valoare x
.remove_if() - elimină elementele care respectă o condiție specificată 
.unique() - elimină elementele duplicate.
sort() - nu are nevoie de introducere
reverse - inverseaza
.merge() - interclasează 2 liste ordonate crescător // v.merge(w)