C++ programozás kezdőknek - programozási tételek

[2022. április 08.] [ christo161 ]

A programozási tételek olyan algoritmusminták, amiket alapvető, gyakran előforduló feladatok megoldásához használhatunk. Szerintem az elnevezés megtévesztő, inkább egyszerű/gyakori algoritmusoknak nevezném őket. Ráadásul az elnevezés magyar (ELTE-s) specialitás, angolul nincs olyan kifejezés, ami pontosan ezeket vagy legalább nagyjából ezeket az algoritmusokat takarná. Hiába keresünk rá angolul például arra, hogy basic algorithms, bonyolultabb illetve ezektől eltérő algoritmusokat is eredményezni fog a keresés.

előző tananyagrész: STL

Tartalom

megszámlálás
összegzés
maximumkiválasztás
sorozatszámítás
eldöntés
kiválasztás
lineáris keresés
logaritmikus keresés
másolás
kiválogatás
szétválogatás
in-place szétválogatás
in-place szétválogatás rendezéssel
összefésülés
összefuttatás
metszet
unió
maximumkeresés kiválogatással
összetett kiválogatás

Néhány gondolat a programozási tételekről

Pontosan miket sorolunk a programozási tételek közé?

Jellemzően: megszámlálás, összegzés, maximumkiválasztás (vagy minimumkiválasztás, esetleg szokták őket együttesen szélsőértékkiválasztásnak is nevezni), eldöntés, kiválasztás, lineáris keresés, logaritmikus keresés vagy más néven bináris keresés.
Esetleg ezek között szokott még szerepelni sorozatszámítás egyes tananyagokban. Például:

progalap.elte.hu - egyszerűbb algoritmusminták

Egyes tananyagok csak az eddigieket sorolják a programozási tételek közé, míg más tananyagok a következőket is: kiválogatás, szétválogatás, összefésülés, összefuttatás.
Talán ezek között találkozhatunk olyannal is, hogy másolás.

progalap.elte.hu - összetettebb algoritmusminták

Esetleg ilyesmikkel is találkozhatunk: metszet, unió.
Továbbá egyes tananyagokban rendezésekkel is találkozhatunk a programozási tételek között (például itt).

Nincs arról közös megegyezés, hogy pontosan hogyan valósítsuk meg (a kódban) a programozási tételeket

Sok tananyagban folyamatábrákkal vagy struktogramokkal, esetleg mondatszerű leírásokkal adják meg a programozási tételeket, ahol nincs tisztázva a pontos megvalósítás a kódban. Néhány példa:

Nincs pontosan megadva, hogy a bemenet, input honnan származik. Pl. fájlból, adatbázisból, a program egy függvényéből (pl. random generált számok), vagy a felhasználótól kérjük be.
Ebben a tananyagban a legtöbb esetben a legegyszerűbb módszert választjuk, literálként előre megadunk egy tömbszerű adatszerkezetben néhány példaértéket, így az eredmény talán valamivel könnyebben ellenőrízhető, mint például random generált adatok esetén.
Nincs pontosan megadva, hogy az elemek tárolásához milyen adatszerkezetet használjunk.
C++ adottság, hogy többféle tömbszerű adatszerkezet közül válaszhatunk, hagyományos tömb, dinamikus allokálás, std::array és std::vector. Természetesen a programozási tételek azt sem szabják meg, hogy ezek közül melyiket használjuk. Illetve ha függvényekben írjuk meg a programozási tételeket akkor írhatunk akár több függvényt, hogy pl. hagyományos tömböket és std::vectorokat is fel tudjunk dolgozni.
Nincs pontosan megadva, hogy egy adatszerkezetet mettől-meddig dolgozzunk fel. Bár jellemzően egy programozási tételt egy adatszerkezet elejétől a végéig alkalmazunk, ez nincs kőbe vésve, akár a felére is alkalmazhatjuk.
Nincs pontosan megadva, hogy egy adatszerkezet (pl. egy tömbszerű adatszerkezet esetén) hogyan megyünk végig az elemeken (for ciklus, ranged for ciklus, std::foreach függvény + iterátorok).
Lineáris keresés vagy maximumkiválasztás esetén nincs pontosan megadva, hogy csak az adott elem értékére van-e szükségünk, vagy a helyére (indexére), esetleg azonosítójára (id-jára) osztály/objektum esetén. Illetve hogy jelezni kell-e azt, ha több azonos érték van, esetleg kigyűjteni az azonos értékek indexét, id-ját.
Kiválogatás esetén létrehozunk egy másik tömböt a kiválogatott elemeknek, vagy például az eredeti tömbből eltávolítjuk a feltételnek nem megfelelő elemeket, vagy például kiíratjuk a kiválogatott elemeket. Erre egy ELTE-s tananyagban vannak különböző változatok.
Érdemes szót ejteni arról is, hogy sok programozási tételt érdemes lehet típusparaméterezéssel template függvényként megvalósítani, így nem kell megírni az egyes típusokra vonatkozó változatokat külön-külön.

Honnan származik a programozási tételek elnevezés?

A programozási tételekkel jellemzően csak magyar nyelvű tananyagokban találkozhatunk. Bár ELTE-s angol nyelvű publikációkban programming theoremsnek fordították angolul ([1] [2] [3] (pdf)), az angol szakirodalom nem vette át a használatukat.

Az elnevezés (programozási tétel) innen származik:
Dijksta, E.W.: A discipline of programming, Prentice Hall, Englewood Cliffs, New Jersey, 1976.

/Zsakó László/

A programozási tételek fogalmát az ELTE-n Fóti Ákos vezette be a 80-as elején. Ezt a fogalmat vettük át (Zsakó László és én) és némileg kibővítettük, ill. kissé más formalizmust rendeltünk hozzá. Ekként publikáltuk, ill. oktattuk a 80-as évek második felétől. A szakmai irodalom érdekes módon nem nagyon alkalmazza a fogalmat. A tételhez viszont tartozik egy feladatspecifikáció is és a kettejük összetartozásának bizonyítása. Vagyis a "programozási tétel" fogalom teljesebb, absztraktabb fogalom, mint az "alapalgoritmusok" fogalom.

/Szlávi Péter/

Ha valakit mélyebben érdekel a téma, ezeket a pdf-eket ajánlom:

Ezek könyv formában is elérhetők voltak, de jelenleg csak antikváriumokból (jó eséllyel előjegyezve) lehet megszerezni őket.

Mikrológia 19, Módszeres programozás, programozási tételek (Szlávi Péter, Zsakó László)

Ha pedig van, akit a programozási tételek matematikai háttere érdekel, annak ezt tudom ajánlani:

Fóthi Ákos - Bevezetés a programozáshoz (pdf)

Megszámlálás

2 fajtára bontható:

megszámoljuk az összes elemet
megszámoljuk a bizonyos feltételnek megfelelő elemeket

Mivel általában tömböket, tömbszerű adatszerkezeteket használunk, így annak nincs sok értelme, hogy megszámoljuk az összes elemet, hiszen az a tömb elemszámát jelentené, a tömb elemszámát pedig vagy tároljuk egy változóban, vagy pl. std::vector esetén a size() tagfüggvénnyel könnyen megkaphatjuk.

Így ezt a programozási tételt a bizonyos feltételnek megfelelő elemek megszámolására használjuk.

Milyen értékeket számolhatunk meg jellemzően?

Például számok esetén: páros számok, páratlan számok, negatív számok, nullák, prímszámok
Például szövegek esetén: valahány karakternél (pl 5 karakternél hosszabb) szövegek, bizonyos karaktereket/szavakat tartalmazó szövegek

Ebben a példában a vec_example nevű std::vectorban lévő páros számokat számoljuk meg.

A count nevű változóban fogjuk tárolni a megszámlálás eredményét. Ennek a változónak a kezdőértéke értelemszerűen 0, hiszen ha esetleg egyetlen elem sem felel meg a feltételnek, akkor az azt jelenti, hogy 0 elem felelt meg a feltételnek.

Egy for ciklussal végigmegyünk a tömbön, és megvizsgáljuk, hogy egy adott feltétel teljesül-e a tömb minden egyes elemére. Ha igen, akkor az eredményhez (a count nevű változó értékéhez) hozzáadunk 1-et.

A for ciklusban végig kell mennünk a tömbszerű adatszerkezet utolsó eleméig (hiszen nem tudhatjuk, hogy az utolsó elem megfelel-e a feltételnek).

Ha már végig kell mennünk a teljes adatszerkezeten, használhatnánk akár ranged for ciklust is, vagy foreach függvényt iterátorokkal, melyek így néznének ki:

ranged for ciklus:

for (const int& element : vec_example) { if (element % 2 == 0) {++count;} }

foreach függvény iterátorokkal (ne felejtsük el, hogy ennek használatához includeolnunk kell az algorithm header fájlt):

#include <algorithm>

[...]

std::for_each(vec_example.begin(), vec_example.end(), [&](const int& element) { if (element % 2 == 0 ) {++count; } });

Megszámlálás programozási tétel egy lehetséges megvalósítása hagyományos for ciklussal:

//count_if example: count even elements of "vec_example"
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};
  
  int count = 0;
  for (int i = 0; i < vec_example.size(); ++i) {
    if (vec_example[i] % 2 == 0) {
      ++count;
    }
  }

  std::cout << "Number of even numbers: " << count << '\n';
}

Megszámlálás programozási tétel egy lehetséges megvalósítása függvénnyel (count_even).

//count_if example: count even elements of "vec_example" (with function)
#include <iostream>
#include <vector>

//define "count_even" function
int count_even(const std::vector<int>& numbers) {
  int count = 0;
  for (const int& element : numbers) { if (element % 2 == 0) {++count;} }
  return count;
}

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  std::cout << "Number of even numbers: " << count_even(vec_example) << '\n';
}

A megszámlálás programozási tétel megvalósítását úgy is továbbfejleszhetjük, ha a feltétel ellenőrzését külön függvénybe (is_even) szervezzük , és ezt a függvényt paraméterként átadjuk a számlálást végző függvénynek (count_if), így a számlálást végző függvény többször is felhasználható különböző feltételek vizsgálásához.

A predikátumfüggvény egy olyan függvény, ami egyetlen értéket vár bemenetként, és eldönti róla, hogy teljesít-e egy adott feltételt. Az eredménye mindig igaz (true) vagy hamis (false).
Gyakran használjuk olyan esetekben, amikor egy tömb vagy más adatszerkezet minden elemére alkalmazunk egy feltételvizsgálatot – például szűrésnél, keresésnél, vagy ellenőrzésnél.

//count_if example: count even elements of "vec_example" with predicate function
#include <iostream>
#include <vector>
#include <functional>

//define "is_even" predicate function
bool is_even(const int& p_number) { return p_number % 2 == 0; }

//define "count_if" function
int count_if(const std::vector<int>& numbers, const std::function<bool(int)>& predicate) {
  int count = 0;
  for (const int& element : numbers) { if (predicate(element)) {++count;} }
  return count;
}

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  std::cout << "Number of even numbers: " << count_if(vec_example, is_even) << '\n';
}

A tétel úgy is továbbfejleszthető, ha típusparaméterezett (template) függvényt készítünk a megszámláláshoz, így például a páros számok megszámolása mellett azt is megszámolhatjuk, hány szóközt tartalmazó string van egy tömbben.
Ebben az esetben viszont a programozó feladata számon tartani, hogy melyik predikátumfüggvényt lehet paraméterként átadni, hogy a művelet elvégezhető legyen. Például ha azt vizsgáljuk, hogy egy tömb elemei páros számok-e, akkor azt egy egész számokat tartalmazó tömb esetén érdemes vizsgálni, nem pedig egy stringeket tartalmazó tömb esetén.

//count_if example: template function
#include <iostream>
#include <vector>
#include <string>
#include <functional>

//define "is_even" predicate function
bool is_even(const int& p_number) { return p_number % 2 == 0; }

//define "contains_space" predicate function
bool contains_space(const std::string& text) { return text.find(' ') != std::string::npos; }

//define generic "count_if" function
template <typename T, typename P>
int count_if(const std::vector<T>& elements, P predicate) {
  int count = 0;
  for (const T& element : elements) {
    if (predicate(element)) { ++count; }
  }
  return count;
}

int main() {
  std::vector<int> vec_example = {2, 2, 3, 5, 10, 7, 8, 9, 11, 0};

  std::cout << "Number of even numbers: " << count_if(vec_example, is_even) << '\n';

  std::vector<std::string> vec_strings = {
    "hello world", "nospaces", "this is fine", "empty", "with space"
  };

  std::cout << "Number of strings containing spaces: " << count_if(vec_strings, contains_space) << '\n';
}

A tételt iterátorokkal is tovább lehet fejleszteni, és akkor bármilyen adatszerkezetre alkalmazható. A példában egy hagyományos tömböt, egy std::vectort és egy std::set-et adunk át paraméterként.

Mivel az std névtérben már van egy beépített count_if STL algoritmus, így a névütközés elkerülése céljából létrehozunk egy névteret, és azon belül definiáljuk az iterátorokkal paraméterezhető függvényt.

