C++-ohjelmointi

Luku 14: Tietorakenteet

Vektori

#include <vector>

C++:n standardikirjaston keskeinen tietorakenne on vektori. Se muistuttaa paljon taulukkoa, mutta alkioiden määrä voi muuttua määrittelyn jälkeen.

Seuraava koodi luo vektorin, jossa on kolme alkiota:

vector<int> v = {1,2,3};

Vektori tarjoaa funktiot push_back ja pop_back, joiden avulla voi lisätä uuden alkion vektorin loppuun sekä poistaa sen viimeisen alkion. Näiden funktioiden avulla vektorin kokoa voi muutaa määrittelyn jälkeen.

Esimerkiksi seuraava koodi luo vektorin v, joka on aluksi tyhjä. Sitten koodi lisää siihen kolme alkiota. Koodin suorituksen jälkeen vektorin sisältönä on {1,2,3}.

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

Vektorin käsittely

Funktio size kertoo, montako alkiota vektorissa on tällä hetkellä. Vektorin alkioita voi käsitellä samalla tavalla kuin taulukossa []-syntaksin avulla. Esimerkiksi seuraava koodi tulostaa kaikki vektorin alkiot:

for (int i = 0; i < v.size(); i++) {
    cout << v[i] << "\n";
}

Vastaavan koodin voi toteuttaa myös lyhyemmin seuraavasti. Tässä muuttuja x käy läpi yksi kerrallaan jokaisen vektorissa olevan alkion.

for (int x : v) {
    cout << x << "\n";
}

Iteraattorit ja välit

Iteraattori osoittaa johonkin tietorakenteen kohtaan. Vektorin iteraattori begin() osoittaa sen ensimmäiseen alkioon ja iteraattori end() osoittaa viimeisen alkion jälkeiseen kohtaan. Nämä iteraattorit määrittelevät puoliavoimen välin, joka sisältää kaikki vektorin alkiot.

Esimerkiksi seuraava koodi luo iteraattorin, joka osoittaa vektorin ensimmäiseen alkioon:

vector<int>::iterator it = v.begin();

Koska iteraattorin tyyppi vector<int>::iterator on pitkä, tässä tilanteessa on kuitenkin kätevämpää käyttää sanaa auto, joka päättelee tyypin automaattisesti:

auto it = v.begin();

Iteraattoria voi käsitellä melko samalla tavalla kuin osoitinta. Esimerkiksi pääsemme käsiksi iteraattorin osoittamaan arvoon *-merkinnällä. Seuraava koodi tulostaa vektorin ensimmäisen alkion:

auto it = v.begin();
cout << *it << "\n";

Seuraava koodi puolestaan tulostaa kaikki vektorin alkiot iteraattorin avulla:

auto it = v.begin();
while (it != v.end()) {
    cout << *it << "\n";
    it++;
}

Järjestäminen

#include <algorithm>

Voimme järjestää vektorin alkiot funktiolla sort, jolle annetaan parametreiksi järjestettävän välin alku- ja loppukohta. Kun annamme iteraattorit begin() ja end(), koko vektori järjestetään:

vector<int> v = {4,2,5,1};
sort(v.begin(),v.end());
// v on nyt {1,2,4,5}

Voimme antaa myös käänteiset iteraattorit rbegin() ja rend(), jolloin alkiot järjestetään käänteiseen järjestykseen:

vector<int> v = {4,2,5,1};
sort(v.rbegin(),v.rend());
// v on nyt {5,4,2,1}

Taulukko vs. vektori

Vektori on monessa tilanteessa mukavampi käyttää kuin taulukko. Sen alkioiden määrää voi muuttaa, ja siinä on monia käteviä funktioita, joita ei ole taulukossa.

Toisin kuin taulukot, vektorit käyttäytyvät samalla tavalla kuin tavalliset muuttujat eli niitä voi kopioida ja vertailla tavallisesti. Esimerkiksi seuraava koodi toimii:

vector<int> a = {1,2,3};
vector<int> b = {4,5,6};
b = a;
if (a == b) cout << "ok\n";

Jos funktion parametrina on vektori, sen sisältö kopioidaan funktioon ja koon saa selville size-funktiolla.

void testi(vector<int> v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << "\n";
    }
}

Vektori on itse asiassa toteutettu sisäisesti taulukon avulla. Taulukko on vain piilotettu vektorin sisään, ja vektori tarjoaa ulospäin mukavamman tavan taulukon käyttämiseen.

Parien käsittely

Pari on tietorakenne, joka sisältää tasan kaksi alkiota. Esimerkiksi seuraava koodi luo parin x, jonka molemmat alkiot ovat kokonaislukuja.

pair<int,int> x = {1,2};
cout << x.first << " " << x.second << "\n"; // 1 2

Seuraava koodi antaa näytteen siitä, miten voimme yhdistellä standardikirjaston osia:

vector<pair<int,int>> v;
v.push_back({2,3});
v.push_back({1,5});
v.push_back({2,1});
sort(v.begin(),v.end());
// v on nyt {{1,5},{2,1},{2,3}}

Koodi luo vektorin, jonka jokainen alkio on pari. Tämän jälkeen koodi lisää vektoriin pareja ja järjestää ne. Parit järjestyvät automaattisesti ensisijaisesti ensimmäisen alkion ja toissijaisesti toisen alkion mukaan.

Muita tietorakenteita

C++:n standardikirjasto sisältää monia muitakin tietorakenteita, kuten seuraavat:

Joukko set pitää yllä järjestettyä alkioiden kokoelmaa ja tarjoaa tehokkaat funktiot, joiden avulla voi lisätä, poistaa ja etsiä alkioita.
Hakemisto map sisältää joukon avain-arvo-pareja. Hakemiston voi ajatella taulukon yleistyksenä, jossa indeksit voivat olla mitä tahansa arvoja.
Pakka deque on dynaaminen taulukko, jonka kokoa pystyy muuttamaan sekä alusta että lopusta.

Näille tietorakenteille on käyttöä tehokkaiden algoritmien toteuttamisessa.

Tie koodariksi