Kihagyás

11. gyakorlat

Adatszerkezetek

Gyakran a problémák megoldása során különféle adatszerkezetekre van szükségünk annak érdekében, hogy hatékonyan, könnyen kevés kódolással megoldhassuk a problémát. Ilyen adatszerkezetek közül mutatunk be párat a leggyakoribbak közül.

A bemutatott adatszerkezetek osztályokként vannak megvalósítva. Mindegyikre igaz, hogy a kezelt típust előre meg kell adnunk. Vagyis ha int-et vagy Kurzus-t szeretnénk használni, azt előre meg kell adnunk. Ezek a megvalósítások úgynevezett template használatával készültek, mely nem része a gyakorlat anyagának, de jobb tudni róla. Számunkra ami fontos, a template hasonló a Java generikushoz és ha hibázunk hosszú fordítási üzenetet képes generálni a rendszer, melyből nehezebb kideríteni a problémát az eddig megszokottnál. Erre példa itt található.

std::set

Halmaz, egy elem csakis egyszer fordulhat elő. A tartalmazott elemek nem módosíthatók (const-ként tároltak), de törölhetők. Minden elem rendezve kerül tárolásra egy fában, így a rendezést biztosítanunk kell. A rendezés megvalósításához szükségünk van a operator<-re.

Használatához include-olni kell a set headert Példa létrehozására és használatára:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <set>

class Kurzus {
private:
    int id;
public:
    Kurzus( int id ) : id(id) {}
    int get_id() const { return id; }
    bool operator<( const Kurzus& kurzus ) const { return this->id < kurzus.id; }
};

bool kurzus_letezik( const std::set<Kurzus>& kurzusok, Kurzus kurzus ) {
    return kurzusok.find( kurzus ) != kurzusok.end();
}

/// a contains csak cpp20-al elérhető.
bool kurzus_letezik2( const std::set<Kurzus>& kurzusok, Kurzus kurzus ) {
    return kurzusok.contains( kurzus );
}

int main() {

    std::set<Kurzus> kurzus_halmaz;
    Kurzus k1( 1 );
    Kurzus k2( 2 );
    Kurzus k3( 3 );
    Kurzus k12( 1 );

    kurzus_halmaz.insert( k1 );
    std::cout << kurzus_halmaz.size() << std::endl;
    kurzus_halmaz.insert( k2 );
    std::cout << kurzus_halmaz.size() << std::endl;
    kurzus_halmaz.insert( k3 );
    std::cout << kurzus_halmaz.size() << std::endl;
    kurzus_halmaz.insert( k12 );
    std::cout << kurzus_halmaz.size() << std::endl;

    int kurzus_id = 1; // probaljuk meg pl. 4-es id-val.
    Kurzus keresendo( kurzus_id );
    if ( kurzus_letezik( kurzus_halmaz, keresendo ) ) {
        std::cout << "A kurzus letezik, id: " << kurzus_id << std::endl;
    } else {
        std::cout << "A kurzus nem letezik, id: " << kurzus_id << std::endl;
    }

    kurzus_id = 2; // probaljuk meg pl. 4-es id-val.
    Kurzus keresendo2( kurzus_id );
    if ( kurzus_letezik2( kurzus_halmaz, keresendo2 ) ) {
        std::cout << "A kurzus letezik, id: " << kurzus_id << std::endl;
    } else {
        std::cout << "A kurzus nem letezik, id: " << kurzus_id << std::endl;
    }

    std::cout << "Az eddig meglevo kurzusok:" << std::endl;
    for( Kurzus k : kurzus_halmaz ) {
        std::cout << "  - " << k.get_id() << std::endl;
    }

    Kurzus torlendo( 3 );
    kurzus_halmaz.erase( torlendo );

    std::cout << "Kurzusok torles utan:" << std::endl;
    for( auto& k : kurzus_halmaz ) {
        std::cout << "  - " << k.get_id() << std::endl;
    }
}

