Koodit: C++: Tarkoituksenmukaiset, tehokkaat ja turvalliset taulukot

Tässä koodivinkissä jatketaan pohdiskeluja "oikeasta" tavasta toteuttaa esimerkiksi kaksiulotteinen taulukko C++:lla. Perintönä C:stä saatua, kielessä jo olevaa taulukkotoiminnallisuutta voi myös parannella, joten sivutuotteena myös yksiulotteisista taulukoista saadaan tuunattu versio. Taulukko-oliot voidaan C++:ssa toteuttaa eri tavoin. Käytön vaatimukset ja järkevät suunnittelukäytännöt kuitenkin ohjaavat sitä, millä tavalla toteutus kannattaa tehdä.

Aivan ensimmäiseksi täytyy sanoa, että taulukko ei useinkaan ole paras tietorakenne tietojen käsittelyyn. Se nyt vain sattuu monille olemaan kaikkein tutuin. Erityisen yliarvostettu otus on kaksiulotteinen taulukko, joka sopii keskimäärin melko huonosti ihan kaikkeen, mihin sitä näkyy käytettävän. Mutta olkoon, mennään eteenpäin.

Tuolla esimerkkilistauksessa on header-tiedosto koorray.hpp. Siinä määritellään neljä luokka-templatea: arr1 yksiulotteisille staattisille eli kooltaan muuttumattomille taulukoille, arr2 kaksiulotteisille staattisille taulukoille, dynarr1 yksiulotteisille dynaamisille eli kokoaan ajon aikana muuttaville taulukoille ja vastaavasti dynarr2 kaksiulotteisille dynaamisille taulukoille.

Jako staattisiin ja dynaamisiin taulukko-otuksiin kannattaa tehdä, sillä niille on erilaista käyttöä. Ja vaikka kielessä on jo valmiina staattiset taulukot, niin vastaavien luokkien käyttö on yllättävän hyödyllistä.

Katsotaanpa sitten esimerkkipätkien valossa, miten nuo määritellyt luokat toimivat. Vertailun lähtökohtana ovat kielen omat taulukkorakenteet. Käyn tätä hommaa läpi melko perusteellisesti ja miltei rautalangasta vääntäen. Juttu on pitkä, koettakaa kestää. Päämääränä on kuitenkin näyttää, miten loppujen lopuksi yksinkertaisilla keinoilla tyypillisimmät aloittelijoiden - ja miksei pidemmälle ehtineidenkin - ongelmat voidaan ratkaista. Kysymykset kun tuntuvat aika usein pyörivän C:stä perityn omaperäisen taulukkoparametrivälityksen ja toisaalta dynaamisten taulukkojen käsittelyn ympärillä. Ja sitten nähdään suorituskykyongelma siellä, missä sitä ei välttämättä ensinkään ole. No niin, asiaan.

Ensiksi muuttujat täytyy tietenkin esitellä:

int             ca[3][4];
arr2<int, 3, 4> sa;
dynarr2<int>    da(3, 4);

Esittelyt eivät ole samanlaisia, mutta lienevät kuitenkin ymmärrettävissä. Suurimmat kiistakysymykset taitavat tulla lähinnä estetiikasta.

Yllä muuttujat ca ja sa ovat alustamattomia, mutta da on alustettu sisältämään nollia. Muuttujat voi tietenkin myös alustaa esittelyssä, mikä onkin ihan järkevä ohjelmointityyli:

int             cb[][4]
                = {{11,12,13,14},{21,22,23,24},{31,32,33,34}};
arr2<int, 3, 4> sb
                = {{{11,12,13,14},{21,22,23,24},{31,32,33,34}}};
arr2<int, 3, 4> const db_init
                = {{{11,12,13,14},{21,22,23,24},{31,32,33,34}}};
dynarr2<int>    db = db_init;

Muuttujan cb määritelyssä on huomattavaa, että ensimmäinen kokomääritys voidaan jättää pois. Kääntäjä päättelee oikean koon, vaikkei sitä näkyviin kirjoittaisikaan. Taulukko-olion sb tapauksessa molemmat ulottuvuudet täytyy antaa, mikä ei liene kauhean paha juttu. Eikä myöskään se, että alustuslistan ympärille täytyy panna ylimääräiset kaarisulut.

