Biblioteca de șabloane standard
Biblioteca de șabloane standard ( STL ) este o bibliotecă software inclusă în biblioteca standard de limbaj C ++ și definește structurile de date generice, iteratorii și algoritmii generici.
Descriere
Biblioteca de șabloane standard (STL) este o bibliotecă software pentru limbajul de programare C ++ care a fost o influență majoră în realizarea bibliotecii standard C ++. Oferă patru componente: algoritmi ( algoritmi ), containere (containere), funcții ( funcții ) și iteratori ( iteratori - o generalizare a pointerilor ).
STL oferă un set de clase C ++. cum ar fi containere și tablouri asociative , care pot fi utilizate cu orice tip de date - fie ele predefinite sau construite de utilizator - care acceptă unele instrucțiuni elementare (copiere, atribuire etc.). Algoritmii implementați în STL sunt independenți de containere, ceea ce reduce semnificativ complexitatea bibliotecii.
STL se bazează pe șabloane , o abordare care permite polimorfismul în timp de compilare, care este mult mai eficient decât polimorfismul în timpul rulării. STL a fost prima bibliotecă de algoritmi generici și structuri de date pentru C ++; se bazează pe patru idei de bază : programare generică, abstractizare fără pierderi de eficiență, modelul de procesare Von Neumann și semantica valorilor.
Istorie
Bibliotecile de șabloane standard (STL) au fost proiectate și dezvoltate la Hewlett-Packard de Alexander Stepanov și Meng Lee și au fost incluse în standardul ANSI / ISO în 1995.
Cuprins
Containere
Containerele STL sunt împărțite în secvențiale și asociative. La rândul său, o parte a containerelor secvențiale poate fi definită ca adaptoare, deoarece acestea sunt de fapt interfețe reduse și specializate ale containerelor principale care nu implementează iteratoare în interfața lor. Containerele secvențiale standard includ vector , listă și deque . Și includ adaptoare coadă , prioritate_coadă și stivă . Containerele asociative sunt setate , multiset , hartă și multimap .
| Recipient | Descriere |
|---|---|
| Secvențial | |
| vector | o matrice dinamică , similară matricei C (de exemplu, capabilă de acces aleatoriu ) cu capacitatea de a se redimensiona automat din cauza inserării sau ștergerii elementelor. Elementele sunt stocate pe o porțiune continuă de memorie. Inserarea și eliminarea elementelor din / din vectorul din coadă se face în timp constant (O (1)). Introducerea și îndepărtarea la început sau în centru și căutarea se fac în timp liniar (O (n)). |
| listă | o listă bidirecțională; articolele nu sunt stocate în memoria continuă. Din acest motiv, nu este posibil să accesați direct un element din lista de acces aleatoriu , dar este necesar să faceți acest lucru prin utilizarea unui iterator . Accesul la elemente se efectuează apoi cu timp liniar (O (n)), precum și cu căutarea, totuși operațiile de inserare și ștergere se efectuează în timp constant (O (1)). |
| Asociativi | |
| a stabilit | un set ordonat care nu permite duplicate; inserarea și ștergerea elementelor într-un set nu invalidează indicarea iteratorilor în set. Operațiile sunt unire, intersecție, diferență, diferență simetrică și testul de includere. |
| multiset | în ceea ce privește setul, dar permite elemente duplicate. |
| Hartă | o matrice asociativă ordonată în raport cu cheia; permite maparea unei date (cheie) asociate alteia (valoare). Ambele tipuri de date pot fi definite de utilizator. Permite căutări rapide cu privire la cheie, accesul la date are un timp logaritmic (O (jurnal n)). Nu vă permite să atribuiți mai multe chei unei singure valori. |
| multimapă | în ceea ce privește harta, dar permite duplicarea cheilor. |
| hash_set hash_multiset | similar cu set, multiset, map sau multimap, respectiv, dar implementat folosind un tabel hash ; cheile nu sunt sortate, dar trebuie să existe o funcție hash pentru fiecare tip de cheie. Aceste containere nu fac parte din biblioteca Standard C ++, dar sunt incluse în extensia SGI a STL și sunt incluse în mod obișnuit, cum ar fi biblioteca GNU C ++, spațiul de nume __gnu_cxx sau spațiul de nume Visual Studio std_ext. Acestea pot fi incluse în viitoarele extensii ale standardului C ++. |
Algoritmi
Mulți algoritmi sunt incluși în STL pentru a efectua operațiuni precum căutarea și sortarea. Astfel de algoritmi sunt utilizați în mod obișnuit pentru manipularea containerelor într-un mod indirect, adică numai prin iteratori . Mulți dintre acești algoritmi funcționează pe o gamă de containere definită de utilizator utilizând doi iteratori care indică extremele gamei.