Standard skabelonbibliotek
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. august 2022; verifikation kræver 1 redigering .Standard Template Library (STL) ( Engelsk Standard Template Library ) er et sæt konsistente generiske algoritmer , containere , midler til at få adgang til deres indhold og forskellige hjælpefunktioner i C++ .
Standardskabelonbiblioteket, før det blev inkluderet i C++-standarden , var en tredjepartsudvikling, først af HP og senere af SGI . Sprogstandarden kalder det ikke "STL", da dette bibliotek er blevet en integreret del af sproget, men mange mennesker bruger stadig dette navn for at skelne det fra resten af standardbiblioteket (I/O-streams ( iostream ), C , stk . mv.).
Et projekt kaldet STLPort , baseret på SGI STL, holder STL-, iostream- og strengklasserne ajour. Flere andre projekter udvikler også private anvendelser af standardbiblioteket til forskellige designopgaver. Hver producent af C++ compilere skal levere en vis implementering af dette bibliotek, da det er en meget vigtig del af standarden og er meget udbredt.
STL-arkitekturen blev designet af Alexander Stepanov og Meng Li.
Biblioteksstruktur
Biblioteket har fem hovedkomponenter:
- Container ( engelsk container ) - opbevaring af et sæt objekter i hukommelsen.
- Iterator ( engelsk iterator ) - giver adgang til indholdet af beholderen.
- En algoritme er en definition af en beregningsprocedure.
- Adapter ( engelsk adapter ) - tilpasning af komponenter for at give en anden grænseflade.
- Funktionelt objekt ( engelsk functor ) - skjuler en funktion i et objekt til brug for andre komponenter.
Adskillelse giver dig mulighed for at reducere antallet af komponenter. For eksempel, i stedet for at skrive en separat elementopslagsfunktion for hver containertype, leveres en enkelt version, der fungerer med hver af dem, så længe de grundlæggende krav er opfyldt.
Containere
STL-beholdere kan opdeles i fire kategorier: sekventielle, associative, adapterbeholdere og pseudo-beholdere.
| Beholder | Beskrivelse |
|---|---|
| Sekventielle beholdere | |
| vektor [1] | C-lignende dynamisk random access-array med automatisk ændring af størrelse, når element tilføjes/fjernes. Adgang efter indeks for . Tilføjelse/fjernelse af et element til slutningen af en vektor tager amortiseret tid, den samme operation i begyndelsen eller midten af en vektor tager . Standard hurtig sortering til . At søge efter et element ved iteration tager . Der er en specialisering af vektorskabelonen for bool -typen , som kræver mindre hukommelse ved at gemme elementer som bits, men den understøtter ikke alle funktionerne i iteratorer. |
| liste [2] | En dobbelt linket liste, hvis elementer er gemt i vilkårlige bidder af hukommelsen, i modsætning til en vektorbeholder, hvor elementer er gemt i et sammenhængende hukommelsesområde. Søgning ved opregning er langsommere end for en vektor på grund af den længere elementadgangstid. Adgang efter indeks for . Hvor som helst i beholderen er indsættelse og sletning meget hurtig ind . |
| dæk [3] | Dobbeltsidet kø . En beholder er som en vektor, men med evnen til hurtigt at indsætte og fjerne elementer i begge ender i . Implementeret som en dobbeltforbundet liste over lineære arrays . På den anden side, i modsætning til vektor, garanterer en deque ikke, at alle dens elementer vil være placeret i sammenhængende hukommelse , hvilket gør det umuligt sikkert at bruge pointer-aritmetik [4] til at få adgang til elementer i en container [5] [6] . |
| Associative containere | |
| sæt | Et bestilt sæt unikke elementer. Når du indsætter/fjerner elementer i et sæt, bliver iteratorer, der peger på elementer i dette sæt, ikke ugyldige. Giver standardoperationer på sæt såsom forening, skæring, subtraktion. Sættets elementtype skal implementere en sammenligningsoperator operator<, eller der skal leveres en komparatorfunktion. Implementeret på basis af et selvbalancerende binært søgetræ . |
| multisæt | Samme som sæt, men giver dig mulighed for at gemme duplikerede elementer. |
| kort | En ordnet associativ matrix af par af elementer, der består af nøgler og deres tilsvarende værdier. Nøgler skal være unikke. Rækkefølgen af elementerne bestemmes af tasterne. I dette tilfælde skal nøgletypen implementere sammenligningsoperatøren operator<, eller du skal levere en sammenligningsfunktion. |
| multimap | Samme som kort, men giver dig mulighed for at gemme flere identiske nøgler. |
| Adapterbeholdere | |
| stak | En stak er en beholder, hvori elementer tilføjes og fjernes fra den ene ende. |
| kø | En kø er en beholder, fra den ene ende kan du tilføje elementer, og fra den anden - tage dem ud. |
| priority_queue | En prioriteret kø organiseret, så det største element altid kommer først. |
| Pseudo containere | |
| bitsæt | Bruges til at opbevare bitmasker. Det ligner en vector<bool>fast størrelse. Størrelsen er fast, når bitsætobjektet erklæres. Der er ingen iteratorer i bitset. Optimeret til hukommelsesstørrelse. |
| grundlæggende_streng | En beholder til opbevaring og bearbejdning af strenge. Gemmer elementer i en række i hukommelsen som en enkelt blok, hvilket giver dig mulighed for at organisere hurtig adgang til hele sekvensen. Elementer skal være POD'er . Sammenkædning er defineret med +. |
| valarray | Skabelonen bruges til at gemme numeriske arrays og er optimeret til at opnå øget beregningsydelse. Lidt magen til vektor, men den mangler de fleste af standard container operationer. Operationer er defineret på to valarrays og på en valarray og en skalar (elementmæssigt). Disse operationer kan implementeres effektivt både på vektorprocessorer og på skalære processorer med SIMD- blokke . |
Containere bruger objekt-for-værdi semantik til at gemme elementer. Med andre ord, når den tilføjes, får beholderen en kopi af elementet. Hvis det er uønsket at lave en kopi, bruges en beholder med elementpointere. Elementer tildeles ved hjælp af tildelingsoperatoren, og de ødelægges ved hjælp af destruktoren. Tabellen viser de grundlæggende krav til elementer i containere:
| Metode | Beskrivelse | Bemærk |
|---|---|---|
| kopi konstruktør | Opretter et nyt element, der er identisk med det gamle | Bruges hver gang et element indsættes i en beholder |
| opgaveoperatør | Erstatter indholdet af et element med en kopi af det originale element | Bruges hver gang elementet ændres |
| Destruktor | Ødelægger elementet | Bruges hver gang et element fjernes |
| Standard konstruktør | Opretter et element uden argumenter | Gælder kun for visse operationer. |
| operatør== | Sammenligner to elementer | Bruges når man laver operatør== på to beholdere |
| operatør< | Bestemmer, om et element er mindre end et andet | Bruges ved udførelse af operator< på to containere |
Alle "fulde" standardbeholdere opfylder et bestemt sæt krav (eller konventioner). Tabellen nedenfor antager, at C er en containerklasse, der indeholder objekter af typen T.
| Udtryk | returtype | Kompleksitet | Bemærk |
|---|---|---|---|
| C::værditype | T | Kompiler tid | |
| C::reference | T | Kompiler tid | |
| C::const_reference | Kompiler tid | ||
| C::pointer | Type pointer, der peger på C::reference | Kompiler tid | Peger til T |
| C::iterator | Type iterator, der peger på C::reference | Kompiler tid | En iterator af enhver anden type end en output-iterator |
| C::const_iterator | Type iterator, der peger på C::const_reference | Kompiler tid | En iterator af enhver anden type end en output-iterator |
| C::størrelsestype | Heltalstype uden fortegn | Kompiler tid | |
| Cobj; | Konstant | Efter: obj.size() == 0 | |
| C obj1; obj1 = obj2; | Lineær | Efter: obj1 == obj2 | |
| Cobj; (&obj)->~C(); | Resultat ikke brugt | Lineær | Efter: obj.size() == 0. |
| obj.begin() | Konstant | ||
| obj.end() | Konstant | ||
| obj1 == obj2 | Vendbar til bool | Lineær | |
| obj1 != obj2 | Vendbar til bool | Lineær | |
| obj.størrelse() | størrelses Type | Afhænger af typen | Anbefales ikke til at kontrollere, om en beholder er tom |
| obj.empty() | Vendbar til bool | Konstant | |
| obj1 < obj2 | Vendbar til bool | Lineær | |
| obj1 > obj2 | Vendbar til bool | Lineær | |
| obj1 <= obj2 | Vendbar til bool | Lineær | |
| obj1 >= obj2 | Vendbar til bool | Lineær | |
| obj.swap(obj2) | ugyldig | Konstant |
Iteratorer
STL-biblioteket bruger en generaliseret abstraktion kaldet en iterator som mellemled for at få adgang til elementer . Hver container opretholder "sin egen" slags iterator, som er en "moderniseret" smart pointer [7] , der "ved", hvordan man får adgang til elementerne i en bestemt container. C++-standarden definerer fem kategorier af iteratorer, beskrevet i følgende tabel:
| Kategori | Understøttede operationer | Bemærk |
|---|---|---|
| Input | operator++, operator*, operator->, copy constructor, operator=, operator==, operator!= | Giver læseadgang i én retning. Giver dig mulighed for at udføre en opgave eller kopiere ved hjælp af opgaveoperatoren og kopikonstruktøren. |
| Weekender | operator++, operator*, copy constructor | Giver skriveadgang i én retning. De kan ikke sammenlignes for ligestilling. |
| Ensrettet | operator++, operator*, operator->, copy constructor, default constructor, operator=, operator==, operator!= | Giver læse- og skriveadgang i samme retning. Giver dig mulighed for at udføre en opgave eller kopiere ved hjælp af opgaveoperatoren og kopikonstruktøren. De kan sammenlignes for ligestilling. |
| Tovejs | operator++, operator--, operator*, operator->, copy constructor, default constructor, operator=, operator==, operator!= | Understøtter alle de funktioner, der er beskrevet for envejs iteratorer (se ovenfor). Derudover giver de dig mulighed for at navigere til det forrige element. |
| tilfældig adgang | operator++, operator--, operator*, operator->, copy constructor, default constructor, operator=, operator==, operator!=, operator+, operator-, operator+=, operator-=, operator<, operator>, operator < =, operator>=, operator[] | Svarende til almindelige pointere: understøtter pointer-aritmetik, array-indekseringssyntaks og alle former for sammenligning. |
Se også
Noter
- ↑ std::vektor . Dato for adgang: 14. februar 2016. Arkiveret fra originalen 27. november 2015.
- ↑ std:liste
- ↑ std::deque . Hentet 14. februar 2016. Arkiveret fra originalen 5. februar 2016.
- ↑ Syntaks for pointere i C++ . Hentet 14. februar 2016. Arkiveret fra originalen 11. marts 2016.
- ↑ Iteratorbibliotek (downlink) . Hentet 14. februar 2016. Arkiveret fra originalen 5. februar 2016.
- ↑ C++ koncepter: Iterator . Hentet 14. februar 2016. Arkiveret fra originalen 19. februar 2016.
- ↑ Typer af iteratorer: Output vs. input vs. frem vs. Random Access Iterator . Hentet 14. februar 2016. Arkiveret fra originalen 23. februar 2016.
Links
- SGI STL klasse og metode referencekilde
- STL trin for trin (rus.) - artikler af Artem Kaev
- Grundlæggende om C++. STL Library Arkiveret 27. februar 2007 på Wayback Machine (russisk) - postlistearkiv
- STL - Standard skabelonbibliotek. C++ programmørvejledning (rus.) - detaljeret vejledning
- Brug af STL i C++ (russisk)
Litteratur
- Scott Meyers. Effektiv brug af STL = Effektiv STL. - Peter, 2002. - S. 224 . — (Programmer's Bibliotek). — ISBN 5-94723-382-7 .
- David R. Musser, Gilmer J. Durge, Atul Seini. C++ og STL: Reference Guide = STL Tutorial og Reference Guide: C++ Programmering med standardskabelonen. — 2. udgave. - M. : "Williams" , 2010. - S. 432. - (C ++ i Dybde-serien). — ISBN 5-89818-027-3 .
- Leen Ammeraal. STL for C++ programmører = STL for C++ programmører. - DMK Press, 1999. - S. 240. - ISBN 5-256-00704-1 .
| C++ | |
|---|---|
| Ejendommeligheder | |
| Nogle biblioteker | |
| Kompilere | |
| påvirket | |
| |