Muistin varaaminen dynaamisesti

Dynaamisia tietorakenteita ovat rakenteet, joiden tarvitsemaa muistia varataan ja mahdollisesti vapautetaan ohjelmoijan kirjoittamien komentojen perusteella ohjelman suorituksen aikana.

Dynaaminen tietorakenne koostuu usein useista samantyyppisistä alkioista. Alkion tyyppi voidaan määritellä esimerkiksi struct-rakenteella, johon tallennetaan useita kenttiä. Linkitetyssä rakenteessa alkioilla on lisäksi linkkikenttiä eli osoittimia, joiden avulla ne yhdistetään toisiinsa.

Yksinkertainen linkitetyn listan alkio voisi näyttää tältä:

struct Solmu {
    int arvo;
    Solmu* seuraava;
};

Kenttä seuraava voi osoittaa listan seuraavaan alkioon. Viimeisen solmun seuraava-osoitin ei osoita mihinkään, joten se voidaan asettaa arvoon nullptr. Tällainen linkitys mahdollistaa alkioiden lisäämisen ja poistamisen ilman, että koko tietorakennetta tarvitsee siirtää yhteen yhtenäiseen muistialueeseen.

Dynaamisten rakenteiden esimerkkejä

Dynaamisia tietorakenteita ovat esimerkiksi:

linkitetty lista, jossa alkiot osoittavat seuraaviin alkioihin
pino ja jono, jotka rajaavat alkioiden lisäys- ja poistamisjärjestystä
puu ja verkko, joissa alkiot voivat liittyä useisiin muihin alkioihin

Nämä rakenteet määritellään usein luokkina, ja niitä käsitellään luokan jäsenfunktioiden kautta. Luokka voi esimerkiksi tarjota metodit alkion lisäämiseen, poistamiseen ja etsimiseen. Kuten muissakin luokissa, ohjelmoijan tehtävänä on toteuttaa nämä metodit oikein ja huolehtia resurssien hallinnasta.

Linkitettyä listaa käsitellään tarkemmin myöhemmin tällä kierroksella.

Muuttujien elinaika ja sen hallinta

Tähän asti käyttämämme muuttujat ovat olleet automaattisia muuttujia. Niiden tallennustilasta ja eliniän päättymisestä huolehditaan automaattisesti ohjelman lohkorakenteen ja C++:n elinkaarisääntöjen perusteella:

Kun muuttuja määritellään, sille järjestetään tarvittava tallennustila.
Kun muuttujan elinaika päättyy, sen olio tuhotaan ja sen käyttämä tallennustila voidaan vapauttaa muuhun käyttöön.

Joustavien tietorakenteiden toteuttamiseen tarvitaan tilanteita, joissa olion elinaika ei pääty automaattisesti saman lohkon päättyessä, jossa se luotiin. Dynaamisen muuttujan elinaikaa hallitaan muistinhallinnan mekanismeilla: muistia varataan suorituksen aikana ja vapautetaan, kun sitä ei enää tarvita.

Elinaika tarkoittaa aikaa olion luomisesta sen tuhoutumiseen. Osoitin, joka säilyttää olion osoitteen, ei itsessään pidennä olion elinaikaa. Muistin varaaminen ja vapauttaminen täytyy siksi suunnitella huolellisesti, jotta muistia ei käytetä tuhoutumisen jälkeen eikä varattua muistia jätetä vahingossa vapauttamatta.

Muistin loppuminen

Jos muistia ei ole tarpeeksi silloin, kun ohjelma yrittää varata sitä, C++:n varausmekanismi ilmoittaa tilanteesta poikkeuksella. Jos poikkeusta ei käsitellä, ohjelman suoritus päättyy.

Muistin loppumiseen liittyvien poikkeusten käsittely on tämän aiheen alussa sivuseikka, joten harjoituksissa oletetaan, että muistia on aina riittävästi. Tärkeintä on nyt ymmärtää, että dynaamisesti varattu muisti on ohjelman käytössä vain niin kauan kuin sen elinkaarta hallitaan oikein.