Kurssiaiheet 5, 6 ja 7¶

Itseopiskelu (videot ja kalvot suomeksi)¶

Standard Template Library (STL)¶

STL:n iteraattoreiden tehokkuus ja iteraattorikategoriat video

STL kalvot

Huom Videossa nimeltä STL säiliöiden tehokkuus on taulukko, jonka otsikko on Säiliön valinta tehokkuuden perusteella. Videossa esitetyssä taulukossa on virheitä. Kuitenkin kalvojen tiedostossa esitetty taulukko on oikein.

Viikko05 - Sanasto

Kysymys 1

STL voidaan jakaa kolmeen osaan. Mitä ne ovat?

yleiset algoritmit, säiliöt ja vuorovaikutukset

iteraattorit, kontaminantit ja yleiset algoritmit

säiliöt, iteraattorit ja yleiset algoritmit

säiliöt, iteraattorit ja geneettiset algebrat

Kysymys 2

Mitä tietoja STL-dokumentaatio sisältää useimpien algoritmien suoritustehokkuudesta?

tyypillisesti ylärajan ja joskus alarajan

tyypillisesti alarajan ja joskus keskimääräisen tehokkuuden

tyypillisesti mediaaniarvon, mutta aina 95%:n luottamusvälin

tyypillisesti ylärajan ja joskus keskimääräisen tehokkuuden

Kysymys 3

C++-ohjelmoijalle on tärkeää osata käyttää STL:ää, koska

STL:ää käyttämällä ohjelmoija voi huijata muita uskomaan, että ohjelmoija on asiantuntija

ohjelmoija voi säästää huomattavasti aikaa käyttämällä STL:n algoritmikokoelmaa, jonka asymptoottinen suorituskyky tunnetaan

STL-säiliöitä ja -algoritmeja käytettäessä ohjelmoijan ei tarvitse ymmärtää koodia mitä hän käyttää tai kirjoittaa

Kysymys 1

STL-säiliöiden päätyypit ovat sarjat ja assosiatiiviset taulukot. Mitkä ovat sarjojen pääominaisuudet?

käyttäjä voi sijoittaa elementit haluamaansa järjestykseen

käyttäjän on määritettävä paikka, johon elementti lisätään tai poistetaan

sarjatietorakenteen koko on aina kiinteä, kun se luodaan

käyttäjän on mahdotonta päästä käsiksi sarjan kahteen peräkkäiseen elementtiin

sarjaelementteihin pääsee käsiksi indeksin tai iteraattorin avulla

Kysymys 2

Kun kyseessä on assosiatiivinen taulukko

säiliön elementit tallennetaan hakuavainten mukaisessa järjestyksessä

säiliön elementit säilytetään aina järjestyksessä

säiliön elementti löytyy hakuavaimella

säiliössä on lukko, joka voidaan avata hakuavaimella sen jälkeen, kun säiliö on suorittanut “muistin tyhjennyksen”

Kysymys 3

Mitkä väitteet pätevät assosiatiivisen säiliön valinnassa?

Kannattaa käyttää unordered settiä, jos on vain avaimia, avaimet ovat uniikkeja eikä järjestyllä ole väliä.

Kannattaa käyttää multimapiä, jos on avaimia, jotka liittyvät elementteihin, nämä avaimet ovat uniikkeja ja niiden järjestys on tärkeää.

Kannattaa käyttää multisettiä, jos elementteihin liittyy avaimia, useilla elementeillä voi olla sama avain ja järjestys on tärkeä.

Kannattaa käyttää multisettiä, jos sinulla on vain avaimia, jotkin avaimet saattavat toistua ja järjestyksen säilyttäminen on tärkeää.

Kannattaa käyttää satunnaistettua ja kierrätettävää säiliötä, jos on avaimia, jotka liittyvät elementteihin, jokaisella elementillä on oma avain ja järjestys ei ole tärkeä.

Kysymys 1

Olkoon \(X\) STL-säiliö ja \(Op1\) jokin perustoiminto (esimerkkihaku arvon perusteella). On mahdollista, että STL:ssä ei ole funktiota, joka tekee \(Op1\) \(X\):lle. Tähän on kaksi syytä. Yksi syy on se, että \(Op1\):n tekeminen \(X\):lle on joko mahdotonta tai siinä ei ole mitään järkeä. Mikä on toinen syy?

