Programming in C++ 2023/24 spring

STL andmestruktuurid II

Pärast selle praktikumi läbimist üliõpilane

• teab assotsiatiivseid andmestruktuure nagu hulk (set) ja sõnastik (kujutus) (map)
• oskab ülesannete lahendamisel kasutada STL andmestruktuure set ja map ja nende modifikatsioone

Sisukord

Assotsiatiivsed (associative) andmestruktuurid

Assotsiatiivsed andmestruktuurid STL teegis on map ja set. Mõlemast on kaks varianti - unikaalsete võtmetega ja võimalike korduvate võtmetega. Võtmed on neis järjestatud. Lisaks on olemas kõigist eelnevaist järjestamata võtmetega variandid.

Hulgad (set ja multiset)

STL konteineris on set ja multiset andmestruktuurid, mis võimaldavad elementide kiiret otsimist. Hulgas set sisalduvad elemendid on unikaalsed, st korduvaid elemente ei saa olla. Andmestruktuuride set ja multiset erinevus seisneb selles, et viimane võimaldab ka korduvaid elemente.

Hulgas set ja multiset saab hoida objekte, millel on defineeritud operaator <. Näiteks koodijupp

struct Punkt {
    double x, y;
};
int main(){
    Punkt p1{3.1, 4.2};
    Punkt p2{2.5, 3.6};
    set <Punkt> punktid{p1, p2}; // viga
    return 0;
}

annab vea, sest objekte p1 ja p2 ei saa võrrelda. Defineerime punktide võrdlemise kohavektori pikkuse abil (lisada tuleb ka päis <cmath>):

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
struct Punkt {
    double x, y;
    double pikkus(){
        return sqrt(x*x + y*y);
    }
};
bool operator<(Punkt p1, Punkt p2){ // punktide võrdlemine
    return p1.pikkus() < p2.pikkus();
}
int main() {
    Punkt p1{3.1, 4.2};
    Punkt p2{2.5, 3.6};
    set <Punkt> punktid{p1, p2};
    for (const Punkt punkt : punktid) {
        cout << "(" << punkt.x << ", " << punkt.y << ")\n";
    }

    return 0;
}

(2.5, 3.6)
(3.1, 4.2)

Kiire otsimise võimaldamiseks on set ja multiset STL-s sisemiselt implementeeritud kahendpuuna. See tähendab, et sisestamisel set ja multiset elemendid sorditakse. Erinevalt vektorist, kus igal elemendil on kindel asukoht, kuhu saab kirjutada suvalise teise elemendi, hulgas antud kohal olevat elementi ei saa asendada teise elemendiga. Sortimiskriteeriumi saab vajadusel hulga loomisel ette anda.

Tabelis on toodud enamkasutatavamaid operatsioone hulkadega.

