Biblioteca de șabloane standard

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 august 2022; verificarea necesită 1 editare .

Biblioteca de șabloane standard (STL) ( Biblioteca de șabloane standard în engleză ) este un set de algoritmi generici consecvenți , containere , mijloace de accesare a conținutului acestora și diverse funcții de ajutor în C++ .

Biblioteca de șabloane standard, înainte de a fi inclusă în standardul C++ , a fost o dezvoltare terță parte, mai întâi de către HP și mai târziu de către SGI . Standardul de limbă nu îl numește „STL”, deoarece această bibliotecă a devenit parte integrantă a limbii, cu toate acestea, mulți oameni încă folosesc acest nume pentru a o deosebi de restul bibliotecii standard (fluxuri I/O ( iostream ), subsecțiunea C etc.).

Un proiect numit STLPort , bazat pe SGI STL, menține actualizate clasele STL, iostream și șiruri. Câteva alte proiecte dezvoltă, de asemenea, utilizări private ale bibliotecii standard pentru diverse sarcini de proiectare. Fiecare producător de compilatoare C++ trebuie să furnizeze o implementare a acestei biblioteci, deoarece este o parte foarte importantă a standardului și este utilizată pe scară largă.

Arhitectura STL a fost proiectată de Alexander Stepanov și Meng Li.

Structura bibliotecii

Biblioteca are cinci componente principale:

Container ( container în engleză ) - stocarea unui set de obiecte în memorie.
Iterator ( iterator în engleză ) - oferind mijloace de acces la conținutul containerului.
Un algoritm este o definiție a unei proceduri de calcul.
Adaptor ( adaptor în engleză ) - adaptarea componentelor pentru a oferi o interfață diferită.
Obiect funcțional ( functor în engleză ) - ascunderea unei funcții într-un obiect pentru a fi utilizată de alte componente.

Separarea vă permite să reduceți numărul de componente. De exemplu, în loc să scrieți o funcție separată de căutare a elementelor pentru fiecare tip de container, este furnizată o singură versiune care funcționează cu fiecare dintre ele, atâta timp cât cerințele de bază sunt îndeplinite.

Containere

Containerele STL pot fi împărțite în patru categorii: containere secvențiale, asociative, containere adaptoare și pseudo-containere.

Container	Descriere
Containere secvențiale
vector [1]	Matrice de acces aleatoriu dinamic asemănătoare C cu redimensionare automată atunci când elementul este adăugat/eliminat. Acces prin index pentru . Adăugarea/eliminarea unui element la sfârșitul unui vector necesită timp amortizat, aceeași operație la începutul sau la mijlocul unui vector durează . Sortare rapidă standard pentru . Căutarea unui element prin iterație necesită . Există o specializare a șablonului vectorial pentru tipul bool , care necesită mai puțină memorie prin stocarea elementelor ca biți, dar nu acceptă toate caracteristicile iteratoarelor. $O(1)$ $O(1)$ $Pe)$ $O(n\log(n))$ $Pe)$
lista [2]	O listă dublu legată ale cărei elemente sunt stocate în bucăți arbitrare de memorie, spre deosebire de un container vectorial în care elementele sunt stocate într-o zonă adiacentă a memoriei. Căutarea după enumerare este mai lentă decât cea a unui vector datorită timpului mai lung de acces la elemente. Acces prin index pentru . Oriunde în container, inserarea și ștergerea sunt foarte rapide - în . $Pe)$ $O(1)$
punte [3]	Coadă cu două fețe . Un container este ca un vector, dar are capacitatea de a introduce și elimina rapid elemente la ambele capete în . Implementat ca o listă dublu legată de tablouri liniare . Pe de altă parte, spre deosebire de vector, un deque nu garantează că toate elementele sale vor fi localizate în memoria contiguă , ceea ce face imposibilă utilizarea în siguranță a aritmeticii pointerului [4] pentru a accesa elementele unui container [5] [6] . $O(1)$
Containere asociative
a stabilit	Un set ordonat de elemente unice. La inserarea/eliminarea elementelor unui set, iteratoarele care indică elementele acestui set nu devin invalide. Oferă operații standard pe mulțimi precum unire, intersecție, scădere. Tipul de element al setului trebuie să implementeze un operator de comparație operator<sau trebuie furnizată o funcție de comparație. Implementat pe baza unui arbore de căutare binar cu auto-echilibrare .
multiset	La fel ca setul, dar vă permite să stocați elemente duplicate.
Hartă	O matrice asociativă ordonată de perechi de elemente constând din chei și valorile corespunzătoare acestora. Cheile trebuie să fie unice. Ordinea elementelor este determinată de taste. În acest caz, tipul de cheie trebuie să implementeze operatorul de comparație operator<sau trebuie să furnizați o funcție de comparare.
multihartă	La fel ca harta, dar vă permite să stocați mai multe chei identice.
Recipiente adaptoare
grămadă	O stivă este un container în care sunt adăugate și îndepărtate elemente de la un capăt.
coadă	O coadă este un container, de la un capăt al căruia puteți adăuga elemente, iar din celălalt - le scoateți.
priority_queue	O coadă cu prioritate organizată astfel încât cel mai mare element să fie întotdeauna pe primul loc.
Pseudo containere
set de biți	Folosit pentru depozitarea măștilor de biți. Pare o vector<bool>dimensiune fixă. Mărimea este fixă atunci când obiectul set de biți este declarat. Nu există iteratoare în set de biți. Optimizat pentru dimensiunea memoriei.
șir_de_bază	Un container pentru depozitarea și prelucrarea șirurilor. Stochează elemente într-un rând în memorie ca un singur bloc, ceea ce vă permite să organizați accesul rapid la întreaga secvență. Articolele trebuie să fie POD-uri . Concatenarea este definită cu +.
valarray	Șablonul este folosit pentru a stoca matrice numerice și este optimizat pentru a obține performanțe de calcul crescute. Oarecum similar cu vector, dar îi lipsesc majoritatea operațiunilor standard ale containerului. Operațiile sunt definite pe două valarray și pe un valarray și un scalar (din punct de vedere al elementelor). Aceste operațiuni pot fi implementate eficient atât pe procesoare vectoriale, cât și pe procesoare scalare cu blocuri SIMD .