Dynaamisen taulukon kohdalla alustuslistan käyttö suoraan ei toimi. Täytyy määritellä (vakio) staattinen taulukko, jota käytetään alustamiseen. Syntaksin puolesta tämä on kyllä rumempaa kuin muissa tapauksissa. Huomattavaa on kuitenkin, että kaikki nämä alustustavat ovat periaatteessa yhtä tehokkaita: Kääntäjä tallettaa alustuslistan tiedot jonnekin, josta ne kopioidaan määriteltyihin muuttujiin ajon aikana.

Jos tässä vaiheessa ajattelee, että niin, mutta tuo kielen perustaulukon määrittely näyttää kuitenkin kivoimmalta ja nuo muut ovat ihan ällöjä, niin käydäänpä vähän kauppaa. Tässä vaiheessa voimmekin jo kokeilla tällaista:

ca = cb;        // error: left operand must be l-value
sa = sb;        // ok
da = db;        // ok

Niinpä juuri, C-tyylisiä taulukoita ei pysty sijoittamaan! Ei olla vielä edes kunnolla päästy vauhtiin, kun huomataan, että noita taulukko-olioita voi sijoitella ja esimerkiksi palauttaa funktioiden paluuarvoina. Ehkäpä nämä eivät niin pahoja olekaan...

Alkioita pitää tietenkin pystyä käsittelemään:

cb[1][2] = 99;
sb(1, 2) = 99;
db(1, 2) = 99;

Muuttujan cb tapauksessa käytetään kahta []-operaattoria, sillä kaksiulotteinen taulukko onkin oikeasti taulukko taulukoita. Vastaava olisi voitu toteuttaa myös staattisiin ja dynaamisiin taulukko-olioihin, mutta miksi vaivautua. "Oikea" tapa osoittaa aitoa kaksiulotteista taulukkoa olisi varmaan sb[1, 2], mutta []-operaattoria ei voi overloadata toimimaan näin. Siksi tyydytään ()-operaattoriin, joka on riittävän samannäköinen.

Perinteisissä taulukkorakenteissa osataulukkoon - siis sen ekaan alkioon - voi viitata näin:

int* pc = cb[2];

Tuo nyt ei ole ylipäätäänkään niin turvallista, sillä siinähän ryhdytään puuhaamaan pointtereiden kanssa. Vastaavan pystyy toki tekemään noilla taulukko-olioilla näin:

int* ps = &sb(2, 0);
int* pd = &db(2, 0);

Ehkä tuokaan ei nyt ole aivan paha, siinähän vain kerrotaan yksityiskohtaisemmin, että mihin osoitellaan. Ihan järkevää on tehdä perinteisellä taulukollakin:

int* pc = &cb[2][0];

Mutta jos tästäkin täytyy käydä kauppaa, niin tarjotaanpa vastineeksi tällaista:

int c = cb[5][5];       // ok!?
int s = sb(5, 5);       // assertion failed: m < M && n < N
int d = db(5, 5);       // assertion failed: m < msize && n < nsize

C-tyylisissä taulukoissa ei ole minkäänlaisia tarkistuksia. Taulukkoluokkaan voi näppärästi sisällyttää vähintäänkin debug-aikaiset tarkistukset, ettei osoitella taulukon ulkopuolelle.

Perinteisillä ja staattisilla taulukoilla ulottuvuudet ovat osa tyyppitietoa. Perinteisillä taulukoilla tieto vain menetetään esimerkiksi funktiokutsuissa. Funktio ei voi sanoa, että "suostun ottamaan vastaan vain 3x4-taulukon":

void func_c3x4(int cp[3][4])
{
    // ...
}
// käyttö:

int cc[2][4];
func_c3x4(cc);          // ok!?
func_c3x4(ca);          // ok

Taulukkoluokassa sitä vastoin tieto säilyy ja kulkee ihan perille saakka:

void func_s3x4(arr2<int, 3, 4>& sp)
{
    for (size_t m = 0; m < sp.m(); ++m) {
        for (size_t n = 0; n < sp.n(); ++n) {
            // ...
        }
    }
}
// käyttö:

arr2<int, 2, 4> sc;
func_c3x4(sc);          // error: cannot convert parameter
func_c3x4(sa);          // ok

Jos taas halutaan funktio, joka tahtoo kaksiulotteisen taulukon niin, että ulottuvuudet voivat olla mielivaltaiset mutta tiedossa, niin silloin täytyy käyttää templatea. Menettely on samanlainen C-tyylisillä taulukoilla ja staattisilla taulukkoluokilla:

void func_mxn(int* p, size_t mm, size_t nn)
{
    for (size_t m = 0; m < mm; ++m) {
        for (size_t n = 0; n < nn; ++n) {
            // ...
        }
    }
}

template<typename T, size_t M, size_t N> void func_2(T (&cp)[M][N])
{
    func_mxn(&cp[0][0], M, N);
}

template<typename T, size_t M, size_t N> void func_2(arr2<T, M, N>& sp)
{
    func_mxn(&sp(0, 0), M, N);
}
// käyttö:

func_2(ca);
func_2(sa);

C++:ssa ei ole sisäänrakennettua dynaamista taulukkomekanismia. Nyky-C:ssä sellainen kyllä on, mutta sillä ei kyllä pitkälle pärjää elon tiellä. Meidän dynaaminen taulukkomme kuitenkin osaa muutamat näppärät perustemput. Dynaaminen taulukko tietenkin tietää omat ulottuvuutensa:

void func_d(dynarr2<int> const& dp)
{
    for (size_t m = 0; m < dp.m(); ++m) {
        for (size_t n = 0; n < dp.n(); ++n) {
            // ...
        }
    }
}
// käyttö:

func_d(da);

Dynaamiseen taulukkoon voidaan sijoittaa toinen dynaaminen taulukko tai staattinen taulukko. Sijoituksen kohteen ulottuvuudet ja sisältö asettuvat samoiksi kuin sen otuksen, joka sijoitetaan:

dynarr2<int> dc(2, 4);  // == {{0,0,0,0},{0,0,0,0}}
dc = sa;                // == {{11,12,13,14},{21,22,23,24},{31,32,33,34}}

Dynaaminen taulukko voidaan myös "muotoilla" uudestaan:

dc.resize(4, 2);        // == {{11,12},{21,22},{31,32},{0,0}}

Ainoa riski näissä sijoitus- ja koonsäätöoperaatiossa on se, että jos jossain on viittauksia (esimerkiksi osoittimia) taulukon alkioihin, ne eivät operaation jälkeen enää välttämättä osoita kelvollisiin alkioihin. Mahtaako tämä olla kovinkin suuri yllätys?

Sitten se suorituskykypuoli. Staattista taulukkoa esittävä luokka on osoittelee alkioita aivan samalla tavalla kuin perinteinen C-tyylinen taulukkokin. Osoitukset on kapseloitu yksinkertaisiin inline-funktioihin, joten optimoidussa käännöksessä turhat välivaiheet jäävät pois. Ainoa ero on, että kehitysaikana noissa osoituksissa on mukana tarkastukset, ettei viitata taulukon ulkopuolelle. Tarkistukset voidaan jättää pois optimoidussa käännöksessä. Siis, suorituskyky on sama kuin perinteisillä taulukoilla.

Dynaamisissa taulukoissa käytetään hyväksi standardikirjaston vector-luokkaa. Dynaamiset taulukot ovat dynaamisen muistinhallinnan takia hitaampia, mutta ne ovat sitten kanssa dynaamisia. Alkioiden osoittaminen ei indeksoinnin käsinlaskennan takia ole hitaampaa kuin vastaavissa perinteisissä taulukoissakaan, sillä niissä lasketaan aivan samalla tavalla, mutta koodaajalta piilossa. Kääntäjä kylläkin pystyy paremmin optimoimaan perinteisten taulukoiden koodia.

En ole kommentoinut esimerkkilistauksen header-koodia. Parin rivin funktiot lienevät aika selkeitä. Ainoastaan kaksiulotteisen taulukon resize-funktiossa on vähän enemmän koodia. Jos jollakulla on epäselvää koodin suhteen, niin täällähän siitä voi kysyä; eiköhän näihin porukalla vastauksetkin löydy.

Luokkia voi toki kehittää vielä pidemmällekin, sillä nyt niistä on jätetty pois kaikki sellainen, mikä mahdollisesti vain sekoittaisi ajatuksia. Luokkia voisi kehittää useampiulotteisille taulukoille ja niihin voisi lisätä toiminnallisuutta, jolla ne mm. toimisivat paremmin standardikirjaston palveluiden kanssa. Kovin kummoisia ei ehkä kannata ruveta virittelemään, ellei ensin perehdy esimerkiksi standardikirjaston luokkiin vector, string, valarray ja tulossa oleva array. Esimerkiksi arr1 on tuon viimeksimainitun halpisversio, jonka idea on kopioitu Stroustrupin kirjasta.

