Java ja C++ standardikirjastot
-merkkijonot, matemaattiset kirjastot, tietorakenteet ja tietovirrat
Timo Tuunanen



























Jyväskylän yliopisto Tietotekniikan laitos
Timo Tuunanen
LuK-tutkielma
Syksy 2001


Sisältö

1 Johdanto

Tämän tutkielman alkuperäisenä tarkoituksena oli selvittää kuinka helposti olemassaolevia standardin mukaisia C++-ohjelmia voidaan muuntaa Java-ohjelmiksi ja päinvastoin. Kuitenkin heti tutkielman alkuvaiheessa kävi selväksi, että muuntaminen on erittäin vaikeata standardikirjastojen erilaisen laajuuden vuoksi.

Java tarjoaa huomattavasti laajemman valikoiman erilaisia kirjastoja ja luokkia. Esimerkiksi graafisia käyttöliittymiä ei pysty toteuttamaan ollenkaan C++:n standardikirjastoilla, kun taas Java tarjoaa kohtuullisen kattavan käyttöliittymäkirjaston jota hyväksikäyttäen tehdyt ohjelmat voidaan siirtää muuttamattomina käyttöjärjestelmästä toiseen.

Näinollen tutkielmassa lähdettiin vertailemaan standardikirjastojen niitä osia jotka ovat samankaltaisia. Yhteneväiset tarkasteluun valitut osat olivat: merkkijonot, matemaattiset kirjastot, tietovarastot ja tietovirrat.

Tutkielmassa tarkasteltiin kirjastojen tarjoamia palveluja ohjelmoijan näkökulmasta toteutusaikana; kuinka samat asiat toteutetaan C++:n ja Javan standardikirjastojen avulla. Tutkielmassa pyrittiin vertailemaan kuinka kattavasti ja monipuolisesti kielet tarjoavat palveluja ohjelmoijalle samankaltaisilta osiltaan ja kuinka helppo näitä palveluja on käyttää hyväksi. Tarkoituksena ei ollut laittaa kieliä paremmuusjärjestykseen vaan pikemminkin tehdä tutkielma siitä mitä kielien peruskirjastoilla voidaan tehdä ja kuinka näitä peruskirjastoja käytännössä käytetään.

2 C++ standardikirjastot

C++ standardikirjasto määritellään C++ standardissa[3], joka valmistui vuonna 1998.

Kirjasto sisältää huomattavan määrän erilaisia funktioita ja luokkia helpottamaan ohjelmoija työtä. Koska C++ perustuu monilta osin C-kieleen eivät kaikki standardikirjaston tarjoamat komponentit ole luokkia. Mukana on myös tavallisia aliohjelmia (kuten printf()) jotka periytyvät C kielen standardikirjastoon.

Kirjaston osat

Stroustrup [1, luku 16] jaottelee standardikirjaston osat seuraavasti:
Tietovarastot (Containers)
sisältää yleisimmät tietorakenteet, kuten taulukot, listat, jonot ja binääripuut.
Yleiset työkalut (General utilities)
sisältää mm. muistinvarausfunktiot tietovarastoille ja C-tyyliset päivämäärä ja aikakirjastot.
Iteraattorit
jotka mahdollistavat tietorakenteiden alkioiden operoinnin. (läpikäynti, lisäys, poisto)
Algoritmit
sisältää geneeriset algoritmit joita käytetään stl:n tietovarastojen käsittelyyn ja C:stä periytyvät haku ja järjestämisalgoritmit.
Virheenkäsittelyn apuvälineet (Diagnostics)
sisältää mm. standardipoikkeukset, C-kielen virheenkäsittelykirjastot ja assert -makron.
Merkkijonot
sisältää sekä vanhat C-merkkijonot että uudet string luokkaan perustuvat merkkijonokirjastot.
I/O kirjastot
sisältää tietovirrat ja C:stä perityvät tulostus ja lukufunktiot.
Lokalisointi (Localization)
sisältää mm. apuvälineet ohjelmien kirjoittamiseen siten, että ne toimivat eri maissa; päivämäärien tulostaminen eri tavoin eri maissa, valuutan merkintä eri tavoin jne.
Kielen tukikirjastot (Language support)
sisältää mm. numeerisia rajoja, kuten suurimmat mahdolliset muuttujien koot, muistinvarauksen, poikkeustenkäsittelykirjastot ja singnaalikäsittelykirjastot.
Matematiikkakirjastot (Numerics)
sisältää mm. kirjastot normaaleille matemaattisille laskutoimituksille, kompleksiluvuille ja satunnaislukufunktiot.

3 Javan luokkakirjastot

Java ei ole varsinaisesti standardoitu ohjelmointikieli, vaan sen kehittämisestä vastaa Sun Microsystems. Huhtikuussa 1999 Sun ehdotti Javan standardoimista, mutta veti joulukuussa 1999 hakemuksensa takaisin[8]. Standardi Javasta puhuttaessa tarkoitetaankin juuri Sunin erilaisia Java versioita. Javasta on olemassa kolme erilaista versiota. Micro Edition on suppeahko versio jota käytetään laitteissa joissa on vähän muistia. (esim PDA-laitteet). Standard Edition on ``normaali'' versio Javasta ja tämä tutkielma perustuu sen tarjoamiin luokkakirjastoihin. Kolmas versio Enterprise Edition on laajin Java-versio. Eri versioiden eroista saa parhaan kuvan katsomalla niiden api-dokumentaatiota, jotka saa haettua internetistä Sunin sivuilta: http://java.sun.com

Javan paketit

