- TituCPP 10. luento 13.12.
- Materiaali
- Esimerkit
- STL - Standard Template Library
- kattava esimerkki geneerisyyden soveltamisesta
- referenssejä
- säiliöt (vector, set, map, ...)
- huom. algoritmien kompleksisuudet eri säiliöluokilla vaihtelevat (esim. lista vs vector)
- vaatimuksia säilöitä käyttäville olioille:
- kopionmuodostin ja sijoitusoperaattori
- assosiatiivisilla säiliöillä sekä avaimille että arvoille - lisäksi avainten tulee olla järjestettävissä
- => viitteitä (sijoitus ei muuta viitettä toiseen olioon) tai auto_ptr:ää (kopiointi siirtää olion omistuksen) ei voi käyttää stl-säiliöihin
- sarjat
- vector ("dynaaminen taulukko")
- nopea käsittely indeksioperaattorilla []
- nopea lisäys ja poisto loppuun (push_back ja pop_back)
- deque (jono)
- molempiin päihin tehdyt lisäykset (push_front, push_back) ja poistot (pop_front, pop_back) vakioaikaisia
- list (linkitetty lista)
- Dynaaminen rakenne: lisääminen ja poisto vakioaikaista (jos tiedetään lisäys/poistopaikka), haun kompleksisuus lineaarinen
- ei indeksointioperaattoria (läpikäynti iteraattoreilla)
- Indeksointi tehotonta (lineaarinen kompleksisuus, vrt. taulukko)
- Perusmalli: alkio sisältää viitteen seuraavaan ja edelliseen
- assosiatiiviset säiliöt
- alkioiden lisäysjärjestyksellä ei merkitystä, käsittely avainolioilla (map-luokissa avain viittaa lisäksi
erillisiin arvo-olioihin, set säilöö vain avaimia)
- lisäyksellä, poistolla ja haulla logaritminen kompleksisuus
- koko tietorakenteen läpikäynti iteraattoreilla
- set - joukko
- Ei salli alkioiden (avainten) moninkertaisia esiintymiä
- Voidaan toteuttaa esim. hajautustauluna tai binääripuuna
- multiset - "laukku" (bag), voi sisältää saman arvon moneen kertaan (lukumäärä kysyttävissä count-metodilla)
- map - assosiaatiotaulu, hakemisto (toteutus esim. hajautustauluna tai binaaripuuna)
- (avain,arvo)-pareja, avain on yksilöllinen
- Avaimet varastoidaan joukkoon, kustakin avaimesta linkki arvoon
- template-parametreina annetaan avaimen ja arvon tyypit
- avaimella tulee olla järjestysoperaattori
- multimap - vrt. multiset
- ks. rakenteet.pdf
- [ http://www.jyu.fi/static/titu/cppolio/materiaali/rakenteet.pdf ]
- säiliösovittimet
- rajoitteita/muuntimia säiliön rajapinnoille "perinteisiä" tietorakenteita varten - sisäinen toteutusrakenne on vaihdettavissa
- stack - pino (yleensä toteutettu dequella) - push lisää alkion pinon päälle ja pop poistaa sen
- queue - jono (yleensä rajoitettu versio dequesta - push lisää alkion jonon loppuun ja pop poistaa alusta)
- priority_queue - prioriteettijono (yleensä vektori) - alkioiden poisto suuruusjärjestyksessä
- iteraattorit
- kohti iteraattoreita: Kerhon eka ja seuraava
- [ http://www.mit.jyu.fi/vesal/kurssit/cpp/kerho/jako.15/kerho.h ]
- ongelmia
- läpikäynnin tilan kytkeminen rakenteeseen eka ja seuraava eivät voi olla const-metodeja
- tietorakenteen läpikäynti samanaikaisesti moneen kertaan
- monesti tietorakennetta käsittelevissä silmukoissa ei olla kiinnostuneita yksittäisistä indekseistä, vaan siitä, että koko tietorakenne tulee käsiteltyä
- ratkaisu: uusi luokka, johon kapseloidaan vain läpikäyntilogiikka
- iteraattorit jaettu niiden ilmaisuvoiman ja käyttötarkoituksen mukaisiin luokkiin
- input iterator - voin luku ja seuraava
- output iterator - vain kirjoitus ja seuraava
- forward iterator - luku, kirjoitus ja seuraava
- bidirectional iterator - kaksisuuntainen
- random access iterator - []-operaattori
- iteraattoreita voi käyttää samaan tapaan kuin osoittimia c-taulukoilla (iteraattorin tyypistä riippuen kuormitetut *, ->, ++ ja -- -operaattorit, hajasaanti-iteraattorilla myös [])
- standardisäiliöihin määritelty valmiiksi iteraattoriluokat (esim vector<int>::iterator) ja metodit begin() ja end(), jotka palauttavat iteraattorin ensimmäiseen alkioon ja paikkaan viimeisen alkion ohi
- Huom. osoittimien tapaan iteraattori voi muuttua kelvottomaksi iterattorin viittaamaa tietorakennetta muutettaessa
- iteraattoriluokkia on mahdollista määritellä itsekin, mutta tämä on harvoin tarpeen (ellei haluta tehdä alusta alkaen mahdollisimman tehokasta ja stl-vakioluokista poikkeavaa omaa tietorakennetta tai rakennetta)
- iteraattorisovittimet (käyttäytyminen poikkeaa tavallisista iteraattoreista)
- käänteisiteraattorit (rbegin, rend -metodit) - läpikäynti käänteisessä järjestlyksessä
- lisääjät (inserter) - kirjoittaminen lisää paikkaan uuden alkion, ei muuta
- virtaiteraattorit (esim. ostream_iterator(cout)) - lukevat ja kirjoittavat tietovirtoihin
- c++ reference, stl algorithms
- [ http://www.cplusplus.com/reference/algorithm/ ]
- geneeriset algoritmit (haku, järjestäminen, ...)
- erillään säiliöistä, koska voivat käyttää mitä tahansa niistä (ja tiettyjen algoritmien osalta myös tavallisia taulukoita, esim. sort) tai itse määriteltyjä uusia tietorakenteita
- algoritmeja käsitellään iteraattorien avulla
- iteraattorilla voi määrätä käsittelyvälin (yleensä begin() ja end())
- sama algoritmi voi toimia eri säiliöillä (tai vaikka itse määritellyillä - sekä säiliön että iteraattorin osalta), kunhan iteraattori on saatavilla
- iteraattorisovittimien avulla voi vaikuttaa algoritmin toimintaan (esim. find ja käänteisiteraattori)
- algoritmeja
- copy
- find
- sort
- merge
- yhdistää välien alkiot ja kopioi ne suuruusjärjestyksessä (voidaan käyttää esim. osana lomituslajittelua)
- for_each
- kutsuu annettua funktiota läpikäytävän rakenteen alkioilla
- partition
- järjestää alkiot annetun ehdon mukaan niin, että ensin tulevat alkiot, joilla ehtofunktio palauttaa ture
- funktio-oliot
- Funktio(naalisesta) ohjelmoinnista yleisesti
- Lisätietoa
- John Hughes: Why functional programming matters (runsaasti viitattu yleisartikkeli)
- Jared Jackson: Use recursion effectively in XSL (xslt-spesifinen, rekursioasiaa)
- olion sijaan ohjelman perusyksikkö on (matemaattinen) funktio
- deklaratiivista ohjelmointia (imperatiivisen sijaan) - pyritään kuvaamaan ongelma ratkaisuaskeleiden sijaan
- ohjelma on funktio - peräkkäisyyden käsitettä ei yleensä tunneta - esim. silmukat korvattu rekursiivisilla kutsuilla
- Rekursion käyttö pienentää ohjelmakokoa, mutta on eräissä tapauksissa silmukkaa tehottomampi
- Lisäksi imperatiiviseen tyyliin tottuneelle rekursiivinen ratkaisu saattaa tuntua aluksi hankalalta
- Funktiokieliä: Haskell, Scheme, osittain myös LISP ja XSLT...
- Funktiokielet ovat yleensä sivuvaikutuksettomia: muuttujalle annettua arvoa ei voi muuttaa
- Mahdollistaa helpommin automaattisen koodin analysoinnin ja mm. oikeaksi todistamisen
- Lisätietoa esim. kurssilla Funktio-ohjelmointi
- [ http://www.mit.jyu.fi/antkaij/opetus/fo/ ]
- jo c-kielessä funktio-osoittimet: toiminnallisuuden vaihto "lennossa" osana funktion suoritusta (esim. qsort)
- keino käsitellä ohjelman _toimintaa_ kuten tietorakennetta
- Perinteinen käyttötarkoitus: graafiset tai menuohjatut käyttöliittymät
- Liitetään menukohtaan metodi (tapahtumankäsittelijä), jota kutsutaan, kun menukohta valitaan
- c++:ssa lisäksi metodiosoittimet - kuten funktio-osoittimet, mutta kohteena on tietyn luokan metodi
- stl-tapa: funktio-oliot
- C++:ssa mahdollista kuormittaa ()-operaattori (voi sisältää parametreja), jolloin oliota voidaan kutsua kuin funktiota - lisäksi C++:n templatet muodostavat oman funktionaalisen kielensä C++:n sisään
- Oliota, jota voidaan kutsua kuten funktiota, kutsutaan joskus myös funktoriksi (funktiokielissa lähellä oleva käsite: sulkeuma (closure))
- Vaihtoehtoinen (+"oliopohjainen") tapa (Javassa pakollinen) rajapintaluokilla, joissa määritellään funktiotyyppi, jota halutaan kutsua - algoritmille annetaan rajapintaluokasta peritty olio
- (huom. tässä tapauksessa rajapinnan tarkoitus poikkeaa loogisesti aiemmin käsitellystä moniperinnän välttämisestä koostamisella)
- Rajapinnat tai funktio-osoittimet tukevat oliosuunnittelua - esim. erilaisten kenttien validaattorioliot
- Esim. määritellään yleinen validaattorirajapinta, josta peritään luokkia esim. henkilötunnuksen tai päivämäärän tarkistamista varten
- stl:n valmiit funktio-oliot
- perusoperaattoreina funktoreina: plus, minus, equal_to, less jne
- bind:kiinteän parametrin kiinnittäminen 2-parametriseen funktio-olioon
- metaohjelmoinnista
- esim. kääntäjät, koodigeneraattorit, itseään muokkaavat ohjelmat
- yksinkertaisimmillaan tilanteessa, jos ohjelma pystyy tutkimaan omaa rakennettaan (javan reflection, esim. "nykyisen" luokan metodien ja attribuuttien haku tai luokkahierarkian tutkiminen)
- c++:ssa huomattavasti rajoitetumpaa - esim. typeid, dynamic_cast, sizeof
- templatet mahdollistavat koodin _käännösaikaisen_ tutkimisen => "template-metaohjelmointi"
- esimerkkejä
- apuluokan tyyppien päättely
- "vector<int>-luokalla täytyy olla iteraattori vector::iterator<int> ja vektorin tietyn alkion palauttavan funktion paluutyypin on oltava int"
- traits - sisäluokan valinta template-parametrilla
- intkorotus -erikoistaminen
- vrt. soveltaminen operaattoriesimerkissä
- numeric_limits
- perustyyppien raja-arvot, korvaa climits ja cfloat-otsikkotiedostoissa olevat vakiot
- mahdollistaa saman funktion käytön eri tyyppien max-arvon hakuun (aiemmin jokaisella tyypillä piti olla omannimisensä vakio)
- itse asiassa template-metaohjelmointi on oik. oma funktiokielensä c++:n sisällä
- esim IF-template: yhtenä tyyppiparametrina boolean-arvo, toisena ehdon "tulostyypit", erikoistumat true- ja false-arvoille
- myös muiden kontrollirakenteiden toteuttaminen mahdollista
- sopivan algoritmin valinta käännösaikana (template-erikoistumat , vector<bool> vs. tavallinen vector)
- esim. iteraattorin läpikäyntifunktio iteraattorin kategorian mukaan
- huom. vastaava olisi mahdollista tehdä myös dynamic_castilla ja switch/casella (+tässä tapauksessa ehkä jopa esimerkkiä ymmärrettävämmin), mutta tällöin tarkistukset tehtäisiin ajonaikaisesti => hitaampaa
- jos metaohjelmointi tuntuu hankalalta, ei kannata huolestua. =) kuitenkin stl-tietorakenteiden, iteraattoreiden ja stl-algoritmien käyttö on syytä hallita
- Aiheesta syvällisemmin mm. Advanced C++ Lessons, luku 6: template metaprogramming
- [ http://aszt.inf.elte.hu/~gsd/halado_cpp/ ]
- varaajat (allocator)
- esim. new-operaattorin uudelleenmäärittely
- ei käsitellä tällä kurssilla
- Kerho-ohjelman loppukehitys
- Oikeellisuustarkistukset
- Oikeellisuustarkistukset välttämättömiä aina, kun loppukäyttäjä syöttää manuaalisesti tietoja!
- Vaihtoehtoja
- Omat tarkistusfunktiot kutakin kenttää varten (esim. suoraan kysy_tiedot-metodissa)
- Paljon koodia, ei ylläpidettävää
- Paluukoodin palauttaminen sijoittamisen yhteydessä
- C-tyyliä, olio-ohjelmassa ennemmin poikkeuksia käyttäen (pakottavat käsittelemään virhetilanteen)
- Funktio-osoittimiin perustuva tarkastus
- Kerho ilmoittaa jokaiselle kentälle osoittimen funktioon (tai metodiin), joka hoitaa tarkastukset
- Kaikilla tarkastajafunktioilla täytyy olla sama rajapinta
- Yleiskäyttöisin (ja oliopohjaisin) tapa: Kenttä- ja Tarkistaja-luokat
- ks. Java-versio, tarkistu_72
- [ http://www.mit.jyu.fi/vesal/kurssit/ohj2/ ]
- Esim. henkilötunnusta tarkastettaessa tarkastus tehtävä Jäsenet-luokan avulla (tässä ei toteutettu)
- Huom. Kenttäoliotkaan eivät tiedä muista tietorakenteista, olioiden yhteistyö ylempien luokkien vastuulla
- 1-M -suhteiden tapauksessa tarvitsevat tietoa myös muista rakenteista -> tarkastus kerhossa (tai kerhoparametrilla)
- Tarkistaja-rajapintaa kehitettävä niin, että kenttä itse tekee "perustarkistuksen", mutta liitosten yli tehtäviä tarkistuksia varten annetaan parametrina kerho ulkopuolelta
- Jasen-luokka voidaan tehdä riippumattomaksi kerhosta lisäämällä metodi annaTarkistaja, jota kerho kutsuu
- Kerhoon lisättävä oma tietorakennekohtainen turvallinen asetusmetodi, joka voi tarkastaa myös liitokset
- Esimerkit:
- kerho/tarkistu.4
- [ http://www.mit.jyu.fi/vesal/kurssit/cpp/kerho/tarkistu.4 ]
- luentoesimerkeissä valmiiksi pakattu versio, projektiin mukaan ali-kirjasto
- puskuroimattomasta luvusta johtuen näppäimistön luku Eclipsen konsolissa ei toimi oikein (debuggaus toimii - breakpoint jasen.sijoita-kutsun kohdalle)
- käytä gdb-debuggeria (ei cygwin)
- C++ -kerho: vapaatyy/kerhotar.cpp
- Tarkistusfunktio sisältää tiedon tarkistettavasta jäsenestä sekä kerhosta
- Etsiminen ja lajittelu
- Idea: tehdään oma tietorakenneluokka hakutuloksia varten, sisältää indeksejä, id-numeroita tai
suoraan löydetyt oliot
- Haku toteutetaan Kerho-ohjelman tapauksessa peräkkäishakuna - binäärihaku mielivaltaisen kentän mukaan vaatisi ylimääräisiä indeksirakenteita
- uusi metodi: etsi_jasenen_tiedot
- Haun laajennusmahdollisuuksia: haku monen kentän mukaan ja yhdistely loogisilla operaattoreilla, jokerimerkit, suurempi-kuin-operaattori..
- Sulkujen lisääminen hakulausekkeisiin vaatisi jo jäsentimen lisäystä hakujärjestelmään - sivuutetaan
- Jos käytetään jokerimerkkejä, voidaan käyttää apuna mjonot-kirjaston wildmat-funktioita
- Jos hakutuloksia on paljon, ne kannattaa antaa selattavaksi ennen niiden tarkempaa tarkastelua
- Esim. näytetään vain otsikot numeroituna, tai sitten esim. 10 tietuetta kerrallaan ja selaus edelliseen/seuraavaan osalistaan
- jos näytetään suoraan kaikki tiedot (kuten esimerkkiohjelmassa), olisi ainakin syytä toteuttaa järjestetty näyttäminen ja +/- -selaus edelliseen ja seuraavaan
- hakutulosten selauksen yhteyteen on kätevää lisätä mahdollisuus tietueen muuttamiseen, poistamiseen (ym. harkkatyön aiheesta riippuvaa toimintaa)
- Useamman relaation yli menevä haku vaatii (taas) lisätyötä...
- Esimerkki: kerho/etsilaj.5
- [ http://www.mit.jyu.fi/vesal/kurssit/cpp/kerho/etsilaj.5 ]
- etsi_jasenen_tiedot
- apuluokka Permutaatiot sisältää löytyneiden jäsenten indeksinumerot
- varsinainen etsintälogiikka kerhon (ja edelleen jäsenen) etsi-metodissa
- hakutulokset lajitellaan hakuavaimen mukaan
- Nykyhenkilö: viimeksi löydetty / selauksen kohdalla oleva henkilö pidetään muistissa käyttöliittymässä
- projektissa mukana myös (poistettava käännöksestä käännettäessä kerhoa)
- taulukko - template-pohjainen geneerinen "cJasenet"-tyylinen taulukkoluokka (vaatii muutoksia uudempaa c++-standardia varten)
- Yleistäminen
- Tulos: ei enää yhtä "kerho-sovellusta", vaan sovelluskehys (application framework) yksinkertaisia tietokantaohjelmia varten
- Jäsen, Harrastus ym voidaan koota yleiseksi tietueolioksi indeksoiduilla kentillä
- Jäsenet, Harrastukset ym. voidaan yleistää yleiseksi tauluolioksi...
- Kenttien validointiin poikkeuskäsittely - vähentää if-lauseita nopeuden kustannuksella (erityisesti, kun asetetaan liitoksia)
- Esim.
- vapaatyy 8 -framework (cpp)
- [ http://www.mit.jyu.fi/vesal/kurssit/cpp/kerho/vapaatyy.8/ ]
- "KerhoFinal"
- Erilliset säiliöluokat poistettu kokonaan, tietueoliot noudattavat nyt samaa rajapintaa
- Yleistämisen varaa vielä edelleen: esim. hakujärjestelmä, joka tukee samalla koodilla hakua eri tietueolioista sekä kerhoon sisällytettävä "skeema", joka kuvaa liitokset yhdessä rakenteessa
- Geneerisyys ja suunnittelumallit
- tempatet ovat "toteutustasoista" uudelleenkäyttöä
- kertaluokkaa merkittävämpää voi olla suunnitteluratkaisujen uudelleenkäyttö
- komponenttia kehitettäessä tunnistettava "pysyvät" ja "vaihtuvat" osat
- pysyvät osat voivat käyttää uudelleen
- käytännössä pysyvien osien löytäminen ja toteuttaminen yleiskäyttöisesti voi olla vaikeaa
- lisäksi yleiskäyttöisen komponentin rajapinnasta voi tulla monimutkainen => käyttöönotto voi olla hankalaa
- laajempi mittakaava: ohjelmistoarkkitehtuuri
- => mitkä osat ohjelmistosta suunnitellaan helposti vaihdettaviksi (mahdollisesti esim. suorituskyvyn kustannuksella)
- eritasoisia malleja
- arkkitehtuurimallit
- vaikuttavat ohjelmiston rakenteeseen laajasti
- esim. "piiput ja filtterit", olioarkkitehtuuri, kerrosarkkitehtuurit
- suunnittelumallit (design patterns)
- suunnittelumalliin liittyy yleensä muutamia keskenään vuorovaikuttavia luokkia
- huom. suunnittelumalleja voidaan pitää myös tapana kiertää ohjelmointikielen "puutteita" - esim. useilla GoF-malleilla matkitaan dynaamisten tai funktiokielten ominaisuuksia
- toteutusmallit (idiomit)
- RAII, PIMPL jne - yleensä yhden luokan tai jopa metodin sisäinen toteutustapa
- esimerkkejä suunnittelumalleista
- singleton
- olio, josta luodaan vain yksi instanssi
- template method
- toiminnallisuuden jakaminen moneen eri metodiin, joista osa syrjäytetään aliluokissa
- composite (kokoelma)
- sama rajapinta sekä puun "vanhempi"- että "lehti"solmuilla
- iteraattori
- mahdollistaa tietorakenteen läpikäynnin ilman, että tarvitsee tuntea rakenteen toteutustapaa
- silta
- toteutuksen erottaminen rajapinnan määrityksestä