22710 afișări Candale Silviu (silviu) 20.11.2020 www.pbinfo.ro
Etichete: STL

Standard Template Library reprezintă un ansamblu de mecanisme scrise în C++ pentru gestionarea eficientă a unor colecții de date, împreună cu algoritmi eficienți care prelucrează aceste date. Este parte a Bibliotecii Standard C++, fiind astfel disponibilă în orice compilator care respectă standardul C++.

Introducere

STL are trei componente fundamentale: containerele, iteratorii și algoritmii, precum și o serie de componente suplimentare: containerele speciale, functorii, alocatorii.

Containerele

Containerele sunt obiecte care conțin date (de orice tip, putând fi la rândul containere). Alocarea memoriei pentru conținutul containerelor se face automat (de regulă dinamic), de către container.

Containerele sunt de două tipuri: containere secvențiale și containere asociative.

Containerele secvețiale gestionează un ansamblu de elemente dispuse strict liniar. Fiecare element al containerului are o poziție bine stabilită, care nu depinde de valoarea elementului. Avem următoarele contaniere secvențiale:

  • vector – gestionează o secvență de elemente asemănătoare tablourilor standard C;
  • deque (double-ended queue)- este o coadă cu operații rapide de adăugare și eliminare la ambele capete;
  • list – gestionează o listă alocată dinamic, oferind operațiile de bază cu aceasta.

Timpul necesar pentru operațiile uzuale asupra containerelor secvențiale este redat mai jos:

Operație vector deque list
Accesarea primului element constant constant constant
Accesarea ultimului element constant constant constant
Accesarea unui element oarecare constant constant liniar
Adăugare/ștergere la început liniar constant constant
Adăugare/ștergere la sfârșit constant constant constant
Adăugare/ștergere oarecare liniar liniar constant

Containerele asociative sunt structuri de date în care fiecare element are asociată o anumită cheie și are o anumită valoare. Ordinea elementelor în container depinde de cheie și se poate schimba în funcție de celelalte elemente. Aceste containere implementează eficient operațiile de adăugare de noi elemente, ștergere a elementelor în funcție de cheie, precum și căutarea elementelor după cheie.

Sunt două familii de containere asociative:

  • set – în care cheia și valoarea elementelor sunt identice; containerele de acest tip sunt:
    • set – memorează elemente distincte; elementele sunt menținute în ordine (strict) crescătoare;
    • multiset – elementele pot fi egale și sunt menținute în ordine crescătoare;
    • unordered_set – memorează elemente distincte; nu este garantată o anumită ordine a elementelor;
    • unordered_multiset – elementele pot fi egale și nu este garantată o anumită ordine a elementelor
  • map – cheile și valorile diferă; accesul la elemente se face prin intermediul cheii; containerele de acest tip sunt:
    • map – cheile sunt distincte; elementele sunt menținute în ordine (strict) crescătoare a cheilor;
    • multimap – cheile pot fi egale și sunt menținute în ordinea crescătoare a cheilor;
    • unordered_map – cheile sunt distincte; nu este garantată o anumită ordine a elementelor;
    • unordered_map – cheile pot fi egale și nu este garantată o anumită ordine a elementelor.

Timpii necesari pentru operațiile de adăugare, ștergere și acces sunt logaritmici pentru containerele asociative care menține elementele ordonate și constanți pentru containerele care nu mențin elementele în ordine.

Iteratorii

Iteratorii reprezintă o generalizare a conceputului de pointer. Ei oferă acces la elementele containerelor într-o manieră uniformă, pentru toate containere și pentru toți algoritmii STL.

Operațiile cu iteratorii sunt similare cu operațiile cu pointeri, putându-i dereferenția, incrementa/decrementa, compara, aduna cu întreg, etc. Unele operații sunt disponibile pentru toți iteratorii, altele doar pentru cei ai unor anumite tipuri de container.

Algoritmii

Algoritmii prelucrează colecții de elemente. Aceste colecții pot fi containere, părți ale unor containere sau slte structuri de date care permit lucrul cu pointeri (de exemplu tablouri standard C).

Algoritmii sunt folosiți sub formă de funcții, iar prelucrările pe care le fac sunt diverse: sortări, căutări, modificări, etc.

Containere speciale

Containerele speciale sunt:

  • bitset – folosit pentru manipularea eficientă a șirurilor de biți
  • containere adaptor – acoperă necesități speciale și sunt create pornind de la containere standard: containerele stack și queue permit gestionarea ușoară a unei stive, respectiv a unei cozi și sunt create pe baza containerului deque, iar containerul priority_queue gestionează o coadă de priorități (heap) și este creat pe baza clasei vector.

Functori și alocatori

Functorii sunt obiecte care se folosesc în maniera unui apel de funcție. Sunt folosite frecvent în cadrul algoritmilor.

Alocatorii sunt obiecte care gestionează alocarea memoriei pentru orice obiect și, în particular, pentru obiectele care fac parte dintr-un container.


22710 afișări Candale Silviu (silviu) 20.11.2020 www.pbinfo.ro