STL-kirjasto

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

Vektori ja muut sarjat säilyttävät alkionsa järjestyksessä. STL:n assosiatiiviset säiliöt järjestävät tietonsa avainten perusteella, jotta avaimella hakeminen olisi tehokasta. Niiden alkioita ei käsitellä indeksinumeroilla, vaan tietoa haetaan avaimella.

Tutustumme ensin kahteen järjestettyyn assosiatiiviseen säiliöön:

  • set vastaa Pythonin joukkoa: kukin arvo esiintyy joukossa enintään kerran.
  • map vastaa Pythonin sanakirjaa: se tallentaa avain–arvo-pareja ja löytää arvon avaimen perusteella.

Järjestettyjen säiliöiden avaintyypille täytyy olla määritelty järjestys. Oletuksena set ja map pitävät avaimet järjestyksessä.

#include <set>
#include <map>

Joukko: set

Seuraava määrittely luo aluksi tyhjän merkkijonojoukon:

set<string> laiva_on_lastattu;

Joukossa ei ole erillistä hakuavainta: sen omat alkiot toimivat avaimina. Siksi alkiotyyppi tarvitsee järjestyksen. Joukon voi kopioida toisesta samantyyppisestä joukosta tai alustaa alustuslistalla:

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

set<int> alkulukuja = { 2, 3, 5, 7, 11, 13, 17 };
set<string> kaverit = { "Matti", "Maija", "Teppo" };

insert lisää arvon. Jos sama arvo on jo joukossa, joukko ei muutu. size() kertoo alkioiden määrän:

laiva_on_lastattu.insert("koirilla");
cout << kaverit.size() << endl;

Joukon jäsenyyttä voi tarkistaa jäsenfunktiolla find. Jos arvoa ei löydy, tuloksena on end():

if (laiva_on_lastattu.find(sana) == laiva_on_lastattu.end()) {
    laiva_on_lastattu.insert(sana);
    cout << "Ok!" << endl;
} else {
    cout << "Hävisit, sana oli jo lastattu!" << endl;
}

Yksittäisen alkion voi poistaa erase-funktiolla. clear() tyhjentää koko joukon, ja empty() kertoo, onko se tyhjä:

kaverit.erase("Teppo");
laiva_on_lastattu.clear();

if (!kaverit.empty()) {
    cout << "Joukossa on ainakin yksi kaveri." << endl;
}

Saman alkiotyypin joukkoja voi verrata esimerkiksi operaattorilla ==; se palauttaa toden, jos joukkojen alkiot ovat samat.

Avain–arvo-säiliö: map

map-tyypin määrittelyssä annetaan sekä avaimen että siihen liittyvän arvon tyyppi. Esimerkiksi seuraava säiliö yhdistää tuotteen nimen ja hinnan:

map<string, double> hinnasto;

Myös map on aluksi tyhjä, ja sen voi kopioida tai alustaa avain–arvo-pareilla:

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 }
};

Avaimeen liittyvän arvon saa at()-metodilla. Olemassa olevaa arvoa voi myös muuttaa:

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

at() ei lisää uutta avainta. Jos avainta ei löydy, se heittää poikkeuksen. Tarkista avaimen löytyminen find()-metodilla ennen at()-kutsua:

if (sanakirja.find(sana) != sanakirja.end()) {
    cout << sanakirja.at(sana) << endl;
} else {
    cout << "Tuntematon hakusana!" << endl;
}

Uuden parin lisäämiseen käytetään insert()-metodia. Jos avain on jo säiliössä, insert ei korvaa olemassa olevaa arvoa. erase poistaa avaimella löytyvän parin ja palauttaa poistettujen alkioiden määrän:

sanakirja.insert({ sana, sana_englanniksi });

if (hinnasto_2.erase("suklaa")) {
    cout << "Tuote poistettiin." << endl;
} else {
    cout << "Tuotetta ei ollut hinnastossa." << endl;
}

size() palauttaa tallennettujen parien määrän. map-säiliössä operator[] tarjoaa vaihtoehtoisen tavan käyttää arvoa, mutta jos avainta ei vielä ole, se lisää avaimen ja luo arvolle oletusarvon. Kun haluat vain tarkistaa olemassa olevan avaimen, käytä at()- tai find()-metodia.