//count_if example: with iterators
#include <iostream>
#include <string>
#include <vector>
#include <set>

namespace itk {
  //define generic "count_if" function with iterators
  template <typename IteratorType, typename Predicate>
  int count_if(IteratorType first, IteratorType last, Predicate pred) {
    int count = 0;
    for (; first != last; ++first) {
      if (pred(*first)) { ++count; }
    }
    return count;
  }
}

int main() {
  double array_example[] = {2.3, 2.0, 3.1, 5.0, 10.3, 7.0, 8.7, 9.0, 11.3, 0.0};
  std::vector<int> vector_example = {0, 2, 0, 5, 0, 7, 8, 0, 11, 0};
  std::set<int> set_example = {-2, 3, -5, 10, -7, 8, -9, 11, 0};

  std::cout << "Number of integer numbers in array_example: " << itk::count_if(std::begin(array_example), std::end(array_example), [](const double& p_number) { return p_number == static_cast<int>(p_number); }) << '\n';

  std::cout << "Number of zero values in vector_example: " << itk::count_if(vector_example.begin(), vector_example.end(), [](const int& p_number) { return p_number == 0; }) << '\n';

  std::cout << "Number of negative numbetrs in set_example: " << itk::count_if(set_example.begin(), set_example.end(), [](const int& p_number) { return p_number < 0; }) << '\n';
}

Hasonló célra használható az STL std::count és std::count_if függvénye, mint a megszámlálás programozási tétel.

Összegzés

Az összegzésnek a legegyszerűbb megvalósítása (egy ciklussal végigmegyünk egy tömbön) hasonló mint a megszámlálás, azzal a különbséggel, egy 0 kezdőértékű változóhoz nem 1-et adunk hozzá egy elem esetén, hanem az adott elem értékét adjuk hozzá.

2 fajtára bontható:

összeadjuk az összes elemet
csak bizonyos feltételnek megfelelő elemeket adunk össze

A megszámlálással ellentétben az összegzés esetén egy tömb esetén is van értelme az összes elem bejárásának, feldolgozásának, hiszen azonos elemszám esetén az összeg eltérő lehet.

A példaprogramban összeadjuk a vec_example nevű std::vectorban lévő páros számokat. Az összeadás eredményét a sum nevű változó tárolja.

Az összegzés programozási tétel egy lehetséges megvalósítása hagyományos for ciklussal:

//sum even elements of "vec_example"
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  int sum = 0;
  for (int i = 0; i < vec_example.size(); ++i) {
    if (vec_example[i] % 2 == 0) {
      sum += example[i];
    }
  }

  std::cout << "Sum of even numbers: " << sum << '\n';
}

Az összegzés programozási tétel egy lehetséges megvalósítása függvénnyel:

//sum even elements of "vec_example"
#include <iostream>
#include <vector>
#include <functional>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

int sum_if(const std::vector<int>& numbers, const std::function<bool(const int)>& predicate) {
  int sum = 0;

  for (const int& element : numbers) {
    if(predicate(element)) { sum += element; }
  }

  return sum;
}

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  std::cout << "Sum of even numbers: " << sum_if(vec_example, is_even) << '\n';
}

Ennek a programozási tételnek a típusparaméterezett változata a sorozatszámtás programozási tétel.

Ezt a programozási tételt meg lehet valósítani az STL std::accumulate függvényével.

Maximumkiválasztás

Két fajtára bontható:

az összes elemet vizsgáljuk
csak bizonyos feltételnek megfelelő elemeket vizsgálunk

Ha az összes elemet vizsgáljuk, akkor megtehetjük azt, hogy az eredmény tárolására használni kívánt változónak először értékül adjuk az első elemet, majd ha ennél nagyobbat találunk, akkor lecseréljük arra az értékre.
Ebben az esetben a ciklust elég a második elemtől indítani, mivel ha az első elemtől indítanánk, akkor az eddigi legnagyobb értéket (vagyis az első elemet) önmagával hasonlítanánk össze.

//max
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  int max = example[0];

  for (int i = 1; i < example.size(); ++i) {
    if (max < example[i]) {
      max = example[i];
    }
  }

  std::cout << "The biggest number: " << max << '\n';
}

Ha külön függvényként szeretnénk megvalósítani ezt a programozási tételt, akkor felmerül az a probléma, hogy ha esetleg üres tömböt adunk neki paraméterül, akkor hogyan jelezzük azt, hogy annak nincs legnagyobb eleme. Mert ha mondjuk visszaadnánk üres tömb esetén 0-át vagy -1-et, akkor annak az a hátránya, hogy önmagában a 0 vagy a -1 értékből nem derül ki, hogy az egy legnagyobb elem értéke, vagy pedig annak a jelzése, hogy üres tömb esetén valamilyen hibás értéket szándékoztunk visszaadni.
Ezért ebben az esetben és az ehhez hasonló esetekben bevezetünk egy bool típusú változót is. Célszerű ezt a bool változót a visszatérési értékkel együtt visszaadni, viszont mivel C++-ban egy függvénynek csak egy változó lehet a visszatérési értéke, így ilyen esetben kénytelenek leszünk valamilyen olyan adatszerkezetet használni, amiben egyszerre két különböző típus is tárolható. Erre használhatjuk pl. az std::pair adatszerkezetet, valamint C++ 17-es szabványtól az std::optional adatszerkezetet.

A find_max nevű függvény visszatérési típusa std::pair<bool, int>, ami egy bool és egy int típusú értéket tud tárolni.

Amikor létrehozunk egy ilyen típusú változót, akkor az első adattaghoz (ami jelen esetben bool típusú) ilyesmi kifejezéssel tudunk hozzáférni: variable_name.first, a második adattaghoz pedig ilyesmivel: variable_name.second

A példában ugyan 0 kezdőértéket adunk az std::pair int típusú adattagjának, de ha az első adattag értéke false, akkor a programban nem használjuk fel a második adattag értékét.

//max of empty std::vector
#include <iostream>
#include <vector>
#include <tuple>

  std::pair<bool, int> find_max(const std::vector<int>& p_array) {
    std::pair<bool, int> result = {false, 0};
    if (p_array.size() == 0) { return result; }

    result.first = true;
    result.second = p_array[0];
    for (int i = 1; i < p_array.size(); ++i) {
      if (result.second < p_array[i]) {
        result.second = p_array[i];
      }
    }
    return result;
  }

int main() {
  std::vector<int> example_arr;

  std::pair<bool, int> result = find_max(example_arr);

  if (!result.first) {
    std::cout << "The array is empty" << '\n';
  } else {
    std::cout << "The biggest number: " << result.second << '\n';
  }
}