Järgmises programmilõigus moodustatakse hulk s elementidest, mis on char tüüpi.

    set<char> s;
    s.insert('A'); //hulka lisamine
    s.insert('D');
    s.insert('D'); // 'D' juba olemas
    s.insert('C');
    s.insert('C');
    s.insert('B');
    cout << "Hulga s elemendid:\n";
    set<char>::iterator it; //iteraator
    for (it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << '\n';
    cout << "Kas hulk sisaldab 'C': ";
    if (s.find('C') == s.end()) { // kas tagastatav iteraator viitab hulga lõppu
        cout << " ei \n";
    } else {
        cout << " jah \n";
    }
    cout << "Eemaldame 'C'\n";
    s.erase('C');
    for (it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << '\n';
    cout << "Kas hulk sisaldab 'C': ";
    if (s.find('C') == s.end()) {
        cout << " ei \n";
    } else {
        cout << " jah \n";
    }

Hulga s elemendid:
A B C D
Kas hulk sisaldab 'C':  jah
Eemaldame 'C'
A B D
Kas hulk sisaldab 'C':  ei

Olgu meil järgmine ülesanne.

Mitu korda on vaja keskmiselt täringut visata, et visatud number tuleks teist korda? Ülesande lahendamiseks koostame funktsiooni veereta täringu viskamiseks, teise funktsiooni mitmes, mis tagastab, mitmendal viskel tuli juba visatud tulemus ja peameetodis arvutame katsete keskmise. Antud näites kasutame keskmise arvutamiseks vastavalt 1000, 5000 ja 10000 katset.

#include <iostream>
#include <random>
#include <set>
#include <ctime>
using namespace std;
int veereta(int n, default_random_engine& genereerija);
size_t mitmes(int n, default_random_engine& genereerija);
int main() {
    default_random_engine genereerija(time(0));
    set<int> iteratsioonid{1000, 5000, 10000};
    int n{365}; // täringu tahkude arv
    srand(time(0)); // seeme
    for (size_t iteratsioone: iteratsioonid) {
        size_t kokku{};
        for (size_t k = 0; k < iteratsioone; ++k) {
            kokku += mitmes(n, genereerija); //
        }
        cout << "Iteratsioonide arv: " << iteratsioone << endl;
        cout << "Keskmine sammude arv: " << double(kokku) / iteratsioone << '\n';
    }
    return 0;
}
int veereta(int n, default_random_engine& genereerija) {
    uniform_int_distribution<int> jaotus(1,n);
        return jaotus(genereerija);
    }

size_t mitmes(int n, default_random_engine& genereerija) {
    set<int> veeretatud{}; // hulk visete hoidmiseks
    while (true) {
        int vise = veereta(n, genereerija);
        if (veeretatud.count(vise)) { // kas vise on hulgas
            return veeretatud.size() + 1;
        }
        veeretatud.insert(vise); // viske lisamine hulka
    }
}

Iteratsioonide arv: 1000
Keskmine sammude arv: 3.798
Iteratsioonide arv: 5000
Keskmine sammude arv: 3.7438
Iteratsioonide arv: 10000
Keskmine sammude arv: 3.7648

Korrates sama katset, aga võttes täringu tahkude arvuks 365, saame midagi sarnast:

Iteratsioonide arv: 1000
Keskmine sammude arv: 25.063
Iteratsioonide arv: 5000
Keskmine sammude arv: 24.312
Iteratsioonide arv: 10000
Keskmine sammude arv: 24.8302

Ehk siis, statistiliselt piisab 25 inimesest ühes ruumis, et kahel neist võiks olla samal päeval sünnipäev. Seda nimetatakse ka "sünnipäeva paradoksiks", vt https://betterexplained.com/articles/understanding-the-birthday-paradox/

Sõnastikud (<map> ja <multimap>)

Sõnastik (ka kujutus) on assotsiatiivne andmestruktuur, mida on kõige lihtsam käsitleda sõnaraamatu või telefoniraamatu üldistusena. Konkreetse võtme (sõna või isiku nime) korral saab seotud väärtuse salvestada ja hiljem kiiresti pärida (definitsioon või telefoninumber). Sõnastiku map võtmed peavad olema unikaalsed, aga multimap võtmed võivad ka korduda. Sõnastiku väärtused ei pea olema unikaalsed. Võtmed on sõnastikus kas sorditud (map) või sortimata unordered_map:

Analoogiliselt set<T> ja unordered_set<T> on teegis STL kaks erinevat andmestruktuuri: map<Key, Value> ja unordered_map<Key, Value>. Erinevalt enamikust teistest andmestruktuuridest vajab sõnastik vähemalt kaht malli tüüpi argumenti, millest üks määrab võtmete tüübi ja teine määrab väärtuste tüübi, nt

map<string, int> m_sõnastik{};

Sõnastikku saab luua ka koos sisuga (võti-väärtus paarid on eraldi loogelistes sulgudes):

map<int, string> m_keeled={    
                           {1, "Javascript",},
                           {2, "Python",},
                           {3, "Go",},
                           {4, "Java",},
                      };

Sõnastikku saab paare lisada mitmel viisil, nt indekseerides m_keeled[5] = "C++" või kasutades funktsiooni insert. Järgmises koodinäites kõik kolm käsku teevad sama asja - lisavad sõnastikku ühe kirje. Kui selline kirje on juba olemas, ei tehta midagi.

m_keeled[5] = "C++";
m_keeled.insert({5, "C++"});
m_keeled.insert(pair<int, string>(5, "C++"));

Viimases käsus on kasutatud malliklassi std::pair<type, type. STL sõnastikus salvestatakse võti-väärtus paarid kasutades malliklassi std::pair<const K, V, kus K on võti ja V on väärtus. Järgmises näites on kasutatud indekseerimist.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    map<string, unsigned long long> telefoniraamat;
    telefoniraamat["Kaja"] = 372'888'1111;
    telefoniraamat["Jüri"] = 372'888'2222;
    cout << "Kaja telefon on " << telefoniraamat["Kaja"] << '\n';
    cout << "Jüri telefon on " << telefoniraamat["Jüri"] << '\n';
    return 0;
}

Kaja telefon on 3728881111
Jüri telefon on 3728882222

Sõnastikku on mugav kasutada sagedustabeli koostamiseks. Järgmises programmilõigus loendame klaviatuurilt sisestatud sõnu:

map<string, int> m_loendaja{}; // tühi sõnastik
string sõna{};
while (cin >> sõna) {
    ++m_loendaja[sõna]; // kas lisab sõnastikku {võti, 1} või suurendab väärtust ühe võrra
}
// tulemused ekraanile
for (auto& paar : m_loendaja) // paar on pair<K, V> isend; võti on isendiväljal @@first@@ ja väärtus @@second@@  
    cout << paar.first << " esines " << paar.second <<
    ((paar.second > 1) ? " korda" : " kord") << '\n'; // siin on tingimuslause

Kes
aias
kes
aias
^D
Kes esines 1 kord
aias esines 2 korda
kes esines 1 kord

Klaviatuurilt info lõpetamise tunnus on ^D. Keskkonnas CLion tuleb sisendi lõppu eraldi seadistada. Näites on kasutatud lühivormi ++sõnade_loendaja[sõna] väärtuse suurendamiseks ühe võrra. See käsk on samaväärne programmilõiguga

if (m_loendaja.count(sõna) > 0){
    m_loendaja[sõna] += 1;
}
else{
    m_loendaja[sõna] = 1;
}

Sõnastikku saab läbida mitmel erineval viisil. Vaatame veel sõnastiku läbimist iteraatori abil. Sõnastiku peal saab tekitada iteraatori, mis on viit (pointer )

for (auto it = m_loendaja.begin(); it != m_loendaja.end(); ++it) {
    cout << it->first << " esines " << it->second <<
         ((it->second > 1) ? " korda" : " kord") << '\n';
}

Järgmises tabelis on toodud põhifunktsioonid sõnastikul m.

Enesetestid

NB! Enesetestides eeldame, et on kasutatud standardnimeruumi (using namespace std;)