Lisää STL:n säiliöitä¶

Esimerkkejä STL:n set-rakenteesta¶

Määritellään joukko, johon voi tallentaa merkkijonoja:

set<string> laiva_on_lastattu;

Määrittelyn jälkeen joukko on automaattisesti tyhjä.

Joukolla ei ole erillistä hakuavainta, vaan sen alkiot toimivat hakuavaimina. Tästä syystä joukon alkioiden tyypillä pitää olla järjestys.

Joukko voidaan alustaa toisella samantyyppisellä joukolla tai siihen voidaan sijoittaa toinen samantyyppinen joukko:

set<int> lottonumerot_1;
...
set<int> lottonumerot_2(lottonumerot_1);
...
lottonumerot_1 = lottonumerot_2;

Joukon alustaminen ja siihen sijoitaminen voi tapahtua myös aaltosulkulistasta:

set<int> alkulukuja = {2, 3, 5, 7, 11, 13, 17};
...

set<string> kaverit;
...
kaverit = { "Matti", "Maija", "Teppo" };

Joukkoon saadaan lisättyä uusi alkio insert-metodilla:

laiva_on_lastattu.insert("koirilla");

Lisäys toimii silloinkin, kun alkio kuuluu joukkoon jo entuudestaan, se vaan ei tee mitään.

Joukon alkioiden lukumäärä saadaan selville size-metodilla:

// Kavereiden lukumäärä
cout << kaverit.size() << endl;

Alkion kuulumista joukkoon voidaan tutkia find-metodilla, joka toimii samaan tapaan kuin algoritmikirjaston find:

// Sana ei ole vielä joukossa, lisätään se.
if ( laiva_on_lastattu.find(sana) == laiva_on_lastattu.end() ) {
    laiva_on_lastettu.insert(sana);
    cout << "Ok!" << endl;

// Sana oli joukossa jo ennestään.
} else {
    cout << "Hävisit, " << sana << " oli jo lastattu!" << endl;
}

Yksittäinen alkio voidaan poistaa joukosta erase-metodilla:

// Teppo ei ole enää kaveri.
kaverit.erase("Teppo");

Metodi clear tyhjentää joukon (poistaa kaikki alkiot):

laiva_on_lastattu.clear();

Vertailuoperaattorit toimivat joukoilla, joiden alkiotyyppi on sama:

if ( lottonumerot_1 == lottonumerot_2 ) {
    // Molemmissa joukoissa tismalleen sama alkiot.
    ...
} else {
    // Joukkojen sisällössä eroavaisuuksia.
    ...
}

Metodi empty palauttaa arvon true, vain jos joukko on tyhjä:

if ( not kaverit.empty() ) {
    // On ainakin yksi kaveri.
}

Esimerkkejä STL:n map-rakenteesta¶

Muista STL:n rakenteista poiketen map-rakenteen määrittely sisältää sekä hakuavaimen että hyötytiedon tyypit:

map<string, double> hinnasto;

Määrittelyn jälkeen alustamaton map-säiliö on tyhjä.

Kuten muutkin säiliöt, myös map voidaan alustaa toisesta saman tyyppisestä map-säiliöstä ja siihen voidaan sijoittaa saman tyyppinen map:

map<string, string> sanakirja_1;
...
map<string, string> sanakirja_2(sanakirja_1);
...
sanakirja_1 = sanakirja_2;

Myös aaltosulkulistalla alustaminen tai sijoittaminen toimii:

map<string, double> hinnasto_2 = {
    { "maito",  1.05 },
    { "juusto", 4.95 },
    { "liima",  3.65 },
};
...
hinnasto_2 = {
    { "pippuri", 2.10 },
    { "kerma",   1.65 },
    { "suklaa",  1.95 },
};

Hakuavaimeen liittyvän tiedon käsittely tapahtuu at-metodilla:

cout << hinnasto_2.at("kerma") << endl;  // 1.65
hinnasto_2.at("kerma") = 1.79;

Käytettäessä at-metodia pitää kuitenkin muistaa vaaratilanne: Jos hakuavainta ei löydy map:istä, tuloksena on poikkeus ja ohjelman suorituksen päättyminen. Huomaa siis: at-metodilla map:iin ei saa lisättyä uusia alkioita.

