Keskustelu: Ohjelmointikysymykset: C++ dynaaminen muisti

Olen käsittänyt, että voin varata ohjelman kulun aikana määrätyn määrän muistia näin:

int maara;
maara = std::cin.get();
int * muisti;
muisti = new int[maara];

Mutta kaksiulotteista taulukkoa en ole saanut luotua, tähän tyyliin:

muisti = new int[maara][maara];

Kääntäjä valittaa että non-constant expression tms., onko mahdollista varata tuolla tavalla kaksiulotteisesti dynaamista muistia?

int maara1 = 10;
int maara2 = 20;

int** muisti;
muisti = new int*[maara1];
for(int i = 0; i < maara1; ++i) {
   muisti[i] = new int[maara2];
}

// ja vapautus
for(int i = 0; i < maara1; ++i) {
 delete [] muisti[i];
}
delete [] muisti;

Kannattaa tutustua myös vektoreihin.

Olisit kokeillut edes jotakin Ohjelmointiputkan lukuisista hakutoiminnoista. Koodivinkkihaku oikealla kielellä ja hakusanalla "taulukot" antaa jo oikein hyvät tulokset, joista koon kirjoittamat (1672 ja 1918) paneutuvat erityisesti dynaamisiin kaksiulotteisiin taulukoihin C++:n menetelmillä.

Dynaamista muistinvarausta "käsin" eli new-operaattorilla kannattaa välttää, standardikirjaston vector-luokka ajaa asian paremmin. Kaksiulotteisen taulukon saa helpoiten aikaan käyttämällä yksiulotteista taulukkoa ja helppoa laskukaavaa:

std::vector<int> taulu;
taulu.resize(leveys * korkeus);
taulu[x + y * leveys] = 0;

Et voi tosiaan suoraan tehdä kaksiulotteista taulukkoa, vaan homma on hoidettava joko yksi ulotteisella taulukolla

int * muisti;
muisti = new int[maara*maara];

tai pienellä kikkailulla

int leveys = 10;
int korkeus = 20
int** muisti;
muisti = new int*[leveys];
for(int i = 0; i < leveys; i++)
	muisti[i] = new int[korkeus];

Tällöin myös taulukon poistaminen tarvitsee samantapaisen tempun.

EDIT: Kaikki haluavat vastata aina samaan kysymykseen yhtäaikaa!

En ymmärrä muutamaa asiaa, ja koska olen vielä suht. aloittelija niin koon koodivinkitkin tuntuvat aika heprealta, joten kysyn vielä:

- minkä vuoksi c++:n omalla new-operaattorilla ei kannata varata dynaamisesti muistia

- koon oppaassa sanotaan, että kaksiulotteiset taulukot ovat useimmiten yliarvostettuja ja asian voisi hoitaa paremmin, mutta mitä haittapuolia normaalin kaksiulotteisen taulukon käytössä sitten on yleensäkin?

"Normaalia" kaksiulotteista taulukkoa on yleensä hankalampi käyttää kuin yksiulotteista taulukkoa, vaikka pienet vakiokokoiset moniulotteiset taulukot (esim. int taulu[1][2][3];) näyttävätkin käteviltä. C:n ja C++:n kaksiulotteiset taulukot ovat nimittäin todellisuudessa taulukoiden taulukoita ja niitä (tai C++:ssa mieluummin vastaavasti listojen/vektorien listoja yms.) kannattaa käyttää vain sellaisessa tilanteessa, jossa rakenne todella kuvaa listaa mahdollisesti erikokoisista listoista - esimerkiksi "kauppalistalistaa" tai jotakin vastaavaa.

Tyypillinen tapaus, jossa moniulotteista taulukkoa ei tarvita eikä kannata käyttää on sellainen, jossa halutaan luoda vaikkapa jonkin lautapelin kaksiulotteista pelilautaruudukkoa kuvaava tietorakenne. Se kannattaa toteuttaa edellisissä viesteissä esitetyllä tavalla yksiulotteisena taulukkona, koska se on helpompaa, eikä "taulukkotaulukko"-luonteesta ole pelilaudan tapauksessa mitään hyötyä. Jokainen rivi/sarake on esimerkiksi saman pituinen ja ne luodaan kaikki kerralla.

C++:ssa tällaisen rakenteen käsittely kannattaa lisäksi enkapsuloida sopivan luokan sisälle, jolloin sen käyttö (esimerkiksi ruudukko.haeAlkio(x,y);) on entistäkin helpompaa ja turvallisempaa.

Ihme_kala kirjoitti:

- minkä vuoksi c++:n omalla new-operaattorilla ei kannata varata dynaamisesti muistia?

