STL:n algoritmit¶

STL-kirjasto algorithm tarjoaa valmiina yleisimmät operaatiot, joita säiliön sisältämille alkioille on tarpeen tehdä. Algoritmikirjaston käyttämiseksi on koodiin lisättävä

#include <algorithm>

STL:n valmiit algoritmit ovat geneerisiä: Ne eivät ota kantaa säiliön tyyppiin, vaan ne osaavat operoida millä tahansa säiliöllä. (Tosin aika moni alla lueteltavista algoritmeista ei toimi map- ja set-rakenteilla, joista kerrotaan seuraavassa teorialuvussa.)

Käsiteltäväksi haluttu osa säiliön alkioista kerrotaan algoritmifunktiolle iteraattorivälin avulla. Jokaisella funktiolla on aina vähintään kaksi iteraattoriparametria.

Esimerkiksi algoritmi (siis funktio) sort osaa lajitella vector-rakenteen alkiot kasvavaan järjestykseen, kunhan sille kerrotaan iteraattoreilla lajiteltavaksi haluttu osaväli:

vector<double> reaalivektori;
...
sort(reaalivektori.begin(), reaalivektori.end());

Kannattaa pitää mielessä, että begin- ja end-iteraattorien paikalla mikä tahansa kahden iteraattorin esittämä osaväli on kelvollinen:

vector<double>::iterator valin_eka = reaalivektori.begin();
vector<double>::iterator valin_vika = reaalivektori.end();
++valin_eka;   // Osoittaa nyt toiseen alkioon
--valin_vika;  // Osoittaa nyt viimeiseen alkioon

// Lajitellaan vektorin sisällä kaikki alkiot
// ensimmäistä ja viimeistä lukuunottamatta.
// Ensimmäinen ja viimeinen pysyvät paikallaan.
sort(valin_eka, valin_vika);

Tärkeä huomio: algoritmikirjaston operaatiot eivät koske jälkimmäisen iteraattoriparametrin osoittamaan alkioon. Edellisessä esimerkissä siis viimeinen vektorin alkio ei enää tullut lajitelluksi, koska valin_vika osoitti siihen.

Seuraavassa lyhyt lista muista hyödyllisistä algoritmikirjaston funktioista. Suurimmassa osassa esimerkkirakenteena on vector, koska se on tässä vaiheessa ainoa tuttu STL-säliötyyppi. Kuitenkin, mikäli ei eriksen mainita, funktiot toimivat muillakin säiliötyypeillä ja merkkijonoilla (string).

count laskee säiliössä olevien tietyn arvoisten alkioiden lukumäärän:

vector<string> vihamiehet;
...
// Kuinka monta Akia vihamiehet-vektorista löytyy?
cout << count(vihamiehet.begin(), vihamiehet.end(), "Aki")
     << " kappaletta Aki-nimisia vihamiehia!" << endl;

count-funktio ei toimi map-rakenteella aivan yhtä suoraviivaisesti.

min_element ja max_element etsivät säiliöstä arvoltaan pienimmän tai suurimman alkion ja palauttavat iteraattorin, joka osoittaa kyseiseen alkioon:
```
vector<int> maarat;
...
vector<int>::iterator pienin_it;
pienin_it = min_element(maarat.begin(), maarat.end());
cout << "Pienin lukumaara: " << *pienin_it << endl;
```
min_element- ja max_element-funktiot eivät toimi map-rakenteella aivan yhtä suoraviivaisesti.

find etsii säiliöstä haluttua arvoa ja palauttaa iteraattorin ensimmäiseen löytämäänsä alkioon tai käsiteltävänä olevan säiliön end-iteraattorin, jos arvoa ei löydy:

vector<string> potilaat;
...
vector<string>::iterator iter;
iter = find(potilaat.begin(), potilaat.end(), "Kai");
if ( iter == potilaat.end() ) {
    // Ei ole Kaita potilasjonossa.
    ...
} else {
    // Kai löytyi ja se sijaitsee iter:in osoittamassa
    // kohdassa: tulostetaan ja poistetaan jonosta.
    cout << *iter << endl;

    // vector-säiliöllä on metodi erase, jolla
    // iteraattorin osoittama alkio voidaan poistaa.
    potilaat.erase(iter);
}