Containerele folosesc semantica obiect după valoare pentru a stoca elemente. Cu alte cuvinte, atunci când este adăugat, containerul primește o copie a elementului. Dacă efectuarea unei copii nu este de dorit, atunci se folosește un container de pointeri de element. Elementele sunt atribuite folosind operatorul de atribuire și sunt distruse folosind destructorul. Tabelul prezintă cerințele de bază pentru elementele din containere:

Metodă	Descriere	Notă
constructor de copiere	Creează un nou element identic cu cel vechi	Folosit de fiecare dată când un element este introdus într-un container
operator de atribuire	Înlocuiește conținutul unui element cu o copie a elementului original	Folosit de fiecare dată când elementul este modificat
Destructor	Distruge elementul	Folosit de fiecare dată când un element este îndepărtat
Constructor implicit	Creează un element fără argumente	Se aplică numai pentru anumite operațiuni.
operator==	Compară două elemente	Folosit când se face operator== pe două containere
operator<	Stabilește dacă un element este mai mic decât altul	Folosit la executarea operator< pe două containere

Toate containerele standard „pline” satisfac un anumit set de cerințe (sau convenții). Tabelul de mai jos presupune că C este o clasă de container care conține obiecte de tip T.

Expresie	tip de returnare	Complexitate	Notă
C::tip_valoare	T	Timp de compilare
C::referință	T	Timp de compilare
C::const_reference		Timp de compilare
C::indicator	Tip de indicator care indică spre C::reference	Timp de compilare	Indicator către T
C::iterator	Tip de iterator care indică către C::reference	Timp de compilare	Un iterator de orice tip, altul decât un iterator de ieșire
C::const_iterator	Tip de iterator care indică C::const_reference	Timp de compilare	Un iterator de orice tip, altul decât un iterator de ieșire
C::tip_dimensiune	Tip întreg fără semn	Timp de compilare
Cobj;		Constant	După: obj.size() == 0
C obj1; obj1 = obj2;		Liniar	După: obj1 == obj2
Cobj; (&obj)->~C();	Rezultatul nu este folosit	Liniar	După: obj.size() == 0.
obj.begin()		Constant
obj.end()		Constant
obj1 == obj2	Reversibilă la bool	Liniar
obj1 != obj2	Reversibilă la bool	Liniar
obj.size()	tipul marimii	Depinde de tip	Nu este recomandat pentru a verifica dacă un recipient este gol
obj.empty()	Reversibilă la bool	Constant
obj1 < obj2	Reversibilă la bool	Liniar
obj1 > obj2	Reversibilă la bool	Liniar
obj1 <= obj2	Reversibilă la bool	Liniar
obj1 >= obj2	Reversibilă la bool	Liniar
obj.swap(obj2)	gol	Constant

