STL:n vektori ja sen läpikäynti (for-lause)¶

STL:n vektori¶

STL:n (Standard Template Library) vector-tietotyyppi muistuttaa hyvin läheisesti Pythonin list-tyyppiä. Molemmat voivat sisältää useita tietoalkioita, joihin päästään käsiksi, jos tiedetään niiden indeksi. Pythonista poiketen C++:n vektorin kaikkien alkioiden on oltava keskenään samantyyppisiä.

Tutkitaan pientä esimerkkiohjelmaa, joka osaa optimoida (silmukattoman) labyrintin läpi löydetyn reitin. Reitti ilmaistaan merkkijonona, jossa merkki P tarkoittaa yhden ruudun pituista siirtymää pohjoiseen, merkki E yhden ruudun pituista siirtymää etelään, jne. Jos esimerkiksi labyrintissä satunnaisesti harhailemalla on onnistuttu löytämään reitti PLIPIPLIILEILLEI, olisi siitä optimoitu reitti PI, koska merkkijonosta voidaan poistaa esimerkiksi toisena ja kolmantena olevat merkit LI ja vastaavasti monta muutakin turhaa kohtaa.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const char POHJ  = 'P';
const char ITA   = 'I';
const char ETELA = 'E';
const char LANSI = 'L';

void TulostaReitti(const vector<char>& reittivektori) {
    vector<char>::size_type indeksi = 0;
    while ( indeksi < reittivektori.size() ) {
        cout << reittivektori.at(indeksi);
        ++indeksi;
    }
    cout << endl;
}

int main() {
    string reitti = "";
    cout << "Syota kuljettu reitti: ";
    getline(cin, reitti);

    vector<char> optimoitu_reitti = { };
    string::size_type i = 0;
    while ( i < reitti.length() ) {
        char uusi_suunta = reitti.at(i);

        if ( optimoitu_reitti.size() == 0 ) {
            optimoitu_reitti.push_back(uusi_suunta);

        } else {
            char edellinen_suunta = optimoitu_reitti.back();
            if ( edellinen_suunta == ITA
                    and uusi_suunta == LANSI ) {
                optimoitu_reitti.pop_back();
            } else if ( edellinen_suunta == LANSI
                           and uusi_suunta == ITA ) {
                optimoitu_reitti.pop_back();
            } else if ( edellinen_suunta == POHJ
                           and uusi_suunta == ETELA ) {
                optimoitu_reitti.pop_back();
            } else if ( edellinen_suunta == ETELA
                           and uusi_suunta == POHJ ) {
                optimoitu_reitti.pop_back();
            } else {
                optimoitu_reitti.push_back(uusi_suunta);
            }
        }

        ++i;
    }
    TulostaReitti(optimoitu_reitti);
}

Vektorityypin käyttämiseksi koodin alkuun tarvitaan:

#include <vector>

Vektorityyppisen muuttujan määrittely tapahtuu näin:

vector<alkioiden_tyyppi> muuttujan_nimi;

esimerkiksi

vector<int> pistemaarat;

jonka tuloksena syntyneeseen muuttujaan pistemaarat voidaan tallentaa useita kokonaislukuja.

Vektorin loppuun voidaan lisätä uusia alkioita yksi kerrallaan:

pistemaarat.push_back(21);

jolloin vektorin koko (siihen tallennettujen alkioiden lukumäärä) kasvaa yhdellä.

Viimeinen alkio saadaan poistettua:

pistemaarat.pop_back();

jolloin vektorin koko pienenee yhdellä.

Jos vektori on tyhjä (siinä ei ole yhtään alkiota), kun pop_back suoritetaan, aiheutuu poikkeus. Tutustumme poikkeusten käsittelemiseen myöhemmässä vaiheessa (emme vielä tällä kurssilla).

Oikeaoppisesti pop_back-metodin kutsua ennen olisi siis syytä varmistua, että vektorissa on poistettavaa jäljellä, kuten on tehty koodissa:

if ( pistemaarat.size() != 0 ) {
    pistemaarat.pop_back();
} else {
    // Virhe, tyhjästä vektorista ei voi poistaa.
}

missä size kertoo vektoriin talletettujen alkioiden lukumäärän.

Jos size-metodin paluuarvo halutaan tallentaa muuttujaan, sen tyypin tulisi olla

vector<alkioiden_tyyppi>::size_type

Esimerkiksi

vector<int>::size_type koko = pistemaarat.size();
...
koko = pistemaarat.size();

Vektorin ensimmäisen ja viimeisen alkion arvoon päästään käsiksi:

cout << "eka:  " << pistemaarat.front() << endl
     << "vika: " << pistemaarat.back() << endl;

Vektorin yksittäisiin arvoihin päästään käsiksi samoin kuin merkkijonon yksittäisiin merkkeihin:

cout << pistemaarat.at(3) << endl;
...
pistemaarat.at(indeksi) = uusi_pistemaara;

Indeksointi alkaa nollasta ja viimeisen alkion indeksi on yhtä pienempi kuin alkioiden lukumäärä.

Jos at-metodilla yritetään indeksoida vektorista alkio, jota ei ole olemassa, seurauksena on poikkeus, joka käsittelemättömänä kaataa ohjelman.

Vektori voi funktion parametrina käytettynä olla joko arvo- tai viiteparametri normaaliin tapaan:

void funktio1(vector<double> mittaustulokset);
void funktio2(vector<double>& mittaustulokset);

