Kirjoittaja: koo
Kirjoitettu: 06.12.2006 – 06.12.2006
Tagit: ohjelmointitavat, koodi näytille, vinkki
Siellä sun täällä olen muutamaan otteeseen nähnyt kysyttävän, miten C++:ssa voisi tehdä kaksiulotteisia taulukoita niin, ettei taulukon kokoa tarvitse määrätä etukäteen. Rustasinpa pienen esimerkkitoteutuksen, jolla asia voidaan hoitaa melko yksinkertaisesti, tehokkaasti ja turvallisesti.
Mietitäänpä ensin, miten tavallinen yksiulotteinen taulukko saadaan toteutettua dynaamisesti. Yleensä ehdotetaan taulukon luontia yksinkertaisesti taulukko-new:llä tähän 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. Parempi ratkaisu on hoitaa homma kääräisemällä resurssienhallinta luokan sisään ja tehdä tuohon luokkaan sellaiset funktiot - tai oikeastaan operaattorit - että sen käyttö muistuttaa sopivasti kielen omaa taulukkoa. Jotta tällainen luokka toimisi sujuvasti kaikentyyppisillä alkioilla, sen on syytä olla template.
Ekassa listauksessa on kokonainen dynarray.hpp-tiedosto. Koska se on tarkoitettu ihan arkipäiväiseen kirjastokäyttöön, itse koodissa ei ole pahemmin kommentteja, mutta selostetaanpa pääpiirteet tässä.
Ensimmäinen luokka on dynarray, jonka on siis tarkoitus muistuttaa C++:n omaa kiinteämittaista taulukkoa, mutta jonka koko voidaan päättää ajon aikana. Luokassa on konstruktori, jolla voi lennossa luoda halutunkokoisen taulukon. Konstruktorilla on explicit-määre, jottei yksittäinen parametri vahingossakaan muunnu suoraan taulukkotyypiksi. Konstruktori varaa muistia, joten luokalla on syytä olla destruktori, joka hoitaa vapautuksen automaattisesti. Ja koska luokalla on erikseen tehty destruktori, sille täytyy - kuten yleensä - tehdä myös sekä kopioiva konstruktori että sijoitusoperaattori. Näin siis muistinhallinta saadaan hanskattua.
Jotta dynarrayn käyttö muistuttaisi taukkoa, luokka overloadaa []-taulukkoviittausoperaattorin. Operaattorista täytyy olla sekä const- että ei-const-versiot, jotta alkioita saadaan kyseltyä silloinkin kun käsissä on const-viite taulukkoon, ja jotta ei-const-taulukon alkioihin voi sijoittaa arvoja. Koska koko on asetettavissa mielivaltaisesti taulukon luonnin yhteydessä, luokalla on myös size-funktio, jolla taulukon kokoa voidaan kysellä.
Tokassa listauksessa on koodinpätkä, jossa ei ole paljon muuta järkeä kuin että se havainnollistaa kuitenkin juttuja, jotka dynarraylla onnistuvat ja eivät onnistu.
Toinen luokka on dynarray2, joka on periaatteessa hyvinkin sama, mutta kaksiulotteisena. Oudompi juttu on dynarray2:n sisällä oleva private-määritelty luokka slice1. C++:ssahan ei ole oikeita kaksi- tai moniulotteisia taulukoita, vaan moniulotteisempi tapaus on aina taulukko taulukoita. Jos esmes taulukko on määritelty "int a[3][4];", niin "a[2]" palauttaakin oikeastaan int[4]-otuksen, joka on käytännössä osoitin emotaulukon kolmannen rivin ekaan alkioon. Kyllä dynarray2:nkin []-operaattori voisi osoittimen palauttaa, mutta slice1-apuluokkaa käyttämällä hommaan saadaan mukaan vähintäänkin debug-aikainen indeksitarkastus: dynarray2:n []-operaattori tarkistaa, ettei osoitella enempää rivejä kuin mitä taulukossa on, ja slice1:n []-operaattori puolestaan, ettei osoitella rivin lopun ohi.
Kolmas listaus demoaa asioita, mitä dynarray2:lla voi ja ei voi tehdä.
Template-luokkien funktioiden toteutukset ovat samaisessa dynarray.hpp-tiedostossa. Template-määrittelyt tietysti vähän mutkistavat asioita, mutta eipä noissa aivan mahdottomuuksia pitäisi olla. Ja vaikka olisikin, luulisi luokkien käytön silti olevan ihan simppeliä, vaikkei konepellin alle katsoisikaan.
Visual Studio 2005:llä kääntelin ja testasin, gnu-kääntäjää ei nyt juuri sattunut olemaan käsillä. Mitään antiikkikääntäjien yhteensopivuutta en edes miettinyt.
Kaikenlaista tuunaamista ja puunaamista tuli kyllä oitis mieleen, mutta nyt nuo luokat hoitavat pari perusjuttua eivätkä yritä tehdä kaikkea mahdollista. Jos jollekulle tulee mieleen ryhtyä noita viilailemaan, kannattaa ottaa huomioon, että luokat olisivat edelleenkin exception safe, niissä olisi edelleenkin debug assert-tarkastukset, ja että onko esmes kaksiulotteinen taulukko lopulta se oikea tietorakenne ja ettei sitten päätyisi keksimään C++:n standardi-containereita (vector mukaan lukien) uudelleen.
dynarray.hpp
#ifndef KOO_DYNARRAY_HPP
#define KOO_DYNARRAY_HPP
#include <cassert>
#include <cstdlib>
template<typename T> class dynarray
{
T *arr;
std::size_t dim;
public:
explicit dynarray(std::size_t d);
dynarray(dynarray const &o);
dynarray &operator=(dynarray const &o);
~dynarray();
T &operator[](std::size_t i);
T const &operator[](std::size_t i) const;
std::size_t size() const;
};
template<typename T> class dynarray2
{
T *arr;
std::size_t dim0;
std::size_t dim1;
class slice1
{
T *arr;
std::size_t dim1;
public:
slice1(T *a, std::size_t d);
T &operator[](std::size_t i);
T const &operator[](std::size_t i) const;
};
public:
dynarray2(std::size_t d0, std::size_t d1);
dynarray2(dynarray2 const &o);
dynarray2 &operator=(dynarray2 const &o);
~dynarray2();
slice1 operator[](std::size_t i);
slice1 const operator[](std::size_t i) const;
std::size_t size0() const;
std::size_t size1() const;
};
////////////////////////////////////////////////////////////////////////
template<typename T> dynarray<T>::dynarray(std::size_t d)
: arr(new T[d]), dim(d)
{
}
template<typename T> dynarray<T>::dynarray(dynarray const &o)
: arr(new T[o.dim]), dim(o.dim)
{
for (std::size_t i = 0; i < dim; ++i) arr[i] = o.arr[i];
}
template<typename T> dynarray<T> &dynarray<T>::operator=(dynarray const &o)
{
assert(dim == o.dim);
for (std::size_t i = 0; i < dim; ++i) arr[i] = o.arr[i];
return *this;
}
template<typename T> dynarray<T>::~dynarray()
{
delete [] arr;
}
template<typename T> T &dynarray<T>::operator[](std::size_t i)
{
assert(i < dim);
return arr[i];
}
template<typename T> T const &dynarray<T>::operator[](std::size_t i) const
{
assert(i < dim);
return arr[i];
}
template<typename T> std::size_t dynarray<T>::size() const
{
return dim;
}
////////////////////////////////////////////////////////////////////////
template<typename T> dynarray2<T>::dynarray2(std::size_t d0, std::size_t d1)
: arr(new T[d0*d1]), dim0(d0), dim1(d1)
{
}
template<typename T> dynarray2<T>::dynarray2(dynarray2 const &o)
: arr(new T[o.dim0*o.dim1]), dim0(o.dim0), dim1(o.dim1)
{
std::size_t const dim = dim0*dim1;
for (std::size_t i = 0; i < dim; ++i) arr[i] = o.arr[i];
}
template<typename T> dynarray2<T> &dynarray2<T>::operator=(dynarray2 const &o)
{
assert(dim0 == o.dim0 && dim1 == o.dim1);
std::size_t const dim = dim0*dim1;
for (std::size_t i0 = 0; i0 < dim; i0 += dim1)
for (std::size_t i1 = 0; i1 < dim1; ++i1)
arr[i0+i1] = o.arr[i0+i1];
return *this;
}
template<typename T> dynarray2<T>::~dynarray2()
{
delete [] arr;
}
template<typename T> typename dynarray2<T>::slice1
dynarray2<T>::operator[](std::size_t i)
{
assert(i < dim0);
return slice1(&arr[i*dim1], dim1);
}
template<typename T> typename dynarray2<T>::slice1 const
dynarray2<T>::operator[](std::size_t i) const
{
assert(i < dim0);
return slice1(&arr[i*dim1], dim1);
}
template<typename T> std::size_t dynarray2<T>::size0() const
{
return dim0;
}
template<typename T> std::size_t dynarray2<T>::size1() const
{
return dim1;
}
template<typename T> dynarray2<T>::slice1::slice1(T *a, std::size_t d)
: arr(a), dim1(d)
{
}
template<typename T>
T &dynarray2<T>::slice1::operator[](std::size_t i)
{
assert(i < dim1);
return arr[i];
}
template<typename T>
T const &dynarray2<T>::slice1::operator[](std::size_t i) const
{
assert(i < dim1);
return arr[i];
}
////////////////////////////////////////////////////////////////////////
#endif#include "dynarray.hpp"
#include <cstring>
int main()
{
dynarray<int> a(10);
for (std::size_t i = 0; i < a.size(); ++i)
a[i] = static_cast<int>(i);
// dynarray<int> b(10) =
// { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }; // ERROR!
int const p[] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
dynarray<int> b(10);
for (std::size_t i = 0; i < b.size(); ++i) b[i] = p[i];
dynarray<int> c(b);
b = a;
// a[10] = 0; // ASSERT FAILED!
dynarray<char> d(10);
// std::strcpy(d, "foobar"); // ERROR!
std::strcpy(&d[0], "foobar");
}#include "dynarray.hpp"
#include <cstring>
int main()
{
dynarray2<int> a2(3, 10);
for (std::size_t i = 0; i < a2.size0(); ++i)
for (std::size_t j = 0; j < a2.size1(); ++j)
a2[i][j] = static_cast<int>(i*10+j);
// dynarray2<int> b2(3, 4) = // ERROR!
// { { 60, 61, 62, 63 }, { 70, 71, 72, 73 }, { 80, 81, 82, 83 } };
int const p2[][4] =
{ { 60, 61, 62, 63 }, { 70, 71, 72, 73 }, { 80, 81, 82, 83 } };
dynarray2<int> b2(3, 4);
for (std::size_t i = 0; i < b2.size0(); ++i)
for (std::size_t j = 0; j < b2.size1(); ++j)
b2[i][j] = p2[i][j];
dynarray2<int> c2(3, 4);
c2 = b2;
// a2[3][0] = 0; // ASSERT FAILED!
// a2[0][10] = 0; // ASSERT FAILED!
dynarray2<char> d2(10, 10);
// std::strcpy(d2[3], "foobar"); // ERROR!
std::strcpy(&d2[3][0], "foobar");
}Vaikuttaa kyllä tosi hyvälle. En nyt jaksa tuota itse ruveta käymään läpi, luotan siihen että on hyvin tehty ja toimiva. :)
using namespace std; ? on kuitenkin sen verran käytetty tässä...