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<T> típusra bővíthető, így lehetőség van Array<double>, Array<char>, Array<Employee>, vagy bármilyen adattípusú tömböt alkotni.
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:
- 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 <list>, csak szimplán láncolt listát valósít meg, azaz lépkedni csak előre lehet benne.
- 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.
- 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 <map>, csak egy a többhöz egyeztetésre is képes, azaz egy kulcshoz több érték is tartozhat.
- set: olyan mint a <map>, 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 <set>, csak a kettős értékekkel is elbánik, azaz lehetnek duplák az elemek között.
- 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 <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iterator>
int main()
{
cout
<< "Írj be két egész számot: ";
std::istream_iterator<int> 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_iterator<int> 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_iterator<int>
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_iterator<int>
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
< p1: igaz, ha p a p1 előtt van
-
p
<= p1: igaz, ha p < p1, 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
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 <numeric> headerből: copy(), fill(), replace(), swap(), count(), find(), search().
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<iostream>
using std::cout;
using std::cin;
using std::endl;
#include <vector>
int main()
{
const int SIZE = 6;
int a[SIZE] = {1, 2, 3, 4, 5, 6};
std::vector<int> v;
cout
<< "A vektor kezdeti mérete: "
<< v.size() << "\nA vektornak
szánt tárhely: " << v.capacity();
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: "
<< v.size() << "\nA vektornak
szánt tárhely: " << v.capacity();
cout
<< "\n\nA tömb tartalma mutatók
segítsegevel: ";
for(int *ptr = a; ptr
!= a + SIZE; ++ptr)
cout
<< *ptr << ' ';
cout
<< "\nA vektor tartalma iterátor
segítségével: ";
std::vector<int>::const_iterator p1;
for(p1 = v.begin(); p1 != v.end(); p1++)
cout
<< *p1 << ' ';
cout
<< "\nA vektor tartalma visszafele:
";
std::vector<int>::reverse_iterator p2;
for(p2 = v.rbegin(); p2 != v.rend(); ++p2)
cout
<< *p2 << ' ';
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::vector<int> 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::vector<int>::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::vector<int>::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 <iostream>
using std::cout;
using std::endl;
#include <iterator>
#include <vector>
#include <algorithm>
#include <exception>
int main()
{
const int SIZE = 6;
int a[SIZE] = {1, 2, 3, 4, 5, 6};
std::vector<int> v(a, a+SIZE);
std::ostream_iterator<int> output(cout, "
");
cout
<< "A vektor tartalma: ";
std::copy(v.begin(),
v.end(), output); //mindent a kimenetre
cout
<< "\nA vektor első eleme: "
<< v.front() << "\nA vektor utolsó eleme: " << v.back();
v[0]
= 7; // első elem = 7 (1 helyett)
v.at(2)
= 10; // harmadik elem = 10 (3 helyett)
v.insert(v.begin()+1,
22); // az első után beszúrja a 22-t (7 után)
cout
<< "\nA vektor tartalma a módosítások
után: ";
std::copy(v.begin(),
v.end(), output);
try
{
v.at(100)
= 725; //Hiba: a vektor csak 6 elemű
}
catch(std::exception& e)
{
cout
<< "\nKivétel: " <<
e.what();
}
v.erase(v.begin());
// kitörli a legelső elemet
cout
<< "\nA vektor tartalma a törles után:
";
std::copy(v.begin(),
v.end(), output);
v.erase(v.begin(),
v.end()); // kitöröl mindent
cout
<< "\nA törlés után a vektor "
<< (v.empty() ? "" : "továbbra sem ") << "üres.";
v.insert(v.begin(),
a, a+SIZE); // a vektort újra feltölti a tömb
elemeivel
cout
<< "\nA vektor tartalma a törlés előtt:
";
std::copy(v.begin(),
v.end(), output);
v.clear();
// kitöröl mindent
cout
<< "\nA törlés után a vektor "
<< (v.empty() ? "" : "továbbra sem ") << "üres.";
return 0;
}
A kimenet:
A vektor tartalma: 1 2 3 4 5
6
A vektor első eleme: 1
A vektor utolsó eleme: 6
A vektor tartalma a
módosítások után: 7 22 2 10 4 5 6
Kivétel:
vector::_M_range_check: __n (which is 100) >= this->size() (which is 7)
A vektor tartalma a törlés
után: 22 2 10 4 5 6
A törlés után a vektor üres.
A vektor tartalma a törlés
előtt: 1 2 3 4 5 6
A törlés után a vektor üres.
Az std::vector<int> v(a,
a+SIZE) utasítás egy int típusú v vektort deklarál. Meghívódik a vector osztálysablon túlterhelt konstruktora, mely két
argumentumot kap. Mivel egy tömb mutatói iterátorként viselkednek, ez a
deklaráció a v vektort az a tömb tartalmával inicializálja a-tól a+SIZE címig kizárólag.
Az std::ostream_iterator<int>
output(cout, " ") utasítás definiálja az output iterátort, mely ostream_iterator típusú és felhasználható a cout -nál ha egész számokat kell kiírni szóközzel
elválasztva. A copy()
függvény az output iterátorra irányítja a begin()és end() közti tartalmát v-nek.
Az első két paraméter a konténerből kiolvasott iterátorok értékei, a harmadik
pedig egy kimenő iterátor. Hogy az STL függvények működjenek, a program elejére
hozzá kell adni az <algorithm> headert. A v[0] = 7 és a v.at(2) = 10 utasítás két példa a vector objektum elemeinek eléréséhez. A [] operátorral ellentétben az at() függvény leellenőrzi, hogy az adott index benne
van-e a vektor tartományában. Ha nincs, akkor kivétel keletkezik, amit kezelni
lehet a try catch blokkok
segítségével, amihez szükség van az <exception> headerre is. A v.insert(v.begin()+1, 22) utasítás az insert() függvényt használja, hogy betegye a 22
értéket az első paraméternek megadott pozíció után. A beszúrást követően minden
más elem pozíciója eltolódik egy lépést. A v.insert(v.begin(), a, a+SIZE) utasítás is az insert() függvényt használja, de ezúttal három
paraméterrel, ami azt jelenti, hogy a beszúrt elem egy másik konténerből
származhat, melynek elejét és végét is meg kell adni. Ebben az esetben ez egy
tömb, ám ez kezelhető konténerként is, mert a mutatói iterátoroknak felelnek
meg. A v.erase(v.begin()) és a v.erase(v.begin(), v.end()) utasítások meghatározzák, hogy melyik
elem vagy elemkollekció kerülhet törlésre. A v.clear() függvény mindet kitöröl v-ből.
List
Egy láncolt lista egy olyan adatstruktúra, amelyben az elemek
csomópontoknak nevezett lineáris objektumkollekciókból állnak, melyeket mutatók
kötnek össze egymással. A lista az első csomópontra mutató mutatóval érhető el.
Az utána következő csomópontok sorba ugrálva érhetők el, az utolsó csomópont a
NULL-ba mutat. A duplán láncolt lista esetén minden csomópontnak két mutatója
van: egy az előző, egy a következő csomóponthoz. A list szekvenciális konténer egy duplán láncolt
listát valósít meg. Az iterátorai bidirectional típusúak azaz mindkét irányban
bejárhatóvá teszik a konténert. Ez azt jelenti, hogy az input, output, forward
és bidirectional típusú iterátorokat megkövetelő algoritmusok használhatóak
ezzel a konténerrel. Az alapértelmezett tagfüggvények mellett a list osztály a következőket is tartalmazza: splice, push_front, pop_front, remove, unique, merge, reverse és sort. A következő program ezekből használ fel
néhányat. Hogy a list
olsztály működjön deklarálni kell a <list> header fájlt.
#include <iostream>
using std::cout;
using std::endl;
#include <list>
#include <algorithm>
#include <iterator>
template <class T>
void printList(const
std::list<T> &listRef);
int main()
{
const int SIZE = 4;
int a[SIZE] = {2, 4, 6, 8};
std::list<int> lista, otherlista;
lista.push_front(1);
lista.push_front(2);
lista.push_back(4);
lista.push_back(3);
cout
<< "A lista tartalma: ";
printList(lista);
lista.sort();
cout
<< "\nA rendezés után a lista tartalma:
";
printList(lista);
otherlista.insert(otherlista.begin(),
a, a+SIZE);
cout
<< "\nA beszúrás után az otherlista
tartalma: ";
printList(otherlista);
lista.splice(lista.end(),
otherlista);
cout
<< "\nA splice után a lista tartalma:
";
printList(lista);
lista.sort();
cout
<< "\nA rendezés után a lista tartalma:
";
printList(lista);
otherlista.insert(otherlista.begin(),
a, a+SIZE);
cout
<< "\nAz otherlista tartalma: ";
printList(otherlista);
lista.merge(otherlista);
cout
<< "\nA merge: után a lista tartalma:
";
printList(lista);
cout
<< "\nAz otherlista tartalma: ";
printList(otherlista);
lista.pop_front();
lista.pop_back();
cout
<< "\nA pop_front és pop_back után a
lista tartalma: ";
printList(lista);
lista.unique();
cout
<< "\nAz unique után a lista tartalma:
";
printList(lista);
//a swap-ot minden konténer alkalmazhatja
lista.swap(otherlista);
cout
<< "\nA swap után a lista tartalma:
";
printList(lista);
cout
<< "\nAz otherlista tartalma: ";
printList(otherlista);
lista.assign(otherlista.begin(),
otherlista.end());
cout
<< "\nAz assign után a lista tartalma:
";
printList(lista);
lista.merge(otherlista);
cout
<< "\nA merge után a lista tartalma:
";
printList(lista);
lista.remove(4);
cout
<< "\nA remove után a lista tartalma:
";
printList(lista);
return 0;
}
template <class T>
void printList(const
std::list<T> &listRef)
{
if(listRef.empty())
cout
<< "Üres!";
else
{
std::ostream_iterator<T>
output(cout, " ");
std::copy(listRef.begin(),
listRef.end(), output);
}
}
A kimenet:
A lista tartalma: 2 1 4 3
A rendezés után a lista
tartalma: 1 2 3 4
A beszúrás után az
otherlista tartalma: 2 4 6 8
A splice után a lista
tartalma: 1 2 3 4 2 4 6 8
A rendezés után a lista
tartalma: 1 2 2 3 4 4 6 8
Az otherlista tartalma: 2 4
6 8
A merge után a lista
tartalma: 1 2 2 2 3 4 4 4 6 6 8 8
Az otherlista tartalma: Üres!
A pop_front és pop_back után
a lista tartalma: 2 2 2 3 4 4 4 6 6 8
Az unique után a lista
tartalma: 2 3 4 6 8
A swap után a lista
tartalma: Üres!
Az otherlista tartalma: 2 3
4 6 8
Az assign után a lista
tartalma: 2 3 4 6 8
A merge után a lista
tartalma: 2 2 3 3 4 4 6 6 8 8
A remove után a lista
tartalma: 2 2 3 3 6 6 8 8
Ebben a programban két int típusú lista van deklarálva, a lista és otherlista. A push_front a lista élére, a push_back a lista végére szúr be értékeket. A
lista.push_front(1);
lista.push_front(2);
lista.push_back(4);
lista.push_back(3);
utasítások után a lista tartalma 2, 1, 4,
3 lesz. A sort tagfüggvény ezt
növekvő sorrendbe rendezi. Az otherlista a tartalmát az a
tömbből kapja az insert
függvény segítségével. A lista.splice(lista.end(), otherlista) parancs kitöröl minden elemet az otherlista-ból és berakja az első paraméternek
megadott iterátor után a lista-ban.
Ebben az esetben ez az iterátor a lista.end(), ezért a lista az 1, 2, 3, 4, 2,
4, 6, 8 elemeket tartalmazza. Ez után egy újabb rendezés következik (1, 2, 2,
3, 4, 4, 6, 8), majd az otherlista újból feltelik a tömb értékeivel. A merge függény kitöröl minden elemet az otherlista-ból és beteszi a lista-ba. Ez csak akkor működik, ha mindkét
lista ugyanúgy rendezve van. A lista
új elemei: 1, 2, 2, 2, 3, 4, 4, 4, 6, 6, 8, 8. A pop_front és pop_back kitöröl egy-egy elemet a lista elejéről és végéről,
így a lista elemei: 2, 2, 2, 3,
4, 4, 4, 6, 6, 8. Az unique
függvény kitörli duplákat: 2, 3, 4, 6, 8. A függvény meghívása előtt érdemes
rendezni a listát, hogy a kettős elemek egymás után legyenek, ezáltal hamarább
lefut az algoritmus. A swap felcseréli a lista és az otherlista elemeit egymás
között. Ettől a lista
tartalma üres lesz és az otherlista felveszi a 2, 3, 4, 6, 8. Az assign átmásolja az otherlista elemeit a lista-ba. A merge ismét összemossa a két listát a lista-ba, majd a remove(4) kivesz minden 4-es értéket a listából. A lista végső értéke: 2, 2, 3, 3, 6, 6, 8, 8.
Az asszociatív konténerek arra vannak tervezve, hogy tárolják és elérjék
az elemeket a kulcsok segítségével, melyeket keresési kulcsoknak is hívnak.
Asszociatív konténer a multiset, set, multimap és map. Mindenik típusban a
kulcsok rendezett sorrendben vannak tárolva és ez alapján járja végig őket az
iterátor. A multiset és set olyan halmazokkal dolgozik melyekben az értékek
azonosak a kulcsokkal. Ezeket egyeztett értékeknek hívjuk. A multiset és set
közti egyetlen különbség, hogy a multisetben lehetnek duplák is. Ugyanez
érvényes a map és multimap-ra is. A többi konténerhez képest, az asszociatív
konténerek rendelkeznek a find, lower_bound, upper_bound és count
függvényekkel is.
multiset
Egy multiset konténer elemeinek rendezettségét egy összehasonlító
objektum adja meg. Például létezhet olyan int típusú multiset konténer, melyben az elemek
növekvő sorrendbe rendeződnek, ha a kulcsokat a less<int> összehasonlító objektummal rendezzük.
Ebben az esetben a kulcsoknak ismerniük kell az operator< összehasonlítást. Egy multiset konténer
bidirectional típusú iterátort használ. Az alábbi program egy növekvő sorrendbe rendezett multiset
konténerrel végez műveleteket. A multiset és set osztályoknak ugyanazok a
tagfüggvényei, és a <set> headerfájlt kell deklarálni, hogy használni lehessen őket.
#include <iostream>
using std::cout;
using std::endl;
#include <iterator>
#include <set>
#include <algorithm>
int main()
{
const int SIZE = 10;
int a[SIZE] = {7,22,9,1,18,30,100,22,85,13};
typedef std::multiset<int,
std::less<int> > ims; //ims = integer multiset
ims
intMultiset; //multiset növekvő kulcsokkal
cout
<< "Összesen " << intMultiset.count(15)
<< " darab 15-ös van a
multisetben.\n";
intMultiset.insert(15);
intMultiset.insert(15);
cout
<< "A beszúrás után "
<< intMultiset.count(15) << "
darab 15-ös van a multisetben.\n";
ims::const_iterator
result; //a
result egy konstans iterátor
result
= intMultiset.find(15); //a find értéket ad az iterátornak
if(result != intMultiset.end()) //ha az iterátor nem a legutolsó elemre mutat
cout
<< "Létezik a 15-ös szám\n";
result
= intMultiset.find(20);
if(result == intMultiset.end()) //ha az iterátor a legutolsó elemre mutat
cout
<< "Nem létezik a 20-as szám\n";
intMultiset.insert(a,
a+SIZE); //feltölti a multisetet az "a"
elemeivel
std::ostream_iterator<int> output(cout, "
"); //kimeneti iterátor
cout
<< "A feltöltes után a multiset
tartalma:\n";
std::copy(intMultiset.begin(),
intMultiset.end(), output);
cout
<< "\nA 22-es baloldali szomszédja :
" << *(intMultiset.lower_bound(22));
cout
<< "\nA 22-es jobboldali szomszédja :
" << *(intMultiset.upper_bound(22));
std::pair<ims::const_iterator,
ims::const_iterator> p;
p =
intMultiset.equal_range(22);
cout
<< "\nAz equal_range szerint a 22-es bal
szomszédja: " << *(p.first) << ",
jobb szomszédja: " << *(p.second);
return 0;
}
A kimenet:
Összesen 0 darab 15-ös van a
multisetben.
A beszúrás után 2 darab
15-ös van a multisetben.
Létezik a 15-ös szam
Nem létezik a 20-as szám
A feltöltés után a multiset
tartalma:
1 7 9 13 15 15 18 22 22 30
85 100
A 22-es baloldali szomszédja
: 22
A 22-es jobboldali
szomszédja : 30
Az equal_range szerint a
22-es bal szomszédja: 22, jobb szomszédja: 30
A count
függvényt mindenik asszociatív konténer ismeri. A paraméterként megadott érték
előfordulási számát téríti vissza. Az insert új
elemet ad a konténerhez. Az elemek keresését a find függvény végzi, ami egy iterator-t
vagy egy const_iterator-t térít vissza, amely az első megtalált
értékre mutat. Ha semmit sem talált, akkor az ugyanazt az iterátort téríti
vissza, amit az end függvény is
eredményezne, így vele is ellenőrizhető. Az insert egész tömbök beszúrására is képes, ahogyan a korábbi példákban tette. A lower_bound és az upper_bound a paraméternek megadott érték szomszédaira mutató iterátort
téríti vissza. Az std::pair<ims::const_iterator, ims::const_iterator> p utasítás létrehozza a p objektumot a pair osztályból. A pair objektumai arra
jók, hogy értékpárokat kapcsoljanak össze. Itt például a p objektumnak két const_iterator iterátora van, melyeknek típusa ims. Azért van szükség a pair típusú objektumra, hogy tárolni lehessen az equal_range
függvény eredményét, ugyanis ez két iterátort térít vissza, a lower- és upper_bound iterátorokat. A két visszatérített iterátor a pair osztály publikus tagfüggvénye, a first és a second.
map
A map konténert a
kulcs-érték egyeztetések tárolására és keresésére használjuk. A kettős kulcsok
nem elfogadottak, így minden kulcshoz csak egy érték tartozhat. A kereséshez a [] operátort használjuk, melybe a kulcsot írjuk, akár egy indexet. A set és multiset konténer számos függvénye használható a map és multimap konténerrel is.
#include<iostream>
using std::cout;
using std::endl;
#include <map>
int main()
{
typedef std::map<int,
double, std::less<int>
> mid;
mid
pairs;
pairs.insert(
mid::value_type(15, 2.7) );
pairs.insert(
mid::value_type(30, 111.11) );
pairs.insert(
mid::value_type(5, 1010.1) );
pairs.insert(
mid::value_type(10, 22.22) );
pairs.insert(
mid::value_type(25, 33.333) );
pairs.insert(
mid::value_type(5, 77.54) );//kettős kulcs
pairs.insert(
mid::value_type(20, 9.345) );
pairs.insert(
mid::value_type(15, 99.3) );//kettős kulcs
cout
<< "a map
tartalma:\nKulcs\tÉrték\n";
mid::const_iterator
iter;
for(iter = pairs.begin(); iter != pairs.end();
++iter)
cout
<< iter->first << '\t'
<< iter->second << '\n';
pairs[25]
= 9999.99;//a 25-ös kulcshoz tartozó érték
pairs[40]
= 8765.43;//a 40-es kulcshoz tartozó érték
cout
<< "\nA műveletek után a map
tartalma:" << "\nKulcs\tÉrték\n";
for(iter = pairs.begin(); iter != pairs.end();
++iter)
cout
<< iter->first << '\t'
<< iter->second << '\n';
return 0;
}
A kimenet:
A map tartalma:
Kulcs Érték
5 1010.1
10 22.22
15 2.7
20 9.345
25 33.333
30 111.11
A műveletek után
a map tartalma:
Kulcs Érték
5 1010.1
10 22.22
15 2.7
20 9.345
25 9999.99
30 111.11
40 8765.43
A typedef std::map<int, double, std::less<int>
> mid utasításban a typedef a mid álnevet
adja a map konténernek, melyben a kulcsok int típusúak, az értékek double típusúak és az elemek növekvő sorrendben
vannak rendezve. A mid pairs utasítás
létrehozza mid típsú pairs objektumot. Az elemek hozzáadási ismét az insert függvénnyel történik, ám a paraméterbe
egyszerre kell szerepeljen a kulcs és az érték is: mid::value_type(15, 2.7), ahol 15 a kulcs, 2.7 az érték. A kettős
kulcsok esetén a második változat nem kerül be a konténerbe. A mid::const_iterator iter egy konstans iterátort deklarál, amellyel
végigjárható a map. Ez az iterátor egyformán hordozza a kulcs (first) és érték (second) információt is. A [] operátor lehetőséget ad, hogy a kulcs segítségével hivatkozzunk az
értékre. Ha a kulcs nem létezik, akkor a [] operátor berakja a konténerbe az értékkel
együtt.
Az STL három adaptert bocsát rendelkezésre: stack, queue és priority_queue. Ezek nem
first-class konténerek, mert önmagukban nem alkotnak adatstruktúrát, ahol az
adatokat tárolni lehet és nem is tudnak iterátorokkal dolgozni. A programozónak
kell kiválasztania az adatstruktúrát, amit az adapterhez csatol. Mindenik
adapter ismeri a push is
pop függvényeket, melyek a beszúró és törlő
műveleteket végzik.
stack
A stack osztály a hozzá
csatolt adatstruktúra egyik végéről enged csak beszúrni és kivenni (LIFO
verem). A stack objektuma bármilyen
szekvenciális konténerrel használható (vector, list, deque).
#include <iostream>
using std::cout;
using std::endl;
#include <stack>
#include <vector>
#include <list>
template <class T>
void popElements(T &s);
int main()
{
std::stack<int> intDequeStack; //deque-hez
csatolt stack
std::stack<int, std::vector<int>
> intVectorStack; //vector-hoz csatolt stack
std::stack<int, std::list<int>
> intListStack; //list-hez csatolt stack
for(int i=0; i<10;
++i) // mindeniket feltölti 1-től 10-ig
{
intDequeStack.push(i);
intVectorStack.push(i);
intListStack.push(i);
}
cout
<< "intDequeStack: ";
popElements(intDequeStack);
cout
<< "\nintVectorStack: ";
popElements(intVectorStack);
cout
<< "\nintListStack: ";
popElements(intListStack);
return 0;
}
template <class T>
void popElements(T &s)
{
while(!s.empty())
{
cout
<< s.top() << ' ';
s.pop();
}
}
A kimenet:
intDequeStack: 9 8 7 6 5 4 3
2 1 0
intVectorStack: 9 8 7 6 5 4
3 2 1 0
intListStack: 9 8 7 6 5 4 3
2 1 0
Ha nem csatolunk semmilyen adatstruktúrát
az adapterhez, akkor alapból a deque
konténer csatolódik hozzá. A pop
függvény nem térít vissza semmit, egyszerűen csak törli a legfelső elemet. A
legfelső elemet a top
téríti vissza anélkül hogy törölné.
queue, priority_queue
A queue osztály a
hozzácsatolt adatstruktúra végére szúr be és az elejéről töröl ki. A queue objektuma list és deque adatstruktúrákkal működik. Ha semmi nincs hozzácsatolva, akkor alapból a deque-t használja. A push a push_back, a pop a pop_front függvényt hívja meg.
A priority_queue osztály rendezni is tudja a beszúrt elemeket, és
az objektuma vector és deque adatstruktúrákkal működik. Alapból
növekvő sorrendbe rendeződnek az elemek (less<T>), de ezen lehet módosítani.
#include <iostream>
using std::cout;
using std::endl;
#include <queue>
int main()
{
std::queue<double> values;
std::priority_queue<double> priorities;
values.push(3.2);
values.push(9.8);
values.push(5.4);
cout
<< "Pop a queue-ből: ";
while(!values.empty())
{
cout
<< values.front() << ' '; //kiírja
values.pop();
//törli
}
priorities.push(3.2);
priorities.push(9.8);
priorities.push(5.4);
cout
<< "\nPop a priority_queue-ből: ";
while(!priorities.empty())
{
cout
<< priorities.top() << ' '; //kiírja
priorities.pop();
//törli
}
return 0;
}
A kimenet:
Pop a queue-ből: 3.2 9.8 5.4
Pop a priority_queue-ből:
9.8 5.4 3.2
A values és priorities két vermet
valósít meg. Az egyik queue,
a másik priority_queue típusú. A queue típus a front, a priority queue a top
függvényt használja a verem első elemének kiolvasásához.
Az STL bevezetése előtt az osztálykönyvtárak és a különböző fejlesztők
algoritmusai nem voltak kompatibilisek egymással. Az algoritmusok az osztályok
funkcióiként szolgáltak. Az STL az iterátorok segítségével elválasztotta ezt a
kettőt, így sokkal egyszerűbb az algoritmusok használata és bővítése. Az
algoritmusok nem függenek a konténerek felépítésének részleteiből, és amíg
eleget tesznek az algoritmusok feltételeinek, addig bármilyen típusú
adatstruktúrákkal alkalmazhatóak. Jelenleg közel 100 STL algoritmus létezik,
melyek közül néhány a következő programokban alkalmazva van:
A fill, fill_n, generate és generate_n algoritmusok
A fill és fill_n függvények feltöltik a konténer elemeit vagy
elemcsoportját egy értékkel. A generate és generate_n függvények is
ugyanezt teszik, csak minden elemet vagy elemcsoportot más értékkel töltenek
fel. A generátorfüggvényeknek nincsenek argumentumai, csupán visszatérítenek
egy értéket amit aztán a konténer elemének lehet átadni.
#include <iostream>
using std::cout;
#include <algorithm>
#include <vector>
#include <iterator>
char nextLetter();
int main()
{
std::vector<char> chars(10);
std::ostream_iterator<char> output(cout, "
");
std::fill(chars.begin(),
chars.end(), '5'); //eléjetől
végéig 5-tel tölti fel
cout
<< "A chars vektor tartalam a fill(5)
után: ";
std::copy(chars.begin(),
chars.end(), output);
std::fill_n(chars.begin(),
5, 'A'); //elejétől
az első 5 elemet A-val tölti fel
cout
<< "\nA chars vektor tartalma a
fill_n(5,A) után:";
std::copy(chars.begin(),
chars.end(), output);
std::generate(chars.begin(),
chars.end(), nextLetter); //elejétől végéig feltölti
A-val kezdve
cout
<< "\nA chars vektor tartalma a
generate(nextLetter) után:\t";
std::copy(chars.begin(),
chars.end(), output); //mivel 10 elem van, a J-ig jut
el
std::generate_n(chars.begin(),
5, nextLetter); //elejétől az első 5 elemet K-val
kezdve tölti fel
cout
<< "\nA chars vektor tartalma a generate_n(5,nextLetter)
után:";
std::copy(chars.begin(),
chars.end(), output); //mivel 10 elem van, az O-ig
jut el
return 0;
}
char nextLetter()
{
static char letter = 'A';
return letter++;
}
A kimenet:
A chars vektor tartalma a
fill(5) után: 5 5 5 5 5 5 5 5 5 5
A chars vektor tartalma a
fill_n(5,A) után:A A A A A 5 5 5 5 5
A chars vektor tartalma a
generate(nextLetter) után: A B C D E F
G H I J
A chars vektor tartalma a
generate_n(5,nextLetter) után:K L M N O F G H I J
A fill argumentumai megkövetelik a az első és utolsó pozíciót is amit fel kell
tölteni, a fill_n pedig a kezdeti
pozíciót és az attól számított elemszámot kéri a feltöltéshez. A generate függvények minden elemre meghívják a nextLetter függvényt.
Matematikai algoritmusok
Ide tartoznak például a random_shuffle, count, count_if, min_element, max_element,
accumulate, for_each és a transform függvények.
#include <iostream>
using std::cout;
#include <algorithm>
#include <numeric>
//accumulate
#include <vector>
#include <iterator>
bool nagyobbmint9(int);
void negyzet(int);
int kob(int);
int main()
{
const int SIZE = 10;
int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int a2[] = {100, 2, 8, 1, 50, 3, 8, 8, 9, 10};
int result;
std::vector<int> v(a1, a1+SIZE); //v egy vektor a1
tartalmával
std::vector<int> v2(a2, a2+SIZE); //v2
egy vektor a2 tartalmával
std::vector<int> cubes(SIZE); //cubes egy 10
elemű üres vektor
std::ostream_iterator<int> output(cout, "
"); //output egy kiíró operátor
cout
<< "A v vektor tartalma: ";
std::copy(v.begin(),
v.end(), output);
std::random_shuffle(v.begin(),
v.end());
cout
<< "\nA v vektor tartalma a
random_shuffle után: ";
std::copy(v.begin(),
v.end(), output);
cout
<< "\n\nA v2 vektor tartalma: ";
std::copy(v2.begin(),
v2.end(), output);
result
= std::count(v2.begin(), v2.end(), 8);
std::cout
<< "\nA 8-asok száma: "
<< result;
result
= std::count_if(v2.begin(), v2.end(), nagyobbmint9);
std::cout
<< "\nA 9-nél nagyobb elemek száma:
" << result;
std::cout
<< "\nA legkisebb elem: "
<< *(std::min_element(v2.begin(), v2.end()));
std::cout
<< "\nA legnagyobb elem: "
<< *(std::max_element(v2.begin(), v2.end()));
std::cout
<< "\nAz elemek összege: "
<< std::accumulate(v.begin(), v.end(), 0);
std::cout
<< "\n\nA v elemei négyzetre emelve:
";
std::for_each(v.begin(),
v.end(), negyzet);
std::transform(v.begin(),
v.end(), cubes.begin(),kob);
cout
<< "\nA v elemei a köbre emelve: ";
std::copy(cubes.begin(),
cubes.end(), output);
return 0;
}
bool nagyobbmint9(int
value) {return value > 9;}
void negyzet(int
value) {cout << value * value << ' ';}
int kob(int value) {return value * value *
value;}
A kimenet:
A v vektor
tartalma: 1 2 3 4 5 6 7 8 9 10
A v vektor
tartalma a random_shuffle után: 9 2 10 3 1 6 8 4 5 7
A v2 vektor
tartalma: 100 2 8 1 50 3 8 8 9 10
A 8-asok száma:
3
A 9-nél nagyobb
elemek száma: 3
A legkisebb
elem: 1
A legnagyobb
elem: 100
Az elemek összege: 55
A v elemei
négyzetre emelve: 81 4 100 9 1 36 64 16 25 49
A v elemei a
köbre emelve: 729 8 1000 27 1 216 512 64 125 343
Az std::random_shuffle(v.begin(), v.end()) véletlenszerűen rendezi a verem elemeit a
megadott pozíciók között. Az argumentumban megadott iterátorok random-access
típusúak. Az std::count(v2.begin(),
v2.end(), 8) utasítás
megszámolja a nyolcasokat a megadott pozíciók között. Az std::count_if(v2.begin(),
v2.end(), nagyobbmint9)
utasítás megszámolja hányszor térít vissza true-t a nagyobbmint9 függvény a megadott pozíciókon belül. Az
a std::min_element(v2.begin(),
v2.end()) legkisebb elemre
mutató iterátort téríti vissza a megadott pozíciók között. Az iterátor által mutatott
érték a * operátorral írható ki.
Az std::accumulate(v.begin(), v.end(), 0) sablonja a <numeric> header fájlban vann deklarálva és feladata, hogy
összeadja a két pozíció közti értékeket. Az std::for_each(v.begin(), v.end(), negyzet) művelet a pozíciók által meghatározott
elemek mindenikére meghívja a harmadik paraméterként megadott függvényt. Ehhez
hasonlít az std::transform(v.begin(),
v.end(), cubes.begin(),kob) művelet, viszont az eredményt egy másik vektorba teszi. Sem a transform sem a for_each nem változtat a vektor eredeti tartalmán.
A következő példa egy beolvasott 5 elemű vektorról
állapítja meg, hogy palindrom-e vagy sem:
#include<iostream>
using std::cout;
using std::cin;
#include<vector>
#include<iterator>
template <class T>
bool palindrom(T &s);
int main()
{
std::vector<int> v;
int ertek;
cout
<< "Kerem a vektor tartalmát: ";
std::istream_iterator<int> beolvas(cin);
for(int i=1; i<=5;
++i)
{
ertek
= *beolvas;
v.push_back(ertek);
if (i<5) ++beolvas;
}
cout
<< "A vektor tartalma: ";
std::ostream_iterator<int> kiir(cout, "
");
std::copy(v.begin(),
v.end(), kiir);
if(palindrom(v))
cout
<< "\nA vektor palindrom";
else
cout
<< "\nA vektor nem palindrom";
return 0;
}
template <class T>
bool palindrom(T &s)
{
std::vector<int>::const_iterator i;
std::vector<int>::reverse_iterator r=s.rbegin();
bool flag = 1; //palindrom
for(i=s.begin(); i!=s.end(); ++i)
{
if (*r!=*i) flag = 0;
++r;
}
if(flag==1) // ha még
mindig palindrom
return 1;
else
return 0;
}
A kimenet:
Kérem a vektor tartalmát: 1 2 3 2 1
A vektor tartalma: 1 2 3 2 1
A vektor palindrom
