Keskustelu: Ohjelmointikysymykset: C++: Moniulotteiset oliotaulukot ja funktiot C++

Yksiuloitteiset taulukot käsittääkseni kannattaa lähettää funktioille tällaisilla prototyypeillä:

funktio (taulukko[],int n);

jossa n on taulukon koko. Näin funktiossa pysytään rajojen sisäpuolella.

for (int i = 0; i < n; i++) {
 ...
muokkaa taulukko<i>
 ...
}

Mutta eipä toimikaan tämä kaksiuloitteisella taulukolla. Devc++ valittaa, että vain ensimmäisen dimension saa määrittää ilman rajoja (varmaan sillä on syy). Eli että pitäisi laittaa prototyyppiin esim.:

funktio(taulukko[][5], int n);

Ongelmanihan on että taulukon molemmat koot vaihtelevat kutsuttaessa funktiota, joten niitä ei voi määrittää etukäteen. Miten tiedot tulisi antaa funktiolle?

Ja vielä monimutkaistan asioita sillä, että on kyse olio-taulukoista ja alkuperäisiä olioita pitäisi pystyä muuttamaan. Siitäkin vielä herjaa ettei saisi tehdä viittaus taulukoita. Osoittimetkaan eivät tunnu kovin järkevältä vaihtoehdolta kun kyseessä olevia olioita on parikymmentätuhatta...

Varaa taulukot dynaamisesti (new[]:llä, googleta konstit kaksiuloitteisen taulukon varaamiseen). Prototyyppaa funktio tyyliin:

funktio(tyyppi **taulukko, int a, int b);

Eli osoitin osoittimeen, johon voi viitata tuttuun tapaan taulukko[x][y].

Mitäs jos teet taulukon näin:

int taulukko[leveys*korkeus];

ja sitten osoitat esim. alkioon rivi/sarake näin:

taulukko[leveys*rivi+sarake]

Tällöin taulukko on tehty yksiulotteiseksi, eikä tarvitse pähkäillä missä muodossa sitä pitäisi siirtää muille funkkareille.

Ongelman juuri on siinä, että C++:ssa ei ole moniulotteisia taulukoita. Kaksiulotteinen taulukko on tarkemmin ajatellen taulukko taulukoita.

Tätä ei kannata yrittää ratkaista millään ihmeellisillä pointterivirityksillä, niiden kanssa saa aika helposti viisarit sekaisin ja muistia vuotamaan. Myöskään new[]:lla ei kannata taulukoita hommailla, kun kirjastosta löytyy std::vector.

Hyvä konsti on tehdä oma pikkuruinen taulukkoluokka ja määritellä siihen haluamansa ominaisuudet. Homman voi hoitaa myös niin, että toteuttaa taulukkoa käsittelevä funktion templatena ja lisätä siihen sellaiset loitsut, että se ottaa selville parametrinsa ulottuvuudet. Tuo eka tapa on oikeastaan aika mukava, tässä pieni esimerkki:

#include <cassert>
#include <vector>
// nämä ovat vain tulostusta varten
#include <iomanip>
#include <iostream>

template<typename T> class array2d
{
        size_t d0;
        size_t d1;
        std::vector<typename T> v;
public:
        array2d(size_t dim0, size_t dim1)
                : d0(dim0), d1(dim1), v(dim0*dim1)
        {}

        typename T& operator()(size_t i0, size_t i1)
        {
                assert(i0 < d0 && i1 < d1);
                return v[i0*d1+i1];
        }

        typename T const& operator()(size_t i0, size_t i1) const
        {
                assert(i0 < d0 && i1 < d1);
                return v[i0*d1+i1];
        }

        size_t size0() const { return d0; }

        size_t size1() const { return d1; }

};

void f(array2d<int> const& a)
{
        std::cout << "taulukko[" << a.size0() << "," << a.size1() << "]\n";
        for (size_t i = 0; i < a.size0(); ++i)
        {
                for (size_t j = 0; j < a.size1(); ++j)
                {
                        std::cout << std::setw(2) << std::setfill('0')
                                << a(i, j) << " " << std::setfill(' ');
                }
                std::cout << "\n";
        }
}

int main()
{
        int const d0 = 3;
        int const d1 = 5;

        array2d<int> arr(d0, d1);
        for (int i = 0; i < d0; ++i)
                for (int j = 0; j < d1; ++j)
                        arr(i, j) = i*10+j;
        f(arr);
}

fawkzin ratkaisusta en oikein osaa sanoa, kooderin oma tekee taulukon kautta ohjelmasta vaikeaselkoisen ja koon ideoista tajusin vain ideat; ohjelmointitaitoni eivät taida vielä riittää. Kiitos kuitenkin.