Tähänkin olisit saanut suoran vastauksen koon vinkistä.

koo kirjoitti:

Yleensä ehdotetaan taulukon luontia yksinkertaisesti taulukko-new:llä tyyliin "int *p = new int[100];". Tämä ei ole hyvä, koska taulukko täytyy vapauttaa taulukko-deletellä, mikä jää helposti tekemättä. Ongelma ei ole deleten kirjoittaminen vaan se, että joskus haarautumisten tai exceptioneiden takia tulee mokanneeksi, eikä deleteä koskaan saavuteta.

Käytännössä ongelmatilanteet voivat näyttää vaikka tältä:

bool lataa_taso() {
  int *valiaikainen_taulukko = new int[10000];
  // ...
  if (virhe) {
    // virhe, palautetaan false.
    return false;
  }
  // ...
  // onnistui, vapautetaan väliaikainen muisti ja palautetaan true
  delete [] valiaikainen_taulukko;
  return true;
}

Esimerkiksi tässä väliaikainen taulukko jää helposti vapauttamatta virhetilanteessa — kuten nyt näköjään kävi. Sen sijaan vector-luokkaa käyttämällä muisti vapautuisi automaattisesti riippumatta siitä, loppuuko funktio kesken vai päästäänkö loppuun asti.

os kirjoitti:

Se [lautapelin pelilauta] kannattaa toteuttaa edellisissä viesteissä esitetyllä tavalla yksiulotteisena taulukkona, koska se on helpompaa, eikä "taulukkotaulukko"-luonteesta ole pelilaudan tapauksessa mitään hyötyä.

Minusta merkintä taulu[y][x] on selkeämpi kuin taulu[y*w+x] ja merkinnät taulu[y][x+1] ja taulu[y+1][x] ovat selkeämpiä kuin taulu[a+1] ja taulu[a+w]. Mitä hyötyä on siitä, että käytetään yksiulotteista taulukkoa?

Onhan taulu[y][x] merkintänä selkeä (selkeämpi kuin taulu[y*w+x]), mutta kaksiulotteisen taulukon muistinvaraus aiheuttaa ainakin minusta tämän saavuttamiseksi kohtuuttomasti vaivaa. Hankalasta merkinnästä pääsee sitäpaitsi helposti yli vaikkapa makrolla:

#define TAULU(x,y) taulu[(y)*w+(x)]

C++:ssa apuluokalla - joko yhtä hienolla kuin koon vinkissä tai näinkin yksinkertaisella

class Taulu
{
private:
    int *alkiot;

    Taulu(const Taulu &);

public:
    const int w, h;

    int &alkio(int x, int y) { return alkiot[y*w+x]; }
    const int &alkio(int x, int y) const { return alkiot[y*w+x]; }

    Taulu(int W, int H) : w(W), h(H) { alkiot = new int[w*h]; }
    ~Taulu() { delete [] alkiot; }
};

tai C:ssä vastaavan toiminnallisuuden apufunktiolla ja -structilla

typedef struct
{
    int *alkiot;
    int w, h;
} Taulu;

int haeAlkio(Taulu t, int x, int y);
void asetaAlkio(Taulu t, int x, int y, int alkio);
Taulu luoTaulu(int x, int y);
void vapautaTaulu(Taulu t);
// ...

EDIT: toisaalta jos sovelluksessa käytettään pieniä vakikokokoisia taulukoita, kuten jätkänshakin 3x3-ruudukko tai esim. OpenGL:n käyttämät 4x4-matriisit, niin miksei kaksiulotteinen taulukkokin voisi olla yksinkertainen ja toimiva ratkaisu...

Eikös kaksiulotteiset taulukot voi olla hitaampiakin ku normaalit taulukot?

Tällaisia asioita koskevat nopeusoptimoinnit kannattaa tehdä vasta jälkikäteen, jos ongelmia ilmenee. Ainoastaan ohjelman havaittuja pullonkaulakohtia kannattaa optimoida. Ennenaikainen mikro-optimointi on kaiken pahan alku ja juuri.

Taulukon käyttötapa ja etenkin sen vaikutus kääntäjä-, käyttöjärjestelmä- ja prosessoritasolla tapatuvaan magiikkaan taitaa nopeuskysymyksissä olla niin merkittävässä roolissa, ettei mitään yleistyksiä moniulotteisten taulukoiden nopeudesta yksiulotteisiin verrattuna muutenkaan voi eikä etenkään kannata ruveta tekemään.