STL:n suunnittelijat eivät olleet tarpeeksi päteviä keksimään toimivaa koodia \(Op1\):lle.

\(Op1\):n suorittaminen säiliölle \(X\) johtaisi aina ohjelman päättymiseen iteraattoreiden mitätöitymisen vuoksi.

Ainoat keinot tehdä \(Op1\) säiliölle \(X\) ovat tehottomia, mutta useat käyttäjät saattaisivat olettaa, että \(Op1\) voidaan suorittaa tehokkaasti.

Jotkut yleisesti käytetyt C++-kääntäjät eivät kyenneet kääntämään koodia \(Op1\), joten STL-suunnittelijat päättivät poistaa \(Op1\):n

Kysymys 2

Missä seuraavista tapauksista STL tarjoaa funktion, jolla on vakioaikainen tehokkuus?

Avaimen tai arvon etsiminen listasta.

Elementin lisääminen map-tietorakenteeseen

mapin pienimmän elementin hakeminen.

mapin arvon hakeminen pienimällä avaimen arvolla

Elementin hakeminen taulukon tietystä kohdasta.

Kysymys 3

Kun kirjoitetaan tehokasta koodia, ohjelmoijan tulisi valita säiliöt siten että..

toiminnot, joita ei koskaan suoriteta, suoritetaan mahdollisimman tehottomasti

kaikki toiminnot suoritetaan mahdollisimman tehokkaasti

tallennettavan tiedon määrä on mahdollisimman pieni

usein suoritettavat toiminnot tehdään mahdollisimman tehokkaasti

Kysymys 1

Mitkä seuraavista väitteistä pätevät STL:n iteraattoreille?

Niille ei ole käyttöä STL:ssä.

Niitä voidaan käyttää osoittamaan useita säiliön elementtejä.

Iteraattori on kuin kirjanmerkki kahden peräkkäisen elementin välillä.

Ne ovat kolmannen tyyppisiä säiliöitä.

Kysymys 2

Oletetaan, että \(i1\) ja \(i2\) ovat iteraattoreita jollekin sarjatietorakenteelle. Jos \(i2 < i1\) on tosi, mikä seuraavista on oikein?

Elementti, johon \(i1\) osoittaa, on suurempi kuin elementti, johon \(i2\) osoittaa.

Iteraattori \(i1\) osoittaa sijaintiin, joka on lähempänä säiliön alkua kuin paikkaa, johon \(i2\) osoittaa.

Iteraattori \(i1\) osoittaa sijaintiin, joka on lähempänä säiliön loppua kuin kohtaa, johon \(i2\) osoittaa.

Sijaintien \(i2\) ja \(i1\) välinen alue on tyhjä.

Kysymys 1

Oletetaan, että \(i1\) ja \(i2\) ovat iteraattoreita kahdesta eri kategoriasta. Mikä seuraavista on totta?

\(i1\):lla ja \(i2\):lla voi olla eri ajonaikainen tehokkuus

Ei ole olemassa sellaisia operaatioita, joita sekä \(i1\) että \(i2\) voisivat tehdä.

On olemassa ainakin yksi operaatio, jonka vain toinen iteraattoreista voi tehdä.

Toiselle iteraattorille \(++\) -operaatio epäonnistuu.

Kysymys 2

Mitkä väitteistä ovat totta seuraaville iteraattorikategorioille?

Vain forward_list tukee kaksisuuntaisia iteraattoreita.

Kaikki iteraattoriluokat sallivat \(--\) (miinus-miinus) -toiminnon.

Mikään assosiatiivinen säiliö ei tue hajasaanti-iteraattoreita.

Kaikki sarjat tukevat hajasaanti-iteraattoreita.

Kaksisuuntainen iteraattori ei salli mielivaltaisia hyppäämistä eteen- tai taaksepäin, kun taas hajasaanti-iteraattori sallii.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

STL-sarjat

STL-assosiatiiviset säiliöt

iteraattorit

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Linkkejä viikon aiheisiin:

The cppreference site: Containers
Wikipedia’s pages on the Standard Template Library
A long list of examples using STL