Toivottavasti koodiin ei jäänyt kovin typeriä virheitä. Miltäs vaikuttaa?

EDIT: Korjattu pari typoa ja johdonmukaistettu esimerkkien numeroarvoja. Lukijalta oikeastaan edellytetään kielen omien taulukoiden toiminnan tuntemista. Voisi olla järkevää tehdä vinkki siihen, miten aloittelija pääsisi suoraan sisään noiden ystävällisempien arr- ja dynarr-luokkien käyttöön ilman rämpimistä C-taulukoissa.

koorray.hpp

#ifndef KOORRAY_HPP_INCLUDED
#define KOORRAY_HPP_INCLUDED

#include <cassert>
#include <cstddef>
#include <vector>

template<typename T, std::size_t N> struct arr1
{
    T& operator()(std::size_t n)
    {
        assert(n < N);
        return _a[n];
    }

    T const& operator()(std::size_t n) const
    {
        assert(n < N);
        return _a[n];
    }

    std::size_t size() const { return N; }

    std::size_t n() const { return N; }

    T _a[N];
};

// ------------------------------------

template<typename T, std::size_t M, std::size_t N> struct arr2
{
    T& operator()(std::size_t m, std::size_t n)
    {
        assert(m < M && n < N);
        return _a[m][n];
    }

    T const& operator()(std::size_t m, std::size_t n) const
    {
        assert(m < M && n < N);
        return _a[m][n];
    }

    std::size_t size() const { return M * N; }

    std::size_t m() const { return M; }

    std::size_t n() const { return N; }

    T _a[M][N];
};

// ------------------------------------

template<typename T> struct dynarr1
{
    explicit dynarr1(std::size_t n) : v (n) {}

    template<std::size_t N> dynarr1(arr1< T, N > const& a)
        : v(&a[0], &a[0] + N)

    {
    }

    template<std::size_t N> dynarr1& operator=(arr1<T, N> const& a)
    {
        std::vector<T> tmp(&a(0), &a(0) + N);
        v.swap(tmp);
        return *this;
    }

    T& operator() (std::size_t n)
    {
        assert(n < v.size());
        return v[n];
    }

    T const& operator() (std::size_t n) const
    {
        assert(n < v.size());
        return v[n];
    }

    void resize(std::size_t n) { v.resize(n); }

    std::size_t size() const { return v.size(); }

    std::size_t n() const { return v.size(); }
private:
    std::vector<T> v;
};

// ------------------------------------

template<typename T> struct dynarr2
{
    dynarr2(std::size_t m, std::size_t n)
        : msize(m),
        nsize(n),
        v(m * n)
    {
    }

    template<std::size_t M, std::size_t N> dynarr2(arr2<T, M, N> const& a)
        : msize(M),
        nsize(N),
        v(&a(0, 0), &a(0, 0) + (M * N))
    {
    }

    template<std::size_t M, std::size_t N> dynarr2&
        operator=(arr2<T, M, N> const& a)
    {
        std::vector<T> tmp(&a[0], &a[0] + (M * N));
        msize = M;
        nsize = N;
        v.swap(tmp);
        return *this;
    }

    T& operator()(std::size_t m, std::size_t n)
    {
        assert(m < msize && n < nsize);
        return v[m * nsize + n];
    }

    T const& operator()(std::size_t m, std::size_t n) const
    {
        assert(m < msize && n < nsize);
        return v[m * nsize + n];
    }

    void resize(std::size_t m, std::size_t n)
    {
        std::vector<T> tmp;
        tmp.reserve(m * n);
        std::size_t const mmin = (m < msize ? m : msize);
        std::size_t const nmin = (n < nsize ? n : nsize);
        for (std::size_t mm = 0; mm < mmin; ++mm) {
            T* const mmv = &v[mm * nsize] ;
            tmp.insert(tmp.end(), mmv, mmv + nmin);
            if (nmin < n) {
                tmp.resize((mm + 1) * n);
            }
        }
        if (mmin < m) {
            tmp.resize (m * n);
        }
        msize = m;
        nsize = n;
        v.swap(tmp);
    }

    std::size_t size() const { return v.size(); }

    std::size_t m() const { return msize; }

    std::size_t n() const { return nsize; }
private:
    std::size_t msize;
    std::size_t nsize;
    std::vector<T> v;
};

#endif