Keskustelu: Ohjelmointikysymykset: C++: yhdistetyn tietorakenteen muokkaaminen toistorakenteessa

Morjesta! Ensimmäinen viestini Ohjelmointiputkassa, joten toivottavasti kaikki menee foorumin periaatteiden mukaan. Asiaan:

Yliopiston ohjelmointi 2 -kurssitehtävässä tallennetaan tekstitiedostosta saatuja tietoja kauppaketjuista sopivasti valittuun tietorakenteeseen ja rakennetaan algoritmeja, joilla tietoja voi tutkia halutuilla tavoilla. Kauppaketjujen tiedot tulee saada seuraavaan formaattiin:

S-Market
....Lielahti
....makkara 0.79
....keppana 1.00
S-Market
....Kaukajärvi
....makkara 0.80
....lappari 1.25
K-Citymarket
....Kaleva
....jogurtti 1.79
....keppana OUT OF STOCK
Prisma
....Koivistonkylä
....lappari 1.19

Tiedot tekstitiedostossa ovat muotoa
S-Market;Lielahti;makkara;0.79
S-Market;Lielahti;keppana;1.00
K-Citymarket;Kaukajärvi;makkara;0.80
jne.

Tuotteiden tallentamiseen käytän structia
struct Product = {
string name;
string status_price;

Ajatuksenani oli käyttää tietojen tallentamiseen yhdistettyä tietorakennetta
map<string, map< string, vector<Product>>> chains. Tiedostonluvussa tekstiriviltä saadut tiedot tallennetaan while-loopissa edellä mainittuun rakenteeseen. Ongelmana on, että kun looppi siirtyy jo mapissa chains valmiiksi sijaitsevan kauppaketjun kohdalle, toistorakenne korvaa edellisen samannimisen avaimen uudella. Tarkoituksena olisi, että tässä tapauksessa ohjelma lisäisi kaupan kyseisen kauppaketjun alle tietoineen. Alla koodinpätkä nykytilanteessa:

map<string, map<string, vector<Product>>> chains;
string line;
while ( getline(input_file_object, line) ) {
    vector<string> parts = split(line, ';', true; // Split pätkii rivin

    if ( parts.size() != 4 ) {
        cout << "Error: the input file has an erroneous line" << endl;
        return EXIT_FAILURE;
    } else {
        string chain_name = parts.at(0);
        map<string, vector<Product>> store = get_store(parts);
        chains.insert( { chain_name, store});
    }
}

Toivottavasti muistin antaa riittävästi informaatiota. Luultavasti ratkaisu on hyvinkin simppeli, mutta ei nyt tule mieleen väsyneillä aivoilla. -.-
Paljon kiitoksia arvon tulevat kolleegat!

Kauppaa ei tarvitse erikseen hakea ja muokata (eikä varsinkaan luoda mitään tyhjää), vaan else-lohkon olennainen sisältö on näinkin yksinkertainen:

chains[chain_name][store_name].push_back({product_name, price});

Muuttujiin haet vain oikeat kohdat partsista.

Ihan hyvä harjoitustehtävä itse asiassa! Piti jopa piruuttain kokeilla miten 8th taipuisi tehtävään ja hyvinhän tuo onnistui. REPL ja mahdollisuus tulostaa tietorakenne muotoiltuna JSON-muodossa auttaa kivasti toteutusta testatessa.

Miltähän muuten näyttäisi C++ koodi mikä tulostaisi kyseisen tietorakenteen sisällön listana aakkosjärjestyksessä ja helppolukuisessa muodossa?

Itse käytin alla olevaa esitysmuotoa omassa toteutuksessani:

K-Citymarket:
  Kaleva:
    makkara: 0.80
Prisma:
  Koivistonkylä:
    lappari: 1.19
S-Market:
  Kaukjärvi:
    makkara: 0.85
  Lielahti:
    keppana: OUT OF STOCK
    makkara: 0.79

jalski kirjoitti:

Miltähän muuten näyttäisi C++ koodi mikä tulostaisi kyseisen tietorakenteen sisällön listana aakkosjärjestyksessä ja helppolukuisessa muodossa?

C++:n map on järjestyksessä. Kun luovutaan vektorista ja käytetään sen sijaan multimapia tuotteiden säilyttämiseen, saadaan nekin kätevästi järjestykseen.

Tulostaminen on aivan helppoa for-silmukalla.

Lukemisesta myös selviää ilman split-funktiota, kun määrittelee getline-funktion kolmanneksi parametriksi lopetusmerkin – toki sillä edellytyksellä, että ohjelmalle syötetään vain kelvollista dataa.

#include <map>
#include <string>
#include <iostream>

typedef std::multimap<std::string, std::string> tuotteet_t;
typedef std::map<std::string, std::map<std::string, tuotteet_t>> data_t;

data_t lue() {
	data_t data;
	std::string a, b, c, d;
	while (std::getline(std::cin, a, ';') && std::getline(std::cin, b, ';') && std::getline(std::cin, c, ';') && std::getline(std::cin, d)) {
		data[a][b].insert({c, d});
	}
	return data;
}

void tulosta(data_t const& data) {
	for (auto& a: data) {
		std::cout << a.first << ":\n";
		for (auto& b: a.second) {
			std::cout << "  " << b.first << ":\n";
			for (auto& c: b.second) {
				std::cout << "    " << c.first << ": " << c.second << "\n";
			}
		}
	}
}

int main() {
	auto data = lue();
	tulosta(data);
}

Oletuksena järjestys menee ASCII-arvojen mukaan, mikä tässä tehtävässä tuottaa varmaankin jo tyydyttävän ratkaisun.

Oikea aakkostus yleisessä tapauksessa onkin jo täysin eri kokoluokan ongelma, jonka ratkaisu riippuu siitä, mitä kieliä ja merkkejä halutaan tukea ja miten käsitellään kaikenlaiset ASCII-merkistön ulkopuoliset asiat kuten tarkkeet (mm. ç, é) ja harvinaisemmat aakkoset (mm. ß, ð, ø).

Jos ASCII-arvoja parempi aakkostus on tarpeen, pitää vain tehdä tästä funktio, joka vertaa kahta merkkijonoa. Tämän voi sitten lisätä map-tyypin parametriksi, niin tietorakenteen saa haluamaansa järjestykseen.

Metabolix kirjoitti:

C++:n map on järjestyksessä. Kun luovutaan vektorista ja käytetään sen sijaan multimapia tuotteiden säilyttämiseen, saadaan nekin kätevästi järjestykseen.

Tuo helpottaa kyllä jonkun verran, että map järjestyy luotaessa avaimien mukaan aakkosjärjestykseen, 8th:lla map ei ole järjestyksessä vaan tulostus täytyy tehdä järjestämällä avaimet järjestykseen ja tulostamalla sitten avaimien mukaisessa järjestyksessä:

needs map/iter

m:new constant chainmap

: process-line  \ s --
  ";" s:/
  a:len 4 n:= not if
    "You and your data suck!" throw
  then
  a:shift
  chainmap swap dup >r m:new m:!? r> m:@ >r
  swap a:shift
  r> swap dup >r a:new m:!? r> m:_@
  m:new rot a:open >r "name" m:_! r> "status_price" m:_! a:push 2drop ;

: read-and-parse  \ fname --
  f:slurp "Cannot open and read file, nothing to process" thrownull
  ' process-line s:eachline ;

: cmp-by-name  \ m1 m2 -- result
  swap "name" m:_@ swap "name" m:_@
  s:cmp ;

: print-product \ m --
  [ "name", "status_price" ] m:@@ nip "    %s: %s\n" s:strfmt . ;

: print-store  \ m k -- m
  dup space space . ":\n" . m:@ ' cmp-by-name a:sort
  ' print-product a:each! drop ;

: print-chain \ m k -- m
  dup . ":\n" . m:@ m:keys ' s:cmp a:sort
  ' print-store m:iter drop ;

: print-sorted-info
    chainmap m:keys ' s:cmp a:sort
  ' print-chain m:iter drop ;

: app:main
  "k.txt" read-and-parse
  print-sorted-info
  bye ;

Kiitoksia Metabolix kätevistä vinkeistä - tuo tiedonlukufunktio on hyvin paljon yksinkertaisempi kuin se ratkaisu mihin itse päädyin. Aion käyttää tuollaista tapaa jatkossa vastaavien ongelmien ratkaisuun, sillä se olisi säästänyt paljolta kirjoittamiselta ja ongelmilta. Kiitos myös Jalski mielenkiinnosta. Ja muuten, sain palautettua projektin deadlineen mennessä niin viimeisteltynä kuin osasin. Tuli mahtava onnistumisen tunne, kun lopulta monien tuskailujen ja turhautumisien jälkeen koodini läpäisi kaikki testit ja sain vihreää valoa.

Huomasin tehtävää tehdessäni, että map oli kätevin paikka tallentaa data, koska se laittoi automaattisesti avaimet järjestykseen ja iteraattorien avulla tulostusfunktiot onnistuivat näppärästi. Näköjään myös väsymyspäissäni kirjoitin muutamia asioita väärin: structissä piti olla string tuotteen nimenä ja double hintana. Kun tuotetta ei ole, laitoin tuotteen hinnaksi -1. Kauppaketjujen dataa ei myöskään tullut tulostaa sellaisenaan missään kohti.

En kirjoittanut tänne kaikkia tehtävänannon vaatimuksia, koska ajattelin, että on parempi tehdä ketju hyvin spesifistä ongelmasta kuin kokonaisesta projektista. Mutta laitetaanpa tänne koko tehtävä siltä varalta että joku haluaisi tehdä:

(P) Kauppaketjut
Tavoite: Kertaan STL:n säiliöiden ja iteraattoreiden toimintaa sekä tiedostojen lukemista. Harjoittelen myös struct-rakenteen käyttämistä (ks. kurssimateriaalin kohta 4.4 Tieto vs kontrolli). Erityisesti harjoittelen valitsemaan sopivan tietorakenteen STL:n tietorakenteiden joukosta. (Riittää valita niiden STL-säiliöiden joukosta, joita on käsitelty kurssin materiaalissa.)

Ohjeita: Luo uusi projekti: student/07/shopping/.

Toteuta ohjelma, joka lukee käynnistyessään kauppaketjujen tuotevalikoimaan liittyviä tietoja tiedostosta, tallentaa ne sopivaan tietorakenteeseen ja antaa käyttäjälle mahdollisuuden tehdä hakuja kyseiseen tietorakenteeseen.

Attention
Ennen kuin aloitat, lue huolellisesti koko tehtävänanto. Huomaa erityisesti kohdat Ohjelman toteuttaminen osissa (vaaditut commitit) sekä Erityisvaatimukset.

Attention
Tämän projektin saa (mutta ei ole pakko) tehdä parityönä. Paripalautusta varten tulee muodostaa ryhmä palauttamalla lomake, joka löytyy vasemman puolen valikosta otsikolla “Luo uusi ryhmä”. Lisäksi tämän sivun alaosan palautuslaatikkossa on näkyvissä kaksi vaihtoehtoa: “Palauta yksin” / “Palauta ryhmässä”. Ole tarkkana, että valitset oikean vaihtoehdon, koska valintaa ei voi myöhemmin perua. Palautuslaatikkoon tulee vain jommankumman jäsenen Git-repositorion osoite. Kirjoittakaa kooditiedoston kommentteihin molempien nimet ym. muut tiedot.
Vaikka tehtävässä ei ole koodipohjaa, sen ei silti pitäisi olla vaikea. Syötetietojen lukeminen on tässä helpompaa kuin ensimmäisessä projektissa. Lisäksi voit kirjoittaa kaiken koodin tiedostoon main.cpp. (Muista kuitenkin jakaa koodi eri funktioihin.)

Ohjelman käsittelemä data

Ajatellaan seuraavan kaltaista informaatiota tuotteiden hinnoista ja saatavuudesta eri kauppaketjujen eri myymälöissä:

S-Market
Hervantakeskus
yogurt 1.05
sausage 3.25
S-Market
Pirkkala
sausage 2.90
yogurt OUT OF STOCK
chocolate OUT OF STOCK
S-Market
Kaukajärvi
yogurt 1.05
sausage 3.25
K-Citymarket
Pirkkala
yogurt 0.95
sausage 2.90
K-Citymarket
Turtola
sausage OUT OF STOCK
yogurt 0.95
K-Citymarket
Lielahti
sausage 3.00
yogurt 0.90
K-Citymarket
Linnainmaa
yogurt 0.95
sausage 2.90
Prisma
Kaleva
yogurt 0.90
sausage 2.90
Prisma
Lielahti
yogurt 0.90
sausage 2.90
Prisma
Koivistonkylä
sausage 2.90
yogurt 0.90
chocolate OUT OF STOCK

Ylläolevassa esimerkissä jokaisessa kaupassa on vain samat kaksi tuotetta sekä suklaa kahdessa kaupassa, mutta niistäkin se on loppu. Tuotteita voisi kuitenkin olla eri määrä, ja eri kaupoissa ei välttämässä ole tarjolla kaikkia samoja tuotteita.

Huomaa, että “tuotetta ei ole laisinkaan tarjolla” ei tarkoita samaa asiaa kuin se, että “tuote on tilapäisesti loppunut” (OUT OF STOCK). Jos tuotetta ei ole laisinkaan kaupan valikoimassa, se puuttuu kyseisen kaupan tuotelistalta kokonaan.

Edellä listatun kaltainen tietomäärä voidaan esittää csv-tiedostona, jonka rivit ovat muotoa:

kauppaketjun_nimi;kaupan_sijainti;tuotteen_nimi;tuotteen_hinta
missä tuotteen_hinta voi olla reaaliluku tai literaalinen merkkijono "out-of-stock".

Yllä käytetty esimerkki näyttäisi syötetiedostoksi kuvattuna siis esimerkiksi seuraavalta:

S-Market;Hervantakeskus;yogurt;1.05
Prisma;Koivistonkyla;chocolate;out-of-stock
S-Market;Pirkkala;chocolate;out-of-stock
Prisma;Koivistonkyla;sausage;2.90
S-Market;Hervantakeskus;sausage;3.25
S-Market;Pirkkala;yogurt;out-of-stock
K-Citymarket;Linnainmaa;sausage;2.90
S-Market;Kaukajarvi;sausage;3.25
K-Citymarket;Pirkkala;yogurt;0.95
Prisma;Kaleva;sausage;2.90
K-Citymarket;Pirkkala;sausage;2.90
Prisma;Lielahti;yogurt;0.90
K-Citymarket;Turtola;sausage;out-of-stock
S-Market;Kaukajarvi;yogurt;1.05
K-Citymarket;Lielahti;yogurt;0.90
K-Citymarket;Linnainmaa;yogurt;0.95
Prisma;Kaleva;yogurt;0.90
Prisma;Lielahti;sausage;2.90
S-Market;Pirkkala;sausage;2.90
Prisma;Koivistonkyla;yogurt;0.90
K-Citymarket;Lielahti;sausage;3.00
K-Citymarket;Turtola;yogurt;0.95

Kenttiä on rivillä neljä kappaletta, ja mikään kenttä ei saa olla tyhjä tai muodostua pelkistä välilyöntimerkeistä. Viimeisen kentän on oltava reaalilukua (double) esittävä merkkijono tai sana "out-of-stock".

Huomaa, kuinka rivien ei tarvitse csv-tiedostossa olla missään erityisessä järjestyksessä. Syötetiedostossa ei myöskään käytetä skandinaavisia kirjaimia.

Mikäli syötetiedostossa on saman kauppaketjun samalle myymälälle esitetty jokin tuote useammin kuin kerran, voimaan jää se hintatieto, joka tuli vastaan tiedostossa viimeisimpänä. Esimerkiksi:

S-Market;Hervantakeskus;yogurt;0.55
Prisma;Koivistonkyla;sausage;2.90
S-Market;Hervantakeskus;sausage;3.25
S-Market;Pirkkala;yogurt;out-of-stock
S-Market;Hervantakeskus;yogurt;1.05
jolloin S-Market Hervantakeskuksessa jogurtin hinta olisi 1.05 €.

Ohjelman toiminta

Kun ohjelma käynnistyy, se lukee käyttäjältä syötetiedoston nimen:

lainaus:

Input file: products.input

Mikäli syötetiedostoa ei saa avattua luettavaksi, tulostetaan käyttäjälle teksti:

lainaus:

Error: the input file cannot be opened

Tämän jälkeen ohjelman suoritus päättyy ilman mitään muita tulosteita paluuarvoon EXIT_FAILURE.

Mikäli syötetiedosto saadaan avattua, mutta se ei ole määritelmän mukainen, esimerkiksi kenttiä ei ole neljää tai kentästä puuttuu arvo, tulostetaan käyttäjälle virheilmoitus Error: the input file has an erroneous line, ja lopetetaan ohjelman suoritus paluuarvoon EXIT_FAILURE. Esimerkiksi:

lainaus:

Input file: products-not-enough-fields.input
Error: the input file has an erroneous line

Ohjelma jäsentelee tiedostosta lukemansa rivit ja tallentaa eri kauppojen tuotetiedot sopivaan sisäiseen tietorakenteeseen. Tietorakenne on ohjelmoijan itsensä päätettävissä, kunhan se noudattaa kaikkia kohdassa Erityisvaatimukset asetettuja lisäehtoja. (Tämä kohta löytyy vähän alempaa tehtävänannosta.)

Kun tiedosto on luettu, ohjelma aloittaa varsinaisen suorituksensa. Aina kun käyttäjältä odotetaan syötettä, tulostetaan rivin alkuun kehote > (> ja välilyönti):

lainaus:

>

Tähän kehotteeseen ohjelman käyttäjä voi syöttää seuraavia käskyjä:

lainaus:

quit

Ohjelman suoritus päätty paluuarvoon EXIT_SUCCESS ilman, että ohjelma tulostaa mitään.

lainaus:

chains

Komento tulostaa aakkosjärjestyksessä allekkain kaikki tunnetut kauppaketjut. Esimerkiksi:

lainaus:

> chains
K-Citymarket
Prisma
S-Market
>

lainaus:

stores <kauppaketjun_nimi>

Komento tulostaa aakkosjärjestyksessä allekkain kaikki annetun kauppaketjun myymälät. Esimerkiksi:

lainaus:

> stores K-Citymarket
Lielahti
Linnainmaa
Pirkkala
Turtola
>

lainaus:

selection <kauppaketjun_nimi> <kaupan_sijainti>

Komento tulostaa tuotteen nimen mukaisessa aakkosjärjestyksessä kaikki annetun kauppaketjun ja sen myymälän tuotevalikoimaan kuuluvat tuotteet ja niiden hinnat. Esimerkiksi:

lainaus:

> selection K-Citymarket Turtola
sausage out of stock
yogurt 0.95
>

Hinnat tulostetaan kahden desimaalin tarkkuudella.

lainaus:

cheapest <tuotteen_nimi>

Komento tulostaa halvimman hinnan annetulle tuotteelle ja sen alle aakkosjärjestyksessä ketjut ja myymälät, joista tuotetta saa kyseisellä hinnalla. Ensijaisesti järjestetään ketjujen mukaan, ja jos ne ovat samoja, järjestetään myymälän mukaan. Tulostusasu käy ilmi seuraavasta esimerkistä:

lainaus:

> cheapest yogurt
0.90 euros
K-Citymarket Lielahti
Prisma Kaleva
Prisma Koivistonkyla
Prisma Lielahti
>

Hinta tulostetaan kahden desimaalin tarkkuudella.

Jos tuote on tuntematon (sitä ei siis esiinny minkään myymälän tuotevalikoimassa), tulostuu ilmoitus:

lainaus:

> cheapest vegemite
The product is not part of product selection
>

Jos tuote kuuluu ainakin joidenkin myymälöiden valikoimaan, mutta se on tilapäisesti loppu kaikista niistä, tulostetaan:

lainaus:

> cheapest chocolate
The product is temporarily out of stock everywhere
>

lainaus:

products

Komento tulostaa näytölle kaikkien kauppaketjujen kaikkien myymälöiden tuotevalikoimat yhtenä pitkänä listana, jossa tuotteet ovat aakkosjärjestyksessä, ja jokainen tuote on listalla vain kerran. Myös tuotteet, jotka ovat tilapäisesti lopussa, ovat mukana. Esimerkki valaisee asiaa parhaiten:

lainaus:

> products
apple
banana
cookies
⋮
mudcake
parsley
sausage
sunroot
⋮
yogurt
>

Huomaa, että tässä esimerkissä on selkeyden vuoksi käytetty useampia tuotenimikkeitä, kuin mitä aiemmassa esimerkkitiedostossa oli.

Kun käyttäjän syöttämä komento on suoritettu, ohjelma tulostaa kehotteen uudelleen. Tätä jatketaan kunnes käyttäjä syöttää komennon quit.

Attention
Edellä mainittiin paluuarvot EXIT_SUCCESS ja EXIT_FAILURE. Käytä niitä ainoastaan main-funktion paluuarvoina. Niitä ei pidä käyttää muiden funktioiden paluuarvoina, sillä todennäköisesti ne eivät muualla toimi odottamallasi tavalla.

Virhetilanteet

Mikäli käyttäjän syöte on virheellinen, tulostetaan virheeseen liittyvä virheilmoitus, minkä jälkeen ohjelma palaa odottamaan uutta syötettä. Ohjelman suoritus ei siis pääty käyttäjän virheelliseen syötteeseen.

Käyttäjän syöttäessä tuntemattoman komennon, tulostetaan seuraava virheilmoitus:

lainaus:

> hello
Error: unknown command: hello
>

Mikäli komennolle annetaan väärä määrä parametreja, tulostetaan virheilmoitus Error: error in command <komento>. Esimerkiksi:

lainaus:

> cheapest yogurt yogurt
Error: error in command cheapest
>

Komentoon selection liittyy kaksi erillistä virheilmoitusta. Mikäli käyttäjän syöttämää kauppaketjun nimeä ei löydetä, tulostetaan virheilmoitus Error: unknown chain name, ja mikäli syötettyä kaupan sijaintia ei löydetä, tulostetaan virheilmoitus Error: unknown store. Esimerkiksi:

lainaus:

> selection K-Market Lielahti
Error: unknown chain name
> selection Prisma Keskusta
Error: unknown store
>

Jos komennon molemmat parametrit (kauppaketju ja sijainti) ovat tuntemattomia, tulostetaan ensimmäistä parametria (kauppaketjua) koskeva virheilmoitus. Esimerkiksi:

lainaus:

> selection K-Market Keskusta
Error: unknown chain name

Jos komennolle stores annetaan kauppaketjun nimi, jota ei löydy, tulostetaan virheilmoitus:

lainaus:

> stores K-Market
Error: unknown chain name
>

Erityisvaatimukset

Seuraavia vaatimuksia on noudatettava, mikäli haluaa työstä hyväksytyn arvosanan:

Syötetiedoston saa lukea vain kerran ohjelman suorituksen aikana.

Minkä STL-tietorakenteen tai tietorakenteiden yhdistelmän valitsetkin työhösi, sinun on käytettävä ainakin yhtä map-rakennetta. Tämän map:in on oltava osana sitä rakennetta, johon tiedostosta luettu informaatio tallennetaan myöhempiä hakuja varten.

Kun tallennat tiedostosta luettuja tuotenimi–hinta-pareja STL-rakenteeseesi, sinun on käytettävä niiden tallentamiseen struct-rakennetta:

struct Product {
    string product_name;
    double price;
};

Tämän struct:in on siis oltava sen STL-rakenteen alkiotyyppinä, jonne tuotteiden nimiä ja hintoja tallennetaan.

Vihjeitä

Voit käyttää syötetiedoston ja käyttäjän antamien syötteiden paloitteluun viikkoharjoituksissa toteutettua split-funktiota. Toteutus on annettu myös tehtävän 6.2.2 Vektorin alkioiden summa koodipohjassa.
Muistathan, missä järjestyksessä rakenteiden map ja set alkiot käydään iteraattorilla läpi.
Riittää käyttää niitä STL:n säiliöitä, jotka on esitelty kurssimateriaalissa.
Tässä projektissa ei ole pakko käyttää luokkia (mutta toki niitä saa käyttää). Joka tapauksessa muista jakaa koodi sopivan kokoisiin funktioihin.
Ohjelman toteuttaminen osissa

Ohjelman toteutus muodostuu pääpiirteiltään kolmesta osasta:

tietorakenteen valinta ja tiedoston lukeminen tietorakenteeseen
käyttöliittymä
hakualgoritmit.
Mieti tarkasti, missä järjestyksessä nuo kannattaa toteuttaa, jotta voit toteuttaa ja testata ne yksi kerrallaan, ennen kuin siirryt seuraavaan vaiheeseen. Vähimmäisvaatimuksena versionhallinnan käyttämiselle on, että nämä kolme osaa on toteutettu omina committeinaan, mutta parempi tietenkin olisi olla enemmänkin committeja.