map-säiliön läpikäynti

map-säiliön alkio koostuu kahdesta osasta: avaimesta ja arvosta. Nämä ovat käytettävissä kenttinä first ja second. Oikeassa map-alkiossa avainkenttä on vakio, jotta järjestys ei voi rikkoutua avainta muuttamalla.

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

using namespace std;

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

    for (auto iter = opiskelijat.begin();
         iter != opiskelijat.end(); ++iter) {
        cout << iter->first << " "
             << iter->second << endl;
    }
}

Kun käytössä on iteraattori, kenttiin viitataan nuolioperaattorilla, kuten iter->first. Range-based for-silmukassa muuttuja on itse pari, joten kenttiin pääsee pisteoperaattorilla:

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

Vakioviite const auto& välttää parin kopioinnin eikä salli map-alkion muuttamista silmukan kautta.

map ja enum yhdessä

Kun halutaan liittää jokaiseen luettelon arvoon teksti, map voi korvata vektorin ja pitkän if-ketjun:

#include <map>
#include <string>

enum class Viikonpaiva { MA, TI, KE, TO, PE, LA, SU };

const map<Viikonpaiva, string> VIIKONPAIVAT = {
    { Viikonpaiva::MA, "Maanantai" },
    { Viikonpaiva::TI, "Tiistai" },
    { Viikonpaiva::KE, "Keskiviikko" },
    { Viikonpaiva::TO, "Torstai" },
    { Viikonpaiva::PE, "Perjantai" },
    { Viikonpaiva::LA, "Lauantai" },
    { Viikonpaiva::SU, "Sunnuntai" }
};

cout << VIIKONPAIVAT.at(Viikonpaiva::MA) << endl;

Avainhaussa at() toimii myös vakiosäiliöllä. Vakiota map-säiliötä ei voi käyttää []-operaattorilla, koska operaattori voi luoda puuttuvan arvon.

Pari: pair

map-alkiot ovat pareja eli kahden toisiinsa liittyvän arvon tietueita. Niiden kenttien nimet ovat first ja second, ja kenttien tyypit määräytyvät parin määrittelyn mukaan.

#include <utility>

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

pair<int, char> pari2(1, 'a');
auto pari3 = make_pair(1, 'a');

Pari sopii tilanteeseen, jossa kaksi arvoa muodostaa luonnollisen kokonaisuuden, esimerkiksi pisteen X- ja Y-koordinaatit. map-säiliössä avain–arvo-pari on usein kuitenkin tietuetta kuvaavampi kokonaisuus, ja kenttiin viitataan nimillä first ja second.

Järjestämättömät säiliöt

map ja set pitävät avaimet järjestyksessä. Tämä on hyödyllistä silloin, kun halutaan käydä alkiot läpi järjestyksessä, ja se voi olla tärkeää myös tulosteen tai testituloksen kannalta.

Jos järjestyksellä ei ole merkitystä ja säiliöstä etsitään, lisätään tai poistetaan yksittäisiä alkioita, unordered_map ja unordered_set voivat olla sopivia vaihtoehtoja:

#include <unordered_map>
#include <unordered_set>

unordered_set<string> tunnukset;
unordered_map<string, double> hinnasto;

Nämä säiliöt eivät pidä alkioita järjestyksessä. Haku, lisäys ja poisto ovat keskimäärin usein nopeita, mutta tulostusjärjestystä ei pidä olettaa ja tehokkuus riippuu käytöstä. Järjestämättömien säiliöiden avaintyyppien pitää olla hajautettavissa ja vertailtavissa yhtäsuuriksi.

Säiliöiden suorituskykyeroihin perehdytään tarkemmin tietorakenteiden ja algoritmien jatkokurssilla.

Lisää esimerkkejä ja lisätietoa

Kurssin esimerkkiohjelmista STL-säiliöitä käytetään esimerkiksi hakemistoissa examples/03/cashier ja examples/03/calendar.

Lisätietoa löytyy C++-standardikirjaston hakemistosta ja sen säiliöitä käsittelevästä osiosta. Kurssilla ja tentissä riittävät tiedot niistä säiliöistä, jotka materiaalissa esitellään.