Mutta tuli mieleen, tekstipeliä kun teen ja ko. kaksiuloitteinen taulukko on kartta, niin jos laitan taulukon muiden tietojen kanssa uuden "maplevel" luokan sisään ja annan funktio(i)lle koko uuden luokan viittauksena.

? Toimisikohan joku tällainen virittely, kun en ole luokkiin vielä niin syvällisesti perehtynyt. Eli voiko kurottaa tyyliin:

maplevel.ruutu[a][b].hae_tiedot()

Ennemmin näin:
maplevel->hae_ruutu(x, y), missä hae_ruutu palauttaa viittauksen ruutuun (Ruudun_Tyyppi &) ja kartta on välitetty luonnollisesti osoittimena.

wumpus kirjoitti:

maplevel.ruutu[a][b].hae_tiedot()

Ei kannata, tuossa ongelma vain siirtyy yhtä kerrosta syvemmälle. Taulukon kokoa ei siltikään voi vaihdella vapaasti.

Jos nyt kumminkin tajusit meikäläisen esimerkistä edes ituja, niin tässä tulee käyttöohje rautalankamallina. Tuon luokan syvempää sielunelämää ei niin tarvi ymmärtääkään.

Kopioi esimerkistäni tuo template-luokkamäärittely vaikkapa tiedostoon array2d.hpp tällä tapaa:

#ifndef ARRAY2D_HPP
#define ARRAY2D_HPP
#include <cassert>
#include <vector>

template<typename T> class array2d
{
        // tähän tuon templaatin oikea sisältö
};

#endif

Nyt sulla on sitten käytettävissä kaksiulotteinen taulukko. Nyt jos haluat käsitellä funktiossa esmes kaksiulotteista kokonaislukutaulukkoa (lasketaan vaikka rivisummien tulo), se menee näin:

#include "array2d.hpp"

int summien_tulo(array2d<int> const& a)
{
        // taulukon ulottuvuuksia ei tarvitse tietää etukäteen,
        // sillä ne voi kysyä

        int korkeus = a.size0();
        int leveys = a.size1();

        int tulo = 1;
        for (int i = 0; i < korkeus; ++i)
        {
                int summa = 0;
                for (int j = 0; j < leveys; ++j) summa += a(i, j);
                tulo *= summa;
        }
        return tulo;
}

Tuota funktiota sitten voi käyttää vaikka näin:

#include "array2d.hpp"

int main()
{
        array2d<int> taulukko(13, 17);
        // taulukossa on 13 riviä ja 17 saraketta, tietty

        // sijoitellaan taulukkoon arvoja, tässä yksi esimerkki
        taulukko(5, 7) = 42;

        // ja sitten se funktiokutsu
        int tulos = summien_tulo(taulukko);

        // jne.
}

Jos funktio haluaa muuttaa taulukon sisältöä, ei tietenkään saa käyttää const-viittausta. Leikitäänpä liukuluvuilla:

#include "array2d.hpp"

void nollaa_eka_rivi(array2d<double>& b)
{
        int const m = b.size1();
        for (int j = 0; j < m; ++j) b(0, j) = 0;
}

Tarviiko tuosta nyt sitten paljon muuta tietääkään? Juoni on siis siinä, että taulukon määrittelyssä sisällön tyyppi annetaan templaten tyyppiparametrina ja halutut taulukon mitat konstruktorin parametreina. Siis:

#include "array2d.hpp"

array2d<float> flotarit(3, 3);
array2d<ruutu> ruudukko(10, 10);

array2d<char> c_tyyli(5, 80);
strcpy(&c_tyyli(2, 0), "Varo c-tyylisiä ylivuotoja!");

Ainoa vika tässä touhussa on, ettei taulukkoa voi alustaa C-tyylisesti = { ... }; -jutuilla. Taulukon riveihin ei myöskään pysty osoittamaan suoraan antamalla vain yhtä indeksiä, mutta se olisi iisisti korjattavissa kirjoittamalla luokkaan kaksi operaattoria lisää.

Tulihan pitkä turina, mutta saatte joka jätkä rahanne takaisin, jos tää ei toimi!

typedef vector<vector<TPalanen>> TKartta;
Voi mennä vähän hankalaksi, mutta jos siitä on pakko tehdä kaksiulotteinen, niin miksei sitten noinkin :)