Javan luokkakirjastojen luokat on jaettu eri paketteihin. Näitä paketteja on eri määrä riippuen käytettävästä Java versiosta. Java Standard Edition sisältää seuraavat paketit1[7]:
java.applet
Tarjoaa applettien kirjoittamiseen vaadittavat luokat.
java.awt
Graafisten käyttöliittymien luokkakirjasto AWT2.
java.beans
Java beanien kirjoittamiseen tarvittavat luokat.
java.io
Tietovirtaluokat, serialisointiin3 tarkoitetut luokat sekä tiedostojärjestelmien käsittelyyn tarkoitetut luokat.
java.lang
Luokat jotka ovat Javan kielen sisäisiä luokkia, kuten Object (kaikkien luokkien yliluokka), Throwable (kaikkien poikkeusten ja virheiden yliluokka), String, Thread ja wrapperiluokat Javan perustietotyypeille. Ilman java.lang pakettia tai jotain sen luokkaa Javan ajoympäristö ei käynnisty. Paketti sisältää myös Math luokan jolla voi suorittaa yleisimmät matemaattiset funktiot.
java.math
Suurten lukujen laskemiseen tarkoitetut luokat BigInteger ja BigDecimal.
java.net
Tietoverkoissa toimivien ohjelmistojen kirjoittamiseen käytettävät luokat kuten Socket ja URL.
java.rmi
RMI:n4 avulla hajautettujen Java ohjelmien tekemiseen tarkoitetut luokat.
java.security
Luokat security frameworkia varten. Sisältää myös mm. kryprografiset avainparit ja turvallisen satunnaislukugeneraattorin.
java.sql
JDBC kirjasto jonka avulla voidaan tehdä tietokantaoperaatioita.
java.text
Tarjoaa luokat tekstin, päivämäärien, numeroiden ja viestien ohjemoimiseen maarippumattomasti.
java.util
Sisältää mm. Javan tietorakenteet, päivämääriä ja aikoja käsittelevät luokat, kansainvälistämiseen tarvittavat luokat, perusluokat Javan tapahtumankäsittelyä varten ja satunnaislukugeneraattorin.
javax
Javax paketin alla on lukuisia muita paketteja jotka sisältävät luokkia mm. hajautettujen ohjelmistojen luontia varten, awt:tä laajempi graafinen luokkakirjasto Swing, ohjelmistoon liitettävien äänien ohjelmointia helpottavia luokkia jne...
org.omg
Sisältää useita muita paketteja joilla voidaan luoda hajautettuja ohjelmistoja käyttäen CORBA-standardia5.

4 Merkkijonot ja matemaattiset kirjastot

C++ ja Java ohjelmointikieliä ei ole alunperin erityisesti suunniteltu merkkijonojen käsittelyyn tai matemaattiseen laskentaan. Merkkijonojen käsittelyyn suositellaan usein Perliä ja matemaattiseen laskentaan Fortrania[9]. Sekä merkkijonon käsittelyä että matemaattisia funktioita kuitenkin tarvitaan lähes jokaisessa ohjelmassa. Matemaattisia funktioita ja merkkijonoja tarvitaan muiden ongelmien ratkaisun apuvälineinä: grafiikkarutiineissa, simuloinnissa, kaupallishallinnon sovelluksissa...

Merkkijonot

C++:n ja javan string-luokilla voidaan tehdä suunnilleen samat operaation hyvin samankaltaisilla menetelmillä. C++:n etuna (monen mielestä myös haittana) on se, että kieli pitää sisällään myös vanhat C-kielen merkkijonokirjastot. C:n aliohjelmakirjastoilla voidaan tehdä monia asioita helpommin kuin varsinaisilla string-kirjaston metodeilla. Esimerkiksi muotoiltu tulostus on huomattavasti näppärämpää C-kielen funktoiden avulla kuin käyttämällä tietovirtojen manipulointia. Toisaalta C-merkkijonotaulukot ovat hyvin virhealttiita ja näinollen kannattaa käyttää C++ merkkijonoja aina kun mahdollista. Javan tilanne ei muotoillun tulostuksen kannalta ole kuitenkaan välttämättä yhtään sen parempi.

Parhaimman kuvan merkkijonokirjastojen samankaltaisuudesta saa esimerkkien avulla. Ensimmäisessä esimerkissä esitellään merkkjonojen peruskäyttöä. Luodaan 2 merkkijonoa, liitetään ne yhteen uudeksi merkkijonoksi ja verrataan syntynyttä merkkjonoa neljänteen merkkijonoon. Huomioitavaa on, että merkkijonojen vertailu on ohjelmointikielissä erilaista. C++:ssa vertailuoperaattori == vertaa merkkijonojen sisällön samankaltaisuutta. Javassa vastaava operaattori vertaa viittaavatko kaksi eri olioviitettä samaan olioon ja varsinainen merkkijonojen sisällön vertailu tulee tehdä käyttäen equals() -metodia.

//C++
#include<string>
string first = "ABC";
string second = "abc";
string third = first + second;
bool same = ("ABCabc" == third);

//Java
String first = "ABC";
String second = "abc";
String third = first + second;
boolean same = "ABCabc".equals(third);

Jotta C++:n string-luokan saa käyttöönsä tulee se sisällyttää ohjelmaan käyttäen lausetta #include <string>. Javan String-luokka on esiteltynä paketissa java.lang jota ei tarvitse erikseen sisällyttää (import).

Javasta löytyy String-luokan lisäksi StringBuffer luokka jota kannattaa käyttää kun merkkijonoon aiotaan luomisen jälkeen lisätä merkkejä. String luokan merkkijonoa ei nimittäin voi muuttaa ja normaali muutosoperaatio itse asiassa luo aina uuden merkkijonon:

String a = "ABC";
a = a + "abc"; //Vastaa sisäisesti a = new String("ABCabc");
Kun taas StringBuffer muuttaa aidosti merkkijonoa:
StringBuffer a = "ABC";
a = a + "abc"; //Vastaa sisäisesti a.append("abc");
Näinollen StringBuffer on nopeampi käyttää kun merkkijonoon lisätään perään merkkejä. StringBufferia kannattaa siis käyttää tilanteissa joissa luetaan esimerkiksi tietoa useista lähteistä ja näistä halutaan koota yksi merkkijono.

Matemaattiset kirjastot

C++:n otsikkotiedosto (header) <cmath> esittelee yleisimmät matemaattiset funktiot. Javan matemaattiset funktiot löytyvät staattisesta luokasta Math joka löytyy paketista java.lang. Lisäksi Javan paketista java.math löytyvät luokat BigInteger ja BigDecimal.

Kummankin kielen kirjastoista löytyvät trigonometriset funktiot, lukujen pyöristämiseen tarkoitetut funktiot, logaritmiset funktiot, neliöjuuri sekä joitakin muita funktioita. C++ tarjoaa hieman suuremman valikoiman matemaattisia funktioita. Se sisältää mm. hyperboliset sinin, kosinin ja tangentin ja 10-kantaisen logaritmin joita Javassa ei ole.