Példa magyarázata

std::set<Kurzus> kurzus_halmaz; A halmaz egy osztály, így példányosítanunk kell. Ami érdekes, hogy a típus megadásánál <> jelek között egy másik típus található. Így tudjuk megadni, hogy milyen elemeket tervezünk a halmazba rakni.

kurzus_halmaz.insert( k1 ); Egy elem beillesztése a halmazba. Természetesen nem rakhatunk bele más típust, csakis amit megadtunk.

kurzus_halmaz.size() A halmazban található elemek számát adja meg.

kurzus_halmaz.insert( k12 ); Habár insert-et hívunk, a méret nem változik, hiszen ilyen elemet már tároltunk, nem adódik újra hozzá.

kurzusok.contains( kurzus ); C++20 óta lehetőségünk van a contains metódus használatára, mely egy olyan típusú elemet vár, mint amilyet a halmazban tárolunk és megmondja, hogy az adott elem, már megtalálható-e a halmazban. Bool értékkel tér vissza.

kurzusok.find( kurzus ) != kurzusok.end(); C++20 előtt a find metódust használhattuk. Ez nem bool értékkel tér vissza, hanem egy olyan elemmel, mely megadja, hol található a keresett elem a halmazon belül (iterátor). Ha található ilyen elem, akkor egy valid iterátort kapunk, ha nem, akkor egy iterátort kapunk, mely a halmaz végét jelenti. Ezt a vég elemet az end metódus hívással érhetjük el. Tehát find metódussal lekérjük az elem pozícióját és ha az nem a végelem, akkor megtalálható a halmazban.

for( Kurzus k : kurzus_halmaz ) A halmaz elemeit bejárhatjuk itertárotok használatával, begin() és end(), azonban így a halmaz által definiált bejárással az összes elemet iterálhatjuk kevesebb kód írásával. Ekkor egy másolatot kapunk a tárolt elemről. Ha a forciklusban nem Kurzus-t, hanem Kurzus&-t írnánk, akkor nem másolatot kapnánk a tárolt elemről, hanem egy referenciát arra. Fontos, hogy referencia használatakor a táorolt elemre kapunk referenciát! Emlékezzünk, azok mindig cont elemek! Helyesen for ( const Kurzus& kurzus : kurzus_halmaz )-t kell használnunk!

for( auto& k : kurzus_halmaz ) Ez a megvalósítás nagyon hasonlít az előbbihez, azonban itt nem kell kiírnunk a típust, hiszen az auto használatával a fordító kikövetkezteti azt.

kurzus_halmaz.erase( torlendo ); A törlés-t az erase metódussal tehetjük meg.

std::vector

A vector több elem tárolására alkalmas edott sorrendben. Egy elem többször is előfordulhat. Előző gyakorlatok során használtunk dinamikus tömböket, erre megvalósítás a vector.

Használatáoz include-olni kell a vector header-t.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>

struct Kurzus {
  int id;
};

int main() {
    std::vector<Kurzus> kurzusok;
    Kurzus k1 { .id = 1 };
    Kurzus k2 { .id = 2 };

    kurzusok.push_back( k1 );
    kurzusok.push_back( k2 );
    kurzusok.push_back( k1 );
    std::cout << kurzusok.size() << std::endl;

    std::cout << "Az egyes indexen lévő kurzus ID-ja: " << kurzusok[ 1 ].id << std::endl;

    std::cout << "Kurzusok:" <<std::endl;
    for ( auto kurzus : kurzusok ) {
        std::cout << "  - " << kurzus.id <<std::endl;
    }

    for ( auto& kurzus : kurzusok ) {
        kurzus.id = 42;
    }

    std::cout << kurzusok.at( 0 ).id << std::endl;
}

Példa magyarázata

std::vector<Kurzus> kurzusok; A vector is egy osztály, ezt is példányosítani kell és itt is meg kell adni, hogy milyen típusú elemeket szeretnénk tárolni.

