LoginRegister

STL-kirjasto

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

C++:ssa monimutkaisemmat tietorakenteet, kuten vektorit, ja niiden käsittelyyn tarkoitetut mekanismit eivät kuulu kielen ydinsyntaksiin, vaan ne toteutetaan kirjastoissa. Näiden kirjastojen kokonaisuutta kutsutaan usein Standard Template Libraryksi (STL).

STL:ssä on kolme keskeistä osaa:

  • Säiliöt ovat tietorakenteita, kuten Pythonin list, set ja dict, sekä monia muita rakenteita.
  • Iteraattorit ovat olioita, joiden avulla voidaan viitata säiliön alkioihin ja siirtyä niiden välillä.
  • Algoritmit tarjoavat valmiita toimintoja, kuten järjestämisen.

STL on laaja kokonaisuus. Tällä kurssilla tutustumme siihen yleisellä tasolla: ensin vector-säiliöön ja myöhemmin muutamiin muihin säiliöihin ja STL:n osiin. Tietorakenteiden ja algoritmien tehokkuutta käsitellään syvällisemmin jatkokurssilla.

Usein ohjelmassa on tietorakenne, jonka alkiot halutaan käsitellä yksi kerrallaan. Pythonissa tähän käytetään tavallisesti for-lausetta. C++:ssa on vastaava säiliön läpikäyntiin tarkoitettu for-rakenne, ja säiliötä voidaan käsitellä myös iteraattorien avulla.

STL:n vektori

STL:n vector muistuttaa Pythonin list-tyyppiä: kumpaankin voi tallentaa useita alkioita ja niihin voi viitata indeksillä. C++:n vektorin kaikkien alkioiden täytyy kuitenkin olla samaa tyyppiä.

Seuraava esimerkki optimoi labyrintistä löydetyn reitin. Reitti on merkkijono, jossa P tarkoittaa siirtymistä pohjoiseen, E etelään, I itään ja L länteen. Vastakkaisiin suuntiin tehdyt peräkkäiset siirtymät kumoavat toisensa: esimerkiksi reitistä LI ei tarvitse jäädä mitään jäljelle.

#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 && uusi_suunta == LANSI)
                    || (edellinen_suunta == LANSI && uusi_suunta == ITA)
                    || (edellinen_suunta == POHJ && uusi_suunta == ETELA)
                    || (edellinen_suunta == ETELA && uusi_suunta == POHJ)) {
                optimoitu_reitti.pop_back();
            } else {
                optimoitu_reitti.push_back(uusi_suunta);
            }
        }
        ++i;
    }
    TulostaReitti(optimoitu_reitti);
}

Vektorin käyttämiseksi lisätään #include <vector>. Vektorimuuttuja määritellään kirjoittamalla alkioiden tyyppi kulmasulkeisiin:

vector<int> pistemaarat;

Vektorin loppuun lisätään alkio metodilla push_back. Koko kertoo alkioiden lukumäärän, ja pop_back poistaa viimeisen alkion:

pistemaarat.push_back(21);  // lisää alkion loppuun
pistemaarat.pop_back();       // poistaa viimeisen alkion
cout << pistemaarat.size();  // alkioiden määrä

Tyhjästä vektorista ei saa poistaa alkiota. Tarkista ennen pop_back-kutsua, että poistettavaa on:

if (pistemaarat.size() != 0) {
    pistemaarat.pop_back();
}

Jos size()-metodin tulos tallennetaan muuttujaan, täsmällinen tyyppi on säiliön size_type:

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

Vektorin ensimmäisen ja viimeisen alkion saa metodeilla front() ja back(). Yksittäiseen alkioon pääsee indeksillä at()-metodin kautta. Indeksointi alkaa nollasta:

cout << "eka: " << pistemaarat.front() << endl;
cout << "vika: " << pistemaarat.back() << endl;
cout << pistemaarat.at(3) << endl;
pistemaarat.at(indeksi) = uusi_pistemaara;

Viimeisen alkion indeksi on aina yhtä pienempi kuin alkioiden määrä. Jos at()-metodille annetaan olemattoman alkion indeksi, se aiheuttaa poikkeuksen; käsittelemätön poikkeus keskeyttää ohjelman.

Vektorit funktion parametreina

Vektorin voi välittää funktiolle arvona tai viitteenä aivan kuten perustietotyypinkin:

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

Suuren tietorakenteen kopioiminen arvoparametriksi voi olla kallista. Jos funktion ei tarvitse muuttaa vektoria, käytä yleensä const-viitettä. Se välttää kopioinnin ja kertoo samalla, ettei funktio muuta vektoria tämän parametrin kautta.

Vektorin alustaminen

Vektorin kokoa ja alkioiden alkuarvoja voi asettaa jo määrittelyssä:

vector<int> luvutA(20);          // 20 alustettua kokonaislukualkiota
vector<double> luvutB(10, 5.3);  // 10 alkiota, jokaisen arvo 5.3

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