//C++
#include <cmath>
...
double sin = sin(1);
double cos = cos(0);
double tan = tan(1);

double log = log(1); // e-kantainen logaritmi
double log10 = log10(100); //10-kantainen logaritmi

Samankaltaisuuksien lisäksi C++:n ja Javan matemaattisissa kirjastoissa on myös eroja. Ohjelmoijan kannalta selkein ero on virheenkäsittelyssä. C++:n matemaatiset kirjastot periytyvät C-kielestä ja tästä johtuen virheenkäsittely hoidetaan käyttämällä errno -kirjastoa:

//C++
#include <cmath>
#include <cerrno>
...
errno = 0; // asetetaan virhenumero virheettömään tilaan
// yritetään laskea nelijuurta negatiiviselle luvulle
double sqrtResult = sqrt(-1);

if( errno == EDOM ) {
  cerr << "Neliöjuurifunktiota sqrt() ei ole määritelty "
       << "negatiivisille luvuille" << endl;
}

Javassa virheiden käsittelyyn käytetään poikkeuksia:

//Java
try {
  int sqrtResult = Math.sqrt(-1)
}
catch (ArithmeticException ex) {
  ex.printStackTrace();
}
C++:n erikoisuutena ovat kompleksilukujen laskemiseen tarkoitetut luokat joiden ansiosta kompleksiluvut näyttävät ohjelmoijalle pitkälti tavallisilta reaaliluvuilta sekä matriisien laskemisen hoitava luokka.

Vaikka kummankin kielen matemaattisilla kirjastoilla voidaan toteuttaa yleisimmät matemaattiset operaatiot ne eivät välttämättä ole paras valinta varsinaisten matemaattisten ohjelmistojen toteuttamiseen. Tähän tarkoitukseen kannattaa valita esimerkiksi Fortran ohjelmointikieli mm. sen laajojen matemaattisten kirjastojen ansiosta. Javan etuna voidaan pitää BigInteger ja BigDecimal luokkien olemassaoloa. Koska desimaaliluvuilla laskeminen tarkasti ei ole tietokoneilla mahdollista6 joudutaan usein ongelmiin mm. lukujen pyöristysten kanssa. Tähän ongelmaan Javan BigDecimal antaa kohtuullisen ratkaisun. Desimaalilukujen laskennan epätarkkuus on niin yleinen ja hyvin tunnettu ongelma, että on oikeastaan aika erikoista, että C++:ssa ei kyseiseen ongelmaan ole standardissa mitään ratkaisua.

5 Tietovarastot (Containers)

Erilaiset tietovarastot ovat ohjelmoijan kannalta erittäin käytännöllisiä. C++ ja Java ohjelmointikielet sisältävät taulukon 1 tietorakenteet.

Tietorakenne C++-luokka Java-luokka
Taulukko vector Vector
Lista list LinkedList
Jono queue ei Javassa
Kummastakin päästä avoin jono deque ei Javassa
Prioriteettijono priority_queue ei Javassa
Pino stack Stack
Binääripuu (arvo) set TreeMap
Binääripuu (arvo) multiset ei Javassa
Binääripuu (avain/arvo) map TreeMap
Binääripuu (avain/arvo) multimap ei Javassa
Hajautustaulu (arvo) hash_map HashMap
Hajautustaulu (arvo) hash_multimap ei Javassa
Hajautustaulu (avain/arvo) hash_set HashSet
Hajautustaulu (avain/arvo) hash_multiset ei Javassa

Taulukko 1: Javan ja C++:n tietovarastoluokat

Kielien tietovarastojen toteutukset ovat monilta osin hyvin samankaltaisia. Tietorakenteisiin voidaan tallettaa minkä tyyppisiä alkioita tahansa ja tietovarastoluokkien tarjoamat metodit ovat lähes identtisiä. Eräs suurimmista eroista on siinä, että C++ kielessä tietovarastojen sisältämien alkioiden tyyppi määritellään tietovaraston luomisen yhteydessä. Esim.:

list<int> lista;
lista.push_back(23);
luo listan johon voidaan tallettaa kokonaislukutyyppisiä alkioita. Javassa tietorakenteisiin voidaan tallettaa mitä tahansa luokkia ilman, että niiden tarvitsee olla edes samaa tyyppiä. Javassa perustietotyyppejä ei voida talletta alkioiksi, vaan tulee käyttää perustietotyyppien luokkatoteutuksia:
LinkedList list = new LinkedList();
list.add(new Integer(12));
C++:n tietorakenteiden huonoimpana puolena pitäisin itse sitä, että aina kun tietorakenteeseen lisätään alkio, alkuperäisestä alkiosta tehdään kopio (olioiden kyseessä ollessä käytetään kopiointimuodostinta) joka lisätään tietorakenteeseen. Näinollen ohjelmassa tehdään usein turhaa muistin kopiointia. Useat ohjelmoijat kiertävät tätä ominaisuutta tallentamalla tietorakenteisiin osoittimia. Tämä kuitenkin sotii tietorakenteiden perusperiaatetta vastaan, jonka mukaan ohjelmoijan ei tarvitse huolehtia tietorakenteen alkioiden tuhoamisesta ennen varsinaisen tietorakenteen tuhoamista. Normaalitilanteessa tietorakenteet tuhoavat sisältämänsä alkiot, mutta jos tietorakenteeseen on tallennettu osoittimia, tuhotaan vain osoittimet ja niiden päässä olevat varsinaiset alkiot jäävät tuhoamatta. Ohjelmoijalle voisi tässä tilanteessa tulla mieleen tallentaa auto_ptr tyyppisiä osoittimia tietorakenteeseen, jotka tuhoutuessaan tuhoavat myös osoittamansa muuttujan/olion, mutta tämä on C++ kielessä estetty[2, 47] Yksi, ja ehkäpä paras, ratkaisu ongelmaan on periä oma luokka joka tuhoaa myös osoittimien päässä olevat oliot.

Javassa tietorakenteiden monimuotoisuus aiheuttaa usein ongelmia. Jokaiselle hiemankaan enemmän Javalla ohjelmoineelle on todennäköisesti tuttu ajonaikanen tyyppikonversiosta aiheutuva poikkeus ClassCastException, joka syntyy kun tietorakenteesta yritetään hakea väärän tyyppistä oliota. Tässä mielessä C++:n tapa määritellä tietovarastojen alkoiden tyyppi jo käännösaikana tuottaa luotettavampaa koodia.

