Kihagyás

12. gyakorlat

Algoritmusok

Az előző anyagban a standard template library (stl) adatszerkezeteinek egy részét és az azokon definiált algoritmusokat vettük végig. Ebben az anyagrészben az stl algoritmusai közül veszünk sorra párat. A függvények, melyek egy - egy algoritmust valósítanak meg, gyakran iterátorokkal, fix értékekkel esetleg olyan függvényekkel együtt használhatók, mleyek egy döntést határoznak meg. Mivel iterátorok használatakor gyakran első és utolsó elemet határozunk meg, fontos, hogy milyen intervallumon dolgoznak az algoritmusok. Általában igaz az, hogy első elemként megadott iterátort figyelembe veszik, míg utolsó elemként megadott iterátort nem használják fel, csupán a bejárás végének meghatározásához. Másként: az első elem zárt intervallum határ '[' az utolsó elem nyílt intervallum határ ')'. Az algoritmusok az header include-olásával érhetők el az astd névtéren bellül.

Iterátorok 2

Az iterátorokat már ismerjük az előző anyagrészből, azonban eddig csak annyit tudtunk, hogy az adatszerkezet egy elemét érhetjük el velük és képesek a teljes adaton végighaladni. Az algoritmusok használata során az iterátorok közt különbséget is kell tennünk. Lehetséges, hogy bizonyos iterátorok csupán az előre léptetést (következő elem / ++ operator) támogatják. Ennél többet tudnak azok az iterátorok, melyek már az előző elemet is képesek elérni (visszalépés / -- operator). Ennél többet tudnak azok az iterátorok, melyek nemcsak egy elemmel képesek léptetni az aktuális mutatott elemet, hanem tetszőleges számmal (random access / indexer operator / (it + n) ).

Az iterátorok típusai és néhány jellemzőjük

  • input iterator: képes a ++ operátorral lépni a következő elemre, azonban a már elhagyott elemek nem tekinthetőek érvényesnek. Ha egy algoritmus egyszer kell végigmenjen az adaton, akkor ez is elegendő.

  • forward iterator: képes a ++ operátorral lépni a következő elemre (akárcsak az input iterator) és a már elhagyott elemek érvényesek maradnak, újrafelhasználhatók. Akkor használatos, ha többször kell végighaladni az adaton.

  • bidirectional iterator: biztosítja a forward iterátor lehetőségeit és azonfelül képes elérni az előző elemet a -- operátorral. Támogatja az adat többszöri bejárását és akkor hasznos, ha szükséges az adott elem előtti elemek elérése.

  • random access iterator: biztosít mindent amit az előző iterátorok és képes egy tetszőleges elem elérésére is (indexer operátor és + operátor). Akkor hasznos, ha az algoritmus nemcsak végigjárja az adathalmazt, hanem indexeli is azt.

Minden olyan típus, mely valamelyik iterátor típus műveleteit kielégíti tekinthető iterátor típusnak és használható az stl-es algoritmusok használatakor.

find

A find algoritmus megkeresi azt az elemet amit megadunk neki. Az első két paramétere egy InputIt típust vár, tehát olyan iterátort mely képes előre lépni, de csak egyszer fog az algoritmus végighaladni az adaton. A harmadik paraméter olyan típusú kell legyen ami található a tárolóban és az az érték amit keresünk. Visszatérési értékként szintén iterátort kapunk, mely a megtalált elemre mutat az adathalmazban. Ha nem találta meg, akkor az adathalmaz végét adja vissza. Ha egy elem többször is szerepelhet a tárolóban, a bejárás szerinti első elemet adja vissza.

Használata: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  int searched_value = 44; // olyan tipusu ertek ami a taroloban talalhato.
  auto find_it = std::find( v_int.begin(), v_int.end(), searched_value );
  if ( find_it != v_int.end() ) { // nem a tarolo veget adta vissza.
    std::cout << *find_it << " megtalalva." << std::endl;
  }
}

Használata olyan iterátorral, mely kielégíti az input iterátor elvárásait (pointer): 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <iostream>
#include <algorithm>
int main() {
  const int size = 5;
  int array[size] = { 2, 4, -1, 55, 4 };
  int searched_value = 55;
  auto find_it = std::find( array, array + size, searched_value );
  if ( find_it != (array + size) ) { // nem az amit a vegenek adtunk meg
    std::cout << *find_it << " megtalalva. Meghhozza pointer cime: " << find_it << std::endl;
  }
}