Niin kuin on jo sanottukin, taulukkoa ei voi luoda dynaamisesti niin, että sen alkioita voisi osoitella kahdella tai useammalla []-indeksillä. Kannattaa kääräistä taulukkotoiminnallisuus luokkaan, jossa on sopiva indeksointioperaattori. Toiminnallisuus on riittävän sama kuin kielen omilla staattisilla taulukoilla, plus että luokka toimii muutenkin järkevämmin. Valmiita luokkia on saatavilla ja niistä on esimerkkejä - niin, itsekin olen niitä rustaillut.

Taulukkojen ongelma on se, että ne ovat kovin matalan tason tietorakenteita, joita C (ja C++) käsittelee aika omaperäisellä tavalla. Useampiulotteisissa taulukoissa ongelmat vielä kertautuvat.

Taulukko ei esimerkiksi tiedä kokoaan. Kääntäjä kyllä tietää jotakin - mm. kaksiulotteisen taulukon leveyden, jotta alkioiden osoittelu onnistuu - mutta tieto on huonosti käytettävissä. Funktiokutsuissa taulukkomuuttuja rappeutuu osoittimeksi ensimmäiseen alkioon, joten se käyttäytyy aika eri tavalla kuin muut muuttujat.

Gaxx ja petrinm: Joo, voi sitä tosiaan luoda esittämällänne tavalla taulukon taulukoita, mutta kyllä tuo konsti on minusta enemmänkin uusi ongelma kuin ratkaisu ongelmaan, on se sen verran kiikkerä viritys.

Antti: Kyllä, taulu[y][x] on selkeämpi kuin taulu[y*w+x], joka onkin aika kamala. Merkintätapa ei nyt vain ole mahdollinen, jos taulukon pitää olla dynaaminen ja taulu on osoitin. Yksiulotteisen taulukon käyttämisessä ei ole tässä kyse hyödyllisyydestä vaan välttämättömyydestä.

os: Makrojen käyttö on aivan ehdottoman huono ratkaisu. Esittämästäsi C++-luokasta puuttuu varmaankin private-piilotettu sijoitusoperaattori. C:ssä structeja ja apufunktioita pyöritellessä saattaa kyllä jossain vaiheessa ruveta mietityttämään, että mitä ongelmaa lopulta oltiinkaan ratkaisemassa.

Spongi: Useampiulotteiset taulukot ovat lähtökohtaisesti yksiulotteisia hitaampia lisälaskennan tai -osoituksen takia. Ero on mitätön. Paljon merkittävämpää on ylipäätään laajojen muistialueiden lukeminen ja kirjoittaminen ja esimerkiksi koneen välimuistien toiminta yms., ihan kuten os sanoo.

Voi olla, että kaksiulotteinen taulukko on näppärä sisäinen tietorakenne pelilautojen tai matriisien esittämiseen. Siinä vain tulee kaupanpäällisinä erinomaisen huono käyttörajapinta niihin tietoihin, eikä sisäinen rakenne lopulta poikkea yksiulotteisesta muistialueesta. Miksi siis vaivautua, jos homma hoituu paremmin oliorajapinnoilla? Jos on pakko olla yhteensopiva jonkun C-jutun kanssa, sen voi järjestää sitten erikseen.

Tämän keskustelun kirvoittamana olen tehnyt vähän päivityksiä tähän asiaan liittyvään koodivinkkiin.

koo kirjoitti:

os: Makrojen käyttö on aivan ehdottoman huono ratkaisu. Esittämästäsi C++-luokasta puuttuu varmaankin private-piilotettu sijoitusoperaattori.

Ei itseasiassa puutu, koska kokomuuttujat ovat tyyppiä const int.

Taulu a(1,2), b(3,4);
a = b;

test.cpp: In member function ‘Taulu& Taulu::operator=(const Taulu&)’:
test.cpp:2: error: non-static const member ‘const int Taulu::w’, can't use default assignment operator
test.cpp:2: error: non-static const member ‘const int Taulu::h’, can't use default assignment operator
test.cpp: In function ‘int main()’:
test.cpp:23: note: synthesized method ‘Taulu& Taulu::operator=(const Taulu&)’ first required here

Pientä virityksen makua ilmassa kyllä, myönnetään.

Makrojen käytöstä C++:ssa olen ihan samaa mieltä, mutta C:ssä kyllä mielelläni käyttäisin juuri tuollaista rumaa makroa, joka olisi tässä tapauksessa minimalistinen tapa saada aikaan juuri se mitä halutaan: päästä eroon merkinnästä taulu[y*w+x] ja erityisesti välttää tyypillisimmät laskuvirheet taulu[(y-2)*w+x-3]-tyylisten aksessointien yhteydessä. Makron voisi vaikka määrittää funktion alussa ja undeffata lopussa.