Week05 - Glossary

Viikko05 - Sanasto

Palauta viikkotehtävät¶

Questions to be submitted this week

Kurssiaihe 6¶

Itseopiskelu¶

Viikon aiheet: STL:n algoritmit, lambda-funktiot

Opetusvideot ja niihin liittyvät kalvot:

STL:n algoritmit video

STL:n algoritmit - esimerkkejä video

Lambda-funktiot video

Lambda-funktiot ja muuttujien kaappaaminen video

STL:n algoritmien ja säiliöden mukauttaminen video

STL kalvot

Lambda-funktioiden kalvot

Esimerkkien c++-koodit

Lambda-funktioiden c++-koodit

STL:n algoritmien ja säiliöden mukauttaminen: c++ koodit

STL:n algoritmit¶

Kysymys 1

Oletetaan, että on olemassa jokin STL-säiliö muuttujassa \(A\) ja halutaan syöttää \(A\) STL-algoritmiin \(X\). Mitä parametria (tai parametreja) pitäisi syöttää algoritmiin \(X\) osoittamaan, että halutaan algoritmin \(X\) käyttävän koko säiliötä \(A\)?

Pitäisi yksinkertaisesti syöttää muuttuja \(A\).

On syötettävä säiliön \(A\) ensimmäisen ja viimeisen elementin todelliset arvot.

On syötettävä iteraattori säiliön \(A\) alkuun ja iteraattori säiliön \(A\) loppuun.

On syötettävä muuttuja \(A\) yhdessä säilötyypin kanssa (esimerkiksi vector tai list tai map).

Kysymys 2

Mistä syistä on parempi käyttää STL:n algoritmeja jonkin tehtävän laskemiseen sen sijaan, että kirjoittaisit omia algoritmeja tehtävän laskemiseksi? (Voi olla enemmän kuin 1 oikea syy.)

STL:n algoritmien käyttö tekee koodista luettavamman ja ymmärrettävämmän.

STL:n algoritmin tehokkuus on aina parempi kuin koodi, jonka kirjoitat itse.

STL:n algoritmissa käsitellään erikoistapauksia ja potetaalisia virhetilanteita.

Kun käytät STL:n algoritmia, sinun ei tarvitse tietää tai ymmärtää, mitä lasket.

Esimerkkejä STL:n algoritmien käytöstä¶

Kysymys 1

Oletetaan, että alku ja loppu ovat kaksi iteraattoria, jotka liittyvät vektoriin v. Oletetaan, että iteraattorin alku oikealla puolella oleva paikka on \(i\) ja iteraattorin loppu oikealla puolella oleva paikka on \(j\). Mikä on erotuksen loppu - alku merkitys?

Erotus on uusi iteraattori, jossa loppu on siirretty vasemmalle \(i\)-paikaa.

Erotuksen arvo on sama kuin \(j-i\).

Erotuksen arvo on sama kuin \(j-i + 1\).

Erotuksen arvo on sama kuin \(i-j + 1\).

Kysymys 2

Mikä seuraavista vaihtoehdoista STL:n algoritmeista on totta?

Ne ovat palikoita, joita voidaan käyttää oman algoritmin muodostamiseen oman tehtävän laskemiseksi.

Saatavilla on STL-algoritmi, joka ratkaisee kaikki laskennalliset tehtävät, joita koskaan kohdataan.

Ne ovat hyödyttömiä, koska niiden käsittelemät tehtävät ovat liian yksinkertaisia.

Lambda-funktiot¶

Kysymys 1

Oletetaan, että on olemassa vektori std::vector<int> v{6, 3, 4, 9, 2, 7, 1, 11}; C++:ssa. Mikä seuraavista tuottaa osoittimen *it, jonka arvo on 2?

auto it = std::find_if(begin(v), end(v), [](auto x){ return x % 2 = 0; });

auto it = std::find_if(begin(v), end(v), [](auto x){ return x % 2 != 0; });

auto it = std::find_if(begin(v), end(v)+3, [](auto x){ return x % 2 != 0; });

auto it = std::find_if(begin(v)+3, end(v), [](auto x){ return x % 3 != 0; });

Kysymys 2