find_if

A find_if hasonló a find-hoz, azonban itt nem egy fix értéket adunk meg, hanem egy műveletet ami eldönti, hogy az adathalmaz elemei közül, melyik az, amelyik megfelel az elvártaknak. Tehát érték helyett valamilyen logikai feltételhez kötjük az érték keresését. Ez a feltétel több minden is lehet, most használjunk függvényeket.

A find_if paraméterezése hasonló a find paraméterezéséhez, azonban a 3. paraméter egy UnaryPredicate. Egy elem akkor tartozik ehhez a típushoz, ha függvényként meghívható, egy paramétert vár abból a típusból amit az adathalmaz tárol és egy bool értéket ad vissza (jelezvén, hogy a kapott elemre igaz vagy hamis a predikátum.)

Használata: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
#include <algorithm>

bool greater_than_four( int value_under_process );

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  auto find_it = std::find_if( v_int.begin(), v_int.end(), greater_than_four );
  if ( find_it != v_int.end() ) { // nem a tarolo vege
    std::cout << *find_it << " megtalalva." << std::endl;
  }
}

bool greater_than_four( int value_under_process ) {
  return value_under_process > 4;
}

Magyarázat:

A harmadik paraméter egy függvény neve. Az algoritmus tudja, hogy azt a függvényt kell meghívnia minden elemre miközben bejárja a tárolót. Az 1, 2 értékekre hamisat ad vissza, majd az 5-re igazat. Ekkor leáll a keresés, megtalálható az elem. Látható, hogy több elem is megfelel a feltételnek, de a bejárás szerinti első elemet kapjuk vissza.

count és count_if

A count és count_if közti kapcsolat hasonló a find és find_if közti kapcsolatra, csupán a végrehajtott algoritmus más. A feltételnek (érték vagy predikátum) megfelelő elemek darabszámát adja vissza.

Használata: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
#include <algorithm>

bool greater_than_four( int value_under_process );

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  auto count_ones = std::count( v_int.begin(), v_int.end(), 1 );
  auto count_greaters = std::count_if( v_int.begin(), v_int.end(), greater_than_four );
  std::cout << "Egyesek szama: " << count_ones << std::endl
  << "Negynel nagyobbak szama: " << count_greaters << std::endl;
}

bool greater_than_four( int value_under_process ) {
  return value_under_process > 4;
}

remove és remove_if

Az elemek törlésére alkalmas. Szintén megtalálható az értékhez és predikátumhoz kötött verzió.

Nagyon fontos: a remove nem törli ki az elemeket! A remove a törlendő elemeket a tároló végére mozgatja és visszaadja azt a pozíciót (iterátort) ahonnan a "töröltnek" titulált elemek találhatók. Ezután kézzel kell törölni az adott itertátortól kezdve az elemeket.

Használata: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  auto end_of_remaining_elements = std::remove( v_int.begin(), v_int.end(), 1 );

  for ( auto it = v_int.begin(); it != v_int.end(); ++it ) { std::cout << *it << std::endl; }
  std::cout << "Igazi hasznos elemek:" << std::endl;
  for ( auto it = v_int.begin(); it != end_of_remaining_elements; ++it ) { std::cout << *it << std::endl; }
}

Használata kézzel való törléssel együtt: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  auto end_of_remaining_elements = std::remove( v_int.begin(), v_int.end(), 1 );

  for ( auto it = v_int.begin(); it != v_int.end(); ++it ) { std::cout << *it << std::endl; }
  std::cout << "Igazi hasznos elemek:" << std::endl;
  for ( auto it = v_int.begin(); it != end_of_remaining_elements; ++it ) { std::cout << *it << std::endl; }

  v_int.erase( end_of_remaining_elements, v_int.end() );
  std::cout << "A teljes tarolo:" << std::endl;
  for ( auto it = v_int.begin(); it != v_int.end(); ++it ) { std::cout << *it << std::endl; }
}

Lambda kifejezés

Az algoritmusok használatakor bizonyos esetekben (predikátum / comparison) függvényt adtunk meg az algoritmusoknak. Sokszor azonban csak egy helyen kell használnunk az adott eljárást, így fölösleges egy teljes függvényt készítenünk, hogy azt átadhassuk; ezzel is szennyezve a scope-ot amiben dolgozunk. Erre megoldás a lambda kifejezés. Egy olyan kis kód elem, ami függvényként hívható.

