Programmeerimine keeles C++ 2023/24 kevad

STL andmestruktuurid I

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

• teab erinevaid andmestruktuure ja iteraatoreid
• tutvub põhjalikumalt järjestikuste andmestruktuuridega

Sisukord

Standardmallide teek STL (Standard Template Library)

C++ standardmallide teek STL sisaldab andmekogumite haldamiseks erinevaid võimalusi. Teek STL sisaldab neli peamist komponenti:

• andmestruktuurid (STL-is containers)
• iteraatorid
• algoritmid
• funktsiooniobjektid e funktorid (functors)

Andmestruktuurid

STL andmestruktuure võib liigitada järgmiselt:

• järjestikused
• assotsiatiivsed
• adapterid

Järjestikuste ja assotsiatiivsete andmestruktuuride erinevus:

• järjestikuses andmestruktuuris elemendid salvestatakse ja saadakse kätte nende asukoha järgi
• assotsiatiivses andmestruktuuris korral elemendid salvestatakse ja saadakse kätte võtme abil

Joonisel on toodud enamkasutatavad andmestruktuurid.

Järjestikused andmestruktuurid

Järjestikusteks dünaamilisteks andmestruktuurideks on vector, list, deque. Nende kasutamiseks tuleb sisse lugeda vastav päisefail.

NB! Järjestikune andmestruktuur on ka fikseeritud pikkusega array päisefailist <array>.

Vektor (vector)

Vektoreid käsitlesime põgusalt ka varem. Vektori loomiseks on palju erinevaid võimalusi, vaatame neist olulisemaid.

vector<double> v1; // tühi 'double' tüüpi vektor
vector<int> v2(5); // 5-elemendiga 'int' tüüpi vektor, elemendid nullid
vector<int> v3(5, 10); // 5-elemendiga 'int' tüüpi vektor, kõik elemendid on 10
vector<int> v4{5, 10}; // 2-elemendiga 'int' tüüpi vektor, elemendid 5 ja 10
vector<int> v5(v3); // vektori v5 loomine v3 baasil

Defineerime funktsiooni erinevat tüüpi vektorite ekraanile kuvamiseks. Elementide arvu saame funktsiooni size() abil.

