A Standard Template Library (STL) a C++ egyik standard könyvtára, amely
az újrahasznosítható komponensek tág készletét kínálja fel. Az 1970-es években
a komponensek struktúrákból és függvényekből álltak. Az 1980-as években a
komponenseket a platform-függő könyvtárak osztályaival valósították meg, majd
az 1990-es évek vége felé az STL megjelenésével a komponensek egyik új
alkalmazása vált lehetővé, amely ezúttal platformtól független osztályokkal
dolgozik.
Az adatstruktúrák bizonyos szabályok alapján rendezett adatkollekciók
vagy konténerek. Tegyük fel, hogy létrehozunk egy Array osztályt, amely int típusú objektumokból álló tömböt kezel.
Osztálysablonnal az int
típus Array
Hasonló módon lehet eljárni a verem típusú adatstruktúrák esetében is. Az STL
nem más, mint osztálysablonokból felépített könyvtár, amely ezek mellett
tartalmazza az adatstruktúrák felépítését is.
A C-ben és a C++-ban a tömb elemei mutatókkal érhetőek el. A C++ STL-ben
a konténerek elemeit iterátor objektumokkal érjük el, melyek olyanok mint a
mutatók, viszont intelligensebbek. Az iterátor objektumok osztályai úgy vannak
megtervezve, hogy általánosan használhatóak legyenek minden konténerben. A
konténerek primitív műveleteket valósíthatnak meg, ám az STL algoritmusai a
konténerektől függetlenek.
A konténerek nem használnak öröklést és virtuális függvényeket a
teljesítmény javítása érdekében, valamint nem használják a new és delete operátorokat.
Konténerek
Az STL konténerek három típúsuak lehetnek:
Szekvenciális konténerek
- vector:
dinamikus tömb, automata átméretezéssel az elemek beszúrásakor és kivételekor. Akár a
statikus tömb esetén, az elemek memóriacímei egymásmelletiek, így egy mutatóval
könnyen hivatkozhatunk bármelyikre. - list: duplán-láncolt lista, gyors beszúrással és törléssel. A beszúrás és törlés a lista bármely
tagjánál lehetséges és mindkét irányba lehet lépkedni. A duplán-láncolt listák
elemei egymástól független memóriahelyeken vannak tárolva, nem lehet a mutató növelésével a szomszédos elemre hivatkozni. Ellenben sokkal
könnyebb az elemeket rendezgetni, cserélgetni, kivenni és hozzáadni, mert nem kell rendelkezésre álljon n egymás melletti üres memóriaterület. A hátrány
az, hogy ezek a műveletek lassúbbak mint például a tömbök esetén, mert az
n-edik elemig mindig el kell lépkedni egy ismert pozíciótól. Emellett plusz memóriát igényel a lista elemei közti
kapcsolat fenntartása is. - forward_list: olyan mint a
- deque:
sor, melynek csak a végéről lehet kivenni és hozzáadni (mindkét végéről - két végű sor). Az elemek nem feltétlenül
egymásutáni memóriacímeken vannak, ezért az előnyök és hátrányok hasonlóak a listáéhoz.
Asszociatív konténerek
- map: egyeztetési lista kulcs-érték párok között. Egy az egyhez egyeztetés. A kulcs az elem egyedi azonosítója és
általában rendezésre, gyorskeresésre használják, míg az érték az elem aktuális értéke, amihez a kulcs tartozik. Azért kell őket egyeztetni, mert típusuk
különbözhet. - multimap: olyan mint a , csak egy a
többhöz egyeztetésre is képes, azaz egy kulcshoz több érték is tartozhat. - set: olyan mint a , csak nem tesz különbséget a kulcs
és érték között, tehát nem kell egyeztni őket, mert a típusuk egyforma.
Emiatt az értékük sem változtatható meg, minden eleme kötelezően konstans. Az elemek a konténerben mindig rendezve
vannak. - multiset: olyan mint a
, csak a kettős értékekkel is elbánik, azaz lehetnek duplák az elemek
között.
Adapterek
- stack:
LIFO (Last In First Out)
verem. Ez olyan mint egy zsák, melyből mindig a legutoljára
berakott elemet lehet elsőre kivenni. - queue:
FIFO (First In First Out)
verem. Ez olyan mint egy lyukas fenekű zsák, melyből a legelsőnek
berakott elem esik ki legelőre. - priority_queue: sor, melyből mindig a legnagyobb
prioritással rendelkező elemet lehet csak kivenni elsőre. A legnagyobb
prioritással a legelső elem rendelkezik. Ez nem feltétlen a legelsőnek vagy
legutolsónak betett elem, ugyanis nem veremről, hanem sorról beszélünk, melynek
mindkét végére beszúrhatóak az elemek. Ez nagyon hasonló a halomhoz (heap),
ahol a legelsőnek beszúrt elem a halom csúcsára kerül, a többi pedig lepereg
róla jobb vagy bal oldalt.
A header fájlok tartalmai a namespace std részét képezik. A szekvenciális és
asszociatív konténereket first-class konténereknek is nevezik. Az STL
konténereknek számos közös tulajdonságuk van, például mind rendelkezik:
- implicit konstruktorral
- másoló konstruktorral
- destruktorral
- empty függvénnyel (amely true, ha van elem a konténerben, különben false)
- =, , >=, ==,
!= operátorokkal
- erase függvénnyel (amely kitöröl egy
vagy több elemet a konténerből - csak a first-class konténerek esetén)
- clear függvénnyel (amely minden elemet
kitöröl a konténerből - csak a first-class konténerek esetén)
Amikor konténereket szeretnénk használni fontos megbizonyosodnunk arról,
hogy az elemek adattípusa (ami például egy osztálytípus) rendelkezzen a
minimális tulajdonságokkal. Amikor berakunk egy elemet a konténerbe, egy
másolat keletkezik róla, ezért az adattípusnak rendelkeznie kell legalább egy
másoló konstruktorral és egy =
operátorral.
Iterátorok
Az iterátoroknak sok közös tulajdonságuk van a mutatókkal és arra jók,
hogy a first-class konténerek elmeire mutassanak. Az iterátor egy olyan objektum,
amely lehetővé teszi a konténer végigjárását annak megvalósításától
függetlenül. Vannak olyan iterátorok is, melyek bizonyos konténerekre vannak
szabva. A * hivatkozó operátor alkalmazható egy iterátoron,
hogy elérjük azt az elemet, amire az iterátor mutat. Ha a ++ operátort alkalmazzuk egy iterátoron, akkor az a
konténer következő elemére ugrik.
Az iterátorokat rendezésre, kivevésre és beszúrásra használják. Az
alábbi példa az istream_iterator iterátort használja az adatszekvenciák bevitelére és az ostream_iterator-t az adatszekvenciák kiolvasására. A
program a billentyűzetről olvas be egész számokat és kiírja azok összegét.
#include
using std::cout;
using std::cin;
using std::endl;
#include
int main()
{
cout
"Írj be két egész számot: ";
std::istream_iteratorint> inputInt(cin); //iterátor
deklarálása
int number1, number2;
number1
= *inputInt; //első szám beolvasasa
++inputInt;
//iterátor növelése a következő beolvasáshoz
number2
= *inputInt; //második szám beolvasása
cout
"Összeg: ";
std::ostream_iteratorint> outputInt(cout);
*outputInt
= number1 + number2; //az összeg kiírása
return 0;
}
A kimenet:
Írj be két egész
számot: 3 4
Összeg: 7
Az std::istream_iteratorint>
inputInt(cin) utasítás egy istream_iterator típusú iterátort deklarál, amely int típusú értékek bevitelére képes a cin standard beviteli eszközről. Amint a number1 változóhoz hozzárendeljük az iterátor értékét,
elindul az első beolvasási folyamat. A második beolvasás előtt az iterátort
növelni kell. Az std::ostream_iteratorint>
outputInt(cout) utasítás egy ostream_iterator típusú iterátort deklarál, amely int típusú értékek beszúrására képes a cout standard kimeneti eszközre. Ebben az esetben az
iterátornak kell a kiírni kívánt értéket adni. Ha konténerben tárolt értékek
megváltozhatnak a program futása alatt, akkor az iterator iterátort kell használni, viszont ha semmiképp se módosulhatnak, akkor
a const_iterator iterátor a megfelelő választás.
Az STL a következőképp kategorizálja az iterátorokat:
- input: elem kiolvasása a konténerből
- output: elem beszúrása a konténerbe
- forward: input és output képességek
- bidirectional: forward képesség mindkét
irányban
- random-access: bidirectional képesség, a lépések véletlenszerű nagyságúak is lehetnek
Az iterátorokkal végzett műveletek a következők lehetnek:
- Minden iterátor:
- ++p: előnövelés
- p++: utónövelés
- input iterátorok:
-
*p: az iterátorra való hivatkozás mint rvalue
-
p =
p1: értékátadás
-
p ==
p1: értékösszehasonlítás
egyenlőségre
-
p
!= p1: értékösszehasonlítás
egyenlőtlenségre
- output iterátorok:
-
*p: az iterátorra való hivatkozás mint lvalue
- forward iterátorok:
-
--p: előcsökkentés
-
p--: utócsökkentés
-random-access iterátorok:
-
p
+= i: a p iterátor növelése i lépéssel
-
p
-= i: a p iterátor csökkentése i lépéssel
-
p +
i: az iterátortól számított i lépés felfelé
-
p –
i: az iterátortól számított i lépés lefelé
-
p[i]: az iterátortól i léplsre lévő elem referenciája
-
p
: igaz, ha p a p1 előtt van
-
p
: igaz, ha p , vagy igaz, ha p ugyanabban a pozícióban van mint p1
-
p
> p1: igaz, ha p a p1 után van
-
p
>= p1: igaz, ha p > p1, vagy igaz, ha p ugyanabban a pozícióban van mint p1
Algoritmusok
Az STL egyik fontos aspektusa, hogy olyan algoritmusokat tartalmaz,
amelyek általánosak minden konténerre: beszúrás, törlés, keresés, rendezés,
stb. Nagyjából 70 standard algoritmus létezik, melyek az iterátorokat használva
közvetett módon bánnak az elemekkel. Mivel az STL bővíthető, könnyen
hozzáadhatók újabb algoritmusok anélkül, hogy a konténeren változtatni kéne. Az
algoritmusokat pointer típusú tömbökön is lehet alkalmazni. Két alapvető
algoritmus fajta létezik: a mutating-sequence algoritmusok megváltoztathatják a
konténer tartalmát, míg a non-mutating-sequence algoritmusok nem változtatnak a
konténer tartalmán. Néhány példa a
Szekvenciális konténerek
Vector
Egy vektor egy olyan
adatstruktúra, melyben az adatok egymás utáni memóriacímeken vannak tárolva. Ez
az elrendezés lehetővé teszi az elemek közvetlen elérését a [] operátorral. Amikor a vector
típusú objektum memóriája már nem elegendő, akkor egy nagyobb memóriaterület
foglalódik le az adott objektumnak, és az elemek átmásolódnak oda,
felszabadítván az előző területet. A konténer egyik legfontosabb jellemzője,
hogy milyen típusú iterátorral képes működni. A vector konténer a random-access iterátorokat
támogatja, azaz a korábban felsorolt összes operátort ismrei. Minden STL
algoritmus képes vector
konténerrel dolgozni. A vector
iterátorai a vektor elemeinek mutatóiként vannak megvalósítva. Ha egy
algoritmusnak egy bizonyos típusú iterátorra van szüksége, hogy működjön, akkor
az alkalmazott konténernek is támogatnia kell azt az iterátort.
A következő példa a vector
osztálysablon néhány funkcióját mutatja be, melyek közül párat minden
first-class STL konténer is használat.
#include
using std::cout;
using std::cin;
using std::endl;
#include
int main()
{
const int SIZE = 6;
int a[SIZE] = {1, 2, 3, 4, 5, 6};
std::vectorint> v;
cout
"A vektor kezdeti mérete: "
"\nA vektornak
szánt tárhely: "
v.push_back(2);
//elem beszúrása a vektor végére
v.push_back(3);
v.push_back(4);
cout
"\nA vektor új mérete: "
"\nA vektornak
szánt tárhely: "
cout
"\n\nA tömb tartalma mutatók
segítsegevel: ";
for(int *ptr = a; ptr
!= a + SIZE; ++ptr)
cout
' ';
cout
"\nA vektor tartalma iterátor
segítségével: ";
std::vectorint>::const_iterator p1;
for(p1 = v.begin(); p1 != v.end(); p1++)
cout
' ';
cout
"\nA vektor tartalma visszafele:
";
std::vectorint>::reverse_iterator p2;
for(p2 = v.rbegin(); p2 != v.rend(); ++p2)
cout
' ';
return 0;
}
A kimenet:
A vektor kezdeti
mérete: 0
A vektornak
szánt tárhely: 0
A vektor új
mérete: 3
A vektornak
szánt tárhely: 4
A tömb tartalma
mutatók segítségével: 1 2 3 4 5 6
A vektor
tartalma iterator segítségével: 2 3 4
A vektor
tartalma visszafele: 4 3 2
Az std::vectorint> v utasítás létrehozza a v objektumot a vector osztályból, és int
értékeket tárolhat. A deklarálás révén létrejön egy nulla elemű és kapacitású
vektor. A kapacitás nem a vektor méretét, hanem a neki fenntartott memória
nagyságát jelenti. Ezt a két értéket a v.size() és a v.capacity() téríti vissza. A push_back függvény beszúr egy értéket a konténerbe.
Ha már nincs hely, a vektor mérete és kapacitása automatikusan megnő.
Az std::vectorint>::const_iterator
p1 utasítás létrehozza a p1 iterátort a vector
konténernek. Mivel ezzel az iterátorral nem változtatunk a konténer tartalmán,
deklarálhatjuk konstansnak (const_iterator). A v.begin() függvény
visszatéríti a v első
elemének a const_iterator-át, a v.end() pedig az utolsót. A p1++ parancs növeli az iterátort egy lépéssel.
A konténer elemére az iterátoron keresztül hivatkozunk (*p1).
A visszafelé való kiíráshoz a std::vectorint>::reverse_iterator p2 deklarálást használjuk, amely esetében az rbegin() függvény jelenti a kezdetet és a rend() függvény a véget.
A következő példában is egy vector típusú objektumot manipulálunk különböző
módszerekkel:
#include
using std::cout;
using std::endl;
#include
#include
#include
#include
int main()
{
const int SIZE = 6;
int a[SIZE] = {1, 2, 3, 4, 5, 6};
