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