Tarkempaa tietoa Javan tietorakenteista löytyy api-dokumentaatiosta[7] ja virallisista Javan luokkakirjastoreferensseistä [6], C++ tietorakenteet on kuvattu hyvin kirjan The C++ Programming Language[1] luvuissa 16 ja 17 sekä kirjan The Standard C++ library - A Tutorial and Reference[2] luvussa 6.

Dynaamiset taulukot

Yksinkertaisin ja usein käyttökelpoisin tietovarasto on taulukko. Sekä C++:ssa että Javassa taulukko määritellään vector luokassa. Vector on kummassakin kielessä dynaaminen taulukko, joten taulukon kasvattamisesta ohjelmoijan ei tarvitse itse huolehtia.

Taulukon hyvänä puolena on yksinkertaisuus, vakioaikainen alkion lisääminen taulukon loppuun poikkeuksia lukuunottamatta (katso alla) ja alkoiden suorasaanti. Taulukoista voidaan hakea alkioita suoraan indeksin avulla. Esimerkeissä luodaan tyhjä taulukko ja lisätään sinne kolme Person-oliota joista haetaan henkilön nimi ja tulostetaan sen jälkeen näytölle:

//C++
vector<Person> v;

Person p("Pekka"); Person k("Kalle"); Person j("Jussi");

v.push_back(p); v.push_back(k); v.push_back(j);

for (int i = 0; i < v.size(); i++) {
  cout << v[i].getName() << endl;
}
Toinen vaihtoehto alkioiden läpikäyntiin on for_each funktio jolle annetaan parametriksi viite tietovaraston alkuun ja loppuun sekä sen funktion nimi jonka halutaan toteuttavan jonkun operaation saadulle alkiolle:
#include <algorithm>
void print(Person &p) {
  cout << p.getName() << endl;
}

for_each(v.begin(), v.end(), print);
Tätä funktiota käyttämällä voidaan vector vaihtaa vaikkapa listaksi ilman että läpikäyntiin tarvitsee tehdä muutoksia.

Koska Javassa Vector luokan alkioina on aina Object tyyppisiä olioita, joista kaikki muut oliot periytyvät, joudutaan alkiolle tekemään tyyppikonversio.

//Java
Vector v = new Vector();
v.add(new Person("Pekka"));
v.add(new Person("Kalle"));
v.add(new Person("Jussi"));

for (int i = 0; i < v.size(); i++)
{
  // tehdään tyyppikonversio
  System.out.println( (Person)v.get(i).getName() );
}
Vaikka vector luokat hoitavat itse muistivarauksen ja taulukon kasvattamisen, voidaan tietorakenteiden toimintaa nopeuttaa usein huomattavasti varaamalla itse tilaa alkioille. Tilanvaraus tapahtuu C++:ssa käyttäen reserve() metodia ja Javassa käyttäen ensureCapacity() metodia. Metodit ovat varsin käyttökelpoisia tapauksissa, joissa tiedetään etukäteen suunnilleen kuinka monta alkiota ollaan lisäämässä tietorakenteeseen. Jos tilanvaraus jätetään luokan vastuulle, voi tapauksissa joissa alkiota lisätään suuri määrä, tapahtua turhaa alkioiden kopiointia taulukosta toiseen. Esimerkiksi Javan Vector luokka varaa oletusarvoisesti tilaa vain 10 alkiolle. Kun tietorakenteeseen lisätään alkioita luokka kasvattaa taulukon kapasiteettiä automaattisesti kaksinkertaiseksi sopivaksi katsomallaan hetkellä ja kopioi alkiot alkuperäisestä taulukosta uuteen taulukkoon. Näinollen esimerkiksi 10 000 alkion lisäämisen yhteydessä joudutaan tietorakenteen kokoa kasvattamaan 10 kertaa ja samalla kopioimaan aina alkiot pienemmästä taulukosta uuteen isompaan taulukkoon. Onneksi Javassa kopioidaan kuitenkin vain olioviitteitä jolloin kopiointioperaatio ei välttämättä ole erityisen raskas. C++:ssa tilanne saattaa kuitenkin olla huomattavasti huonompi. Eräässä HP-UX:n C++ kääntäjän toteutuksessa taulukon kokoa kasvatettiin sen täyttyessä aina 80 alkiolla ja tässä tapaukessa taulukon kasvattaminen ja alkioiden kopiointi jouduttiin suorittamaan 10 000 alkion lisäyksessä 125 kertaa!

Toisissa C++ -kääntäjätoteutuksissa taulukon kasvattaminen on kuitenkin optimoitu niin, että lisääminen on hyvinkin nopeaa. Esimerkkiohjelmassa (liite 1) luetaan tiedostosta 45424 merkkijonoa ja lisätään ne vectoriin tämän jälkeen poistetaan vectorista joka toinen alkio. C++ kääntäjänä toimi GNU C++ version 2.96 20000731. Ajoalustana toimi Red Hat Linux 7.1. Vertailuohjelmana toimi(liite 2) vastaava Javaohjelma joka ajettiin Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1-b24) Java HotSpot(TM) Client VM (build 1.3.1-b24, mixed mode) ympäristössä. Ajanmittaus tehtiin Linuxin time ohjelmalla ( time compare tai time java compare ) Vertailun tulokset näkyvät taulukosta 2.

C++ pelkkä lisäys lisäys+poisto Java pelkkä lisäys lisäys+poisto
0m0.260s 1m52.310s 0m0.230s 0m54.890s
0m0.250s 1m52.100s 0m0.240s 0m54.880s
0m0.230s 1m52.310s 0m0.250s 0m55.030s

Taulukko 2: Tehokkuusvertailu vectorin käytöstä

Tuloksista nähdään selvästi, että poistosta johtuva taulukon koon muuttaminen on hyvin raskas operaatio. Java selviytyi tehtävästä nopeammin todennäköisesti juuri siitä syystä, että sen ei tarvinnut missään vaiheessa kopioida itse alkioita taulukon koon muuttuessa, vaan pelkkiä viitteitä.

Listat