Kannattaa pitää mielessä, että string-tietotyypillä ja myöhemmin tutuiksi tulevilla set- ja map-rakenteilla on metodifunktio nimeltä find, jota kannattaa ehdottomasti käyttää, koska varsinkin kahden jälkimmäisen tapauksessa se on monta kertaluokkaa nopeampi kuin algoritmi-kirjaston find.

replace korvaa kaikki halutut arvot uudella arvolla:
```
replace(tekstivektori.begin(), tekstivektori.end(), "TTY", "TUNI");
```
jossa kaikki vektorissa olevat alkiot, joiden arvo on “TTY” korvataan arvolla “TUNI”.

replace ei toimi set-rakenteella tai map-rakenteella.

fill muuttaa kaikki iteraattorivälin alkiot annetun arvoisiksi:

string merkkijono = "";
...
// Seuraavan fill-operaation jälkeen koko
// merkkijono on täynnä kysymysmerkkejä.
fill(merkkijono.begin(), merkkijono.end(), '?');

fill ei toimi set-rakenteella tai map-rakenteella.

reverse kääntää annetun välin takaperoiseen järjestykseen:

vector<Pelaaja> vuorojarjestys;
...
// Seuraavalla pelikierroksella
// vuorojärjestys on käänteinen.
reverse(vuorojarjestys.begin(), vuorojarjestys.end());

reverse ei toimi set- ja map-rakenteilla ollenkaan.

shuffle sekoittaa alkiot satunnaiseen järjestykseen:
```
vector<Pelikortti> korttipakka;
minstd_rand gen; // Luodaan satunnaislukugeneraattori nimeltä gen
...
shuffle(korttipakka.begin(), korttipakka.end(), gen);
```
shuffle ei toimi set- ja map-rakenteilla ollenkaan.

C++:ssa on valmiina määritelty useita erilaisia satunnaislukugeneraattoreita, jotka löytyvät kirjastosta random. Tietotyypin minstd_rand avulla voit luoda yhdenlaisen satunnaislukugeneraattorin ja aiemmin esiintyneen default_random_engine-tyypin avulla toisen. Tässä vaiheessa riittää, että osaat luoda näistä yhden (tai molemmat). Halutessasi voit hakea internetistä lisätietoa C++:n erilaisista satunnaislukugeneraattoreista.
copy kopioi säiliön alkiot johonkin toiseen säiliöön:
```
string merkkijono = "";
...
// Alustetaan merkkivektori siten, että siinä on
// yhtä monta alkiota kuin merkkijonossa on merkkejä.
// Huomaa että tässä on taas tilanne,
// jossa alustuksessa pitää käyttää kaarisulkeita.
vector<char> merkkivektori(merkkijono.length());

// Kopioidaan kaikki merkkijonon merkit
// alkioiksi merkkivektoriin.
copy(merkkijono.begin(), merkkijono.end(), merkkivektori.begin());
```
Kopioinnin kohteessa (siis siellä minne alkiota kopioidaan) pitää olla valmiiksi tilaa tarjolla. Edellä merkkivektori on valmiiksi alustettu sisältämään yhtä monta alkiota kuin merkkijono:ssa on merkkejä.

Tämä pätee kaikkiin STL-algoritmeihin, jotka tallettavat tuloksia säiliöön: Kohdesäiliössä pitää olla valmista tilaa kaikille talletettaville alkioille.

Lähtösäilion ja kohdesäiliön alkioiden tyyppien pitää olla samat.

Useista algorithm-kirjaston funktioista on olemassa versio, jonka toimintaa voidaan säätää funktioparametrin avulla. Otetaan tässä esimerkkinä sort-funktio.

