1. COMP.CS.300
  2. 5. STL-kirjasto
  3. 5.3 Kurssiaiheen 6 tehtävät

Kurssiaiheen 6 tehtävät

Iteraattorit

Miten seuraavat asiat tehdään koodissa? Kyseessä oleva iteraattori on tyypiltään std::vector<int>::iterator, ellei toisin mainita.

Siirretään iteraattoria it viisi kertaa eteenpäin?
Haetaan viimeiseen alkioon osoittava iteraattori? ( Kirjanmerkki-ajattelulla merkki olisi siis kahden viimeisen kirjan välissä.)
Lasketaan vektorin koko?

Mitä seuraava koodinpätkä tulostaa?

1
2
3
4
5
6
7
8
9
  vector<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  auto iter = ints.begin();
  auto another = iter + 5;
  iter += 3;
  if ( iter < another ){
      cout << *iter;
  } else {
      cout << *another;
  }

Mitä seuraava koodinpätkä tulostaa?

1
2
3
4
5
6
7
8
9
  vector<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  auto iter = ints.begin();
  auto another = ints.insert(iter, 11);
  iter = ints.begin() + 5;
  if ( iter < another ){
      cout << *iter;
  } else {
      cout << *(another + 2);
  }

Mitä seuraava koodinpätkä tulostaa?

1
2
3
4
  vector<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  auto iter = ints.begin();
  iter = iter * 3;
  cout << *iter;

STL-säiliöt

Seuraavassa on lueteltu erilaisia käyttötilanteita tietorakenteille. Mikä C++ STL:n tietorakenne sopisi tehokkuutta ajatellen parhaiten kuhunkin kohtaan? Tarkempaa tietoa tietorakenteiden tehokkuuksista löytyy esim. luentodioista ja cppreference.com

Huomioi, että tehtävän voi palauttaa kolme kertaa, mutta kysymykset satunnaistetaan joka kierrokselle.

  1. Alkioita lisätään tietorakenteen loppuun ja luetaan & poistetaan käänteisessä järjestyksessä niin, että viimeksi lisätty otetaan ulos ensimmäisenä.
  1. Alkioita lisätään tietorakenteeseen ja luetaan & poistetaan järjestyksessä niin, että ensiksi lisätty otetaan ulos ensimmäisenä.
  1. Alkioita lisätään usein tietorakenteeseen ja niitä käydään usein läpi lisäysjärjestyksessä. Aina joskus tulee tarve käydä alkiot läpi niiden suuruusjärjestyksessä, jonka jälkeen suurin alkio poistetaan.
  1. Alkioita lisätään usein tietorakenteeseen. Usein tulee tarve käydä alkiot läpi niiden suuruusjärjestyksessä, jonka jälkeen pienin alkio poistetaan.
  1. Alkioita lisätään usein tietorakenteen loppuun, harvoin lisätään myös keskelle tietorakennetta (johonkin annettuun paikkaan). Usein tulee tarve hakea tietorakenteesta i:s alkio (i vaihtelee).
  1. Alkioita lisätään jonkin jo etsityn alkion vasemmalle tai oikealle puolelle. Alkioita poistetaan lopusta.
  1. Alkioita lisätään usein tietorakenteeseen. Usein tulee myös tarve selvittää, onko tietynsuuruinen alkio tietorakenteessa ja poistaa ko. alkio (jos se löytyy).
  1. Alkioita lisätään usein tietorakenteeseen. Usein tulee myös tarve selvittää, onko tietynsuuruinen alkio tietorakenteessa ja poistaa ko. alkio (jos se löytyy). Harvemmin tulee tarve käydä läpi alkiot suuruusjärjestyksessä.

  1. Säiliöön lisätään N alkiota.

    Millä asymptoottisella tehokkuudella kaikki lisäykset tapahtuisivat yhteensä, jos säiliö olisi list?

  1. Entä jos edellisen kysymyksen säiliö olisi set?

  1. Säiliöstä, jossa on N alkiota mielivaltaisessa järjestyksessä, halutaan tarkistaa, sisältääkö se jo jotain arvoa.

    Mikä olisi keskimäärin asymptoottinen tehokkuus tarkistukselle, jos säiliö olisi vector?

  1. Entä jos edellisen kysymyksen säiliö olisi unordered_set?

Asymptoottisen tehokkuuden arviointi

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Iteraatio-tehtävä

Iteraatio

Iteraatio - lyhyet ohjeet

Päivitä kurssin repositorio vetämällä viimeisimmät muutokset course-upstreamista omaan repositorioosi seuraavalla komennolla: git pull course-upstream main

Repositoriossasi sinun tulisi nähdä hakemisto wk03_stl/iteration seuraavalla sisällöllä: 

wk03_stl/iteration
          ├── iteration.pro
          ├── iteration1.hh
          ├── iteration2.hh
          ├── iteration3.hh
          ├── iteration4.hh
          ├── iteration1.cc (edit the function in here)
          ├── iteration2.cc (edit the function in here)
          ├── iteration3.cc (edit the function in here)
          ├── iteration4.cc (edit the function in here)
          ├── main.cc
          └── CLI11.hh

Arvostelija tulee kopioimaan vain sinun iteration*.cc tiedostot. Älä tee minkäänlaisia sisällytyksiä (includes) tiedostoihin.

Tehtävänäsi on toteuttaa neljä erilaista funktiota, jotka ottavat kaikki STL list -säiliön argumentikseen. Sitten lista iteroidaan STL iteraattoreiden avulla, ja riippuen funktiosta joko kaikki tai jotkut listan kohteet tulostetaan.

Kaikkien funktioiden on tulostettava listan kohteet samalle riville erotettuna vain yhdellä tyhjällä välilyönnillä " " ja sitten rivin lopussa yksi uusi rivi (std::endl). On hyväksyttävää tulostaa yksi välilyönti viimeisen listakohteen jälkeen. Ennen ja jälkeen tulevat tyhjät välilyönnit jätetään huomiotta.

Arvostelija vertaa funktioidesi tulostetta malliratkaisun tulosteeseen, joten on tärkeää, ettet tulosta mitään muuta kuin listan itemeita.

Implementoitavat funktiot
# Funktion nimi Tiedosto Odotettu tuloste listalle: {5, 6, 9, 13, 17, 21, 23, 29}
1 void printAllItems(const list<int>& lst) iteration1.cc 
5 6 9 13 17 21 23 29
2 void printEverySecond(const list<int>& lst) iteration2.cc 
5 9 17 23
3 void printHalf(const list<int>& lst) iteration3.cc 
5 6 9 13
4 void printReverse(const list<int>& lst) iteration4.cc 
29 23 21 17 13 9 6 5

Funktioidesi testaaminen

wk03_stl/iteration -kansiossa avaa Qt-projektitiedosto iteration.pro Jotta voit ajaa ohjelman parametrien kanssa, sinun täytyy joko suorittaa se terminaalissa tai muuttaa komentoriviparametrit Qt Creatorista.

Komentoriviparametrien muuttaminen Qt Creatorissa

Kun olet avannut projektin, valitse vasemmalla olevasta valikosta Qt Creatorissa projektit (pyöräavainkuvake / wrench icon). Avatussa valikossa, vasemmalla Build & Run< -osion alla valitse run. Nyt pitäisi näkyä Command line arguments, ja voit liittää parametrit sinne.

Ohjelman suorittaminen

Testien suorittaminen on helppoa, ja iteration-ohjelma tulostaa käyttöohjeet, jos suoritat sen ainoana komentoriviparametrina --help.

Tehtävän palauttaminen Plussaan

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Palautusta lähetetään...