Toinen yleinen tietorakenne lista, on myös totetutettu kielissä hyvin samankaltaisesti. Listatoteutus on kummassakin luokassa kaksoislinkitetty7, joten listan läpikäynti onnistuu sekä alusta loppuun, että lopusta alkuun.

Kuten monien muidenkin tietorakenteiden, myös listojen läpikäynti on toteutettu kummassakin ohjelmointikielessä iteraattoreiden avulla. Tosin alkioita voidaan käydä läpi myös ilman iteraattorien apua. C++:ssa käytetään iterator-luokkaa jolle esittelyn yhteydessä määritetään minkä tyyppisiä alkioita sillä käsitellään:

//C++
list<string> strList;
...
list<string>::iterator iter = myList.begin();
Javassa listan käsittelyyn käytetään luokkaa ListIterator:
//Java
LinkedList list = new LinkedList();
...
// asetetaan listan indeksiin 0, eli alkuun
ListIterator iter = myList.listIterator( 0 );

Listarakenteiden käsittely on kohtuullisen helppoa ja samankaltaista:

//C++
list<string> l;

l.push_back("first"); l.push_back("second"); l.push_back("third");

// tulostetaan listan alkiot
copy(l.begin(), l.end(), ostream_iterator<string>(cout, " "));

// Poistetaan listasta toinen alkio
list<string>::iterator iter = l.begin();
iter++;
l.erase(iter);

// Java
LinkedList list = new LinkedList();

list.add("first"); list.add("second"); list.add("third");

// Käydään listan kaikki alkiot läpi
if (list.size() > 0) {
  ListIterator i2 = list.listIterator();

  while (i2.hasNext()) {
    String str = (String)i.next()
    // Täässä voidaan tehdä haluttu operaatio alkiolle
  }
}

// Poistetaan listasta alkio
int index = list.indexOf("second");
// palauttaa -1 jos alkiota ei löytynyt
if (index > 0 ) {
  list.remove(index);
}

Koska kaksisuuntainen linkitetty lista on kohtuullisen yksinkertainen toteuttaa, ei kummankaan ohjelmointikielen listatoteutus pääse loistamaan toista paremmilla ominaisuuksilla. Kummassakin kielessä listatoteutus on hyvin perinteinen ja siinä tarkoituksessa aivan toimiva.

Jonot ja pinot

Jono ja pinorakenteet ovat hieman taulukoita ja listoja vähemmän käytettyjä tietorakenteita. Tavallinen jono on tietorakenne, jonka lopuun voidaan lisätä uusia alkoita ja hakea rakenteen ensimmäinen alkio. Tällaista saantitapaa kutsutaan FIFOksi (first in first out). Pino taas on rakenne johon voidaan pinota alkiota päällekäin. Tässä rakenteessa viimeiseksi lisätty alkio on se joka voidaan myös rakenteesta hakea. Tällaista saanitapaa kutsutaan LIFOksi (last in first out).
Tietorakenne C++ Java
Jono queue ei Javassa
Kummastakin päästä avoin jono deque ei Javassa
Prioriteettijono priority_queue ei Javassa
Pino stack Stack

Taulukko 3: Jono ja pinoluokat

Jono ja pinorakenteiden luonteen vuoksi ne on helppo toteuttaa muiden tietorakenteiden avulla. Jonon toteuttamiseen kelpaa hyvin lista johon voidaan vakioajassa lisätä alkio listan loppuun ja hakea ensimmäinen alkio. Pinorakenteen toteuttamiseen kelpaavat sekä lista että taulukko joissa viimeisen alkion lisääminen, hakeminen ja poistaminen ovat vakioaikaisia operaatioita.

Jostain syystä Javassa ei ole erikseen totetettu jonorakenteita, vaan ohjemoija joutuu joko toteuttamaan ne itse tai käyttämään listoja jonon tavoin.

C++ jono- ja pinoluokat

queue
Jonoluokka joka käyttää käyttää sisäisenä rakenteenaan dequea.

deque
luokkaa käytetään C++:ssa sekä tavallisen jonon toteuttamiseen että itsenäisenä luokkana. Deque on hyvin samankaltainen taulukon kanssa, mutta se on avoin kummastakin päästä, joten lisääminen sekä alkuun, että loppuun on onnistuu vakioajassa.

priority_queue
Jonoluokka jossa jokaiselle alkiolle annetaan tärkeysluokka (prioriteetti) jonka perusteella alkio asetetaan jonoon.

stack
on C++:n pinoluokka joka luokka käyttää sisäisesti joko vectoria tai dequea. Ohjelmoija voi tehdä valinnan tietorakenteiden välillä.

Java jono- ja pinoluokat

Javassa ei ole määritelty erikseen luokkaa jonojen toteuttamiseen. Tämän vuoksi joudutaan käyttämään joko suoraan LinkedList-luokkaa tai tekemään toteutus itse. Tavallisen jonoluokan toteuttaminen tosin on triviaalia esimerkiksi tekemällä uusi pinoluokka, joka käyttää periytyy listaluokasta:

import java.util.LinkedList;

public class Queue extends LinkedList
{
    public Queue() {
        super();
    }

    public void push( Object o ) {
        super.add( o );
    }

    public Object front() {
        return super.getFirst();
    }

    public void pop() {
        super.removeFirst();
    }
}
Koska tavallinen jonoluokka on triviaalia toteuttaa ei sen puuttumiseta ole erityisesti haittaa. Sen sijaan prioriteettijonon toteutuksen soisi löytyvän myös Javasta. Pinoluokka Stack löytyy Javan stardardikirjastosta. Stack periytyy Vector -luokasta[7] ja käyttää näinollen sisäisenä rakenteenaan taulukkoa.

Kehittyneemmät tietorakenteet

Ohjelmoija tarvitsee usein tietorakenteita joihin alkiot voidaan lisätä nopeasti ja joista tarvittava alkio löytyy nopeasti. Listojen ja taulukoiden järjestäminen ja alkioiden järjestykseen laittaminen on kohtuullisen hidasta. Näinollen käytetään yleensä joitain muita tietorakenteita. Yleisimmät kehittyneemmät tietorakenteet ovat puurakenteet ja hajautustaulut.