Vaaratilanne vältetään tarkistamalla, onko hakuavain map:issä ennen at-metodin kutsua, kuten on tehty seuraavassa koodissa.

if ( sanakirja_3.find(sana) != sanakirja_3.end() ) {
    // Sana löytyi mapista.
    cout << sanakirja_3.at(sana) << endl;
} else {
    // Sana ei ole mapissa.
    cout << "Virhe, tuntematon hakusana!" << endl;
}

Siinä hyödynnetään aiemmin mainittua seikkaa, että find palauttaa end()-iteraattorin, jos etsittyä tietoa ei löydy.

Avain–hyötytieto -parin saa poistettua map:ista antamalla erase-metodille parametrina poistettavan hakuavaimen:

if ( hinnasto_2.erase("suklaa") ) {
    // Poisto onnistui, "suklaa" ei
    // ole enää hinnastossa
    ...
} else {
    // Poisto epäonnistui, "suklaa" ei ollut
    // hinnastossa alunperinkään.
    ...
}

Vaikka olemassa olemattoman hakuavain–hyötytieto -parin poisto ei olekaan virhe, ennen poistoa tilanteen voisi halutessaan varmistaa find-metodilla.

Uusi tietopari saadaan lisättyä insert-metodilla:

sanakirja_1.insert( { sana, sana_englanniksi } );

Jos edellisessä sana on sanakirja_1:ssa hakuavaimena jo valmiiksi, insert ei tee mitään.

Metodi size-palauttaa map:iin talletettujen tietoparien lukumäärän:

cout << "Sanakirjassa on " << sanakirja_2.size()
     << " sanaparia." << endl;

Myös map-rakenteen alkioiden läpikäynti on toteutettu iteraattorien avulla. Tämä ei kuitenkaan ole aivan yhtä suoraviivaista kuin muiten STL-säiliöiden tapauksessa, koska jokainen alkio sisältääkin kaksi osatietoa: hakuavaimen ja hyötytiedon. Tämä on toteutettu siten, että map-rakenteen alkiot ovat itse asiassa tietueita (vrt. edellisen kierroksen materiaali tieto-ohjatusta ohjelmoinnista). Jos siis on esimerkiksi määritelty map-rakenne

map<int, string> opiskelijat = {
    // opnum, nimi
    { 123456, "Teekkari, Teemu" },
    ...
};

niin rakenteeseen talletetut alkiot olisivat tyypiltään seuraavan kaltaisia tietueita:

struct {
    int    first;
    string second;
};

jossa tietueen kenttien nimet tosiaankin ovat first hakuavaimelle ja second hyötytiedolle.

Täten map-rakenteen alkiot voidaan käydä iteraattorin avulla läpi seuraavasti:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    map<int, string> opiskelijat = {
        { 200001, "Teekkari, Tiina" },
        { 123456, "Teekkari, Teemu" },
        // ···
    };

    map<int, string>::iterator iter;
    iter = opiskelijat.begin();
    while ( iter != opiskelijat.end() ) {
        cout << iter->first << " "
             << iter->second << endl;
        ++iter;
    }
}

Koodissa on syytä panna merkille, kuinka iteraattorin osoittaman tietueen kenttiä (osatietoja) käsitellään operaattorilla -> tavanomaisen . -operaattorin sijaan.

Jos halutaan välttää iteraattoreiden suora käyttö, map:in alkiot voidaan käydä läpi myös for-rakenteella:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    map<int, string> opiskelijat = {
        { 200001, "Teekkari, Tiina" },
        { 123456, "Teekkari, Teemu" },
        // ···
    };

    for ( auto tietopari : opiskelijat ) {
        cout << tietopari.first << " "
             << tietopari.second << endl;
    }
}

Koska tietopari ei ole edellisessä silmukassa iteraattori, vaan varsinainen map:istä löytyvä tietue, käytetään first- ja second-kenttien käsittelyyn normaalia . -operaattoria.

STL:n pair¶

Edellä tarkasteltiin map-rakennetta. Sen alkiot ovat pareja eli tietueita, joilla on kaksi kenttää. Pari on siis tietueen erikoistapaus, ja sen kentillä on esimääritellyt nimet: first ja second. Näiden kenttien tyypit määräytyvät parin esittelyn perusteeella.