Mitkä seuraavista väitteistä lambda-funktioista ovat totta. (Voi olla enemmän kuin 1 väite, joka on tosi.)

Lambda-funktio voidaan antaa parametrina STL-algoritmille.

Lambda-funktio voidaan aina kirjoittaa käyttämättä aritmeettisia laskelmia.

Lambda-funktio voi tuottaa vain totuusarvoja (true/false).

Lambda-funktio on nimetön funktio.

Kysymys 3

Oletetaan, että on olemassa vektori std::vector<int> v{-19, 21, -4, 6}; C++:ssa. Mikä on osoittimen *it arvo, seuraava rivi lasketaan?:: auto it = std::find_if(begin(v), end(v), [](int i){ return (i%2 != 0 && i >0); });

-19

-4

Lambda-funktiot ja muuttujien kaappaaminen¶

Kysymys 1

Kun sanomme, että lambda-funktio kaappaa muuttujan, tarkoitamme,

että ei mikään muu funktio saa käyttää muuttujaa, jolla on sama nimi kuin kaapatulla muuttujalla

että lambda-funktio poistaa paikallisen muuttujan funktiosta, joka käyttää lambda-funktiota

että lambda-funktio tekee kopion muuttujasta tai viittauksesta, jota se käyttää itsessään

että, kun lambda-funktio käyttää paikallista muuttujaa, muuttujan nimen on alettava etuliitteellä capt!, joka on lyhenne sanasta captured

Kysymys 2

Oletetaan, että C++:ssa on olemassa vektori v, jonka alkiot ovat kokonaislukuja, ja muuttuja d, joka on nollasta poikkeava kokonaisluku. Mikä on muuttujan a arvo, kun seuraava rivi lasketaan?:: int a = std::count_if(v.begin(), v.end(), [d](int i){return (i % d != 0 && i*d > 0 );});

Vektorissa v olevien alkioiden lukumäärä, jotka ovat nollasta poikkeavia ja suurempi kuin d.

Nolla aina.

Niiden vektorissa v olevien alkioiden lukumäärä, jotka ovat jaollisia muuttujalla d tai joilla on sama etumerkki kuin muuttujalla d.

Niiden vektorissa v olevien alkioiden lukumäärä, jotka eivät ole jaollisia muuttujalla d ja joilla on sama etumerkki kuin muuttujalla d.

STL:n algoritmien ja säiliöiden mukauttaminen¶

Kysymys 1

Mitkä seuraavista STL-algoritmien mukauttamista koskevista väitteistä on totta? (Useampi kuin yksi väite voi olla totta.)

Mukauttamisen avulla voimme laajentaa olemassa olevien STL-algoritmien käyttöä.

Kun STL-algoritmi mukautetaan, algoritmiin syötettyjen parametrien määrä kasvaa aina.

STL-algoritmin mukauttamiseksi meidän on kirjoitettava STL-algoritmikoodi uudelleen vastaamaan vaatimuksiamme.

Kun STL-algoritmi mukautetaan, nimeämme STL-algoritmin uudelleen selventääksemme sen käyttöä koodissamme.

Kun mukautetaan STL-algoritmia, lisätään usein nimetyn funktion tai lambda-funktion STL-algoritmikutsuun.

Kysymys 2

STL-kirjasto sisältää algoritmit count_if, find_if ja remove_if. Mikä seuraavista ominaisuuksista on kaikilla näillä algoritmeilla?

Ne kaikki vaativat täsmälleen kaksi syöteparametria, jotka ovat molemmat iteraattoreita.

Yksi niiden tarvitsemistaan syöteparametreista on joko lambda-funktio tai osoitin nimetylle funktiolle.

Kaikki ne palauttavat yhden iteraattorin.

Syöteparametreina käytettyjä iteraattoreita ei voi liittyä vektorisäiliöön.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

STL:n algoritmit

Esimerkkejä STL:n algoritmien käytöstä

Lambda-funktiot

Lambdat ja muuttujien kaappaaminen

STL:n algoritmien ja säiliöiden mukauttaminen

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Lisäinformaatiota aiheesta:

STL:n algoritmien sivut; cppreference.com

Viikko06 - Sanasto

Kurssiaiheiden palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Palautusta lähetetään...