Javan standardikirjasto sisältää kumpaakin menetelmää käyttäviä tietorakenteita, kun taas C++ standardi määrittelee vain puurakenteeseen perustuvat tietorakenteet. Tosin suurimmassa osassa C++:n kirjastototeutuksista löytyy myös hajautuslukuun perustuvat tietorakenneluokat.

Avaimen perusteella järjestetyt tietorakenteet

Avaimen perusteella järjestetyt tietorakenteet käyttävät järjestämisavaimena itse alkiota jos niitä voidaan verrata keskenään (esim. merkkijonot ja luvut). Jos alkioita ei voida verrata keskenään (esim. luokat), joudutaan käyttämään avain/arvo paria jossa avaimia pitää voida verrata keskenään ja niiden avulla alkio lisätään ja haetaan tietorakenteesta.

Tällaisia tietorakenteita löytyy sekä C++:sta että Javasta.

Tietorakenne C++-luokka Java-luokka
Binääripuu (arvo) set TreeSet
Binääripuu (arvo) multiset ei Javassa
Binääripuu (avain/arvo) map TreeMap
Binääripuu (avain/arvo) multimap ei Javassa

Taulukko 4: Avaimen perusteella järjestetyt tietorakenteet

Kuten kaikki C++:n järjestetyt tietorakenteet, set, multiset, map ja multimap -luokat käyttävät yleensä sisäisenä tietorakenteena tasapainotettua8 binääripuuta[2, 176]. C++ standardi ei määrää tätä, mutta käytännössä näin yleensä tehdään.

Myös Javasta löytyvät TreeSet ja TreeMap käyttävät sisäisenä rakenteena tasapainotettua binääripuuta[6, 298].

Suurin ero C++:n ja Javan puurakenteissa on se, että Javassa ei ole binääripuuluokkia, joissa voi olla kaksi eri alkiota samalla avaimen arvolla. Tällaiset rakenteet ovat kuitenkin käytössä C++:ssa (multiset ja multimap). Joissain tilanteissa ohjelmoija todella haluaisi lisätä puurakenteeseen kaksi eri alkiota samalla avaimen arvolla. Tällaisessa tilanteessa Javalla ohjelmoitaessa ollaan suurissa vaikeuksissa. Ohjelmoijan tulee luoda oma luokka joko perimällä alkuperäinen puuluokka tai luoda koostamalla oma luokka joka käyttää sisäisenä tietorakenteenaan puuluokkaa. Nämä operaatiot eivät kuitenkaan ole kovin helppoja toteuttaa ja vaikka tällaisen luokan pystyykin rakentamaan, tulee syntyneestä luokasta todennäköisesti alkuperäistä hitaampi.

Lisäksi C++ tarjoaa puiden läpikäyntiin iteraattorin sekä etu että takaperin kun taas Java antaa mahdollisuuden kulkea puuta pitkin vain etuperin. Kummastakin toteutuksesta puuttuu mahdollisuus kulkea puun alkiot läpi väli -tai jälkijärjestyksessä.

Hajautuslukuun perustuvat tietorakenteet

Toinen tietorakenteiden toteutuskeino, jossa sekä alkion lisäys että haku ovan nopeita operaatioita, on hajautuslukuun perustuvat tietorakenteet. Hajautuslukuun perustuvat rakenteet laskevat alkion perusteella hajautusluvun (kokonaisluku) jonka perusteella alkiot asetetaan hajautustauluun. Etuna puhtaaseen alkion perusteella järjestämiseen on esimerkiksi se, että jos avaimena on merkkjono on sen vertaaminen toiseen merkkijonoon hitaampaa kuin luvun vertaaminen toiseen. Koska hajautusfunktion laskema luku on kokonaisluku, on käytännöllistä käyttää alkioiden tallettamiseen taulukkoa koska alkio voidaan tallettaa hajautusluvun osoittamaan taulukon paikkaan. Tällöin alkio voidaan hakea ja lisätä vakioajassa9.

Javan standardikirjasto sisältää luokat HashMap ja HashSet.

C++ standardikirjasto ei määrittele hajautuslukutaulua. Alkuperäisessä STL-ehdotuksessa hajautuslukutaulua ei ollut mukana ja komitea tuli siihen tulokseen, että ehdotus sen mukaan ottamisesta standardiin tuli liian myöhään ja jätti sen standardiehdotuksen ulkopuolelle.[2, 221] Kuitenkin monet kirjastojen toteutukset tarjoavat neljä erilaista hajatuslukutauluimplementaatiota:

Tietorakenne C++-luokka Java-luokka
Hajautusrakenne (arvo) hash_map HashMap
Hajautusrakenne (arvo) hash_multimap ei Javassa
Hajautusrakenne (avain/arvo) hash_set HashSet
Hajautusrakenne (avain/arvo) hash_multiset ei Javassa

Taulukko 5: Hajautukseen perustuvat tietorakenteet

Koska C++ standardi ei määrittele hajautuslukutauluja, standardin mukaista esimerkkiä niiden käytöstä ei voida kirjoittaa. Ohjelmoijan tulee tarkastaa käyttämänsä kirjaston ohjeista kuinka ko. luokkia käytetään.

Javan hajautuslukutaulu (Hashtable) on hieman puurakennetta (TreeMap tai TreeSet) nopeampi, mutta koska hajautustaulun alkioita ei voida käydä suuruusjärjestyksessä läpi joudutaan usein käyttämään puurakenteita.

6 Tietovirrat ja levyoperaatiot

Tietovirrat mielletään usein apuvälineiksi tietojen kirjoittamseen ja lukemiseen tiedostoista sekä näytölle tulostamiseen ja näppäimistöltä lukemiseen. Lisätietoja [2] luku 13 Tämä on kuitenkin suppea näkemys tietovirroista. Esimerkiksi myös verkosta tulevan binääridatan lukemiseen voidaan käyttää tietovirtoja.

C++:n tietovirtaluokat ovat huomattavasti geneerisempiä ja monikäyttöisempiä kuin Javan tietovirtaluokat. Lukumäärältään niitä on kohtuullisen vähän. Javan luokat keskittyvät pienempien osakokonaisuuksien hallintaan. Tämä johtaa siihen, että Javassa tietovirtaluokkia on huomattavasti C++:aa enemmän.

Tietovirta C++-luokka Java-luokka
Lukeminen istream InputStream
Kirjoittaminen ostream OutputStream

