Tárolók és algoritmusaik

Algoritmusok¶

A 3. gyakorlaton megismertük a standard template library (stl) adatszerkezeteinek egy részét és az azokon definiált alap algoritmusokat vettük végig. Ebben az anyagrészben az stl hasznosabb 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, melyek egy feltételt fogalmaznak meg a vizsgált elemekre vonatkozóan. Mivel iterátorok használatakor gyakran első és utolsó elemet határozunk meg, igy 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 már nem használják fel, csupán a bejárás végének meghatározásához használják ezt. Másként: az első elem zárt intervallum határ '[' az utolsó elem nyílt intervallum határ ')'. Az algoritmusok az <algorithm> header include-olásával érhetők el az std névtéren belül.

Iterátorok (korábbi anyag kiegészítése)¶

Az iterátorokat már ismerjük a korábbi anyagrészből, azonban eddig csak annyit tudtunk, hogy az adatszerkezet egy elemét érhetjük el velük és általuk bejárhatóak a tárolóban tárolt adatok. 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 algoritmusnak egyszer kell csak végigmenni az adatokon, 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 adatokon.
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 megvalósítja, 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 típusa megfelel a tárolóban tárolt adatok típusának, ő egy érték, amit keresünk. Visszatérési értékként egy iterátort kapunk, amely 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:

#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;
  }
}

Kimenet

44 megtalalva.

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

#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. Az adat ezen a memoriacimen erheto el: " 
              << find_it << std::endl;
  }
}

Kimenet

55 megtalalva. Az adat ezen a memoriacimen erheto el: 0xe54d9ffbdc

find_if ¶

A find_if hasonló a find-hoz, azonban itt nem egy fix értéket adunk meg, hanem egy feltétel vizsgálatot, ami az adathalmaz elemeit szűri, melyik az, amelyik megfelel az elvártnak. 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 a feltétel megvizsgálásához 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:

#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;
}

Kimenet

5 megtalalva.

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ó, ha több elem is megfelel a feltételnek, akkor 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 adják vissza ezek.

Használata:

#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;
}

Kimenet

Egyesek szama: 2
Negynel nagyobbak szama: 3

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 csupán a következő nem törlendő elemet a törlendő helyére mozgatja, és visszaadja azt a pozíciót, amely az utolsó nem törölt elem utánra mutat. Ezután kézzel kell törölni az adott itertátortól kezdve az elemeket.

Használata:

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

  std::cout << "Meret remove utan: " << v_int.size() << std::endl;

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

Kimenet

Meret: 8
Meret remove utan: 8

Igazi hasznos elemek: 2 5 4 7 44

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

#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::cout << std::endl << "Igazi hasznos elemek:" << std::endl;
    for ( auto it = v_int.begin(); it != end_of_remaining_elements; ++it ) { std::cout << *it << " "; }
    std::cout << 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::cout << std::endl;
}

Kimenet

2 5 4 7 44 44 1
Igazi hasznos elemek:
2 5 4 7 44
A teljes tarolo:
2 5 4 7 44

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. Ilyenkor 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 szintaxist 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:

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

Kimenet

Mukodik.
42
42
42

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:

#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 ); // greater 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;
}

Kimenet

Egyesek szama: 2
Negynel nagyobbak szama: 3

Lambda megvalósítás¶

Lambda kifejezés a fent említett függvény objektumok rövidített írásmódja, amikor nincsen szükség az adott típusra tö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:

#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;
}

Kimenet

Egyesek szama: 2
Negynel nagyobbak szama: 3

Ha egy lambda kifejezésben szeretnénk használni változókat, akkor azokat a [] jelek közt kell magadnunk. Ezeket átadhatjuk másolat szerint, esetleg referencia szerint is. Erre példa:

#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;
}

Kimenet

Egyesek szama: 2
Negynel nagyobbak szama: 3
A valtoztatott limit: 11

Utolsó frissítés: 2024-08-01
Létrehozva: 2022-11-30

Tárolók és algoritmusaik

Algoritmusok¶

Iterátorok (korábbi anyag kiegészítése)¶

find¶

find_if¶

count és count_if¶

remove és remove_if¶

Lambda kifejezés¶

Függvény objektum¶

Lambda megvalósítás¶

find ¶

find_if ¶

count és count_if ¶

remove és remove_if ¶

Lambda kifejezés ¶