Vakiomallikirjasto
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. elokuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .Standardimallikirjasto (STL) ( englanniksi Standard Template Library ) on joukko johdonmukaisia yleisiä algoritmeja , säilöjä , tapoja käyttää niiden sisältöä ja erilaisia aputoimintoja C++ :ssa .
Standardimallikirjasto, ennen kuin se sisällytettiin C++ -standardiin , oli kolmannen osapuolen kehittämä, ensin HP :n ja myöhemmin SGI :n kehittämä . Kielistandardi ei kutsu sitä nimellä "STL", koska tästä kirjastosta on tullut kiinteä osa kieltä, mutta monet ihmiset käyttävät edelleen tätä nimeä erottaakseen sen muusta vakiokirjastosta (I / O-virrat ( iostream ), C alajakso jne.).
STLPort - niminen projekti , joka perustuu SGI STL:ään, pitää STL-, iostream- ja merkkijonoluokat ajan tasalla. Myös useat muut hankkeet kehittävät standardikirjaston yksityiskäyttöä erilaisiin suunnittelutehtäviin. Jokaisen C++-kääntäjien valmistajan on toimitettava jokin tämän kirjaston toteutus, koska se on erittäin tärkeä osa standardia ja sitä käytetään laajalti.
STL-arkkitehtuurin suunnittelivat Alexander Stepanov ja Meng Li.
Kirjaston rakenne
Kirjastossa on viisi pääosaa:
- Kontti ( englanniksi kontti ) - objektijoukon tallennus muistiin.
- Iteraattori ( englanniksi iterator ) - tarjoaa keinot päästä käsiksi säilön sisältöön.
- Algoritmi on laskennallisen proseduurin määritelmä.
- Adapter ( englanniksi sovitin ) - komponenttien mukauttaminen eri käyttöliittymän tarjoamiseksi.
- Funktionaalinen objekti ( englanniksi functor ) - toiminnon piilottaminen objektiin muiden komponenttien käyttöön.
Erottamisen avulla voit vähentää komponenttien määrää. Esimerkiksi sen sijaan, että kirjoitettaisiin erillinen elementtihakutoiminto jokaiselle säilötyypille, tarjotaan yksi versio, joka toimii jokaisen kanssa, kunhan perusvaatimukset täyttyvät.
Kontit
STL-säilöt voidaan jakaa neljään luokkaan: peräkkäiset, assosiatiiviset, sovitinsäiliöt ja pseudo-säilöt.
| Säiliö | Kuvaus |
|---|---|
| Peräkkäiset säiliöt | |
| vektori [1] | C:n kaltainen dynaaminen suorasaantitaulukko, jossa on automaattinen koon muutos, kun elementtiä lisätään/poistetaan. Pääsy hakemiston avulla kohteelle . Elementin lisääminen/poistaminen vektorin loppuun vie amortisoitua aikaa, sama toimenpide vektorin alussa tai keskellä kestää . Tavallinen nopea lajittelu . Elementin etsiminen iteraatiolla kestää . Vektorimalli on erikoistunut bool -tyyppiin , joka vaatii vähemmän muistia tallentamalla elementtejä bitteinä, mutta se ei tue kaikkia iteraattorien ominaisuuksia. |
| lista [2] | Kaksinkertaisesti linkitetty luettelo , jonka elementit on tallennettu mielivaltaisiin muistin osiin, toisin kuin vektorisäiliö, jossa elementit on tallennettu viereiselle muistialueelle. Haku luettelemalla on hitaampaa kuin vektorilla johtuen pidemmästä elementin pääsyajasta. Pääsy hakemiston perusteella . Säilön missä tahansa kohdassa lisääminen ja poistaminen tapahtuvat erittäin nopeasti . |
| kansi [3] | Kaksipuolinen jono . Säiliö on kuin vektori, mutta sen molemmista päistä voi nopeasti lisätä ja poistaa elementtejä . Toteutettu kaksoislinkitettynä luettelona lineaarisista taulukoista . Toisaalta, toisin kuin vektori, deque ei takaa, että kaikki sen elementit sijaitsevat vierekkäisessä muistissa , mikä tekee mahdottomaksi käyttää osoitinaritmetiikkaa [4] turvallisesti kontin [5] [6] elementteihin . |
| Assosiatiiviset säiliöt | |
| aseta | Tilattu sarja ainutlaatuisia elementtejä. Kun lisäät/poistat joukon elementtejä, tämän joukon elementteihin osoittavat iteraattorit eivät muutu kelpaamattomiksi. Tarjoaa standardioperaatioita joukoille, kuten liitos, leikkaus, vähennyslasku. Joukon elementtityypin tulee toteuttaa vertailuoperaattori operator<, tai siinä on oltava vertailutoiminto. Toteutettu itsetasapainottavan binaarihakupuun perusteella . |
| multiset | Sama kuin sarja, mutta voit tallentaa päällekkäisiä elementtejä. |
| kartta | Järjestetty assosiatiivinen ryhmä elementtipareja, joka koostuu avaimista ja niitä vastaavista arvoista. Avainten on oltava yksilöllisiä. Elementtien järjestys määräytyy näppäimillä. Tässä tapauksessa avaintyypin on otettava käyttöön vertailuoperaattori operator<tai sinun on annettava vertailutoiminto. |
| monikartta | Sama kuin kartta, mutta voit tallentaa useita identtisiä avaimia. |
| Adapterisäiliöt | |
| pino | Pino on säiliö, jossa elementtejä lisätään ja poistetaan toisesta päästä. |
| jonottaa | Jono on kontti, jonka toisesta päästä voit lisätä elementtejä ja toisesta - ottaa ne pois. |
| prioriteettijono | Prioriteettijono järjestetty siten, että suurin elementti tulee aina ensin. |
| Pseudo-säiliöt | |
| bittisarja | Käytetään bitimaskien säilyttämiseen. Näyttää vector<bool>kiinteältä koosta. Koko on kiinteä, kun bittijoukkoobjekti on ilmoitettu. Bittijoukossa ei ole iteraattoreita. Optimoitu muistin koon mukaan. |
| perus_merkkijono | Säiliö merkkijonojen säilytykseen ja käsittelyyn. Tallentaa elementit riviin muistiin yhtenä lohkona, jonka avulla voit järjestää nopean pääsyn koko sarjaan. Tuotteiden on oltava PODeja . Kytkentä määritellään +. |
| valarray | Mallia käytetään numeeristen taulukoiden tallentamiseen, ja se on optimoitu parantamaan laskentatehoa. Hieman samanlainen kuin vektori, mutta siitä puuttuu suurin osa tavallisista konttitoiminnoista. Toiminnot määritellään kahdelle valarraylle sekä valarraylle ja skalaarille (elementtikohtaisesti). Nämä toiminnot voidaan toteuttaa tehokkaasti sekä vektorisuorittimilla että skalaariprosessoreilla SIMD -lohkoilla . |
Säilöissä käytetään objektikohtaista semantiikkaa elementtien tallentamiseen. Toisin sanoen lisättynä säilö saa kopion elementistä. Jos kopioinnin tekeminen ei ole toivottavaa, käytetään elementtiosoittimien säiliötä. Elementit osoitetaan määritysoperaattorilla ja ne tuhotaan destruktorilla. Taulukko näyttää perusvaatimukset säiliöissä oleville elementeille:
| Menetelmä | Kuvaus | Merkintä |
|---|---|---|
| kopioinnin rakentaja | Luo uuden elementin, joka on identtinen vanhan kanssa | Käytetään aina, kun elementti työnnetään säiliöön |
| toimeksiantooperaattori | Korvaa elementin sisällön alkuperäisen elementin kopiolla | Käytetään aina, kun elementtiä muutetaan |
| Tuhoaja | Tuhoaa elementin | Käytetään aina, kun elementti poistetaan |
| Oletuskonstruktori | Luo elementin ilman argumentteja | Koskee vain tiettyjä toimintoja. |
| operaattori == | Vertaa kahta elementtiä | Käytetään tehtäessä operaattori== kahdelle säiliölle |
| operaattori< | Määrittää, onko yksi elementti pienempi kuin toinen | Käytetään suoritettaessa operaattoria< kahdelle säiliölle |
Kaikki "täydet" vakiosäiliöt täyttävät tietyt vaatimukset (tai sopimukset). Alla olevassa taulukossa oletetaan, että C on konttiluokka, joka sisältää T-tyypin objekteja.
| Ilmaisu | palautustyyppi | Monimutkaisuus | Merkintä |
|---|---|---|---|
| C::arvo_tyyppi | T | Kokoamisaika | |
| C::viite | T | Kokoamisaika | |
| C::const_reference | Kokoamisaika | ||
| C::osoitin | Osoittimen tyyppi, joka osoittaa C::viittaukseen | Kokoamisaika | Osoitin kohtaan T |
| C::iteraattori | C::viitteeseen osoittavan iteraattorin tyyppi | Kokoamisaika | Minkä tahansa muun tyyppinen iteraattori kuin tulositeraattori |
| C::const_iterator | Iteraattorin tyyppi, joka osoittaa C::const_reference | Kokoamisaika | Minkä tahansa muun tyyppinen iteraattori kuin tulositeraattori |
| C::koko_tyyppi | Etumerkitön kokonaislukutyyppi | Kokoamisaika | |
| Cobj; | Jatkuva | Jälkeen: obj.size() == 0 | |
| C obj1; obj1 = obj2; | Lineaarinen | Jälkeen: obj1 == obj2 | |
| Cobj; (&obj)->~C(); | Tulosta ei käytetty | Lineaarinen | Jälkeen: obj.size() == 0. |
| obj.begin() | Jatkuva | ||
| obj.end() | Jatkuva | ||
| obj1 == obj2 | Käännettävä booliin | Lineaarinen | |
| obj1 != obj2 | Käännettävä booliin | Lineaarinen | |
| obj.size() | Koko Tyyppi | Riippuu tyypistä | Ei suositella tarkastettavaksi, onko säiliö tyhjä |
| obj.empty() | Käännettävä booliin | Jatkuva | |
| obj1 < obj2 | Käännettävä booliin | Lineaarinen | |
| obj1 > obj2 | Käännettävä booliin | Lineaarinen | |
| obj1 <= obj2 | Käännettävä booliin | Lineaarinen | |
| obj1 >= obj2 | Käännettävä booliin | Lineaarinen | |
| obj.swap(obj2) | mitätön | Jatkuva |
Iteraattorit
STL-kirjasto käyttää yleistettyä abstraktiota, jota kutsutaan iteraattoriksi , välittäjänä elementtien käyttämiseen . Jokainen säilö ylläpitää "omaa" iteraattoriaan, joka on "modernisoitu" älykäs osoitin [7] , joka "tietää" kuinka päästä käsiksi tietyn säilön elementteihin. C++-standardi määrittelee viisi iteraattoriluokkaa, jotka on kuvattu seuraavassa taulukossa:
| Kategoria | Tuetut toiminnot | Merkintä |
|---|---|---|
| Syöte | operaattori++, operaattori*, operaattori->, kopiointikonstruktori, operaattori=, operaattori==, operaattori!= | Tarjoaa lukuoikeuden yhteen suuntaan. Voit suorittaa tehtävän tai kopioida käyttämällä toimeksiantooperaattoria ja kopiointikonstruktoria. |
| Viikonloppuisin | operaattori++, operaattori*, kopiointikonstruktori | Tarjoaa kirjoitusoikeuden yhteen suuntaan. Niitä ei voi verrata tasa-arvoon. |
| Yksisuuntainen | operaattori++, operaattori*, operaattori->, kopiointikonstruktori, oletuskonstruktori, operaattori=, operaattori==, operaattori!= | Tarjoaa luku- ja kirjoitusoikeudet samaan suuntaan. Voit suorittaa tehtävän tai kopioida käyttämällä toimeksiantooperaattoria ja kopiointikonstruktoria. Niitä voidaan verrata tasa-arvoon. |
| Kaksisuuntainen | operaattori++, operaattori--, operaattori*, operaattori->, kopiointikonstruktori, oletuskonstruktori, operaattori=, operaattori==, operaattori!= | Tukee kaikkia yksisuuntaisille iteraattoreille kuvattuja toimintoja (katso edellä). Lisäksi niiden avulla voit siirtyä edelliseen elementtiin. |
| satunnainen pääsy | operaattori++, operaattori--, operaattori*, operaattori->, kopiointikonstruktori, oletuskonstruktori, operaattori=, operaattori==, operaattori!=, operaattori+, operaattori-, operaattori+=, operaattori-=, operaattori<, operaattori>, operaattori < =, operaattori>=, operaattori[] | Vastaa tavallisia osoittimia: tuki osoittimien aritmetiikkaa, taulukon indeksointisyntaksia ja kaikenlaista vertailua. |
Katso myös
Muistiinpanot
- ↑ std::vektori . Käyttöpäivä: 14. helmikuuta 2016. Arkistoitu alkuperäisestä 27. marraskuuta 2015.
- ↑ std:lista
- ↑ std::deque . Haettu 14. helmikuuta 2016. Arkistoitu alkuperäisestä 5. helmikuuta 2016.
- ↑ Osoittimien syntaksi C++:ssa . Haettu 14. helmikuuta 2016. Arkistoitu alkuperäisestä 11. maaliskuuta 2016.
- ↑ Iteraattorikirjasto (downlink) . Haettu 14. helmikuuta 2016. Arkistoitu alkuperäisestä 5. helmikuuta 2016.
- ↑ C++-käsitteet: Iteraattori . Haettu 14. helmikuuta 2016. Arkistoitu alkuperäisestä 19. helmikuuta 2016.
- ↑ Iteraattorityypit: Lähtö vs. syöttö vs. eteenpäin vs. Random Access Iterator . Haettu 14. helmikuuta 2016. Arkistoitu alkuperäisestä 23. helmikuuta 2016.
Linkit
- SGI STL- luokan ja menetelmän viitelähde
- STL askel askeleelta (rus.) - Artem Kaevin artikkelit
- C++:n perusteet. STL Library Arkistoitu 27. helmikuuta 2007 Wayback Machinessa (venäjäksi) - postituslista-arkisto
- STL - vakiomallikirjasto. C++ ohjelmoijan opas (rus.) - yksityiskohtainen opas
- STL:n käyttö C++:ssa (venäjä)
Kirjallisuus
- Scott Meyers. STL:n tehokas käyttö = Effective STL. - Peter, 2002. - S. 224 . — (Ohjelmoijan kirjasto). — ISBN 5-94723-382-7 .
- David R. Musser, Gilmer J. Durge, Atul Seini. C++ ja STL: Viiteopas = STL-opetusohjelma ja viiteopas: C++-ohjelmointi vakiomallilla. – 2. painos. - M. : "Williams" , 2010. - S. 432. - (C ++ Depth-sarjassa). — ISBN 5-89818-027-3 .
- Leen Ammeraal. STL C++-ohjelmoijille = STL C++-ohjelmoijille. - DMK Press, 1999. - S. 240. - ISBN 5-256-00704-1 .
| C++ | |
|---|---|
| Erikoisuudet | |
| Jotkut kirjastot | |
| Kääntäjät | |
| vaikutti | |
| |