Edellisen esimerkin for-lause olisi voitu kirjoittaa ilman auto-sanaa seuraavasti:

#include <iostream>
#include <string>
#include <map>
#include <utility>

using namespace std;

int main() {
    map<int, string> opiskelijat = {
        { 200001, "Teekkari, Tiina" },
        { 123456, "Teekkari, Teemu" },
        // ···
    };

    for ( pair<int, string> tietopari : opiskelijat ) {
        cout << tietopari.first << " "
             << tietopari.second << endl;
    }
}

Parit löytyvät utility-kirjastosta. Tästä syystä yllä olevaan koodiin on lisätty uusi include-rivi. Jos map-rakennetta käytetään ilman mitään mainintaa pareista, kuten tehtiin aikaisemmin (lukuunottamatta ihan viimeisintä esimerkkiä), ei ole mitään tarvetta edellä mainittuun includointiin.

Pareja voidaan käyttää myös sellaisenaan eli ilman, että ne olisivat mapin alkioita. Seuraavassa esitellään erilaisia tapoja esitellä ja alustaa pareja:

pair <int, char> pair1;
pair1.first = 1;
pair1.second = 'a';

pair <int, char> pair2 (1, 'a');

pair <int, char> pair3;
pair3 = make_pair(1, 'a');

auto pair4 = make_pair(1, 'a');

Pari sopii luonnostaan tilanteisiin, joissa on täsmälleen kaksi toisiinsa liittyvää tietoalkiota. Esimerkiksi pisteellä on usein kaksi koordinaattia: x- ja y-koordinaatit.

Järjestämättömiä säiliöitä¶

Edellä esitetyillä map- ja set-säiliöillä on sellainen ominaisuus, että niiden alkiot pidetään avainkentän mukaisessa järjestyksessä. Uusi alkio lisätään siis aina sellaiseen kohtaan, että järjestys säilyy.

Edellä nähtiin esimerkki, jossa map-rakenne käydään läpi iteraattorin avulla tai for-silmukassa. Esimerkkien tulostuslauseet tulostavat alkiot nousevassa järjestyksessä. Joissakin tilanteissa tämä on hyödyllinen ominaisuus. Tämän kurssin (STL-säiliöihin liittyvissä) tehtävissä tulostuksilta vaaditaan usein tietty järjestys, sillä tämä helpottaa automaattitestien toteuttamista.

Yleisesti ottaen järjestyksen ylläpitäminen kuitenkin tekee joistakin operaatioista tehottomia. Tästä syystä esimerkiksi map- ja set-säiliöille on STL:ssa vastineet: unordered_map ja unordered_set. Kuten nimestäkin voi päätellä, jälkimmäisissä säiliöissä alkiot eivät ole järjestyksessä.

Koska järjestystä ei tarvitse ylläpitää, saadaan alkioiden etsintä, lisääminen ja poisto toimimaan keskimäärin tehokkaammin kuin järjestetyissä säiliöissä. Järjestämättömiä säiliöitä kannattaa käyttää, jos alkioiden järjestyksellä ei ole merkitystä, eikä säiliötä käydä kokonaan läpi alkio alkiolta, vaan sieltä vain etsitään yksittäisiä alkioita.

Myöhemmin tulevalla kurssilla “Tietorakenteet ja algoritmit” pohditaan tarkemmin eri säiliöiden tehokkuuksia, ja juuri tehokkuussyistä siellä käytetään useimmiten unordered_map- ja unordered_set-säiliöitä säiliöiden map ja set sijasta.

Muita esimerkkejä¶

Muutaman laajemman esimerkin STL-säiliöiden käyttämisestä löydät kurssin materiaaleista: examples/05/cashier ja examples/05/calendar.

Lisätietoa¶

Lisätietoa säiliöistä löytyy seuraavista linkeistä:

• C++ Reference (etusivu)
• C++ Reference (säiliöt)

Yllä olevista linkeistä löytyy siis nimenomaan lisätietoa. Kurssilla (ja tentissä) riittää tiedot niistä säiliöistä, jotka esitellään Plussa-materiaalissa.