Suurikokoisia tietorakenteita ei yleensä kannata välittää funktiolle arvoparametrina, jos se voidaan välttää. (Mieti, mitä arvonvälityksessä tapahtuu. Piirrä vaikkapa kuva. Tai palauta mieleesi materiaalin kohta 3.2.) Tehokkuussyistä kannattaa arvoparametrien sijaan käyttää const-viitteitä:

void funktio3(const vector<double>& mittaustulokset);

Viitteen yhteydessä avainsana const aiheuttaa sen, että viitteen osoittamaa kohdetta ei voi muuttaa kyseisen viitteen kautta. Tämä tekee viiteparametrin välittämisen turvallisemmaksi: Funktion kutsuja tietää, että funktio ei tee muutoksia parametrina välitettävään muuttujaan.

Jos halutaan, vektorin alkioiden määrä voidaan asettaa jo sen määrittelyvaiheessa:

// Vektori, jossa valmiiksi tilaa 20 kokonaisluvulle.
// Luvut itsessään alustamattomia.
vector<int> luvutA(20);

// Tilaa 10 reaaliluvulle, jokainen niistä
// alustettu arvoon 5.3.
vector<double> luvutB(10, 5.3);

Huomaa, että vektoreille (ja muillekin STL-rakenteille) on useita eri alustusnotaatioita. Esimerkiksi, mutta ei tyhjentävästi:

vector<string> nimetA(5);
vector<string> nimetB(10, "tuntematon");
vector<string> nimetC = { "Matti", "Maija" };

Yleisesti ottaen STL-vektori on tietorakenne, joka säilyttää alkiot siinä järjestyksessä, kuin ne on siihen talletettu. STL-terminologiassa tällaisia rakenteita kutsutaan sarjoiksi (sequence). STL:ssä on useita sarjoja:

• Vektori sopii hyvin käytettäväksi tilanteissa, joissa on kyettävä tallentamaan paljon tietoalkioita myöhempää prosessointia varten, varsinkin jos talletettuun tietoon ei tehdä hakuja, tai hakujen nopeudella ei ole erityisen suurta merkitystä. Luonnollisesti vektori on hyvä valinta myös tilanteessa, jossa alkiot on pystyttävä prosessoimaan samassa järjestyksessä kuin ne lisättiin säiliöön.
• Aiemmin mainittu deque on hyvin samankaltainen rakenne kuin vector, mutta tehottomampi. Tosin deque:n etu on, että sen alkuun voi lisätä alkioita valmiilla metodilla push_front ja sen alusta voi poistaa alkioita pop_front-metodilla.
• Tämän lisäksi löytyy mm. list, jolla ei kuitenkaan ole mitään tekemistä Pythonin list-tietorakenteen kanssa, eikä sitä kannata käyttää, jos et ole perehtynyt siihen, miten dynaaminen muistinhallinta toimii.

Säiliöiden välisiin eroihin perehdytään kurssilla COMP.CS.300 Tietorakenteet ja algoritmit 1 mm. tehokkuuden näkökulmasta.

Virheiden etsinnän helpottamiseksi¶

Kun ohjelmakoodissa käytetään STL:n säiliöitä, kannattaa Qt Creatorin projektitiedostoon lisätä seuraava rivi:

QMAKE_CXXFLAGS += -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC

Tällä tavoin kääntäjä antaa enemmän varoituksia STLn säiliöihin liittyvästä epäilyttävästä ohjelmakoodista (esim. ohi-indeksoinneista), mikä yleensä auttaa virheiden löytämisessä.

Kurssin henkilökunta on lisännyt tämän rivin projektitiedostoihin niissä tehtävissä, joissa käytetään STLn säiliöitä.

C++:n for-silmukka¶

C++:n for-silmukkaa voi käyttää pääpiirteissään kahdella eri tavalla:

1. Säiliön alkioiden läpikäynti:

   vector<int> lukuvektori;
   ...
   for ( int vektorin_alkio : lukuvektori ) {
       cout << vektorin_alkio << endl;
   }
   

   Tämä käyttö on periaatteessa jo entuudestaan tuttu ja vastaa Pythonin rakennetta:

   for alkio in lista:
       print(alkio)
   

2. Halutun kokonaislukuvälin arvojen läpikäynti:

   for ( int luku = 5; luku < 10; ++luku ) {
       cout << 9 * luku << endl;
   }
   

   joka on jonkin verran monisanaisempi vastine Python-rakenteelle:

   for luku in range(5, 10):
       print(9 * luku)
   

for ( int vektorin_alkio : lukuvektori ) {
    cout << vektorin_alkio << endl;
}

for ( int& vektorin_alkio : lukuvektori ) {
    vektorin_alkio = vektorin_alkio * 2;
}

int i = 42;

auto i = 42;

vector<int> lukuvektori;
...
for ( auto vektorin_alkio : lukuvektori ) {
    cout << vektorin_alkio << endl;
}

for ( int luku = 5; luku < 10; ++luku ) {
    cout << 9 * luku << endl;
}

for ( alustus; ehto; kasvatus ) {
    runko
}

for( int i : { 2, 3, 5, 7, 11, 13, 17 } ) {
    ...
}

Lisää esimerkkejä¶

Tämän kierroksen materiaaleista löytyy esimerkkiohjelma, joka tulostaa alkuluvut tiettyyn ylärajaan saakka (examples/04/primes). Ohjelmassa on käytetty for-silmukkaa sekä vektoria, jonka alkiot ovat bool-tyyppisiä.