Iteratori

Biblioteca STL folosește o abstractizare generalizată numită iterator ca intermediar pentru a accesa elemente . Fiecare container menține „propriul” tip de iterator, care este un indicator inteligent „modernizat” [7] care „știe” cum să acceseze elementele unui anumit container. Standardul C++ definește cinci categorii de iteratoare, descrise în următorul tabel:

Categorie	Operațiuni suportate	Notă
Intrare	operator++, operator*, operator->, constructor de copiere, operator=, operator==, operator!=	Oferă acces de citire într-o singură direcție. Vă permite să efectuați o atribuire sau o copiere folosind operatorul de atribuire și constructorul de copiere.
Weekend-uri	operator++, operator*, constructor de copiere	Oferă acces de scriere într-o singură direcție. Ele nu pot fi comparate pentru egalitate.
Unidirecțional	operator++, operator*, operator->, constructor de copiere, constructor implicit, operator=, operator==, operator!=	Oferă acces de citire și scriere în aceeași direcție. Vă permite să efectuați o atribuire sau o copiere folosind operatorul de atribuire și constructorul de copiere. Ele pot fi comparate pentru egalitate.
Bidirecțional	operator++, operator--, operator*, operator->, constructor de copiere, constructor implicit, operator=, operator==, operator!=	Acceptă toate funcțiile descrise pentru iteratoarele unidirecționale (vezi mai sus). În plus, vă permit să navigați la elementul anterior.
acces aleatoriu	operator++, operator--, operator*, operator->, constructor de copiere, constructor implicit, operator=, operator==, operator!=, operator+, operator-, operator+=, operator-=, operator<, operator>, operator < =, operator>=, operator[]	Echivalent cu indicatorii obișnuiți: suport aritmetica pointerului, sintaxa de indexare a matricei și toate formele de comparație.

Vezi și

Note

↑ std::vector . Data accesului: 14 februarie 2016. Arhivat din original pe 27 noiembrie 2015. (nedefinit)
↑ std:list
↑ std::deque . Consultat la 14 februarie 2016. Arhivat din original pe 5 februarie 2016. (nedefinit)
↑ Sintaxa pointerilor în C++ . Preluat la 14 februarie 2016. Arhivat din original la 11 martie 2016. (nedefinit)
↑ Bibliotecă iteratoare (link descendent) . Consultat la 14 februarie 2016. Arhivat din original pe 5 februarie 2016. (nedefinit)
↑ Concepte C++: Iterator . Consultat la 14 februarie 2016. Arhivat din original pe 19 februarie 2016. (nedefinit)
↑ Tipuri de iterator: Ieșire vs. intrare vs. înainte vs. Iterator cu acces aleatoriu . Consultat la 14 februarie 2016. Arhivat din original pe 23 februarie 2016. (nedefinit)

Link -uri

Sursă de referință pentru clasa și metoda SGI STL
STL pas cu pas (rus.) - articole de Artem Kaev
Bazele C++. Biblioteca STL Arhivată 27 februarie 2007 la Wayback Machine (rusă) - arhiva listei de corespondență
STL - Biblioteca de șabloane standard. Ghidul programatorului C++ (rus.) - ghid detaliat
Utilizarea STL în C++ (rusă)

Literatură

Scott Meyers. Utilizarea eficientă a STL = STL efectiv. - Petru, 2002. - S. 224 . — (Biblioteca programatorului). — ISBN 5-94723-382-7 .
David R. Musser, Gilmer J. Durge, Atul Seini. C++ și STL: Ghid de referință = Tutorial STL și Ghid de referință: Programare C++ cu șablonul standard. — ediția a II-a. - M. : "Williams" , 2010. - S. 432. - (C ++ în seria Depth). — ISBN 5-89818-027-3 .
Leen Ammeral. STL pentru programatorii C++ = STL pentru programatorii C++. - DMK Press, 1999. - P. 240. - ISBN 5-256-00704-1 .

C++
C++98 C++03 C++11 C++14 C++17 C++20 C++23
Particularități	Supraîncărcarea funcției Supraîncărcarea operatorului Șabloane moștenire virtuală Legături Regula de trei POD SFINAE
Unele biblioteci	Biblioteca standard STL Boost POCO Qt
Compilatoare	Borland C++ C++ Builder cfront Zăngăni GCC Compilatorul Intel C++ Visual C++ deschide watcom
influențat	C# D Java C++ gestionat Rugini Vala
Categoria C++