Feltételes maximumkeresés

Ha bizonyos feltételnek megfelelő elemek között keressük a legnagyobb értéket, akkor ügyelnünk kell arra, hogy előfordulhat, hogy nincs is a feltételnek megfelelő érték az értékek között (pl. ha keressük a legnagyobb páros számot, de nincsenek páros számok a tömbben).

Ez az eset hasonlóképp oldható meg, mint a fentebbi példa (amikor üres tömböt is átadhatunk egy függvénynek).
Itt is egy logikai értéket használunk, csak most annak jelzésére, hogy nincs a feltételnek megfelelő érték. Ezt a logikai értéket szintén std::pair vagy std::optional segítségével köthetjük össze a lehetséges eredménnyel.

Az std::pair bool típusú adattagjának false kezdőértéket adunk (max.first = false;). Ha ez false marad a ciklus végéig, akkor az azt jelenti, hogy nem találtunk a feltételnek megfelelő (páros) elemet.

Ha megtaláljuk az első feltételnek megfelelő (páros) elemet, akkor az std::pair bool típusú adattagjának az értékét true-ra állítjuk (ezzel jelezve, hogy van a feltételnek megfelelő elem), illetve az int típusú adattagjának az értékét beállítjuk az első feltételnek megtalált elem értékére. Innentől kezdve az algoritmus ugyanúgy működik mint a hagyományos maximum keresés. A további páros elemekből ha van olyan, ami nagyobb, mint amit eddig találtunk, akkor azt fogjuk eltárolni. A második elemnél pedig már ugyanúgy néz ki a maximumkiválasztás, mint az előző példákban, összehasonlítjuk, hogy az eddigi értéknél nagyobb-e a következő érték, ha igen, akkor kicseréljük arra.

//max of even numbers
#include <iostream>
#include <vector>
#include <tuple>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

std::pair<bool, int> max_of_even(const std::vector<int>& numbers) {
  std::pair<bool, int> max {false, 0};

  for (const int& element: numbers) {
    if (!is_even(element)) { continue; }

    if (!max.first) {
      max.second = element;
      max.first = true;
    } else if (element > max.second) {
      max.second = element;
    }
  }
  return max;
}

int main() {
  std::vector<int> vec_example = {13,8,7,21,5,31,-2,17,11,10};

  std::pair<bool, int> max = max_of_even(vec_example);

  if (!max.first) {
    std::cout << "There is no even number in the std::vector\n";
  } else {
    std::cout << "The biggest even number in the std::vector: " << max.second << '\n';
  }
}

//max example: with iterators
#include <iostream>
#include <string>
#include <vector>
#include <tuple>

//define generic "count_if" function with iterators
template <typename ResultType, typename IteratorType, typename Predicate>
std::pair<bool, ResultType> max(IteratorType first, IteratorType last, Predicate pred) {
  bool element_exists = false;
  ResultType max;
  for (; first != last; ++first) {
    if (!pred(*first)) { continue; }
    
    if (!element_exists) {
      element_exists = true;
      max = *first;
    } else if (*first > max) {
      max = *first;
    }
  }
  return std::make_pair(element_exists, max);
}

int main() {
  std::string array_example[] = {"abc", "aac", "acc", "aa", "a"};
  std::vector<int> vector_example = {1, 2, -3, 5, -2, 7, 8, 4, 11, 7};

  std::cout << "Lexicographically biggest string: " << max(std::begin(array_example), std::end(array_example), [](const std::string& element) { return element.size() > 2; }) << '\n';

  std::cout << "Max of even numbers: " << max(vector_example.begin(), vector_example.end(), [](const int& element) { return element % 2 == 0; }) << '\n';
}

Ezekben a maximumkiválasztásos feladatokban a maximum indexét nem tároltuk.

Sorozatszámítás

A sorozatszámítás valójában az általánosítása az olyan programozási tételeknek, amikor több adatból állítunk elő egy adatot, például egy tömbszerű adatszerkezet elemeiből egy végeredményt (pl. összegzés, megszámlálás, összefűzés, összeéselés, összevagyolás). A sorozatszámításban paraméterként adhatjuk meg a végeredmény változó kezdőértékét (nullelemét), illetve az elvégzendő műveletet.

Ez tulajdonképpen az std::accumulate STL algoritmus, vagy például a reduce JavaScript függvény.

Szerény véleményem szerint szerencsésebb lett volna összevonásnak, felhalmozásnak, vagy szakszavakkal esetleg akkumulálásnak, redukciónak, aggregálásnak nevezni. (Az aggregálás itt most nem keverendő össze az objektum-orientált programozásban lévő aggregálással.)

Amint az látható a példában, ez az egy programozási tétel használható mindenféle összevonás művelet megvalósításához:

//accumulate
#include <iostream>
#include <vector>

template<typename IteratorType, typename ResultType, typename BinaryOperation>
ResultType accumulate(IteratorType first, IteratorType last, ResultType result, BinaryOperation op) {
  for (; first != last; ++first) {
    result = op(result, *first);
  }
  return result;
}

int main() {

  std::vector<int> array_example1 = {1, 2, 3, 4, 5};

  /*sum*/
  int sum = accumulate(array_example1.begin(), array_example1.end(), 0,
    [](int sum, int element) {
      return sum + element;
    });
  std::cout << "Sum of array_example1: " << sum << "\n";

  /*prod*/
  int product = accumulate(array_example1.begin(), array_example1.end(), 1,
    [](int prod, int element) {
      return prod * element;
    });
  std::cout << "Prod of array_example1: " << product << "\n";

  /*countif*/
  int count_even = accumulate(array_example1.begin(), array_example1.end(), 0,
    [](int count, int element) {
      return count + (element % 2 == 0 ? 1 : 0);
    });
  std::cout << "Number of even in array_example1: " << count_even << "\n";

  /*sumif*/
  int sum_even = accumulate(array_example1.begin(), array_example1.end(), 0,
    [](int sum, int element) {
      return sum + (element % 2 == 0 ? element : 0);
    });
  std::cout << "Sum of even in array_example1: " << count_even << "\n";

  std::vector<std::string> array_example2 = {"Hello", " ", "World", "!"};

  /*concat*/  
  std::string concat = accumulate(array_example2.begin(), array_example2.end(), std::string(""),
    [](const std::string& concat, const std::string& element) {
      return concat + element;
    });
  std::cout << "Result of concat: " << concat << "\n";

  std::vector<int> array_example3 = {2, 4, 6, 8};

  /*logical accumulate*/
  bool all_even = accumulate(array_example3.begin(), array_example3.end(), true,
    [](bool acc, int x) {
      return acc && (x % 2 == 0);
    });
  std::cout.setf(std::ios::boolalpha);
  std::cout << "Are all numbers even in array_example3? " << all_even << "\n";
  
  /*maximum*/
  int max_value = accumulate(array_example1.begin(), array_example1.end(), array_example1[0],
    [](int current_max, int element) {
        return (element > current_max) ? element : current_max;
    });
  std::cout << "Max of array_example1: " << max_value << "\n";
  
  /*sum of squares*/
  int sum_of_squares = accumulate(array_example1.begin(), array_example1.end(), 0,
    [](int sum, int x) {
        return sum + x * x;
    });
  std::cout << "Sum of squares in array_example1: " << sum_of_squares << "\n";
}

