Standard Template Library -- aloittelijan opas
Mureakuha
STL on C++-kielen standardikirjasto, joka tarjoaa käyttäjälle kasan erilaisia luokkia, funktioita ja tapoja toteuttaa ohjelmia ja algoritmeja C++:n avulla. Muun muassa dynaaminen taulukko voidaan toteuttaa luokalla std::vector.
Sisällysluettelo |
STL
Käytännössä kaikki idiomaattisella C++:lla tehdyt ohjelmat nojaavat STL:n johonkin osaan. Esimerkiksi pelkästään tulostaminen hoituu coutin avulla, joka on osa STL:n iostreamia. STL on suunniteltu antamaan käyttäjälle paremmat valmiudet tehdä helposti ja ylläpitää erilaisia normaalisti ongelmallisia tietorakenteita, jotka on helpompia käsitellä kuin vastaavantyyliset C-kielen tietorakenteet. Sellainen on esimerkiksi dynaaminen taulukko :
int *taulukko = (int*) malloc (sizeof(int) * solujen_määrä);
Äskeisessä esimerkissä määritellään yksinkertainen dynaaminen taulukko osoittimen avulla ja varataan sinne tietty määrä soluja, jota kuvastaa muuttuja solujen_määrä. Kyseinen tapa voi kumminkin näyttää jokseenkin monimutkaiselta, varsinkin jos käyttäjän tuntemus osoittimista on varsin suppea. Sen vuoksi asioita yksinkertaistamaan C++ tarjoamalla vector-luokan. Sen avulla voidaan äskeinen toteuttaa alla olevalla tavalla:
std::vector<int> taulukko(solujen_määrä);
Kuten esimerkistä käy ilmi, erottuakseen selvästi käyttäjän koodista koko STL majailee std-nimiavaruudessa. Toisin sanoen, jotta voisit käyttää STL-kirjaston list-tietorakennetta, sinun on ilmoitettava kääntäjälle että kutsut sitä std-nimiavaruudesta laittamalla std:: -etuliitteen tietorakenteen (tai muun) eteen: std::list. Jos kumminkaan käyttäjä ei halua joka kerta jotain tiettyä STL:n komponenttia käyttäessään niin tehdä, on mahdollista sisällyttää std-nimiavaruus nykyiseen nimiavaruuteen käyttämällä using-lauseketta vastaavasti:
using namespace std;
STL tarjoaa monenlaisia lisäyksiä C++-kieleen tavallisten luokkien lisäksi, jotka itsekin nojaavat näihin ominaisuuksiin: mallit, säiliöt ja iteraattorit. Äsken esitelty vector-luokka on säiliö ja toimiakseen edellyttää mallien käyttöä.
Mallit
Mallit, engl. yks. template, eivät varsinaisesti ole osa STL:ää vaan kuuluvat ihan C++-kieleen, joten ne eivät periaatteessa kuulu tämän artikkelin piiriin. Kumminkin, käyttäjä joka ei tunne malleja ei varmaankaan helposti ymmärrä STL:n toimintaa muutenkaan. Ja STL:ssä on monta ominaisuutta, esimerkiksi säiliöt, josta tyypillisimpiä ovat vector, map ja list, jotka tarvitsevat toimiakseen malleja. Säiliöiden lisäksi niitä hyödyntää erilaiset algoritmit, esimerkiksi sort, joka lajittelee tietorakenteen sisällön. Kumminkin, std::sortin käytössä pitää muistaa, että säiliön sisällön objekteilla pitää olla vertailuoperaattori määriteltynä: C++ ei tiedä miten ja minkä perusteella lajittelu tehdään.
Mallit mahdollistavat yleisten tyyppien (engl. generic types) käytön. Tämä tarkoittaa käytännössä sitä, että jos määritellään tietty malli funktiolle, funktio toimii määrittelemän mallin mukaan funktion parametrien, palautusarvon tai minkä tahansa tyypistä riippumatta. Toisin sanoen, mallit mahdollistavat minkä tahansa muuttujatyypin käytön, esimerkiksi funktion määrittelyn yhteydessä. Jos käyttäjä haluaa määritellä yhteenlaskufunktion, mutta ei halua heti määritellä yhteenlaskettavien arvojen tai muuttujien tyyppejä, on mahdollista antaa funktion määrittelystä malli. Malli siis ei rajoita funktion toimintaa yhteen tyyppiin, vaan mahdollistaa sen toiminnan minkä tahansa tyypillä, jota ei ennalta tiedetä. Alla yksinkertainen esimerkki yhteenlaskufunktiosta, joka käyttää mallia:
template <typename T> void pluslasku(T x, T y) { cout << "Summa: " << x + y << endl; }
Tutkikaamme nyt edelläolevaa koodia. Siellä on havaittavissa template-avainsana, joka siis tekee funktiosta mallin. Huomaa <>-merkkien sisällä oleva typename T joka määrittelee T:n ennalta määritetyksi tyypiksi. Voisimme myös käyttää class T, mahdollistaen luokkien käytön. Sen jälkeen tulee itse funktio, jonka parametreinä on annettu x ja y ja jotka mollemat ovat siis tyyppiä T. Funktiota voidaan kutsua seuraavasti:
pluslasku<int>(1,2); // tulos: Summa: 3
Tai näin:
pluslasku<double>(2.34, 4.66); // tulos = 7.00
Ominaisuudet eivät suinkaan rajoitu tähän: mallien yksi perusideoista on tyyppien johtaminen. Eli tarkoittaa käytännössä sitä, että esimerkiksi mallifunktio osaa päätellä mitä tyyppiä sille annetaan. Toisin sanoen plus(1, 2) toimisi yhtä hyvin kuin plus<int>(1, 2).
Säiliöt
Mitä säiliöt sitten oikein ovat? Jotta voisi parhaiten ymmärtää säiliöiden toimintaperiaatteen, niitä kannattaa käsitellä ikään kuin "isoina taulukoina". Niillä on kumminkin yksi tärkeä ominaisuus: geneerisyys. Toisin sanoen, niiden on kyettävä toimimaan millä tahansa tietotyypillä. Tämä on mahdollista mallien avulla, kuten edellä selvisi.
Esimerkiksi, kuvitellaan kaksi lukutaulukkoa: yksi niistä sisältäisi desimaalilukuja ja toinen sisältäisi kokonaislukuja. Kumminkin, ulkoisesti niiden pitäisi olla täysin samanlaisia -- perustoimintojen täytyy olla samat.
Toisin ilmaistuna säiliö on "taulukko", jonka tyyppi voi olla mitä vain. Sen sijaan, että tehdään n+1 erilaista taulukkoa, tehdään yksi taulukkotyyppi, jonka määrittelyn yhteydessä voidaan ilmaista, mitä ne sisältävät. Käyttäjä voi siis kuvitella olevansa omenoiden kasvattaja, joka kerää eri lajikkeet erivärisiin ämpäreihin. Itse kasvattajalle tämä ei aiheuttaisi mitään ongelmaa — ämpäreitä tarvitsee vain ostaa erivärisinä ja käyttää tarpeen mukaan.
Kumminkin, ohjelmoijan kannalta homma on astetta monimutkaisempi, sillä kyse ei ole vain "ostamisesta" ja "käyttämisestä", vaan ohjelmoijalle jää työksi myös tehdä kyseinen "ämpäri". Kärjistäen se tarkoittaisi sitä, että ohjelmoijan pitäisi määritellä jokainen tyyppi erikseen, eli "rakentaa" se. Sen takia, työn säästämiseksi, olisi ohjelmoijan viisaampaa tehdä yksi samanvärinen ämpärityyppi, jossa lukisi sen sisältämä omenalajike. Tietysti tämähän kävisi omenanviljelijällekin, mutta on huomattavasti työläämpää lukea joka purkin kyljestä lajikenimi, kuin vilkaista purkkia värin perusteella.
Niinpä siis STL:n säiliöt ovat juuri näitä "ämpäreitä". Yksi näistä on vector. Muita säiliöitä ovat muun muassa set, list ja map. Kaikki ovat kumminkin erilaisia, ja tarkoitukseemme vector sopii parhaiten, sillä se on dynaaminen taulukko. Seuraavassa esimerkissä vähän monimutkaisempi vectorin käyttötapa:
void main(int argc, char **argv) { vector<int> v; vector<int>::iterator iteraattori; for(int i = 0; i < 10; i++) v.push_back(i); int loppu = 0; iteraattori = v.begin(); while (iteraattori != v.end()) { loppu += *iteraattori; iteraattori++; } cout << "Lopullinen arvo: " << loppu << endl; }
Tässä koodissa luomme kokonaislukusäiliön ja lisäämme sinne kymmenen kertaa joka kerralla kasvavia lukuja Sitten tulostamme viimeisen arvon, jossa v.end() palauttaa iteraattorin vektorin loppuun. Tässä siis 45. Yksinkertaimillaan iteraattorit voisi kuvailla ns. "laskimiksi" eli tavallaan ne lukevat luvun vektorista ja hyppäävät yhdellä. Iteraattoreihin pätee myös mallisäännöt, joten voit määritellä iteraattorin mille tahansa tyypille.
On tietenkin olemassa monia muita säiliöitä, esimerkiksi list, jonka mainitsin edellä. list ei eroa vektorista kovinkaan paljon: se tarjoaa vain nopeammat tietueiden tallennuksen- ja poistamismahdollisuuden. Säiliöillä on paljon yhtäläisyyksiä: samat perusfunktiot (mukaanlukien erase, swap ja assert), vertailuoperaattorit (!= == jne.) ja myöskin mahdollisuus käyttää yhtä tiettyä tyyppinimeä. Vektorilla (kuten muillakin säiliöillä) on miellyttäviä ominaisuuksia:
- Muistinvaraus itsenäistä: käyttäjän ei tarvitse huolehtia siitä
- ...kuten ei muistinvapautuksestakaan: hyvästi muistivuodot!
- Perusalgoritmit, kuten push_back, pop_back, erase, swap ja assign
Iteraattorit toimivat ikään kuin "laskureina" joiden avulla voimme siirtyä säiliöissä eteen- ja taaksepäin. Myöskin voimme palauttaa luettavannäköisen arvon mistä tahansa säiliöstä. Iteraattoreita voi verrata monesti osoittimiin (sitä ne ovatkin, mutta ei sillä nyt väliä). Sitäpaitsi ne palauttavatkin arvon osoittimena. Monet funktiot palauttavat iteraattorin tiettyyn kohtaan säiliötä, esimerkiksi vector::begin()palauttaa iteraattorin vektorin alkuun. Siis jos haluamme siirtyä eteempäin vektorissa ja hakea vaikka neljännen arvon ja ollaan kolmannessa, niin yksinkertaisesti kasvatamme iteraattoria yhdellä: iteraattori++;. Jos haluamme saada vektorin ensimmäisen arvon, niin emme tee sitä näin:
cout << v.begin() << endl; // tulos: roskaa
Tässä tapauksessa tulosteeksi annetaan osoitin iteraattorin, mikä ei tietenkään ole luettavaa, ellet sitten juoksentele kadulla alasti huutaen ""En Taro Adun!" nyrkit sumpussa. kuin lahopää. Jos kumminkin olet utelias, voit selvittää asian itse. Tarvitsemme siis iteraattorin osoittaman tyypin, emmekä itse osoitetta.
vector<int> v; vector<int>::iterator i; // int - tyyppinen iteraattori vektoriin v.push_back(1); // alkuun 1 v.push_back(3); i = v.begin(); i++; // siirrytään TOISEEN arvoon int arvo = *i; // huomaa osoitin cout << arvo << endl; // arvo coutille, tulos: 3
Tämä siis antaa meille kokonaisluvun osoittimen vektorin v alussa oleevaan arvoon. Tässä tapauksessa yksi. Kokeile huvin vuoksi korvaamalla viimeisellä rivillä oleva arvo i:llä, niin näet mitä selitin.
On olemassa monenlaisia iteraattoreita...on olemassa "yksisuuntaisia" jotka lukee/kirjoittaa arvoja containerista tai sitten kaksisuuntaisia. Allaolevassa taulukossa kaikki iteraattorityypit.
| Iteraattori | Kuvaus |
|---|---|
| input_iterator | Lukee tietueita ja siirtää iteraattoria eteenpäin. Näille voi tehdä vertauksia sekä suurennuksia (iteraattori++) ja antaa arvoja. |
| output_iterator | Kirjoittaa tietueita ja siirtää iteraattoria eteenpäin. Näille voi tehdä suurennoksia ja antaa arvoja. |
| forward_iterator | Kirjoittaa ja lukee tietueita ja siirtää iteraattoria eteenpäin. Nämä yhdistävät input- ja output_iterator:in ominaisuudet mahdollistamalla tietueiden tallennuksen. |
| bidirectional_iterator | Kaksisuuntainen iteraattori joka lukee/kirjoittaa ja siirtää iteraattoria eteen- tai taaksepäin. Ihan kuten edellinen mutta näitä voi pienentää. |
| random_iterator | Kaksisuuntainen iteraattori jossa on satunnainen luku/kirjoitusoikeus joka siirtää i
teraattoria eteenpäin. Satunnainen luku/kirjoitusoikeus tarkoittaa sitä että voimme osoittaa mitä tahansa kohtaa iteraattoria esim. hyppäämme 1:stä 7:skaan toisin kuten kaksisuuntaisisissa, joutuisimme hyppimään 7 kertaa. |
| reverse_iterator | Joko satunnainen tai kaksisuuntainen iteraattori mutta toimii toiseen suuntaan. |
Jokainen STL:n sisältää sisältää iteraattorin ja myöskin jokainen STL:n algoritmi käyttää tietyn tyyppistä iteraattoria. Satunnaiset iteraattorit poikkeavat normaaleista iteraattoreista siten, että voimme katsoa mitä tahansa kohtaa iteraattoria, eikä meidän tarvitse hyppiä ylettömästi. Yleensä säiliöt käyttävät niitä. Tässä esimerkki:
vector<int>::iterator i; // vector::iterator on satunnaisiteraattori vector<int> v; for(int i = 0; i <= 10; i++) v.push_back(i); i = v.begin(); i += 7; // siirytään seitsemänteen arvoon // kumminkaan emme voi tehdä i = 7 vaan joudumme aina hyppimään.... // normaaleilla joutuisimme tekemään i += 1; 7 kertaa. int arvo = *i; cout << i << endl;
Normaaleissa tapauksissa joutuisimme käyttämään for-looppia (tai jotakin muuta tapaa suurentaa sitä), mutta nämä satunnaisiteraattorit ovat juuri sen takia käteviä koska ei yksinkertaisesti tarvitse käyttää for - looppeja, vaan voimme suoraan osoittaa kahdeksanteen arvoon.
Algoritmit
Algoritmit ovat huomattava osa STL:ää, jotka helpottavat monin verroin koodaajan työtä. Kun lajittelet vektoria, niin sen sijaan että kävisit läpi kokonaisen vektorin ja samalla tallennat lajitellun tiedot toiseen vektoriin iteraattoreiden avulla, niin sen voi tehdä yhdessä hujauksessa sortin avulla. Sort on määritelty STL:ssä näin:
template void sort(RandomAccessIterator first, RandomAccessIterator last);
RandomAccessIterator on tietenkin satunnaisiteraattori elikkä esimerkiksi vector::iterator palauttaa satunnaisiteraattorin. first on lajittelun alkukohta ja last loppukohta. Voimme käyttää sort-algoritmia näin:
vector<string> v; v.push_back("foo"); v.push_back("bar"); sort(v.begin(), v.end());
Tuossa siis luomme string-tyyppejä sisältävän vektorimallin ja pistämme sinne kaksi merkkijonoa. Sitten rivillä 4 lajittelemmev.begin():stä v.end():iin (jotka ovat molemmat satunnaisiteraattoreita) käyttämällä sort():ia. Mutta! Tässä pätkässähän käytin std::sortia, kun taas vector-luokka tarjoaa oman metodin, mitä siis oikein menin tekemään? No, yksi syy voi olla se, että itse vector-luokan tarjoama sort-metodi vaatii < ja > -vertailuoperaattoreiden määrittelyn. Miten sitten tulostamme kyseisen vektorin? Pitääkö taas tehdä n2n+α silmukkaa? No, ei. Avuksi tulee algoritmi copy joka on määritelty näin:
template <class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
Tässä InputIterator first on sisäänpäin suuntautunut iteraattori, josta lukeminen alkaa ja InputIterator last, johon lukeminen päättyy. OutputIterator result on taas ulospäin suuntautunut iteraattori, joka hoitaa tiedon tallentamisesta — toisin sanoen paikka, minne iteraattoreiden tieto ohjataan iteraattorin muodossa.
copy(v.end(), v.begin(), ostream_iterator(cout, "\n"));
Tässä koodissa käytämme ostream_iterator -iteraattoria, joka on ulospäin suuntautunut virtaiteraattori. Mallien sääntöä noudattaen se soveltuu mille tahansa std::ostream-virrasta johdetulle virtatyypille. Toisin sanoen, voit vaikka kirjoittaa oman socket-virran ja tehdä sille serialisointijärjestelmän (ooh!) ja lähetellä verkon yli toiselle ohjelmalle suoraan vaikka structeja. Ihanaa. C# osaa tämän jo tosin :)
Algoritmit ovat eräänlainen siunaus ohjelmoijalle. Useat helpottavat ongelmien ratkontaa, ohjelmien suunnittelua, parantavat luettavuutta ja lisää suorityskykyä. Kaikki varmaan haluavat käyttää foreach-algoritmia säiliön läpikäymiseen, tai sitten käyttää back_inserter-algoritmia iteroinnissa. Tässä esimerkki yhdestä algoritmista:
#include <algorithm> #include <string> #include <iterator> #include <vector> #include <iostream> using namespace std; int main(int argc, char **argv) { vector<string> v; // tungetaan neljä merkkijonoa v.push_back("to be or not to be"); v.push_back("that is a question"); v.push_back("what now matters, however"); v.push_back("does my horse have a fever?"); // lajitellaan sort(v.begin(), v.end()); cout << "Vektori lajiteltuna:" << endl; copy(v.begin(), v.end(), ostream_iterator<string>(cout, "\n")); cout << "Vektorissa oli " << count(v.begin(), v.end(), "a"); cout << "kappaletta a-kirjainta" << endl; }
Nyt siis laitamme neljä englanninkielistä älyvapaata lausetta vektoriimme. Sitten lajittelemme, käytämme copy-metodia ja läpikäymme vektorin käyttämällä "\n" -erotinta. Sen jälkeen laskemme montako kappaletta vektorissa oli a-kirjaimia. Nyt voimmekin antaa mielikuvitukselle tilaa ja lisätä ohjelmaan syötteen.
#include <algorithm> #include <string> #include <iterator> #include <vector> #include <iostream> using namespace std; int main(int argc, char **argv) { vector<string> v; string sana; // tungetaan kaksi merkkijonoa v.push_back("foo"); v.push_back("bar!"); v.push_back("fuschbar"); v.push_back("foo"); // lajitellaan sort(v.begin(), v.end()); cout << "Vektori lajiteltuna:" << endl; copy(v.begin(), v.end(), ostream_iterator<string>(cout, "\n")); // pyydetään syöttöä cout << "Anna sana: "; getline(cin, sana); cout << "Vektorissa oli " << count(v.begin(), v.end(), sana.c_str()); cout << " kappaletta " << sana << " - sanaa" << endl; }
Tässä siis kysytään sanaa, jonka koko on maksimissaan kymmenen merkkiä. Itse voit yrittää tehdä sellaisen systeemin joka kysyy mitä lisätään ko. vektoriin. Mutta se onkin astetta monimutkaisempi juttu, ja sitä tässä artikkelissa ei käsitellä ollenkaan.