kurzusok.push_back( k1 ); A vector végére helyezi el a kapott elemet. Több beszúrási lehetőség is van, azonban a vector végére szúrni konstans időben lehet.

kurzusok[ 1 ].id Akárcsak a megszokott tömböknél, itt is van lehetőségünk az elemeket index alapján elérni.

kurzusok.at( 0 ).id Ezzel a hívással úgyanúgy indexelhetjük az elemeket, azonban ekkor a megadott index validálásra kerül. hibás indexeléskor std::out_of_range keletkezik.

for ( auto& kurzus : kurzusok ) Akárcsak a set esetében itt is elérhetjük for ciklusban az elemeket. Akár másolattal akár referenciával, azonban itt figyeljünk arra, hogy itt nem kell const-ként hivatkozni rájuk, akár módosíthatók is az eredeti elemek!

std::map

A map kulcs éték tárolására alkalmas. Minden kulcs egyedi érték kell legyen!

Példa: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <map>

struct Kurzus {
    std::string nev;
    Kurzus( const std::string& nev ) : nev( nev ) {}
    Kurzus() = default;
    bool operator<( const Kurzus k ) const { return nev.length() < k.nev.length(); }
};

int main() {
    std::map<std::string, Kurzus> oktatok_kurzusa;
    Kurzus prog2{ "prog2" };
    Kurzus prog1{ "prog1" };
    std::string prog2_eloado = "C++ elaodo";
    std::string prog1_eloado = "Java eloado";

    oktatok_kurzusa[ prog2_eloado ] = prog2;
    oktatok_kurzusa[ prog1_eloado ] = prog1;

    std::cout << prog2_eloado << " kurzusa: " << oktatok_kurzusa.at( prog2_eloado ).nev << std::endl;
    std::cout << prog1_eloado << " kurzusa: " << oktatok_kurzusa[ prog1_eloado ].nev << std::endl;

    Kurzus prog3{ "prog3" };
    std::string prog3_eloado = "Carbon eloado";

    if ( oktatok_kurzusa.find( prog1_eloado ) != oktatok_kurzusa.end() ) {
        std::cout 
        << prog1_eloado << "-nak van oraja, meghozza: " 
        << oktatok_kurzusa.at( prog1_eloado ).nev 
        << std::endl;
    }

    for ( auto& element : oktatok_kurzusa ) {
        std::cout
        << "Oktato: " << element.first
        << "Ora: " << element.second.nev 
        << std::endl;
    }

    // c++17 ota hasznalhato
    for ( auto& [oktato, ora] : oktatok_kurzusa ) {
        std::cout
        << "Oktato: " << oktato
        << "Ora: " << ora.nev 
        << std::endl;
    }
}

Példa magyarázata

std::map<std::string, Kurzus> oktatok_kurzusa; A map is egy osztály, így ezt is példányosítani kell, de most nem egy, hanem két extra típust is meg kell adnunk: az első a kulcsok típusa a második a tárolt értékeke típusa.

oktatok_kurzusa[ prog2_eloado ] = prog2; Az indexer operátorral egy kulcshoz egy adott értéket rendelhetünk. Fontos, ha az adott kulcs nem létezett, akkor egy új elem kerül beszúrásra. Kulcs tárolt értékének frissítésére is alkalmas. Új érték beszúrásakor a default konstruktorra szükség van!

oktatok_kurzusa[ prog1_eloado ].nev Az indexer operátor nemcsak beillesztésre / frissítésre alkalmas, lekérdezésre is használhatjuk. Ezzel vigyázzunk, hiszen, ha olyan értéket kérünk le, mely nem létezik, a default konsturktorral alkotott érték beszúrásra kerül az új kulcshoz!

oktatok_kurzusa.at( prog2_eloado ).nev Lekérdezés biztonságosabb módja. Így nem kerül új érték beszúrásra, azonban kivétel dobódhat. Meghívása előtt érdemes ellenőrizni, hogy elérhető-e az adott elem vagy kivételre felkészülni!