Eldöntés

Két dolgot vizsgálhatunk:

van-e az elemek között a feltételnek megfelelő
az összes elem a feltételnek megfelelő

Ebben a tételben nem vizsgáljuk a következőket:

a feltételnek megfelelő elem, elemek értéke, indexe
hány darab feltételnek megfelelő elem van

Egy logikai változóban tároljuk, hogy találtunk-e a feltételnek megfelelő elemet. A logikai változó kezdőértéke hamis, és ha nincs az elemek között a feltételnek megfelelő, akkor a ciklus végén is hamis marad a logikai változó értéke.
Ha találunk a feltételnek megfelelő elemet, akkor a logikai változó értékét igazra állítjuk.

Van viszont valami, ami az eddigi tételekben nem fordult elő. Ha csak az a lényeg, hogy eldöntsük, hogy az elemek között van-e a feltételnek megfelelő, akkor ha megtaláltuk az első ilyen elemet, nem kell tovább folytatnunk a ciklust, kiléphetünk a ciklusból.

Általában megvetendőnek tartják, ha a ciklusból való kilépést a break utasítással érjük el. Ezzel kapcsolatban 3 dolgot érdemes tudni:

ciklusok esetén a break használata kiváltható azzal, ha módosítjuk a ciklus feltételét
ranged for ciklusból elfogadottnak tartják a break utasítással való kilépést
ha függvényeket használunk, akkor a return utasítás kiváltja a break utasítást

Ebben a példában azt vizsgáljuk, hogy van-e az elemek között negatív szám.