Taulukko 6: Javan ja C++:n tietovirtaluokkien yliluokat

C++ tietovirrat

IOStream kirjasto. C++:n tärkeimmät tietovirtaluokat (stream classes) ovat:
istream
Määrittelee tietovirtojen lukuoperaatiot.
ostream
Määrittelee tietovirtojen kirjoitusoperaatiot.
Nämä ovat yliluokkia tietovirtaluokille jotka erikoistuvat näytöltä, tiedostoista tai verkosta tulevan datan lukemiseen tai kirjoittamiseen.

IOStream kirjastossa määritellään lisäksi useita globaaleja objekteja jotka ovat tyyppiä istream tai ostream. Nämä globaalit luokat vastaavat yleisiä I/O kanavia:

cin
Standardi lukukanava (input channel) käyttäjän tietojen lukemiseen. Yleensä liitetty näppäimistöön.
cout
Standardi tulostuskanava sovelluksen tulostuksiin. Yleensä tulostus näkyy näytöllä.
cerr
Standardi kanava virheviesteille. Yleensä virheet tulostuvat näytölle.
clog
Vastaava kuin edellinen mutta puskuroitu kanava virheviesteille.

Seuraava esimerkki lukee tiedostosta kaikki rivit ja tallentaa ne vectoriin. Toinen esimerkki kirjoittaa vectorin sisältämät merkkijonot toiseen tiedostoon:

ifstream inputFile( "./luku.txt" );

if (!inputFile) {
  // tiedoston avaus epäonnistui.
}

vector<string> v;
string s;
while ( !inputFile.eof() ) {
  getline(inputFile, s);
  v.push_back(s);
}

...

ofstream outPutFile("./kirjoitus.txt", ios::app );

if (!outPutFile) {
// tiedoston avaus epäonnistui.
}

// Kirjoitetaan merkkijonovektorissa olevat merkkijonot tiedostoon
// eri riveille.
copy(v.begin(), v.end(), ostream_iterator<string>(outPutFile, "\n"));

Java tietovirrat

Javan tietovirrat määritellään java.io -paketissa. Paketista löytyy lukuisa joukkko erilaisia luokkia tietovirtojen käsittelyyn. Kaikki tietovirtaluokat periytyvät luokista:
InputStream
Abstrakti yliluokka kaikille lukemiseen tarkoitetuille tietovirtaluokille.
OutputStream
Abstrakti yliluokka kaikille kirjoittamiseen tarkoitetuille tietovirtaluokille.

Javassa tiedostoista lukemiseen ja kirjoittamiseen tarvitaan useamman luokan yhteistyötä:

Vector v = new Vector();

try {
  File inputFile = new File("luku.txt");
  FileReader in = new FileReader(inputFile);
  BufferedReader inputData = new BufferedReader(in);
  String s;

  while ( (s = inputData.readLine()) != null) {
    v.add(s);
  }
}
catch (Exception e){
  System.err.println("File input error");
}

...

try {
  File outputFile = new File("./kirjoitus.txt");
  FileWriter out = new FileWriter(outputFile);
  BufferedWriter outputData = new BufferedWriter(out);
  PrintWriter p = new PrintWriter(outputData);

  for (int i = 0; i < v.size(); i++) {
    p.write( (String)v.get(i) + "\n" );
  }
}
catch (Exception e){
  System.err.println("File output error");
}

Javassa tietovirtaluokat on voivat usein käyttää hyväksi muita luokkia. Hyvä esimerkki tietovirtojen ja tietorakenteiden yhteiskäytöstä on Properties luokan käyttäminen konfiguraatiotiedostojen lukemiseen. Jos tiedoston sisältö on Properties luokan ymmärtämässä muodossa konfiguraatioalkioiden tiedot hakea hyvin helposti.

#config file
FIRST=firstValue
SECOND=secondValue

//Java
Properties p = new Properties();
try {
  p.load( new FileInputStream( "./config.cfg" ) );
}
catch (Exception ex) {
  ex.printStackTrace();
}

String str = p.getProperty("FIRST");
System.out.println( str ); // tulostaa firstValue

Javan tietovirtaluokkavalikoima on C++:n vastaavaa laajempi. Javasta löytyy tietovirtaluokat mm. pakattujen tiedostojen lukemista ja kirjoittamista varten. (ZipInputStream ja GZIPInputStream)

7 Yhteenveto

Javan ja C++:n standardikirjastoissa on loppujen lopuksi yllättävän vähän yhteneväisiä piirteitä. Näinollen voidaan sanoa, että jommalla kummalla kielellä toteutetun ohjelman muuntaminen toiseksi ei onnistu ilman suurta käsityötä. Näinollen myös standardikirjastojen vertaileminen on kohtuullisen vaikeata.

Java tarjoaa huomattavasti laajemman kokonaisuuden luokkia joiden avulla voidaan toteuttaa suurin osa ohjelmoijalle vastaan tulevista onglemista. Tässä suhteessa C++ on huonommassa asemassa. C++ ohjelmassa joudutaan usein käyttämään alustariippuvaisia ei standardeja kirjastofunktioita tai luokkia. Tällaisia sovelluksia ovat mm. kaikki graafisen käyttöliittymän omaavat sovellukset. Toisaalta C++:n ne osat jotka löytyvät myös Java kielestä, ovat useimmiten hieman laajemmin ja monipuolisemmin toteutettuja. Omana mielipiteenäni voisin jopa todeta, että Javassa kirjastojen ja luokkien määrällä pyritään korvaamaan laatua.

Tutkielmaa tehdessäni koin yllätyksekseni, että C++:n standardikirjastojen käytön oppiminen oli itselleni helpompaa kuin Javan kirjastojen oppiminen. C++:aa kun pidetään yleisesti hankalana kielenä. C++:n tapauksessa löysin useimmin sopivan luokan tai funktion, jolla onglemani ratkesi hyvinkin nopeasti. Javan kanssa olin hetkittäin ihmeissäni, kun en meinannut millään keksiä kuinka erilaisia luokkia yhdistellään, jotta haluttu lopputulos saataisiin aikaiseksi. Tämä korostui erityisesti tietovirtojen toteutuksen yhteydessä, jossa Java tuntui ensikertalaisesta vähintäänkin hankalalta ja yksinkertaisenkin operaation toteuttamiseen vaadittin usean luokan yhteistyötä (ks. Java tietovirrat).

