STL: Lyhyenläntä oppimäärä

 

Standard Template Libraryn idea

STL on C++:n oma kirjasto, joka sisältää kaikenlaista yleishyödyllistä kivaa. Se on toteutettu pitkälti mallien avulla, geneerisen ohjelmoinnin periaatteiden mukaan. STL ei ole pelkästään kokoelma hyödyllisiä ohjelmanpätkiä, vaan laajennettava kehysjärjestelmä (framework), jonka avulla voidaan luoda uusia geneerisiä järjestelmiä.

STL:n ytimen muodostovat tietorakenteet (containerit tai suomettuneesti "kontit") ja niihin sovellettavat algoritmit. Niiden välissä ovat iteraattorit. Voidaan ajatella, että iteraattori on abstraktio tietorakenteiden käsittelystä, samalla tavalla kuten naulaaminen on abstraktio naulan ja naulaajan välisestä toiminnasta. Iteraattoreiden avulla voidaan erottaa toiminnallisuus (algoritmit) ja data (tietorakenteet) - kun vertaat tätä lähestymistapaa oliosuunnitteluun, huomaat kuinka se eroaa "luokassa on kapseloitu toiminnallisuus ja data" -ajattelusta.

 

Tietorakenteet ja lähes tietorakenteet

Containerit, kontit, tietorakenteet - miksi niitä haluaakaan kutsua - ovat STL:n ydin. STL:n tietorakenteet astuvat kuvaan kun taulukot eivät riitä. Geneerisen ohjelmoinnin periaatteiden mukaan eri tietorakenteiden välillä ei ole juurikaan yhteyksiä: mitään tietorakenteiden hierarkiaa ei ole. Koska suorituskyky on hyvin tärkeää yleiskäyttöisessä, suuria tietomääriä käsittelevässä koodissa, ei rakenteisiin ole toteutettu sellaisia ominaisuuksia jotka eivät ole niille ominaisia - eli sellaiset ominaisuudet jotka olisi ollut mahdollista toteuttaa, mutta jotka olisivat toimineet hitaasti, on jätetty pois (esimerkkinä listan indeksointi).

Tärkeimmät containerit ovat: vector<...>, joka on vektori eli taulukko jonka koko voi muuttua; list<...> eli linkitetty lista, kätevä kun alkiota lisätään ja poistetaan paljon; stack<...> eli pino ja queue<...> eli jono, ensimmäisenä laitettu alkio tulee pinosta viimeisenä, jonosta ensimmäisenä (kuten nimistä voikin päätellä); map<...> eli sanakirja eli hakupuu, josta alkiota voidaan hakea nopeasti avaimen perusteella (kuten nimi numeron perusteella) ja set<...> eli joukko, jossa samanarvoisia alkioita voi olla vain yksi. Hyvin pitkälle pääsee jo vector<...>, list<...> ja map<...> -kolmikolla. Lisäksi löytyvät puoliveriset tietorakenteet, kuten string eli merkkijono ja array eli normaali taulukko, jotka tukevat osittain containerien operaatioita.

 

Iteraattorit

STL:n tietorakenteet eivät ole samasta tyypistä periytettyjä, joten jotta algoritmejä (kuten järjestely) ei tarvitse toteuttaa erikseen niille kaikille, tulee välissä olla jotakin. Se jotakin on iteraattorit. Iteraattorit ovat abstrahoituja iteroimisen eli plaraamisen tapahtumia: jos tietorakenteet olisivat kirjoja, niin iteraattorit olisivat "sivunkääntimiä". Iteraattoreilla ei myöskään ole yhteistä kantaluokkaa, mutta ne tukevat samoja operaatioita. Tärkeimpiä ovat kasvatus (i++, ++i, i += 4) ja vastaavat vähennykset sekä alkion arvon haku (*i). Kuten huomaat, normaali osoitin taulukon alkioon on myös iteraattori: sitä voidaan kasvattaa, jolloin se siirtyy alkion koon mukaisilla askelilla ja *-operaattorilla saadaan sen osoittama arvo.

Kun iteraattori luodaan, tulee luonnollisesti tietää sen tyyppi. Sen löytyy määriteltynä (typedefin avulla) tietorakenteen luokasta, nimellä iterator. Mikäli iteraattorin avulla vain luetaan tietoja, voimme käyttää tyyppiä const_iterator. Koska tyypin määrittely tietorakenneluokan kautta on kohtuullisen vaivalloinen kirjoittaa, kannattaa usein määritellä uusi tyyppinimi sille (eli käyttää typedefiä). Tässäpä esimerkki, toivottavasti näet kuinka takana olevien tietorakenteiden erot häviävät kun niitä käsitellään iteraattorien kautta:

#include<iostream>
#include<vector>
#include<list>
#include<string>

int main() 
{
	// otetaan kaksi containeria
	vector<string> vec;
	list<string> lis;

	// työnnetään niihin tietoa (vec:ssä on tuplasti enemmän alkioita)
	vec.push_back(string("Satu"));
	vec.push_back(string("meni"));
	lis.push_back(string("saunaan,"));
	vec.push_back(string("pani"));
	vec.push_back(string("laukun"));
	lis.push_back(string("naulaan."));

	// Otetaan iteraattorit, huomaa että iteraattorien tyyppi tulee aina
	// ottaa luokan tyyppimäärittelyistä, yleensä kannattaa määritellä typedef
	// helpottamaan kirjoittamista - kuten jälkimmäisessä on tehty
	vector<string>::iterator vi = vec.begin();
	typedef list<string>::iterator list_iter;
	list_iter li = lis.begin();

	// Kunnes vektorin iteraattori tulee loppuun...
	while (vi != vec.end()) {
		// Ensin otetaan iteraattorin osoittama arvo (*-operaattori), sitten
		// kasvatetaan sitä
		std::cout << *vi++ << " ";
		std::cout << *vi++ << " ";
		std::cout << *li++ << " ";
	}
	
	return EXIT_SUCCESS;
}

 

