STL:n algoritmit

---

STL:n <algorithm>-kirjasto tarjoaa valmiita yleisiä toimintoja säiliöiden alkioiden käsittelyyn. Ota algoritmit käyttöön lisäämällä ohjelmaan:

#include <algorithm>

Algoritmit toimivat iteraattorien kautta. Niiden käyttämä säiliö tai sen osa annetaan tavallisesti puoliavoimena iteraattorivälinä: alkuiteraattori osoittaa ensimmäiseen käsiteltävään alkioon ja loppuiteraattori heti viimeisen käsiteltävän alkion jälkeiseen kohtaan. Loppuiteraattorin osoittamaa alkiota ei käsitellä.

Algoritmit ovat geneerisiä siinä mielessä, etteivät ne yleensä vaadi tiettyä säiliöluokkaa. Käyttökelpoisuus riippuu kuitenkin algoritmin vaatimista iteraattoriominaisuuksista ja siitä, sallivatko säiliön alkiot muutokset. Esimerkiksi sort vaatii satunnaispääsyiteraattorit, joten se toimii vektoreilla ja merkkijonoilla mutta ei esimerkiksi list-, set- tai map-säiliöillä.

Järjestäminen: sort

sort järjestää annetun välin oletuksena nousevaan järjestykseen:

vector<double> reaalivektori;
// ... lisätään vektoriin arvoja
sort(reaalivektori.begin(), reaalivektori.end());

Algoritmille voi antaa myös säiliön osavälin. Seuraavassa järjestetään kaikki paitsi ensimmäinen ja viimeinen alkio:

vector<double>::iterator valin_eka = reaalivektori.begin();
vector<double>::iterator valin_vika = reaalivektori.end();
++valin_eka;   // toinen alkio
--valin_vika;  // viimeinen alkio

sort(valin_eka, valin_vika);

Koska loppuiteraattori rajaa välin ulkopuolelle jäävän kohdan, viimeinen alkio pysyy tässä lajittelematta. Varmista myös, että säiliössä on riittävästi alkioita ennen ensimmäisen tai viimeisen alkion ohittamista.

Alkioiden laskeminen ja etsiminen

count laskee, montako tiettyä arvoa iteraattorivälillä esiintyy:

vector<string> vihamiehet;
// ...
cout << count(vihamiehet.begin(), vihamiehet.end(), "Aki")
     << " kappaletta Aki-nimisia vihamiehia!" << endl;

find etsii arvon ensimmäisen esiintymän. Se palauttaa alkioon osoittavan iteraattorin tai end()-iteraattorin, jos arvoa ei löytynyt:

vector<string> potilaat;
// ...
auto iter = find(potilaat.begin(), potilaat.end(), "Kai");
if (iter == potilaat.end()) {
    cout << "Kaita ei loytynyt." << endl;
} else {
    cout << *iter << endl;
    potilaat.erase(iter);  // poistaa löytyneen vektorialkion
}

string-, set- ja map-tyypeillä on oma find-jäsenfunktionsa. Käytä sitä yleensä näissä rakenteissa: erityisesti set- ja map-säiliöissä se voi löytää alkion yleistä std::find-algoritmia tehokkaammin.

min_element ja max_element palauttavat iteraattorin pienimpään tai suurimpaan alkioon. Välin täytyy sisältää vähintään yksi alkio, jotta palautettua iteraattoria voi käyttää:

vector<int> maarat;
// ...
if (!maarat.empty()) {
    auto pienin_it = min_element(maarat.begin(), maarat.end());
    cout << "Pienin lukumaara: " << *pienin_it << endl;
}

Alkioiden muuttaminen ja kopioiminen

replace korvaa iteraattoriväliltä kaikki annetun arvoiset alkiot uudella arvolla:

replace(tekstivektori.begin(), tekstivektori.end(), "TTY", "TUNI");

fill asettaa kaikki välin alkiot samaan arvoon:

string merkkijono = "";
// ... merkkijonon pituus asetetaan ensin
fill(merkkijono.begin(), merkkijono.end(), '?');

Nämä algoritmit muuttavat alkioita, joten ne eivät sovellu muuttumattomiin avainarvoihin kuten set- ja map-säiliöissä.

reverse kääntää välin järjestyksen:

vector<Pelaaja> vuorojarjestys;
// ...
reverse(vuorojarjestys.begin(), vuorojarjestys.end());

shuffle sekoittaa välin satunnaiseen järjestykseen. Se tarvitsee satunnaislukugeneraattorin, ja käsiteltävän välin tulee tukea satunnaispääsyä:

#include <random>

vector<Pelikortti> korttipakka;
minstd_rand gen;
// ...
shuffle(korttipakka.begin(), korttipakka.end(), gen);

C++:n satunnaislukugeneraattorit löytyvät <random>-kirjastosta. minstd_rand ja default_random_engine ovat kaksi vaihtoehtoa; generaattori alustetaan kerran ja välitetään shuffle-funktiolle.

copy kopioi alkioita lähdevälistä kohteeseen. Kohteessa täytyy olla valmiiksi tarpeeksi tilaa tulokselle. Esimerkiksi merkkijonon merkit voidaan kopioida yhtä pitkään vektoriin näin:

string merkkijono = "";
// ... merkkijono saa ensin sisältönsä
vector<char> merkkivektori(merkkijono.length());
copy(merkkijono.begin(), merkkijono.end(), merkkivektori.begin());

Tämä tilavaatimus koskee algoritmeja, jotka kirjoittavat tuloksia kohdealueelle. copy-esimerkissä lähteen ja kohteen alkiot ovat molemmat merkkejä.

Oma vertailufunktio

sort ja eräät muut algoritmit tarvitsevat alkioille vertailujärjestyksen. Perustyypeillä ja merkkijonoilla järjestys on määritelty valmiiksi. Omalle tietuetyypille järjestys täytyy kertoa itse: esimerkiksi opiskelijan voi järjestää opiskelijanumeron tai nimen mukaan.

struct Opiskelija {
    string nimi;
    int opnum;
};

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

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

Vertailufunktio ottaa kaksi vakioviitettä ja palauttaa bool-arvon. Se palauttaa true täsmälleen silloin, kun ensimmäisen alkion kuuluu olla ennen toista. Vertailun täytyy muodostaa johdonmukainen järjestys; esimerkiksi yhtäsuuruus ei saa saada vertailufunktiota palauttamaan true.

Vertailufunktio annetaan algoritmille funktion nimenä ilman sulkeita:

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

sort(opiskelijat.begin(), opiskelijat.end(), vertaile_opiskelijanumeroita);
for (const auto& opisk : opiskelijat) {
    cout << opisk.opnum << " : " << opisk.nimi << endl;
}

sort(opiskelijat.begin(), opiskelijat.end(), vertaile_nimia);

Vertailufunktion nimeä ei kutsuta tässä kohdassa. Jos nimen perään kirjoitettaisiin sulkeet, funktiota yritettäisiin kutsua heti, eikä algoritmille annettaisi vertailufunktiota.

Samaa vertailufunktiota voi käyttää myös max_element-algoritmissa:

auto iter = max_element(opiskelijat.begin(), opiskelijat.end(),
                         vertaile_opiskelijanumeroita);
if (iter != opiskelijat.end()) {
    cout << iter->nimi << endl;
}

Funktiota, joka saa toisen funktion parametrina, kutsutaan korkeamman kertaluvun funktioksi (higher-order function). STL:n algoritmit käyttävät tätä tapaa, jotta niiden toimintaa voidaan mukauttaa erilaisiin tietotyyppeihin ja käyttötarkoituksiin.