Minusta varsin hyvä tapa olisi käyttää sitä yksiulotteista. Koodin selkeyttämistä varten on keksitty makrot ja funktiot, mutta eiköhän makro riitä.
#define Ruutu(X, Y) ((X) + ((Y) * Leveys))
Ruudut[Ruutu(10, 31)] = Ruudut[Ruutu(5, 2)];
Itse käytin tätä tapaa, kun muinoin tilepohjaista peliä väsäsin.

Tuo vector vectoreita toimii kyllä, mutta se ei ole ihan niin hyvä: alustus oikeisiin mittoihin on vähän hankala, alkioiden osoitteiden räknääminen ei toimi taulukkomaisesti ja käyttäjä voi (vahingossa) muutella mittoja.

Makroja kannattaa välttää. Niistä koituu helposti harmeja erityisesti laajemmissa hankkeissa. Kaikkien tunnettujen makro-ongelmien lisäksi tuo Ruutu-makro on riippuvainen jostakin Leveys-arvosta (sen lisäksi että se indeksoi väärin). Taulukon leveys siis joudutaankin fiksaamaan. Yhtä hyvinhän sitä sitten voisi koodata, että
void funktio(int taulukko[][Leveys]).

Luokatkin auttavat koodin selkeydessä. Kumpi vaikuttaa selkeammältä ja robustimmalta?

#define Ruutu(X, Y) ((X) + ((Y) * Leveys))
// ...
Ruudut[Ruutu(10, 31)] = Ruudut[Ruutu(5, 2)];

// vai

#include "array2d.hpp"
// ...
Ruudut(10, 31) = Ruudut(5, 2);

Luulenpa vielä, että saa olla melko erikoista koodia, että optimoidun käännöksen jälkeen noissa näkyy merkittävää suorituskykyeroa. Luokan avulla toteutettu versio on ohjelmoijan kannalta turvallisempi.

koo kirjoitti:

Tulihan pitkä turina, mutta saatte joka jätkä rahanne takaisin, jos tää ei toimi!

tuota pitää lainailla useamminkin!

Nyt selveni koko homma kun vähän mietin, saa nähdä saanko toimimaan sitten kotona :)
(tai ennen kaikkea saanko sovitettua ton ohjelmaan...)

Minä taas luulen, että noissa voi olla jo huomattavakin suorituskykyero, sikäli kuin tuollaisilla yleensä mitään merkitystä on; yleensä pullonkaula tapaa olla hieman toisaalla. Mutta yleensä nopein tapa on kuitenkin käyttää taulukollista taulukkoja. Vektorit ovat minun kokemukseni mukaan hitaampia kuin taulukot. Minä tekisin tähän tapaan:

TPala ** Ruudukko;
Ruudukko = new TPala *[Leveys];
// Kaikki muisti kerralla
Ruudukko[0] = new TPala[Leveys * Korkeus];
// Ja loput rivit kohdalleen
for (int i = 1; i < Leveys; ++i)
{
  Ruudukko[i] = &(Ruudukko[i-1][Korkeus]);
}

// Tuhoaminen:
delete [] Ruudukko[0];
delete [] Ruudukko;

Tällä tavalla koko taso on mahdollista lukea tiedostosta kerralla, jos TPala on luettavissa suoraan.

Puolustetaanpa vielä noita muita tapoja, vaikken niitä itse käytäkään:

Makroja ei pitäisi noin kovasti tyrmätä. Hyvin tehdyssä ohjelmassa kaikki on moduloitu niin hyvin, että tuon makron voi määritellä yhden tai parin funktion ajaksi ja sitten poistaa (#undef).

Tuokin on aika kaukaa haettu syytös vektoriratkaisulle, että joku voi vahingossa laajentaa riviä. Kyllähän joku voi aivan yhtä hyvin osoittaa tavallisen taulukon ulkopuolelle muistissa tai muuten vain tehdä jossakin virheen, joten tuo on melkoisen väärä perustelu. Kyllähän moni ohjelmoi myös C:llä, josta valmiit tarkistukset puuttuvat täysin, eikä heitä silti pidetä huonoina ohjelmoijina.

Onko niin kovin vaikea kirjoittaa funktio, jossa alustaa tuon "vektoritaulun"? Eipä ole monen rivin juttu.

Tosissani en tuota vektoriratkaisua heittänyt, mutta minusta kaikki nuo perustelut ovat aivan tuulesta temmattuja. Jos ohjelmointitapa on huono siksi, että se mahdollistaa virheen, niin silloin ei taida hyvää tapaa olla olemassakaan.

Mutta aika kattavasti tapoja tässä on käsitelty, ja lopulta paras on taas kerran se, jota käyttäjä itse osaa käyttää.

Vektorikokemukset voivat varmaan vaihdella. Jotta ei jäisi ihan luulottelun varaan, väkersinpä sitten pienen mittariohjelman. Näin kävi:

Taulukon luonti ja tuhoaminen:
n       2        5       10       20       50      100
   89,684  356,355  366,416  316,523  888,676 3130,389
   47,564  180,909  186,762  203,542  857,598 3584,806
    0,005    0,005    0,005    0,005    0,005    0,005

Taulukon läpikäynti, std::swap(a[i][j], a[j][i]) kullekin alkiolle:
n       2        5       10       20       50      100
    1,497    7,446   27,810  106,758  688,642 2729,303
    1,000    3,609   12,104   41,901  252,256 1065,343
    1,157    1,947    7,462   51,294  244,506 1047,593

Ekalla rivillä on int-taulukon koko (n*n). Tokalla on pointteritaulukkokoodilla saatu tulos ja kolmannella array2d-väkästyksen lukema. Neljännellä rivillä tavallisilla pinosta ei-dynaamisilla mitoilla varattavien [n][n]-taulukoitten vertailulukuja. Testit on ajettu Ibarin pari vuotta vanhassa WinXP-läppärissä. Koodi on käännetty MSVC++2003:lla, Release-asetuksilla. Lukemat ovat luupeista skaalattuja kestoja, joissa on hieman käyttiksen sielunelämästä johtuvia satunnaisuuksia. Suuruusluokkien pitäisi kuitenkin olla oikein.

Makroja ei pidä käyttää yhtään mihinkään sellaiseen, jonka voi tehdä vakioilla, typedefeillä, inline-funkkareilla tai templaateilla. Makrot eivät noudata kielen näkyvyyssääntöjä (tunnukset, funktiot, luokat, nimiavaruudet), tyyppitarkastuksia ei ole, parametrien evaluointi on yllätyksellistä, koodiin saattaa tulla ihmeellisiä riippuvuuksia ja debuggaaminen on mitä sattuu. Makrojen asetteleminen ja poisteleminen käsin... kiitos ei! Include-vahdit, rajattujen alusta- ja ympäristöriippuvuuksien hanskaaminen, minimaaliset apurakenteet... no joo, ei makroja kokonaan kannata tyrmätä.

Kaikki vector vector -häkkyrästä heittämäni "syytökset" johtavat kuitenkin siihen, ettei otus ole kovin hyvä natiivin a[r][c]:n korvike. Jos otus on "kuin kaksiulotteinen taulukko", onko kaukaa haettua olettaa, että jos a[0][5] ja a[1][0] ovat ok, a[1][5] on myös ok? Tässäpä otuksessa niin ei olekaan, vaan pitää tietää, että se on vektorivektori. Hyvätkin koodarit voivat tehdä virheitä, varsinkin jos jokin juttu ei vastaa ennakkotietoja tai -odotuksia.

Muuten, huomasiko kukaan, mitä array2dn optimoimattomassa versiossa tapahtuu, jos indeksit menevät taulukon ohi?

Vaikeata ei ole kirjoittaa funktiota, joka alustaa vektoritaulun. Vaikeata on muistaa kirjoittaa se tai kutsua sitä, ellei se hoidu automaagisesti.

Tuulesta temmattua... No, C++-oliopuuhastelun etu kuitenkin on, että on hyviä konsteja kuvata erilaisia abstraktioita, määritellä lupauksia ja jakaa vastuita. Tämä vähentää vahinkomahdollisuuksia ilman, että esimerkiksi suorituskyky erityisemmin kärsii.

En pidä niin ilmiselvästi parhaana tapana aina sitä, jonka käyttäjä osaa. Sellainen tapa, joka on helppo oppia, käyttää ja opettaa, voi olla parempi, jos muutoin ollaan samalla hehtaarilla.

Tuossa pointteritaulukkomallissa tarvitaan array2d-pakettiin verrattuna aika monta temppua, jotta homma pelittää oikein. Ollakseen muutamassa minuutissa standardipalikoista väsätty array2d on suorastaan hävyttömän suorituskykyinen ja turvallinen pointterirakennelmaan (jossa on vielä kahden deleten mokaamismahdollisuus ja exception unsafety) verrattuna. Pointterirakennelman voi kääräistä luokaksi, jolloin käyttö helpottuu ja turvallisuus paranee, mutta sittenpä pakkaus näyttääkin päältä päin aika samalta kuin array2d.

(Tuo pointterirakennelma voisi tietysti indeksoida alkioita oikeassakin järjestyksessä. Ja array2dhen voisi uhrata puoli tuntia lisää aikaa, niin sen saisi siistimmäksi ja indeksoinnit toimisivat []-operaattoreilla taulukoitten tapaan.)