//contains negative
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  bool contains_negative = false;

  for (int i = 0; i < example.size() && !contains_negative; ++i) {
    if (example[i] < 0) {
      contains_negative = true;
    }
  }

  if (contains_negative) {
    std::cout << "There is an even number in the numbers.\n";
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Függvénnyel:

//contains negative
#include <iostream>
#include <vector>

bool is_negative(const int& p_number) { return p_number < 0;}

bool contains_negative(std::vector<int>& numbers) {
  for (const int& element : numbers) {
    if(is_negative(element)) {
      return true;
    }
  }
  return false;
}

int main() {
  std::vector<int> vec_example1 = {13,8,7,21,5,32,-2,17,11,10};
  std::vector<int> vec_example2 = {13,8,7,21,5,32, 2,17,11,10};

  if (contains_negative(vec_example1)) {
    std::cout << "There is a negative number in vec_example1.\n";
  } else {
    std::cout << "There isn't any negative number in vec_example1.\n";
  }

  if (contains_negative(vec_example2)) {
    std::cout << "There is a negative number in vec_example2.\n";
  } else {
    std::cout << "There isn't any negative number in vec_example2.\n";
  }
}

Hasonlóan működik az std::find vagy std::find_if algoritmus.

Kiválasztás

Ezt a programozási tételt akkor alkalmazzuk, amikor biztosra vesszük, hogy az adott elemek között van a feltételnek megfelelő, amit keresünk, és ezek közül az elsőt adjuk vissza.

Random generálással létrehozunk 7 dobókockával dobott értéket. Ezek között biztos lesz 2 egyező érték. Az első egyező érték helyét (index+1) adjuk vissza.

//first duplicate
#include <iostream>
#include <random>
#include <vector>

int select_first_duplicate(std::vector<int>& numbers) {
  for (int i = 0; i < numbers.size(); ++i) {
    for (int j = i+1; j < numbers.size(); ++j) {
      if (numbers[i] == numbers[j]) {
        return i+1;
      }
    }
  }
}

int main() {
  //initialize random
  std::random_device rnd_device;
  std::mt19937 rnd_generator(rnd_device());
  std::uniform_int_distribution<int> int_dist(1,6);

  std::vector<int> vec_example;
  //random generate numbers between 1 and 6, 7 times
  for (int i = 1; i <= 7; ++i) {
    vec_example.push_back(int_dist(rnd_generator));
  }

  std::cout << "The elements:\n";
  for (const int& element : vec_example) {
    std::cout << element << ' ';
  }
  std::cout.put('\n');

  std::cout << "The place of the first duplicate value: " << select_first_duplicate(vec_example) << '\n';
}

Lineáris keresés

Ez a tétel akár lehetne az eldöntés és a kiválasztás hibridje. Ha nincs a feltételnek megfelelő elem, azt egy logikai változóban tároljuk, ha van, akkor pedig az első találatnak az helyét (index+1) adjuk vissza. Ez utóbbi esetben kiléphetünk a ciklusból.

//linear search (even number)
#include <iostream>
#include <vector>#include <tuple>

int main() {
  std::vector<int> vec_example = {13,8,7,21,5,32,-2,17,11,10};
  std::pair<int, bool> found;
  found.second = false;

  for (int i = 0; i < vec_example.size() && !found.second; ++i) {
    if (vec_example[i] % 2 == 0) {
      found.second = true;
      found.first = i+1;
    }
  }

  if (found.second) {
    std::cout << "There is an even number in the numbers.\n";
    std::cout << "Its place is: " << found.first << '\n';
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Függvénnyel:

//linear search (even number)
#include <iostream>
#include <vector>
#include <tuple>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

std::pair<int, bool> find_even(std::vector<int>& numbers) {
  std::pair<int, bool> found;
  found.second = false;

  for (int i = 0; i < numbers.size(); ++i) {
    if (is_even(numbers[i])) {
      found.second = true;
      found.first = i+1;
      return found;
    }
  }
  return found;
}

int main() {
  std::vector<int> vec_example = {13,8,7,21,5,32,-2,17,11,10};

  std::pair<int, bool> found = find_even(vec_example);

  if (found.second) {
    std::cout << "There is an even number in the numbers.\n";
    std::cout << "Its place is: " << found.first << '\n';
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Hasonlóan működik az STL std::find_if függvénye.

Logaritmikus keresés, vagy más néven bináris keresés

Csak rendezett tömbökre működik.

Megfelezzük a tömböt. Megnézzük, hogy az elem a tömb első vagy a második felében van. Ha például az első felében, akkor azt tovább felezzük, és így tovább, amíg meg nem találjuk az elemet.

Ebben a példában egy 1 és 12 közti random generált számot keresünk meg egy 1 és 10 közötti számokat tartalmazó tömbben.

//binary search
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

int generate_rnd_number(const int& intval_begin, const int& intval_end) {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(intval_begin,intval_end);
  return int_dist(rnd_generator);
}

int main () {
  std::vector<int> example = {1,2,3,4,5,6,7,8,9,10};
  int find = generate_rnd_number(1,12);
  bool contains = false;
  int index = -1;

  int low = 0;
  int high = example.size()-1;

  while (low <= high && !contains) {
    int mid = (low + high) / 2;
    if (find == example[mid]) {
      contains = true;
      index = mid;
    } else if (find < example[mid]) {
      high = mid-1;
    } else if (find > example[mid]) {
    low = mid+1;
  }
}

  std::cout << "Find: " << find << '\n';
  if (contains) {
    std::cout << "Found at index: " << index << '\n';
  } else {
    std::cout << "Not found\n";
  }
}

Kiválogatás

Egy tömbből bizonyos feltételnek megfelelő elemeket átmásoljuk egy másik tömbbe. Pl. kiválogatjuk a páros számokat.

//select
#include <iostream>
#include <vector>

int main() {
  std::vector<int> input = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> output;

  for (int i = 0; i < input.size(); ++i) {
    if (input[i] % 2 == 0) {
      output.push_back(input[i]);
    }
  }

  for (const int& element : output) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}

Szétválogatás

Egy tömbből bizonyos feltételnek megfelelő elemeket átmásoljuk egy másik tömbbe, a feltételnek nem megfelelő elemeket pedig egy harmadik tömbbe.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> input = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> even;
  std::vector<int> odd;

  for (int i = 0; i < input.size(); ++i) {
    if (input[i] % 2 == 0) {
      even.push_back(input[i]);
    } else {
      odd.push_back(input[i]);
    }
  }

  std::cout << "Even numbers:\n";
  for (const int& element : even) {
    std::cout << element << " ";
  }
  std::cout.put('\n');

  std::cout << "Odd numbers:\n";
  for (const int& element : odd) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}

In-place (helyben végzett) szétválogatás, más néven partícionálás

Ebben a példában páros és páratlan számokat válogatunk szét. A párosak kerülnek a tömb elejére, a páratlanok a tömb végére.

Az első elem mindenképp át lesz helyezve, mégpedig középre, így tehát mindegy, hogy páros vagy páratlan. A többi áthelyezésnél pedig mindig az előző áthelyezésnél felszabadult helyre helyezünk át.

#include <iostream>
#include <random>
#include <vector>

void generate_rnd_number(std::vector<int>& vec, const int& howmany, const int& intval_begin, const int& intval_end) {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(intval_begin, intval_end);

  for (int i = 0; i < howmany; ++i) {
    vec.push_back(int_dist(rnd_generator));
  }
}

void print_vector(const std::vector<int>& vec) {
  for (const int& element : vec) { std::cout << element << ' '; }
  std::cout.put('\n');
}

bool is_even(const int& p_element) {
  return p_element % 2 == 0;
}

void even_odd_sort(std::vector<int>& vec){
  int low = 0;
  int high = vec.size()-1;
  int mid = vec[0];

  while (low < high){
    while (low < high && !is_even(vec[high])) {
      --high;
    }

    if (low < high) {
      vec[low] = vec[high];
      ++low;
    }

    while (low < high && is_even(vec[low])){
      ++low;
    }

    if (low < high){
      vec[high] = vec[low];
      --high;
    }
  }
  vec[low] = mid;
}

int main() {
  std::vector<int> stdvec_example1;

  const int howmany = 10;
  generate_rnd_number(stdvec_example1, howmany, 1, 100);

  std::cout << "Elements before sorting:\n";
  print_vector(stdvec_example1);

  even_odd_sort(stdvec_example1);

  std::cout << "Elements after sorting:\n";
  print_vector(stdvec_example1);
}

In-place szétválogatás rendezéssel

#include <iostream>

#include <vector>

#include <algorithm>

void even_odd_sort(std::vector < int > & vec) {
int low = 0, high = vec.size() - 1;

while (low < high) {
while (low < high && vec[low] % 2 == 0) ++low;
while (low < high && vec[high] % 2 != 0) --high;

if (low < high) std::swap(vec[low], vec[high]);
}

// Szétválogatás után külön rendezzük a két részt
std::sort(vec.begin(), vec.begin() + low); // Páros rész rendezése
std::sort(vec.begin() + low, vec.end()); // Páratlan rész rendezése
}

int main() {
std::vector < int > vec = {
10,
3,
2,
8,
5,
1,
4,
9,
6,
7
};

even_odd_sort(vec);

for (int num: vec) {
std::cout << num << " ";
}
}

Összefésülés

Két rendezett tömb uniójaként, duplikátumokkal.

Két rendezett tömb elemeit átmásoljuk egy harmadik tömbbe, a rendezettséget megőrízve.

Először két tömbön haladunk egy ciklussal addig amíg az egyik tömb végére nem érünk. Eközben amelyik tömbben van éppen kisebb elem, azt másoljuk át a harmadik tömbbe, és növeljük az annak megfelelő ciklusváltozót. Ha esetleg az elemek egyenlőek (ebben a példában ilyen eset nem fordul elő), akkor mindkét ciklusváltozót növeljük.

Ezt követően ha az egyik tömb feldolgozása még nem ért véget, akkor a fennmaradó elemeket átmásoljuk a harmadik tömbbe.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> even = {2,4,6,8,10,12,14,16};
  std::vector<int> odd = {1,3,5,7,9,11,13};
  std::vector<int> output;

  int i = 0, j = 0;
  for (; i < even.size() && j < odd.size();) {
    if (even[i] < odd[j]) {
      output.push_back(even[i]);
      ++i;
    } else if (odd[j] < even[i]) {
      output.push_back(odd[j]);
      ++j;
    } else if (even[i] == odd[j]) {
      output.push_back(even[i]);
      ++i; ++j;
    }
  }

  for (; i < even.size(); ++i) {
    output.push_back(even[i]);
  }

  for (; j < odd.size(); ++j) {
    output.push_back(odd[j]);
  }

  for (const int& element : output) {
    std::cout << element << " ";
  }std::cout.put('\n');
}

Összefuttatás

két rendezett tömb uniójaként, duplikátumok nélkül.

Az összefuttatás tétele két (vagy több) rendezett sorozat közös elemeinek keresésére szolgál.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Összefuttatás: Két rendezett tömb uniója (duplikátumok nélkül)

vector<int> osszefuttatas(const vector<int>& A, const vector<int>& B) {
vector<int> result;
size_t i = 0, j = 0;

auto add_if_not_duplicate = [&](int value) {
if (result.empty() || result.back() != value)
result.push_back(value);
};

while (i < A.size() && j < B.size()) {
if (A[i] < B[j]) {
add_if_not_duplicate(A[i++]);
} else if (A[i] > B[j]) {
add_if_not_duplicate(B[j++]);
} else {
add_if_not_duplicate(A[i]);
i++; j++;
}
}
while (i < A.size()) add_if_not_duplicate(A[i++]);
while (j < B.size()) add_if_not_duplicate(B[j++]);

return result;
}

int main() {
vector<int> A = {1, 2, 2, 4, 5};
vector<int> B = {2, 3, 5, 6};

vector<int> unio1 = osszefuttatas(A, B);

cout << "Összefuttatás (duplikátumok nélkül): ";
for (int x : unio1) cout << x << " ";
cout << endl;

return 0;
}

-----

Összefuttatás (merge/intersection helyett union)
Ha jól értem, a pontosítás lényege az, hogy az összefuttatás során két rendezett sorozatot úgy egyesítünk, hogy azok unióját kapjuk meg, nem pedig a metszetüket. Ez logikus, hiszen az algoritmus végigmegy mindkét sorozaton, és minden elemet beemel a kimenetbe a megfelelő sorrendben. Ha eddig metszetként volt kezelve, akkor ezt érdemes korrigálni.

Összefésülés (duplikátumok kezelése)
Az összefésülésnél minden azonos elem bekerül a kimenetbe, nem történik duplikátumszűrés. Ez is teljesen jogos, és így még jobban illeszkedik a gyakorlati implementációkhoz, például rendezett tömbök egyesítésénél. Az is fontos, hogy az algoritmus mindig rendezett sorozatokon működik, és ez valóban egyfajta unióként is értelmezhető, ha az elemek többszörös előfordulásával együtt nézzük.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Összefuttatás: Két rendezett tömb uniója (duplikátumok nélkül)
vector<int> osszefuttatas(const vector<int>& A, const vector<int>& B) {
vector<int> result;
size_t i = 0, j = 0;
while (i < A.size() && j < B.size()) {
if (A[i] < B[j]) {
result.push_back(A[i++]);
} else if (A[i] > B[j]) {
result.push_back(B[j++]);
} else { // Duplikátumot kihagyjuk
result.push_back(A[i]);
i++; j++;
}
}
while (i < A.size()) result.push_back(A[i++]);
while (j < B.size()) result.push_back(B[j++]);
return result;
}

// Összefésülés: Két rendezett tömb uniója (duplikátumokkal)
vector<int> osszefesules(const vector<int>& A, const vector<int>& B) {
vector<int> result;
size_t i = 0, j = 0;
while (i < A.size() && j < B.size()) {
if (A[i] < B[j]) {
result.push_back(A[i++]);
} else {
result.push_back(B[j++]);
}
}
while (i < A.size()) result.push_back(A[i++]);
while (j < B.size()) result.push_back(B[j++]);
return result;
}

int main() {
vector<int> A = {1, 2, 2, 4, 5};
vector<int> B = {2, 3, 5, 6};

vector<int> unio1 = osszefuttatas(A, B);
vector<int> unio2 = osszefesules(A, B);

cout << "Összefuttatás (duplikátumok nélkül): ";
for (int x : unio1) cout << x << " ";
cout << endl;

cout << "Összefésülés (duplikátumokkal): ";
for (int x : unio2) cout << x << " ";
cout << endl;

return 0;
}

auto add_if_unique = [&](int x) {
if (result.empty() || result.back() != x)
result.push_back(x);
};

Magyarázat:

Összefuttatás (osszefuttatas): Uniót készít úgy, hogy kihagyja a duplikátumokat.
Összefésülés (osszefesules): Uniót készít, de megtartja az összes elemet, akárhányszor szerepel.
Main függvény: Példaként összehasonlítja a két megoldást.

Maximumkeresés indexek kiválogatásával

Ebben a feladatban megállapítjuk, hogy az elemek közül melyik a legnagyobb, illetve azt is megmondjuk, hogy ez az elem hol található meg a tömbben (mi az indexe). Ha a legnagyobb elem többször is előfordul, akkor az összes előfordulásához kigyűjtjük az indexeket.

Gondolhatnánk, hogy ezt egy std::map adatszerkezettel oldhatjuk meg, ami kulcs-érték párokat tartalmazhat, de valójában elég lesz egyetlen kulcs-érték, amit az std::pair adatszerkezet képes tárolni. Az std::pair egyébként az std::map egyetlen eleme. Ez azért van így, mert csak egyetlen maximum érték lesz.

A függvényen belül először

//max with all indices
#include <iostream>
#include <vector>

std::pair<int, std::vector<int>> find_max_with_indices(const std::vector<int>& p_arr) {
  int max = p_arr[0];
  std::vector<int> indices = {0};

  for (int i = 1; i < p_arr.size(); ++i) {
    if (p_arr[i] > max) {
      max = p_arr[i];
      indices.clear();
      indices.push_back(i);
    } else if (p_arr[i] == max) {
      indices.push_back(i);
    }
  }

  return std::make_pair(max, indices);
}

int main() {
  std::vector<int> vec_example = {8, 8, 2, 4, -1, 11, 2, 11, 6, 7, 11};

  std::pair<int, std::vector<int>> max_with_indices = find_max_with_indices(vec_example);

  const int max = max_with_indices.first;
  const std::vector<int>& indices = max_with_indices.second;

  std::cout << "The max value in vec_example: " << max << '\n';

  std::cout << "All indices of " << max << ":\n";
  for (int index : indices) {
    std::cout << index << ' ';
  }
}

Ez a példakód nem kezeli azt, ha a függvénynek üres tömböt adunk át. Persze ebben a példában ez biztos nem fordul elő, de nézzük meg ezt azt esetet is. Például így, vagy C++17-től std::optional-el lehet megoldani:

//max with all indices
#include <iostream>
#include <vector>

std::pair<bool, std::pair<int, std::vector<int>>> find_max_with_indices(const std::vector<int>& p_arr) {
if (p_arr.empty()) { return {false, {0, {}}}; }
  
  int max = p_arr[0];
  std::vector<int> indices = {0};

  for (int i = 1; i < p_arr.size(); ++i) {
    if (p_arr[i] > max) {
      max = p_arr[i];
      indices.clear();
      indices.push_back(i);
    } else if (p_arr[i] == max) {
      indices.push_back(i);
    }
  }

  return {true, {max, indices}};
}

int main() {
  std::vector<int> vec_example = {};

  std::pair<bool, std::pair<int, std::vector<int>>> result = find_max_with_indices(vec_example);
  
  if (!result.first) {
    std::cout << "The array is empty\n";
  } else {
    const int max = result.second.first;
    const std::vector<int>& indices = result.second.second;

    std::cout << "The max value in vec_example: " << max << '\n';

    std::cout << "All indices of " << max << ":\n";
    for (int index : indices) {
      std::cout << index << ' ';
    }
  }
}

Kiválogatás indexek kiválogatásával

//TODO
/*Míg a maximumkeresésnél csak egyetlen érték lehetett a maximum, itt az összes különböző értékű elemnél ki kell gyűjteni a hozzá tartozó indexeket. Arra is ügyelni kell, hogy azok az elemek, amikhez az indexeket kigyűjtjük, csak egyszer szerepeljenek, mivel ha többször szerepelnek, akkor többször ki kell gyűjteni hozzájuk az indexeket, ami felesleges.

Először a filter_unique nevű függvénnyel kiválogatjuk egy halmaz (std::set) adatszerkezetbe a páros számokat. A halmaz adatszerkezetben egy elem csak egyszer szerepelhet, még akkor is, ha megpróbáljuk többször is hozzáadni az insert tagfüggvénnyel.

A filter_indices függvény lehet, hogy elsőre nem átlátható. Az indices az index többesszáma angolul vagyis indexek.

Egy ilyen típusú adatszerkezetbe gyűjtjük ki az elemeket:

std::vector<std::pair<int, std::vector<int>>>

Ez azt jelenti, hogy több olyan párt tárolunk, ahol a pár első eleme egy szám (az előző feladatban kigyűjtütt páros számok egyike), a pair második eleme pedig egy std::vector, ami majd az adott szám előfordulásait, vagyis indexeit fogja tartalmazni.

Ennek a függvénynek átadtuk a kiválogatott elemeket (a halmaz adatszerkezetet), illetve az std::vectort, amiben az eredeti elemek vannak. Ez utóbbiból tudjuk kiválogatni az elemek előfordulásait, indexeit.

Egy for ciklusban először egy std::pair adatszerkezet első elemének értékül adjuk a világogatott elemek (filtered_numbers) soron következő elemét. Az előfordulásokhoz egy belső for ciklus kell, amivel az std::vectoron megyünk végig, ami az eredeti elemeket tartalmazta.*/

#include <iostream>
#include <vector>
#include <map>
#include <functional>

bool is_even(int n) { return n % 2 == 0; }

std::map<int, std::vector<int>> filter_with_indices( 
const std::vector<int>& numbers,
const std::function<bool(int)>& predicate) {
  std::map<int, std::vector<int>> result;

  for (int i = 0; i < numbers.size(); ++i) {
    int val = numbers[i];
    if (predicate(val)) {
      result[val].push_back(i);
    }
  }

  return result;
}

int main() {
  std::vector<int> vec_example = {2, 4, -1, 11, 2, 11, 6, 4, 11};

  std::map<int, std::vector<int>> filtered_elements = filter_with_indices(vec_example, is_even);

  std::cout << "Filtered elements and indices:\n";
  for (std::pair<const int, std::vector<int>>& pair : filtered_elements) {
    int element = pair.first;
    const std::vector<int>& indices = pair.second;

    std::cout << element << ":\n";
    for (int idx : indices) {
      std::cout << idx << ' ';
    }
  std::cout << '\n';
  }
}

Buborékrendezés

//bubble sort
#include <iostream>
#include <random>
#include <vector>

int main() {
  std::vector<int> stdvec_example = {9,6,11,3,1,7,8,-2};

  for (int i = stdvec_example.size()-1; i >= 0; --i) {
    for (int j = 0; j < i; ++j) {
      if (stdvec_example[j] > stdvec_example[j+1]) {
        int temp = stdvec_example[j];
        stdvec_example[j] = stdvec_example[j+1];
        stdvec_example[j+1] = temp;
      }
    }
  }

  for (const int& element : stdvec_example) {
    std::cout << element << ' ';
  }
  std::cout.put('\n');
}

Egyéb tananyagok

előző tananyagrész: STL

Szólj hozzá!

[programozási tételek ]

[itk] Számítástechnika kezdőknek

C++ programozás kezdőknek - programozási tételek

Tartalom

Néhány gondolat a programozási tételekről

Pontosan miket sorolunk a programozási tételek közé?

Nincs arról közös megegyezés, hogy pontosan hogyan valósítsuk meg (a kódban) a programozási tételeket

Honnan származik a programozási tételek elnevezés?

Megszámlálás

Összegzés

Maximumkiválasztás

Feltételes maximumkeresés

Sorozatszámítás

Eldöntés

Kiválasztás

Lineáris keresés

Logaritmikus keresés, vagy más néven bináris keresés

Kiválogatás

Szétválogatás

In-place (helyben végzett) szétválogatás, más néven partícionálás

In-place szétválogatás rendezéssel

Összefésülés

Összefuttatás

Maximumkeresés indexek kiválogatásával

Kiválogatás indexek kiválogatásával

Buborékrendezés

Egyéb tananyagok

A bejegyzés trackback címe:

Kommentek:

C++ programozás kezdőknek - programozási tételek

Tartalom

Néhány gondolat a programozási tételekről

Pontosan miket sorolunk a programozási tételek közé?

Nincs arról közös megegyezés, hogy pontosan hogyan valósítsuk meg (a kódban) a programozási tételeket

Honnan származik a programozási tételek elnevezés?

Megszámlálás

Összegzés

Maximumkiválasztás

Feltételes maximumkeresés

Sorozatszámítás

Eldöntés

Kiválasztás

Lineáris keresés

Logaritmikus keresés, vagy más néven bináris keresés

Kiválogatás

Szétválogatás

In-place (helyben végzett) szétválogatás, más néven partícionálás

In-place szétválogatás rendezéssel

Összefésülés

Összefuttatás

Maximumkeresés indexek kiválogatásával

Kiválogatás indexek kiválogatásával

Buborékrendezés

Egyéb tananyagok

Ajánlott bejegyzések:

A bejegyzés trackback címe:

Kommentek: