Szabványos sablonkönyvtár
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. augusztus 9-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .A Standard Template Library (STL) ( angol szabványos sablonkönyvtár ) konzisztens általános algoritmusok , konténerek , tartalmuk elérésére szolgáló eszközök és különféle segédfunkciók halmaza a C++ nyelven .
A Standard Template Library, mielőtt belekerült a C++ szabványba , egy harmadik fél fejlesztése volt, először a HP , később az SGI fejlesztése volt . A nyelvi szabvány nem nevezi "STL"-nek, mivel ez a könyvtár a nyelv szerves részévé vált, azonban sokan még mindig ezt a nevet használják, hogy megkülönböztessék a szabványos könyvtár többi részétől (I / O folyamok ( iostream ), a C alszakasz stb.).
Az STLPort nevű projekt , amely az SGI STL-en alapul, naprakészen tartja az STL-, iostream- és karakterlánc-osztályokat. Számos más projekt is fejleszti a szabványos könyvtár magáncélú felhasználását különféle tervezési feladatokhoz. Minden C++ fordítógyártónak biztosítania kell ennek a könyvtárnak valamilyen implementációját, mivel ez a szabvány nagyon fontos része és széles körben használatos.
Az STL architektúrát Alexander Stepanov és Meng Li tervezte.
A könyvtár szerkezete
A könyvtár öt fő összetevőből áll:
- Container ( angol konténer ) - objektumok halmazának tárolása a memóriában.
- Iterátor ( angol iterator ) - hozzáférést biztosít a tároló tartalmához.
- Az algoritmus egy számítási eljárás definíciója.
- Adapter ( angol adapter ) - az összetevők adaptációja más interfészt biztosító.
- Funkcionális objektum ( angol functor ) - egy függvény elrejtése egy objektumban, hogy más összetevők használhassák.
Az elválasztás lehetővé teszi az alkatrészek számának csökkentését. Például ahelyett, hogy minden egyes tárolótípushoz külön elemkereső függvényt írnánk, egyetlen verzió áll rendelkezésre, amely mindegyikkel működik, mindaddig, amíg az alapvető követelmények teljesülnek.
Konténerek
Az STL tárolók négy kategóriába sorolhatók: szekvenciális, asszociatív, adapterkonténerek és pszeudokonténerek.
| Tartály | Leírás |
|---|---|
| Szekvenciális konténerek | |
| vektor [1] | C-szerű dinamikus véletlen hozzáférésű tömb automatikus átméretezéssel az elem hozzáadásakor/eltávolításakor. Hozzáférés indexen keresztül a következőhöz: . Egy elem hozzáadása/eltávolítása egy vektor végéhez amortizált időt vesz igénybe, ugyanaz a művelet a vektor elején vagy közepén . Szabványos gyors rendezés a következőhöz: . Egy elem iterációval történő keresése . A bool típusú vektorsablonnak van egy specializációja , amely kevesebb memóriát igényel, mivel az elemeket bitként tárolja, de nem támogatja az iterátorok összes funkcióját. |
| lista [2] | Duplán összekapcsolt lista , amelynek elemei tetszőleges memóriadarabokban vannak tárolva, szemben a vektortárolóval, ahol az elemek egy összefüggő memóriaterületen vannak tárolva. A felsorolás alapján történő keresés lassabb, mint a vektoré, a hosszabb elemelérési idő miatt. Hozzáférés indexen keresztül a következőhöz: . A tárolóban bárhol, a beillesztés és a törlés nagyon gyors - in . |
| fedélzet [3] | Kétoldalas sor . A tároló olyan, mint egy vektor, de képes gyorsan beilleszteni és eltávolítani az elemeket mindkét végén . Lineáris tömbök kétszeresen összekapcsolt listájaként valósítva meg . Másrészt a vektorral ellentétben a deque nem garantálja, hogy minden eleme a szomszédos memóriában fog elhelyezkedni , ami lehetetlenné teszi a pointer aritmetika [4] biztonságos használatát egy tároló [5] [6] elemeinek eléréséhez . |
| Asszociatív konténerek | |
| készlet | Egyedi elemek rendezett készlete . Egy halmaz elemeinek beillesztésekor/eltávolításakor a halmaz elemeire mutató iterátorok nem válnak érvénytelenné. Szabványos műveleteket biztosít olyan halmazokon, mint az egyesülés, metszés, kivonás. A halmaz elemtípusának egy összehasonlító operátort kell megvalósítania operator<, vagy komparátor funkciót kell biztosítani. Egy önkiegyensúlyozó bináris keresőfa alapján valósítva meg . |
| multiset | Ugyanaz, mint a készlet, de lehetővé teszi ismétlődő elemek tárolását. |
| térkép | Kulcsokból és a hozzájuk tartozó értékekből álló elempárok rendezett asszociatív tömbje . A kulcsoknak egyedinek kell lenniük. Az elemek sorrendjét a billentyűk határozzák meg. Ebben az esetben a kulcstípusnak implementálnia kell az összehasonlító operátort operator<, vagy meg kell adnia egy összehasonlító funkciót. |
| multimap | Ugyanaz, mint a térkép, de lehetővé teszi több azonos kulcs tárolását. |
| Adapter tartályok | |
| Kazal | A verem egy olyan tartály, amelyben elemeket adnak hozzá, és az egyik végéről eltávolítják. |
| sorban | A várólista egy tároló, amelynek egyik végéből elemeket adhat hozzá, a másik végéről pedig kiveheti őket. |
| prioritás_sor | Egy prioritási sor úgy rendezve, hogy mindig a legnagyobb elem legyen az első. |
| Pseudo konténerek | |
| bitkészlet | Bitmaszkok tárolására szolgál. vector<bool>Fix méretnek tűnik . A méret a bitkészlet objektum deklarálásakor rögzítésre kerül. A bitkészletben nincsenek iterátorok. A memória méretére optimalizálva. |
| basic_string | Tartály húrok tárolására és feldolgozására. Az elemeket egy sorban, egyetlen blokkként tárolja a memóriában, amely lehetővé teszi a teljes sorozathoz való gyors hozzáférés megszervezését. Az elemeknek POD-oknak kell lenniük . Az összefűzést + jellel határozzuk meg. |
| valarray | A sablon numerikus tömbök tárolására szolgál, és a megnövelt számítási teljesítmény elérésére van optimalizálva. Kissé hasonló a vektorhoz, de hiányzik belőle a legtöbb szabványos konténerművelet. A műveletek két valarray-n, valamint egy valarray-n és egy skaláron vannak meghatározva (elemenként). Ezek a műveletek hatékonyan megvalósíthatók vektorprocesszorokon és SIMD blokkokkal rendelkező skaláris processzorokon is . |
A tárolók objektum-érték szemantikát használnak az elemek tárolására. Más szavakkal, hozzáadásakor a tároló megkapja az elem másolatát. Ha a másolat készítése nem kívánatos, akkor elemmutatók tárolóját kell használni. Az elemek hozzárendelése a hozzárendelés operátorral történik, és megsemmisítésük a destruktorral történik. A táblázat a konténerekben lévő elemekre vonatkozó alapvető követelményeket mutatja be:
| Módszer | Leírás | jegyzet |
|---|---|---|
| másolat konstruktor | Létrehoz egy új elemet, amely megegyezik a régivel | Minden alkalommal használatos, amikor egy elemet behelyeznek egy tárolóba |
| hozzárendelés operátor | Egy elem tartalmát az eredeti elem másolatára cseréli | Minden alkalommal használatos, amikor az elemet módosítják |
| Pusztító | Elpusztítja az elemet | Minden alkalommal használatos, amikor egy elemet eltávolítanak |
| Alapértelmezett konstruktor | Létrehoz egy elemet argumentumok nélkül | Csak bizonyos műveletekre vonatkozik. |
| operátor== | Két elemet hasonlít össze | Ha operátor== műveletet végez két tartályon |
| operátor< | Meghatározza, hogy az egyik elem kisebb-e, mint a másik | Akkor használatos, ha két konténeren végrehajtja a< operátort |
Minden "tele" szabványos konténer megfelel bizonyos követelményeknek (vagy konvencióknak). Az alábbi táblázat feltételezi, hogy C egy T típusú objektumokat tartalmazó tárolóosztály.
| Kifejezés | visszatérési típus | Bonyolultság | jegyzet |
|---|---|---|---|
| C::érték_típus | T | Összeállítási idő | |
| C::referencia | T | Összeállítási idő | |
| C::const_reference | Összeállítási idő | ||
| C::mutató | A C::referenciára mutató mutató típusa | Összeállítási idő | Mutass T-re |
| C::iterátor | A C::referenciára mutató iterátor típusa | Összeállítási idő | Bármilyen típusú iterátor, kivéve a kimeneti iterátort |
| C::const_iterator | A C::const_reference-re mutató iterátor típusa | Összeállítási idő | Bármilyen típusú iterátor, kivéve a kimeneti iterátort |
| C::méret_típus | Előjel nélküli egész típus | Összeállítási idő | |
| Cobj; | Állandó | Utána: obj.size() == 0 | |
| C obj1; obj1 = obj2; | Lineáris | Utána: obj1 == obj2 | |
| Cobj; (&obj)->~C(); | Az eredmény nem használt | Lineáris | Utána: obj.size() == 0. |
| obj.begin() | Állandó | ||
| obj.end() | Állandó | ||
| obj1 == obj2 | Visszafordítható bool-ra | Lineáris | |
| obj1 != obj2 | Visszafordítható bool-ra | Lineáris | |
| obj.size() | méret típus | Típustól függ | Nem ajánlott ellenőrizni, hogy egy tartály üres-e |
| obj.empty() | Visszafordítható bool-ra | Állandó | |
| obj1 <obj2 | Visszafordítható bool-ra | Lineáris | |
| obj1 > obj2 | Visszafordítható bool-ra | Lineáris | |
| obj1 <= obj2 | Visszafordítható bool-ra | Lineáris | |
| obj1 >= obj2 | Visszafordítható bool-ra | Lineáris | |
| obj.swap(obj2) | üres | Állandó |
Iterátorok
Az STL könyvtár az iterátornak nevezett általános absztrakciót használja közvetítőként az elemek eléréséhez . Minden tároló fenntartja a "saját" típusú iterátort, amely egy "modernizált" intelligens mutató [7] , amely "tudja", hogyan lehet elérni egy adott tároló elemeit. A C++ szabvány az iterátorok öt kategóriáját határozza meg, amelyeket a következő táblázat ismertet:
| Kategória | Támogatott műveletek | jegyzet |
|---|---|---|
| Bemenet | operátor++, operátor*, operátor->, másolás konstruktor, operátor=, operátor==, operátor!= | Egyirányú olvasási hozzáférést biztosít. Lehetővé teszi hozzárendelés végrehajtását vagy másolását a hozzárendelés operátor és a másoláskonstruktor használatával. |
| Hétvégén | operátor++, operátor*, másoláskonstruktor | Egyirányú írási hozzáférést biztosít. Nem hasonlíthatók össze az egyenlőség szempontjából. |
| Egyirányú | operátor++, operátor*, operátor->, másolásépítő, alapértelmezett konstruktor, operátor=, operátor==, operátor!= | Olvasási és írási hozzáférést biztosít ugyanabban az irányban. Lehetővé teszi hozzárendelés végrehajtását vagy másolását a hozzárendelés operátor és a másoláskonstruktor használatával. Az egyenlőség szempontjából összehasonlíthatók. |
| Kétirányú | operátor++, operátor--, operátor*, operátor->, másolás konstruktor, alapértelmezett konstruktor, operátor=, operátor==, operátor!= | Támogatja az egyirányú iterátoroknál leírt összes funkciót (lásd fent). Ezenkívül lehetővé teszik az előző elemhez való navigálást. |
| véletlenszerű hozzáférés | operátor++, operátor--, operátor*, operátor->, másolás konstruktor, alapértelmezett konstruktor, operátor=, operátor==, operátor!=, operátor+, operátor-, operátor+=, operátor-=, operátor<, operátor>, operátor < =, operátor>=, operátor[] | Egyenértékű a normál mutatókkal: támogatja a mutató aritmetikáját, a tömb indexelési szintaxisát és az összehasonlítás minden formáját. |
Lásd még
Jegyzetek
- ↑ std::vector . Hozzáférés dátuma: 2016. február 14. Az eredetiből archiválva : 2015. november 27..
- ↑ std:lista
- ↑ std::deque . Letöltve: 2016. február 14. Az eredetiből archiválva : 2016. február 5..
- ↑ A mutatók szintaxisa C++ nyelven . Letöltve: 2016. február 14. Az eredetiből archiválva : 2016. március 11.
- ↑ Iterátor könyvtár (downlink) . Letöltve: 2016. február 14. Az eredetiből archiválva : 2016. február 5..
- ↑ C++ fogalmak: Iterátor . Letöltve: 2016. február 14. Az eredetiből archiválva : 2016. február 19..
- ↑ Az iterátor típusai: kimenet vs. bemenet vs. előre vs. Random Access Iterator . Letöltve: 2016. február 14. Az eredetiből archiválva : 2016. február 23..
Linkek
- SGI STL osztály és metódus referenciaforrás
- STL lépésről lépésre (rus.) - Artem Kaev cikkei
- A C++ alapjai. STL Library archiválva 2007. február 27-én a Wayback Machine -nél (orosz nyelven) - levelezőlista archívum
- STL – Szabványos sablonkönyvtár. C++ programozói útmutató (rus.) - részletes útmutató
- STL használata C++ nyelven (orosz)
Irodalom
- Scott Meyers. Az STL hatékony használata = Effective STL. - Péter, 2002. - S. 224 . — (Programozói könyvtár). — ISBN 5-94723-382-7 .
- David R. Musser, Gilmer J. Durge, Atul Seini. C++ és STL: Reference Guide = STL Tutorial és Reference Guide: C++ programozás a szabványos sablonnal. — 2. kiadás. - M. : "Williams" , 2010. - S. 432. - (C ++ a Depth sorozatban). — ISBN 5-89818-027-3 .
- Leen Ammeraal. STL C++ programozóknak = STL C++ programozóknak. - DMK Press, 1999. - P. 240. - ISBN 5-256-00704-1 .
| C++ | |
|---|---|
| Sajátosságok | |
| Néhány könyvtár | |
| Fordítók | |
| befolyásolta | |
| |