Függvény objektum.

Azt már láttuk, hogy osztályoknak definálhatunk operátorokat, ezzel is egy különleges szintakiszt alakítva ki. Ilyen operátor pl. a ++, --, +=, *, /, [] de akár maga a vessző is. Ezek mellett az operátorok mellett felüldefiniálható a függvény hívás operátor is operator(). Ha egy típusra definiáljuk ezt az operátort, annak a típusnak az objektumai "függvény szerűen" meghívhatók.

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
#include <iostream>

class A {
  unsigned u = 0;
public:

  A() = default;
  A( unsigned u ) : u( u ) {}

  bool operator()( unsigned parameter ) {
    std::cout << "Mukodik." << std::endl;
    for ( unsigned i = 0; i < parameter; ++i ) {
      std::cout << u << std::endl;
    }
    return true;
  }
};

int main() {

  A a(42); // objektum peldanyositas

  a(3); //objektum operator() fuggveny hivasa unsigned parameterrel.
}

Ha egy osztály példánya függvényként hívható, az algoritmusoknak függvények helyett osztály példányokat is átadhatunk.

Példa: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>

class greater_than {
  int u = 0;
  public:
    greater_than( int u ) : u( u ) {}

    bool operator()( int i ) { return i > u; }
};

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };

  greater_than greater_than_four( 4 ); // greter than objektum 4-es ertekkel.

  auto count_ones = std::count( v_int.begin(), v_int.end(), 1 );
  auto count_greaters = std::count_if( v_int.begin(), v_int.end(), greater_than_four );
  std::cout << "Egyesek szama: " << count_ones << std::endl
  << "Negynel nagyobbak szama: " << count_greaters << std::endl;
}

Lambda megvalósítás

Lambda kifejezés a fent említett függvény objektumok rövidített írásmódja, mikor nincsen szükség az adott típusra öbb helyen, csupán egy, rövid feladata van.

Lambda kifejezés írásakor egy osztály készül, melynek csupán a hasznos részeit készíti el a fordító, pl. a függvényhívás operátor.

Lambda kifejezés: [](){}. Részletezése: - a [] részben adhatunk meg változókat, melyek az eredeti scope-ban voltak elérhetők, pl. változók. Ez az úgynevezett 'capture'. - () részben a lambda / függvény paramétereit adjuk meg. - {} részben a lambda törzsét adjuk meg, hogy mi fusson meghívásakor.

Példa: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };

  auto count_ones = std::count( v_int.begin(), v_int.end(), 1 );

  auto count_greaters = std::count_if( v_int.begin(), v_int.end(), []( int i ){ return i > 4; } );

  std::cout << "Egyesek szama: " << count_ones << std::endl
  << "Negynel nagyobbak szama: " << count_greaters << std::endl;
}

Ha egy lambda kifejezésben szeretnénk használni változókat, akkor azt a [] jelek közt kell magadnunk, hogy az adott változót hazsnálni szeretnénk. Ekkor a változót átadhatjuk másolat szerint esetleg referencia szerint is. Erre 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
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };

  int greater_than_limit = 4;

  auto count_ones = std::count( v_int.begin(), v_int.end(), 1 );

  // auto count_greaters = std::count_if( v_int.begin(), v_int.end(), []( int i ){ return i > greater_than_limit; } );
  // Ez a kodresz forditasi hibas, hiszen a lambdaban nem elerheto a greater_than_limit valtozo


   auto count_greaters = std::count_if( v_int.begin(), v_int.end(),
     [greater_than_limit]( int i ){ return i > greater_than_limit; }
  );
  // Itt nem valtoztathatjuk meg a valtozot, hiszen nem referencia szerint adtuk at.

  auto count_next_greaters = std::count_if( v_int.begin(), v_int.end(),
     [&greater_than_limit]( int i ){ ++greater_than_limit; return i > greater_than_limit; }
  );
  // Itt megvaltoztathatjuk, hiszen az eredeti objektumon dolgozunk.
  // Ekkor minden osszehasonlitaskor megvaltozik az ertek.

  std::cout << "Egyesek szama: " << count_ones << std::endl
  << "Negynel nagyobbak szama: " << count_greaters << std::endl
  << "A valtoztatott limit: " << greater_than_limit << std::endl;
}
Utolsó frissítés: 2022-12-02 12:34:57