Lähteet

1
Stroustrup Bjarne, The C++ Programming Language, Addison Wesley, USA, 1997

2
Josuttis Nicolai M., The C++ Standard Library, Addison Wesley, USA, 2000

3
ISO, Information Technology - Programming Languages - C++ ISO/IEC 14882-1998, ISO/IEC, 1998

4
Chan Patrick, Lee Rosanna, Kramer Douglas, The Java Class Libraries Second Edition, Volume 1, Addison Wesley, USA, 1998

5
Chan Patrick, Lee Rosanna, Kramer Douglas, The Java Class Libraries Second Edition, Volume 2, Addison Wesley, USA, 1998

6
Chan Patrick, Lee Rosanna, Kramer Douglas, The Java Class Libraries Second Edition, Volume 1, Supplement for the Java 2 Platform Standard Edition, v1.2, Addison Wesley, USA, 1999

7
Sun Microsystems, Java 2 Platform Standard Edition v1.3 API documentation

8
Sun Microsystems, JavaTechnology Standardization, saatavilla WWW-muodossa http://java.sun.com/aboutJava/standardization/, 10.1.2001

9
Mösli Bernd, A Comparison of C++, FORTRAN 90 and Oberon-2 for Scientific Programming, saatavilla WWW-muodossa http://www.arithmetica.ch/Oberon/CFORTRANOberon.nhtml, 9.9.2001

10
Sun Microsystems, SUN MICROSYSTEMS WITHDRAWS JAVATM 2 PLATFORM SUBMISSION FROM ECMA, saatavilla WWW-muodossa http://java.sun.com/pr/1999/12/pr991207-08.html, 10.1.2001

Liite 1

//Tällä ohjelmalla luetaan tiedostosta merkkijonoja vectoriin
//jonka jälkeen vectorista poistetaan joka toinen alkio
//Timo Tuunanen 9.9.2001
#include <string>
#include <vector>
#include <fstream>
#include <iostream>

using std::string;
using std::vector;

int main(void)
{
  // luodaan luokka jolla avataan tietovirta tiedostoon
  ifstream inputFile("/usr/share/dict/words");

  if (!inputFile) {
    cout << "Tiedoston avaaminen epäonnistui" << endl;
    return 1;
  }

  //luodaan vektori jonne alkiot talletetaan
  vector<string> v;
  string s;

  //luetaan tiedostoa rivi kerrallaan
  while ( !inputFile.eof() ) {
    getline(inputFile, s);
    v.push_back(s);
  }

  cout << v.size() << endl;

  // Tästä kommentoituna kun ajettiin pelkkää lisäystestiä
  vector<string>::iterator iter;
  bool remove = false;

  // käydään taulukkoa läpi ja poistetaan joka toinen alkio
  for (iter = v.begin(); iter != v.end(); iter++) {
    if (remove) {
      v.erase(iter);
      // Kun iteraattorin osoittama alkio poistetaan siirtyy
      // iteraattori osoittamaan seuraavaa alkiota. Jotta
      // seuraavan alkion yli ei hypättäisi siirretään
      // iteraattoria yksi alkio taaksepäin
      iter--;
    }
    remove = !remove;
  }
  // tähän saakka kommentit lisäystestissä

  cout << v.size() << endl;
  return 0;
}

Liite 2

//Tällä ohjelmalla luetaan tiedostosta merkkijonoja vectoriin
//jonka jälkeen vectorista poistetaan joka toinen alkio
//Timo Tuunanen 9.9.2001
import java.io.*;
import java.util.*;

class compare
{
  public static void main(String args []) {
    compare c = new compare();
  }

  public compare()
  {
    Vector v = new Vector();

    try {
      // luodaan luokat joiden avulla saadaan tietovirta
      // tiedostoon
      File inputFile = new File("/usr/share/dict/words");
      FileReader in = new FileReader(inputFile);
      BufferedReader inputData = new BufferedReader(in);
      String s;

      //luetaan tiedostoa rivi kerrallaan
      while ( (s = inputData.readLine()) != null) {
        v.add(s);
      }
      System.out.println(v.size());
    }
    catch (Exception e){
      System.err.println("File input error");
    }

    // Tästä kommentoituna kun ajettiin pelkkää lisäystestiä
    boolean remove = false;

    // käydään taulukkoa läpi ja poistetaan joka toinen alkio
    Enumeration e = v.elements();
    while (e.hasMoreElements()) {
      if (remove) {
        v.remove(e.nextElement());
      }
      remove = !remove;
    }
    // tähän saakka kommentit lisäystestissä

    System.out.println(v.size());
  }
}

About this document ...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.47)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html LuK.tex -split 0

The translation was initiated by Timo on 2001-09-14


Footnotes

... paketit1
Listassa on vain pakettihierarkian ylin paketti. Tässä esitetyt paketit sisätävät useita alipaketteja
... AWT2
Abstract window toolkit on Javan graafinen peruskirjasto
... serialisointiin3
Serialisoituva (serializable) luokka on luokka joka voidaan muuttaa tavukoodiksi ja takaisin ajettavaksi luokaksi. Luokan jäsenmuuttujien tila pysyy samana muutoksesta huolimatta.
... RMI:n4
Remote method invocation (RMI) on Javassa oleva protokolla hajautustettujen ohjelmistojen tekemiseen.
... CORBA-standardia5
Common Object Request Broker Architechture (CORBA) on Object Management Groupin (OMG) standardisoima tapa tehdä hajautettuja ohjelmistoja
... mahdollista6
Lisätietoja esim. http://www.uta.fi/jm58660/jutut/ohjelmointi/liukuluku/laskee_vaarin.html
... kaksoislinkitetty7
C++ standardi ei pakota toteuttamaan listaa kaksoislinkitettynä, mutta käytännössä näin yleensä tehdään.[1, 470]
... tasapainotettua8
Itse asiassa toteutukseen käytetään yleensä puna-mustia puita.
... vakioajassa9
Koska hajautusluvun laskemisessa tapahtuu usein niinsanottuja yhteentörmäysiä, ts. kahdesta eri avaimesta muodosutuu hajautusfunktiossa sama hajautusluku, ei hakeminen ja lisääminen onnistu aivan vakioajassa

Timo 2001-09-14