Kihagyás

vector, set, map

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 az általuk tárolt/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.

Halmaz (std::set)

A halmazban 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. Amennyiben egy adattípusra nem definiált a rendezés reláció, és az adattípust setben szeretnénk tárolni, fordítási hibát kapunk.

A halmaz 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 getId() const { return id; }
    bool operator<( const Kurzus& kurzus ) const { return this->id < kurzus.id; }
};

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

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

int main() {

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

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

  int kurzus_id = 1; // probaljuk meg pl. 4-es id-val.
  Kurzus keresendo( kurzus_id );
  if ( kurzusLetezik( kurzusHalmaz, 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 ( kurzusLetezik2( kurzusHalmaz, 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 : kurzusHalmaz ) {
    std::cout << "  - " << k.getId() << std::endl;
  }

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

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

Kimenet

1
2
3
3
A kurzus letezik, id: 1
A kurzus letezik, id: 2
Az eddig meglevo kurzusok:
    - 1
    - 2
    - 3
Kurzusok torles utan:
    - 1
    - 2

Példa magyarázata

std::set<Kurzus> kurzusHalmaz; 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.

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

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

kurzusHalmaz.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 : kurzusHalmaz ) A halmaz elemeit bejárhatnánk itertárotok használatával is, begin() és end() metódusok segítenek a kezdő és végelemek kezelésében, ugyanakkor az iterátorral rendelkező adattárolók bejárása egyszerűbben is megadható az itt megadott bejárással. Í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árolt elemre kapunk referenciát! Emlékezzünk, azok mindig const elemek! Ezért helyesen for ( const Kurzus& kurzus : kurzusHalmaz )-t kell használnunk!

for( auto& k : kurzusHalmaz ) 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.

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

Vektor (std::vector)

A vector több elem tárolására alkalmas, adott sorrendben. Egy elem többször is előfordulhat.

Használatához include-olni kell a vector headert.

 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
class Kurzus {
public: 
  int id;
};

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

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

  std::cout << "Az egyes indexen levo 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;
}

Kimenet

3
Az egyes indexen levo kurzus ID-ja: 2
Kurzusok:
  - 1
  - 2
  - 1
42

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!

Leképezés (std::map)

A map kulcs érté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
49
50
#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++ eloado";
  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;
  }
}

Kimenet

C++ eloado kurzusa: prog2
Java eloado kurzusa: prog1
Java eloado-nak van oraja, meghozza: prog1
Oktato: C++ eloado Ora: prog2
Oktato: Java eloado Ora: prog1
Oktato: C++ eloado Ora: prog2
Oktato: Java eloado Ora: prog1

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ékek típusa. A kulcs típus elemei kell, hogy rendelkezzenek egy rendezési relációval. Primitív típusoknál ez nyilván adott, saját típusoknál nekünk kell erről gondoskodni.

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 ennek hiányában 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.

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 elemre mutat. A konkrét érték elérése érdekében az iterátort dereferálni kell, amiből most számunkra annyit kell érteni és tudni, hogy az iterátor neve elé kell tenni egy *-t, és így kapjuk meg az értéket, amire az iterátor hivatkozik!

Iterátorok haszná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;
  }
}

Kimenet

1
77
4
-8
33

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.
}

Kimenet

1
4
-8
33

Utolsó frissítés: 2024-08-01
Létrehozva: 2020-11-16