Alustusnotaatioita on useita. Esimerkiksi oletusarvoinen alustus asettaa kokonaislukualkiot nollaksi ja merkkijonoalkiot tyhjiksi merkkijonoiksi.

Vektori säilyttää alkionsa siinä järjestyksessä, jossa ne on lisätty. Tällaisia järjestettyjä rakenteita kutsutaan STL:n terminologiassa sekvensseiksi. Vektori sopii erityisesti tilanteisiin, joissa alkioita kerätään käsiteltäväksi järjestyksessä ja niihin halutaan päästä indeksillä.

Muita sekvenssejä ovat esimerkiksi deque ja list. deque muistuttaa vektoria, mutta mahdollistaa tehokkaan lisäyksen ja poiston myös alusta (push_front ja pop_front). C++:n list ei vastaa Pythonin listaa; sen käyttöön kannattaa perehtyä vasta, kun linkitetyn listan ja dynaamisen muistinhallinnan toimintaperiaatteet ovat tuttuja.

STL-säiliöiden virheiden etsiminen

Qt Creatorin projektitiedostoon voi lisätä seuraavan asetusrivin, joka auttaa löytämään STL-säiliöiden virheellistä käyttöä, kuten indeksointia säiliön rajojen ulkopuolelle:

QMAKE_CXXFLAGS += -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC

Kurssin henkilökunta on lisännyt asetuksen valmiiksi niihin tehtäviin, joissa STL-säiliöitä käytetään.

C++:n for-silmukka

C++:n for-silmukalla on kaksi tavallista käyttötapaa. Ensimmäinen käy läpi säiliön alkiot:

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

Tämä vastaa Pythonin rakennetta for alkio in lista. Esimerkin muuttuja saa jokaisen alkion arvon vuorollaan.

Oletuksena alkio kopioidaan silmukkamuuttujaan. Jos tarkoitus on muuttaa vektorin alkioita, käytä viitettä:

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

Alkioiden tyypin voi usein antaa kääntäjän pääteltäväksi avainsanalla auto, mikä on kätevää etenkin pitkien ja monimutkaisten tyyppien kanssa:

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

Älä lisää tai poista alkioita säiliöstä sitä läpikäyvän range-based for-silmukan aikana. Se voi mitätöidä silmukan käyttämät viitteet ja iteraattorit.

Numeroalueen läpikäynti

Toisessa käyttötavassa kolmiosainen for-rakenne käy läpi lukuvälin:

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

Rakenne on muotoa for (alustus; ehto; kasvatus). Alustus suoritetaan kerran ennen silmukkaa. Ehto tarkistetaan ennen jokaista kierrosta, ja kasvatus suoritetaan rungon jälkeen.

Kolmesta osasta minkä tahansa voi jättää pois, mutta puolipisteet säilyvät. Vektorin voi käydä läpi myös indekseillä, kun silmukan ehto rajataan sen kokoon:

for (vector<int>::size_type i = 0;
     i < lukuvektori.size(); ++i) {
    cout << lukuvektori.at(i) << endl;
}

Jos ehto puuttuu, silmukka jatkuu, kunnes se keskeytetään muulla tavoin:

for (;;) {
    // ikuinen silmukka
}

Tämä vastaa toimintaperiaatteeltaan rakennetta while (true). Alustuksessa ja kasvatuksessa voi olla useampi lauseke, jotka erotetaan pilkuilla.

Alustuslistan avulla voidaan käydä läpi myös yksittäisiä arvoja:

for (int i : { 2, 3, 5, 7, 11 }) {
    // käsittele alkion i arvo
}

Kaksiulotteinen vektori

Vektorin alkio voi olla myös toinen vektori. Näin muodostuu kaksiulotteinen vektori, jota voi käyttää esimerkiksi pelilaudan ruudukon tallentamiseen:

vector<vector<int>> kaksi_ulotteinen_vektori;

Tyyppi on pitkä, joten sille voi antaa using-määrittelyllä kuvaavamman nimen:

using Board = vector<vector<int>>;
Board board;
Kaksiulotteisen vektorin alkiot muistissa peräkkäin riveittäin
Kaksiulotteinen vektori: alkiot muistissa peräkkäin riveittäin.

Saman rakenteen voi piirtää myös toisin päin. Ruudukkomuoto auttaa hahmottamaan koordinaatteja sekoittamatta X- ja Y-suuntia. Kun tietorakennetta on vaikea ymmärtää, piirrä siitä kuva ja merkitse alkioiden indeksit.

Kaksiulotteinen vektori esitettynä ruudukkona
Kaksiulotteinen vektori ruudukkomuodossa.

Vektori voi sisältää vektoreita myös useammalla sisäkkäisyystasolla, joten ohjelmoinnissa ei ole rajoituttu kotiavaruutemme kolmeen ulottuvuuteen.

Lisää esimerkkejä

Tämän kierroksen esimerkkiohjelmista primes tulostaa alkuluvut annettuun ylärajaan asti. Siinä käytetään for-silmukkaa ja bool-alkioita sisältävää vektoria.