template<typename T>
void print_vektor(const vector<T> &v) { // parameetriks 'T' tüüpi vektor viitena
    for (size_t i{}; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << '\n';
}

NB! Kui ei ole vaja andmestruktuuri muuta, siis lisame parameetrile const, mis garanteerib, et andmestruktuuri elemente ei muudeta. Katse siiski elemente muuta annab kompilaatori vea. Loome main funktsioonis mõned vektorid ja kuvame ekraanile

int main() {
    vector<double> v1; // tühi 'double' tüüpi vektor
    cout << "---\n";
    print_vektor(v1);
    vector<int> v2(5); // 5-elemendiga 'int' tüüpi vektor, elemendid nullid
    cout << "---\n";
    print_vektor(v2);
    vector<int> v3(5, 10); // 5-elemendiga 'int' tüüpi vektor, kõik elemendid on 10
    cout << "---\n";
    print_vektor(v3);
    vector<int> v4{5, 10}; // 2-elemendiga vektor, elemendid 5 ja 10
    cout << "---\n";
    print_vektor(v4);
    vector<int> v5(v3); // vektori v5 loomine teise v3 baasil
    cout << "---\n";
    print_vektor(v5);

---

---
0 0 0 0 0
---
10 10 10 10 10
---
5 10
---
10 10 10 10 10

Funktsioon print_vektor kasutab vektori läbimiseks indekseid. On võimalik ka lihtsam foreach tsükkel, mida saab kasutada ka teiste andmestruktuuride korral. Vaatame siin kahte varianti. Esimeses variandis tehakse igast elemendist koopia muutujasse el

template<typename T>
void print_vektor_foreach(const vector<T> &v) { // parameetriks vektor viitena
    for (auto el : v) { // el on koopia järjekordsest elemendist
        cout << el << " ";
    }
    cout << '\n';
}

Teises kasutame viidet järjekordsele elemendile auto& el, mis ei tee elemendist koopiat ja nõuab seetõttu vähem ressursse.

template<typename T>
void print_vektor_foreach_koopiata(const vector<T> &v) { // parameetriks vektor viitena
    for (auto& el : v) { // el on viide järjekordsele elemendile
        cout << el << " ";
    }
    cout << '\n';
}

Vektori elementide muutmiseks eemaldame päisest parameetri omaduse const:

void print_vektor(vector<T> &v)  

Elemente saab muuta ka foreach tsükliga, kui parameetriks on mittekonstantne vektor viitena

template<typename T>
void muuda_vektor_foreach(vector<T> &v) { // parameetriks vektor viitena
    for (auto& el : v) { // el on viide järjekordsele elemendile
        el += 2; // suurendame elementi kahe võrra
    }
} 

Katsetame:

vector<int> v = {5, 3, 6, 8};
muuda_vektor_foreach(v);
print_vektor_foreach_koopiata(v);

7 5 8 10

Iteraatorid

Andmestruktuurides (STL konteinerites) on defineeritud iteraatorid. Iteraatorid kasutavad päist <iterator>. Iteraatorit võib käsitleda viida (pointer) üldistusena. Iteraator on objekt, mis võimaldab juurdepääsu (viidata) andmestruktuuri elementidele sarnaselt viitadele. Enamiku iteraatorite korral saab kasutada operaatoreid * ja -> objektide kirjutamiseks või lugemiseks, operaatorit ++ iteraatori nihutamiseks ühe koha võrra edasi ning iteraatorite võrdlemist == või != abil. Iteraatoreid on palju erinevaid tüüpe. Olulisemad neist on kaht tüüpi iteraatorid:

• kahesuunalised (bidirectional) iteraatorid, mida saab nihutada operaatoritega ++ ja --.
• otsejuurdepääsuga (random access) iteraatorid, mis on kahesuunalised ja võimaldavad lisaks teostada etteantud positsioneerimist. On lubatud iteraatoriga täisarvu liitmine ja lahutamine, samuti iteraatorite lahutamine.

Igal andmestruktuuril (konteineril) on oma iteraatoritüüp, sarnaselt nagu igal andmetüübil on oma viidatüüp. Andmestruktuuridel vektor<T> ja array<T> on pidev (contiguous) iteraator ja andmestruktuuril list<T> on kahesuunaline (bidirectional) iteraator.

Vaatame iteraatorite kasutamist vektori näitel. Näiteks,

v.begin()

tagastab vektori v iteraatori, mis viitab vektori v esimesele elemendile ja

v.end()

tagastab vektori v iteraatori, mis viitab kohale peale vektori v viimast elementi. Järgmisele elemendile liikumiseks on vaja lihtsalt iteraatorit ühe võrra suurendada. Kirjutame ümber vektori elementide ekraanile kuvamise funktsiooni iteraatori abil.

template<typename T>
void print_vektor_iteraatoriga(const vector<T>& v) { // parameetriks vektor viitena
    auto algus = v.begin(); // algus on iteraator, mis viitab esimesele elemendile
    auto lõpp = v.end(); // lõpp on iteraator, mis viitab kohale peale viimast elementi
    while (algus != lõpp) {
        cout << *algus << " "; // viidatav element
        algus++; // nihutamine ühe elemendi võrra
    }
    cout << '\n';
}

Kirjutame sama funktsiooni kasutades for-tsüklit. Defineerime siin iteraatori kasutades tüüpi <T>eraldi. Funktsiooni parameetriks olev vektor ei saa olla enam konstantne.

template<typename T>
void print_vektor_iteraatoriga_for(vector<T>& v) {
    typename vector<T>::iterator it = v.begin(); // defineerime vektorile <T> tüüpi iteraatori
    for (; it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << '\n';
}

Järgmises tabelis on toodud tähtsamad tegevused vektoritega (kõik tegevused ei ole seotud iteraatoritega).

Järgnev programmilõik illustreerib põhiliste funktsioonide kasutamist vektorite korral

    vector<int> v = {5, 2, 6};
    cout << "Esialgne vektor: \n";
    print_vektor_foreach_koopiata(v);
    int& esimene = v.front(); // viide esimesele elemendile
    int& viimane = v.back(); // viide viimasele elemendile
    cout << "Esimene ja viimane element: " << esimene << " " << viimane << '\n';
    int& teine = v.at(1); // element indeksiga 1
    cout << "Element indeksiga 1: " << teine << '\n'; 
    cout << boolalpha << "v.empty(): " << v.empty() << '\n';
    v.pop_back(); // kustutab viimase elemendi
    cout << "Kustutati viimane element\n";
    print_vektor_foreach_koopiata(v);
    v.push_back(8); // lisab lõppu 8
    cout << "Lisati lõppu 8\n";
    print_vektor_foreach_koopiata(v);
    auto it = v.begin(); // viit (iteraator) esimesele elemendile
    it += 2; // iteraatori nihutamine kahe võrra paremale
    cout << "it += 2: iteraator viitab nüüd elemendile " << *it << '\n';
    it = v.insert(it, 3); // lisab iteraatoriga viidatud elemendiks 3
    cout << "Lisati iteraatori kohale element 3\n";
    print_vektor_foreach_koopiata(v);
    cout << "Iteraator viitab nüüd elemendile " << *it << '\n';
    it--; // viida nihutamine ühe võrra vasakule
    cout << "it--: iteraator viitab nüüd elemendile " << *it << '\n';
    it = v.erase(it); // kustutatakse iteraatoriga viidatud element
    cout << "Kustutati iteraatoriga viidatud element\n";
    print_vektor_foreach_koopiata(v);
    cout << "Iteraator viitab nüüd elemendile " << *it << '\n';
    auto suurus = v.size(); // elementide arv
    cout << "Vektori elementide arv: " << suurus << '\n';
    v.clear(); // eemaldab kõik elemendid
    cout << "Tühi vektor: " << '\n';
    print_vektor_foreach_koopiata(v);

Esialgne vektor:
5 2 6
Esimene ja viimane element: 5 6
Element indeksiga 1: 2
v.empty(): false
Kustutati viimane element
5 2
Lisati lõppu 8
5 2 8
it += 2: iteraator viitab nüüd elemendile 8
Lisati iteraatori kohale element 3
5 2 3 8
Iteraator viitab nüüd elemendile 3
it--: iteraator viitab nüüd elemendile 2
Kustutati iteraatoriga viidatud element
5 3 8
Iteraator viitab nüüd elemendile 3
Vektori elementide arv: 3
Tühi vektor:

Täpsemalt saab vektorite kohta uurida aadressil https://en.cppreference.com/w/cpp/header/vector

Iteraatorite kohta saab uurida lähemalt aadressil https://en.cppreference.com/w/cpp/iterator/iterator

Massiiv array

Fikseeritud suurusega massiiv array hoiab oma elemente mälus lineaarses järjestuses. Massiivi ei saa suurendada, elementidele on juurdepääs indeksi abil (operaator []) või funktsioonide at, front, back abil. Näiteid andmestruktuuriga array opereerimisest:

#include <array>
#include <iostream>
#include <string>
using namespace std;
int main() {
    array<int, 5> m1{{3, 4, 5, 1, 2}}; // 3, 4, 5, 1, 2
    for (auto &el: m1) cout << el << ' ';
    cout << '\n';
    array<int, 5> m2 = {1, 2, 3, 4, 5}; //1, 2, 3, 4, 5
    for (auto &el: m2) cout << el << ' ';
    cout << '\n';
    array<string, 2> m3 = {"kaks", "kolm"};
    for (auto &el: m3) cout << el << ' ';
    cout << '\n';
    // Täidame m2 10-tega
    m2.fill(10);
    for (auto &el: m2) cout << el << ' ';
    cout << '\n';
    return 0;
}

3 4 5 1 2 
1 2 3 4 5 
kaks kolm 
10 10 10 10 10 

Põhilised erinevused C++ andmestruktuuride vector ja array vahel:

Vectorit (vector) on parem kasutada elementide sagedase lisamise ja kustutamise korral, samas massiiv array sobib olukorras, kus on vajalik elementidele sagedane juurdepääs.

Täpsemalt saab array kohta uurida aadressil https://en.cppreference.com/w/cpp/header/array

Kahe otsaga järjekord deque

Kahe otsaga järjekord deque toetab sarnaselt vektoriga efektiivset elemendi lisamist ja kustutamist nii alguses kui ka lõpus. deque toetab ka otsejuurdepääsu elementidele.

Kahe otsaga järjekorra deque toimingud on peaaegu samad, mis vektori puhul, mõne väikese erinevusega. Andmestruktuuril deque ei ole erinevalt vektorist mahutavuse (capacity) mõistet, sest STL standardi järgi ei pea elemente salvestama kõrvuti. Andmestruktuur deque pakub lisaks funktsioonile push_back ka funktsioone push_front, pop_front() ja pop_back.

Näide deque elementide lisamisest, asendamisest ja kustutamisest:

#include <iostream>
#include <deque>
using namespace std;
template <typename T>
void tryki(deque<T>* d){
    for (T el: *d) {
        cout << el << " ";
    }
    cout << '\n';
}
int main() {
    deque<int> d1 = {1, 2, 3, 4};
    d1.insert(d1.begin() + 2, 25); // 1, 2, 25, 3, 4
    d1.pop_front(); // 2, 25, 3, 4
    d1.erase(d1.begin() + 1); // 2, 3, 4
    d1.push_front(11); // 11, 2, 3, 4
    d1[1] = 5; // 11, 5, 3, 4
    d1.at(0) = 12; // 12, 5, 3, 4
    d1.front() = 10; // 10, 5, 3, 4
    d1.back() = 20; // 10, 5, 3, 20
    tryki(&d1);
    return 0;
}

10 5 3 20 

Täpsemalt saab deque kohta uurida aadressil https://en.cppreference.com/w/cpp/container/deque

Listid list ja forward_list

List list paigutab oma elemendid topeltahelana (doubly linked list), aga forward_list paigutab elemendid tavalise ahelana (linked list). Kumbki ei paiguta elemente mällu järjest. Seetõttu ei ole listide elemente võimalik kätte saada indeksi abil, st operaatorit operator[] ei toetata. Elemendi kättesaamiseks käiakse list elementhaaval läbi alates algusest (forward_list), st saab kasutada ainult ühesuunalisi iteraatoreid; seevastu list toetab ka kahesuunalisi iteraatoreid, st juurdepääs on andmestruktuuri mõlemast otsast. Kui järg on sobiva elemendi peal, siis elementide lisamine ja kustutamine on lihtne, sest vaja on tõsta vaid paar viita ümber.

Listi keskel olevat elementi saab kätte ainult iteraatori abil. Vaatame listi kasutamist näite abil. Kui listimuutuja on viit, siis tuleb list initsialiseerida käsu new abil ja hiljem mälu vabastada.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

void tryki(list<int>* l){
    list<int>::iterator it;
    for (it = l->begin(); it != l->end(); ++it)
        cout << ' ' << *it;
    cout << '\n';
}
void täida(list<int>* l){
    for (int i = 0; i < 5; ++i) {
        l->push_back(i);
    }
    cout << '\n';
}
int main() {
    list<int> l1;
    list<int> l2;
    list<int>* l3 = new list<int>; 

    for (int i = 0; i < 5; ++i) {
        l1.push_back(i * 2); // 0 2 4 6	8
        l2.push_front(i * 3); // 12 9 6 3 0
    }

    täida(l3); // 0 1 2 3 4
    cout << "List 1 (l1) on : ";
    tryki(&l1); // 0 2 4 6 8

    cout << "List 2 (l2) on : "; // 12 9 6 3 0
    tryki(&l2);

    cout << "List 3 (l3) on : "; // 0 1 2 3 4
    for (list<int>::iterator it = l3->begin(); it != l3->end(); ++it) {
       cout << ' ' << *it;
    }
    cout << '\n';

    cout << "l1.front() : " << l1.front() << '\n'; // 0
    cout << "l1.back() : " << l1.back() << '\n'; // 8

    cout << "l1.pop_front() \n";
    l1.pop_front(); // eemaldab algusest 0
    cout << "l1.pop_back() \n";
    l1.pop_back(); // eemaldab lõpust 8
    cout << "List 1 (l1) on : ";
    tryki(&l1); // 2 4 6
    delete l3;
    return 0;
}

List 1 (l1) on : 0 2 4 6 8
List 2 (l2) on : 12 9 6 3 0
List 3 (l3) on : 0 1 2 3 4
l1.front() : 0
l1.back() : 8
l1.pop_front() 
l1.pop_back() 
List 1 (l1) on : 2 4 6

Järgmises tabelis on kokku võetud põhilised operatsioonid järjestikustel andmestruktuuridel

Enesetestid

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