oktatok_kurzusa.find( prog1_eloado ) != oktatok_kurzusa.end() Hasonlóan a set-hez itt is a find egy iterátort ad vissza, s akkor található meg egy elem, ha az a map NEM utolsó utáni (vég) eleme.

for ( auto& element : oktatok_kurzusa ) Az elemek egy map-nél is bejárhatók, azonban ekkor két értéket kapunk, hiszen kulcs-érték párról beszélünk. a kapott element egy pair, aminek van first és second eleme. Erre példa a következő magyarázatban található.

element.first és element.second.nev Az iterálás során kapott objektum egy pair, melyben a first adattagban a map-ben tárolt KULCS található. A second attribútumban található a VALUE. FIRST -> kulcs SECOND -> érték

for ( auto& [oktato, ora] : oktatok_kurzusa ) C++17 óta az előbbi iterációt egyszerűsíthetjük. Ekkor nem kell egy pair first és second attribútumát használnunk, automatikusan a kulcsot is és az értéket is egy objektumhoz rendelhetjük. Jelen esetben az oktato objektumba kerül az aktuális KULCS és az ora objektumba az ÉRTÉK.

Iterátorok

A fentebbi példákban több példát is láthattunk arra, hogy for ciklussal be tudjuk járni az egyes tárolókat. Ezek a bejárások azt biztosítják, hogy minden elemre sor kerül. A háttérben iterátorok használata történik.

Iterátor: Olyan objektum, ami segítségével egy tároló elemein képesek vagyunk végigjárni. Az iterátor típusától függően támogathatja az előre, vissza irányba léptetést és a tetszőleges elemmel való léptetést. Az iterátor nem az egyes elemeket jelenti, csak az adott elemet reprezentálja. A konkrét érték elérése érdekében az iterátort dereferálni kell!

Iterátorok hazsnálatakor vannak bizonyos elemek, melyeket megkülönböztetünk. Ilyen a bejárás során az első elem és az utolsó elem. Szokványos bejárás során az első elemet reprezentáló iterátort a begin metódussal a tároló végét reprezentáló iterátort az end metódussal kérhetjük el.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <iostream>
#include <vector>
int main() {
  std::vector<int> v_int = { 1, 4, -8, 33 };
  std::cout << *v_int.begin() << std::endl; // a dereferalas utan mar az erteket iratjuk ki.
  *v_int.begin() = 77; // iteratorok segitsegevel erteket is atirhatunk egyes taroloknal. lsd. cppreference alapjan.
  for ( int ertek : v_int ) {
    std::cout << ertek << std::endl;
  }
}

Az iterátorokkal való bejárás során változót kell létrehozni amivel elérhetjük az elemeket. Ennek a változónak a típusa függ a használt tárolótól, az abban tárolt elemtől. Különféle tárolók iterátorai más - más műveletet engedhetnek meg, de a ++ operátort legtöbb esetben használhatjuk. Ennek segítségével a következő elemre referáló iterátort kapjuk meg. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <iostream>
#include <vector>
int main() {
  std::vector<int> v_int = { 1, 4, -8, 33 };
  std::vector<int>::iterator it; // ez a tipusa az iteratornak.
  for ( it = v_int.begin(); it != v_int.end(); ++it ) { 
    // addig lepkedunk mig az iterator nem a tarolo vege iteratorral egyezik meg.
    std::cout << *it << std::endl; // az iteratort dereferalni kell
  }

  auto it2 = v_int.begin(); // az iterator tipusanak megadasakor hasznalhato az auto, ezzel roviditve a kodot.
}

Gyakorló kérdések

A set példájánál használható-e a következő kódrészlet? Miért? Miért nem? kurzus_halmaz.insert( 5 ); // Kurzus halmazba egy intet szúrnánk be.

Gyakori hibák compile error logokkal

TODO

Utolsó frissítés: 2022-11-25 13:18:07