Ennen varsinaista asiaa, on tärkeä ymmärtää, että sort-funktio ei voi lajitella suuruusjärjestykseen kuin sellaista tietoa, jolle on määritelty jonkinlainen suuruusrelaatio. Tämä ei päde esimerkiksi vektorille, jonka alkiot ovat värejä, sillä ei ole ollenkaan itsestäänselvää, onko purppura pienempi vai suurempi kuin vaikkapa violetti, koska väreillä ei ole suuruusjärjestystä.

Tämä ei ole ongelma silloin, kun lajiteltavassa säiliössä on alkioina kielen perustyyppistä tietoa, merkkijonoja tai joitakin muita C++:ssa valmiiksi määriteltyjä tyyppejä. Mutta heti, jos yritetään käsitellä omatekemiä tyyppejä (luokkia), joita ei pystytä automaattisesti vertailemaan, törmätään ongelmiin.

Tutkitaan pieni esimerkki (tilan säästämiseksi epäolennaisia koodirivejä jätetty pois):

class Opiskelija {
public:
    Opiskelija(string const& nimi, int opnum);
    string hae_nimi() const;
    int hae_opnum() const;
    void tulosta() const;
private:
    string nimi_;
    int opnum_;
};


bool vertaile_opiskelijanumeroita(Opiskelija const& op1,
                                  Opiskelija const& op2) {
    return op1.hae_opnum() < op2.hae_opnum();
}


bool vertaile_nimia(Opiskelija const& op1,
                    Opiskelija const& op2) {
    return op1.hae_nimi() < op2.hae_nimi();
}


int main() {
    vector<Opiskelija> opiskelijat = {
        { "Teekkari, Tiina", 121121 },
        { "Arkkari, Antti",  111222 },
        { "Fyysikko, Ville", 212121 },
        { "Teekkari, Teemu", 100011 },
        { "Kone, Kimmo",     233233 },
    };

    // Järjestetään nousevaan järjestykseen opiskelijanumeroiden perusteella
    // ja tulostetaan
    sort(opiskelijat.begin(), opiskelijat.end(), vertaile_opiskelijanumeroita);
    for ( auto opisk : opiskelijat ) {
        opisk.tulosta();
    }

    cout << string(30, '-') << endl;

    // Järjestetään nousevaan järjestykseen nimen perusteella
    // ja tulostetaan
    sort(opiskelijat.begin(), opiskelijat.end(), vertaile_nimia);
    for ( auto opisk : opiskelijat ) {
        opisk.tulosta();
    }
}

Esimerkin funktiot vertaile_opiskelijanumeroita ja vertaile_nimia ovat nk. vertailufunktioita:

Parametrit (2 kpl) ovat vakioviitteitä sen tietotyypin alkioihin, joita funktion on tarkoitus vertailla.
Paluuarvon tyyppi on bool.
Paluuarvo on true täsmälleen silloin, kun ensimmäinen parametri on aidosti pienempi kuin toinen parametri.

Vertailufunktion voi antaa lisäparametrina sellaisille algoritmikirjaston funktioille, joiden toiminta riippuu käsiteltävänä olevan säiliön alkioiden suuruudesta.

Näin ollen edellisen esimerkin vektorista voitaisiin hakea ja tulostaa opiskelijanumeroltaan suurin opiskelija:

vector<Opiskelija>::iterator iter;
iter = max_element(opiskelijat.begin(),
                   opiskelijat.end(),
                   vertaile_opiskelijanumeroita);

// Koska seuraava tulosta-metodi kohdistetaan
// iteraattorin osoittamaan olioon, käytetään
// -> -operaattoria pisteen sijaan.
iter->tulosta();

Kun vertailufunktio annetaan parametrina algoritmikirjaston funktiolle, kutsukohdassa käytetään pelkkää funktion nimeä. Jos funktion perässä olisi kaarisulkeet, yrittäisi kutsua funktiota ja antaa parametrina vertailufunktion paluuarvon, mikä ei ole tarkoitus.

Funktioita, jotka saavat parametrina toisen funktion, kutsutaan korkeamman kertaluvun funktioiksi (higher-order function).