Algoritmit

Olen väsymättömästi toistanut, kuinka iteraattorit toimivat tietorakenteiden ja algoritmien välissä. Ja nyt se nähdään: algoritmit eivät syö tietorakenteita, vaan tarvitsevat iteraattorin tietorakenteen alkuun ja loppuun. Eli vektori (mikä tahansa muu tietorakenne) järjestellään:

sort(vektori.begin(), vektori.end());

Tärkeimpiä algoritmeja ovat: sort, joka järjestelee tietorakenteen (ei voi käyttää listaan!); merge joka yhdistää kaksi järjesteltyä rakennetta säilyttäen järjestyksen; unique joka siirtää duplikaatit (samat alkiot) järjestellystä rakenteesta loppuun ja palauttaa iteraattorin uniikkien alkioiden alueen loppuun; find joka etsii jonkin alkion ja palauttaa iteraattorin siihen; count joka laskee tiettyjen alkioiden lukumäärän ja max_element (tai min_element vastaavasti) joka paluttaa iteraattorin suurimpaan elementtiin. Allapa on henkilöstohallinnollinen esimerkki, huomaa kuinka näpsäkästi algoritmit toimivat ihan tavallisten C-taulukoiden kanssa:

#include<string>
#include<vector>
#include<algorithm>
#include<iostream>

using std::cout;
using std::endl;

int main()
{
	vector<string> tyontekijat;
	tyontekijat.push_back(string("Raimo"));
	tyontekijat.push_back(string("Liisa"));
	tyontekijat.push_back(string("Kalle"));
	tyontekijat.push_back(string("Liisa"));
	tyontekijat.push_back(string("Benjamin"));

	// järjestellään työntekijät
	sort(tyontekijat.begin(), tyontekijat.end());

	// Liisoja on kaksi, erotetaan toinen kun ei koskaan muista
	// että kumpi on kumpi
	vector<string>::iterator new_end = unique(tyontekijat.begin(), tyontekijat.end());

	// Hesekiel tulee Kallen tilalle
	*find(tyontekijat.begin(), new_end, string("Kalle")) = string("Hesekiel");

	for (vector<string>::const_iterator i = tyontekijat.begin(); i != new_end; ++i)
		cout << *i << endl;

	int palkat[] = {17000, 11000, 9000, 9000};
	
	cout << "Yhdeksää tonnia saa " << count(&palkat[0], &palkat[4], 9000) << ", suurin palkka on " << *max_element(&palkat[0], &palkat[2]) << endl;

	return EXIT_SUCCESS;
}

 

Virrat

C++:n virrat ovat hyvin monipuolisia vekkuleita. Kaikki on parametrisoitu: esimerkiksi sovittaminen uuteen merkistöön on täysin mahdollista. Normaali kuolevainen ohjelmoija kuitenkin harvoin tarvitsee tuonkaltaisia ominaisuuksia. Peruskoodaajan kannalta tärkein asia on mahdollisuus omien tyyppien sovittamiseen mukaan virtoihin. Se tapahtuu määrittelemälle operaattori <<, joka saa parametrikseen virran ja sinne pukattavan kanootin. Hyvin näppärä apu ovat myös stringstreamit, virrat jotka tulostavat merkkijonoon. Niitä on kiva käytellä lukujen muuttamiseen merkkijonoiksi, tähän tyyliin:

#include<iostream>
#include<sstream>
#include<string>

// oma lukutyyppimme, ei vielä vakiintunut normaalikäytössä
class huuhaaluku
{
public:
	int hups;
	int hips;
};

ostream& operator<<(ostream& o, const huuhaaluku h)
{
	stringstream ss;
	ss << h.hups * 5 + h.hips << "!!" << h.hips;

	return o << ss.str();
}

int main()
{
	huuhaaluku h;
	h.hips = 5;
	h.hups = 3;

	std::cout << "Huuhaa: " << h << std::endl;

	return EXIT_SUCCESS;
}

 

Numerot ja matematiikka

STL tarjoaa moninaisia ominaisuuksia myös numeerisiin karkeloihin. Tavallisimpia on numeric_limits<...>-malli, jolla saa selville eri numerotyyppien lukualueiden rajoja ja perinteiset matemaattiset funktiot kuten sini, kosini, tangentti ja neliöjuuri. Paletista löytyy myös matemaattisiin vektorioperaatioihin suunniteltu val_array ja matriisien esittämistä varten slice. Tässä pieni esittelykierros:

#include<cmath>
#include<limits>
#include<iostream>

using namespace std; // jotta esimerkki säilyisi lyhyenä...

int main() 
{
	cout << "intin lukualue on " << numeric_limits<int>::min() << " - " << numeric_limits<int>::max() << endl;
	cout << "unsigned intin lukualue on " << numeric_limits<unsigned int>::min() << " - " << numeric_limits<unsigned int>::max() << endl;

	double i = -1.0;

	// otetaan i:n itseisarvon neliön neliöjuuren sinin arkussinin vastaluku
	double r = -asin(sin(sqrt(pow(abs(i), 2))));

	cout << "r on " << r << endl; // pitäisi tulla -1.0, pyöristysvirheet poislukien

	return EXIT_SUCCESS;
}

 

Takaisin