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

C++ programozás kezdőknek - STL

[2022. április 04.] [ christo161 ]

Ebben a tananyagrészben a standard library azon részéről lesz szó, ami az adatszerkezeteket és algoritmusokat érinti. Ezt bizonyos tananyagok STL-nek (azaz standard template librarynek) nevezik, de az is előfordul, hogy egyes tananyagok az egész standard libraryt hívják STL-nek.

előző tananyagrész: templatek
következő tananyagrész: programozási tételek

Alapvető tudnivalók

Az adatszerkezetek több elem tárolására alkalmasak. C++ nyelvben ezek az elemek jellemzően azonos típusúak (pl. egy std::vectorban nem tárolhatunk egyszerre különböző típusú elemeket).

Az stl főbb adatszerkezetei

std::vector, std::array

Az esetek túlnyomó részében teljesen jó, ha std::vectort vagy std::arrayt használunk, és nem kell foglalkozni az egyéb adatszerkezetekkel (mint például std::list, std::deque, satöbbi).

std::array-t akkor használunk, ha az elemszám fordítási időben ismert.

std::vector-t akkor használunk, ha az elemszám változik, vagy pedig ha az elemszámot a felhasználótól kérjük be, vagy fájlból olvassuk be.

Ebben a tananyagrészben tárgyaltuk a használatukat:

std::list

Láncolt lista. Hasonló a vectorhoz, azzal a különbséggel, hogy az elemek nem egymás után helyezkednek el a memóriában, hanem szétszórtan. Minden elem tartalmaz egy mutatót is, aminek segítségével megtalálható a következő elem helye a memóriában.

Az új elem hozzáadása gyorsabb, mint az std::vector esetén, viszont egy adott elem megtalálása lassabb.

Fontos tudni, hogy nem minden művelet működik az std::listtel. Például nem lehet indexelni a [] operátorral, illetve például nem működik az std::sort.

//std::list example
#include <iostream>
#include <string>
#include <list>
#include <algorithm>

int main() {
  std::list<int> example = {2,3,5,7};
  example.push_front(1);
  example.push_back(9);

  std::list<int>::iterator it = std::find(example.begin(),example.end(),5);
  if (it != example.end()) {
    example.insert(it,6);
  }

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

std::set

Halmaz. Nem lehet benne két azonos értékű elem.

//std::set example
#include <iostream>
#include <set>

int main() {
  std::set<int> example;
  example.insert(5);
  example.insert(5);
  example.insert(2);

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

Ebben a tananyagrészben a speciális eseteknél szerepelt egy std::set-et használó példa:

std::deque

Kettős végű sor. Arra van optimalizálva, hogy ne csak a végére, hanem az elejére is hozzá lehessen adni új elemet, illetve el lehessen távolítani.

std::map

Asszociatív tömb, dictionary, kulcs-érték párok tárolására alkalmas.

Ebben a példában kiíratjuk, hogy a felhasználó által beírt szöveg hány azonos karaktert tartalmaz. Pl. almafa esetén:

a:3
f:1
l:1
m:1

Linuxon ctrl+d billentyűkombinációval lehet a bemenetet lezárni, Windowsban pedig ctrl+z-vel.

//std::map example
#include <iostream>
#include <map>
#include <algorithm>

void print(const std::pair<char,int>& p) {
std::cout << p.first << ':' << p.second << '\n';
}

int main() {
  std::map<char,int> st;
  char ch;

  while(std::cin >> ch) {
    ++st[ch];
  }

  std::for_each(st.begin(), st.end(), print);
}

std::stack

Verem adatszerkezet. LIFO-nak szokták nevezni (last in first out, az utoljára belerakott elemet lehet kivenni először). Nem lehet kiíratni egyszerre az összes elemét, hanem mindig csak azt, amit utoljára beletettünk.

//std::stack example
#include <iostream>
#include <stack>

int main() {
  std::stack<int> example;
  example.push(5);
  example.push(2);

  std::cout << example.top() << '\n';

  example.pop();

  std::cout << example.top() << '\n';
}

std::pair

Rendezett pár. Egy std::pair-ben egyszerre két érték tárolható, melyek lehetnek akár különböző típusúak.

//std::pair example
#include <iostream>
#include <string>
#include <utility>

int main() {
  std::pair<std::string,int> example;
  example.first = "example";
  example.second = 1;

  std::cout << example.first << ' ' << example.second << '\n';
}

std::tuple

Rendezett N-es. Egy std::tuple-ben egyszerre több, akár egymástól különböző típusú érték tárolható.

//std::tuple example
#include <iostream>
#include <string>
#include <tuple>

int main() {
  std::tuple<std::string, int, double> example = std::make_tuple("example", 1, 2.5);

  std::cout << std::get<0>(example) << ", " << std::get<1>(example) << ", " << std::get<2>(example) << '\n';

  std::get<0>(example) = "example2";

  std::cout << std::get<0>(example) << ", " << std::get<1>(example) << ", " << std::get<2>(example) << '\n';
}

Algoritmusok

Végiglépkedés az elemeken iterátorral

//iterator example
#include <iostream>
#include <iterator>
#include <vector>

int main() {
  std::vector<int> example = { 1, 2, 3, 4, 5 };

  std::vector<int>::iterator it;

  for (it = example.begin(); it < example.end(); ++it) {
    std::cout << *it << " ";
  }
}

std::for_each

A for_each függvénnyel végiglépkedünk az elemeken, és valamilyen műveletet végrehajtunk minden elemre.

//std::for_each example
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> example = {2,3,5,4};

  //modify elements
  std::for_each(example.begin(), example.end(), [](int& element) {element *= 2;});
  //print elements
  std::for_each(example.begin(), example.end(),[](const int& element){ std::cout << element << ' ';});
}

Végiglépkedés az elemeken fordítva. Például egy string megfordítása:

//std::for_each example
#include <iostream>
#include <string>
#include <algorithm>

int main() {
  std::string str_example = "something";

  std::string reverse = "";

  std::for_each(
    str_example.rbegin(), str_example.rend(), [&reverse](const char& element) {reverse += element;}
  );

  std::cout << reverse << '\n';
}

std::accumulate

Elemek összeadása vagy összeszorzása.

//std::accumulate example
#include <iostream>
#include <vector>
#include <numeric>

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

  int sum = std::accumulate(example.cbegin(), example.cend(), 0);

  std::cout << sum << '\n';
}

std::copy

Az std::copy segítségével lemásolhatjuk például egy std::vector tartalmát egy másik std::vectorba, akár fordított sorrendben is.

//std::copy example
#include <iostream>
#include <vector>
#include <algorithm>

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

  std::copy(input.rbegin(), input.rend(), std::back_inserter(output));

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

std::copy_if

Egy adatszerkezetből egy másik adatszerkezetbe átmásoljuk azokat az elemeket, amelyekre teljesül egy feltétel. Például a páros számokat kiválogatjuk az egyik std::vectorból a másikba.

//std::copy_if example
#include <iostream>
#include <vector>
#include <algorithm>

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

  std::copy_if(input.cbegin(), input.cend(), std::back_inserter(output), [](const int& number) { return number % 2 == 0; });

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

Az std::copy_if függvénnyel az is megvalósítható, hogy nem egy másik adatszerkezetbe másoljuk át a feltételnek megfelelő elemeket, hanem kiíratjuk őket.

//std::copy_if example
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

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

  std::copy_if(
    input.cbegin(), input.cend(), std::ostream_iterator<int>(std::cout, " "), [](const int& number) { return number % 2 == 0; }
  );

  std::cout.put('\n');
}

std::count

Hány darab adott érték van pl. egy std::vectorban.

//std::count example
#include <iostream>
#include <vector>
#include <algorithm>

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

  int num_items = std::count(example.cbegin(), example.cend(), 4);

  std::cout << "number of 4s: " << num_items << '\n';
}

std::count_if

Hány darab, a feltételnek megfelelő érték van egy adatszerkezetben. Pl. hány darab páros szám van egy std::vectorban.

//std::count_if example
#include <iostream>
#include <vector>
#include <algorithm>

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

  int num_items = std::count_if(example.cbegin(), example.cend(), [](const int& i){return i % 2 == 0;});

  std::cout << "number of even numbers: " << num_items << '\n';
}

std::iota

Egy adott számértéktől kezdődően növekvő számsorozattal tölti ki a konténert (pl. egy std::vectort).

//std::iota example
#include <iostream>
#include <vector>
#include <numeric>

int main() {
  std::vector<int> example;
  example.resize(10);

  std::iota(example.begin(), example.end(), 42);

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

std::equal

Megvizsgálja, hogy két tartományban azonos értékek találhatók-e.

//std::equal example
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> example1 = {12,3,5,8,-2,1,16,9};
  std::vector<int> example2 = {12,3,5,8,-2,1,16,9};
  std::vector<int> example3 = {12,3,5,8,-2,1,16,10};
  bool equal = false;
  std::cout.setf(std::ios::boolalpha);

  equal = std::equal(example1.begin(), example1.end(), example2.begin());

  std::cout << "example1 == example2: " << equal << '\n';

  equal = std::equal(example1.begin(), example1.end(), example3.begin());

  std::cout << "example1 == example3: " << equal << '\n';
}

std::fill

Egy konténer (pl. std::vector) kitöltése adott értékkel.

//std::fill example
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> example;
  example.resize(10);

  std::fill(example.begin(), example.end(), -1);

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

std::find

Egy érték megkeresése egy adatszerkezetben.

//std::find example
#include <iostream>
#include <vector>
#include <algorithm>

int main () {
  std::vector<int> example = {9, 8, 7, 6, 5};

  std::vector<int>::iterator it = std::find(example.begin(), example.end(), 8);

  if (it != example.end()) {
    std::cout << "Element found in the vector: " << *it << '\n';
  } else {
    std::cout << "Element not found in the vector\n";
  }
}

std::find_if

Egy adott feltételnek megfelelő érték megkeresése egy adatszerkezetben. Pl. páros szám keresése egy std::vectorban.

//std::find_if example
#include <iostream>
#include <vector>
#include <algorithm>

int main () {
  std::vector<int> example = {9, 1, 8, 7, 6, 5};

  std::vector<int>::iterator it = std::find_if(example.begin(), example.end(), [](const int& i){return i % 2 == 0;});

  if (it != example.end()) {
    std::cout << "Even number found in the vector: " << *it << '\n';
  } else {
    std::cout << "Even number not found in the vector\n";
  }
}

std::generate

Egy függvény által visszaadott eredménnyel tölti fel a megadott adatszerkezetet. Például random generált számokkal:

//std::generate example
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

int rnd_number() {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(1,100);
  return int_dist(rnd_generator);
}

int main() {
  std::vector<int> example = {12,3,5,8,-2,1,16,9};
  example.resize(10);

  std::generate(example.begin(), example.end(), rnd_number);

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

std::max_element

Maximumkeresés

//std::max_element example
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> example = {12,3,5,8,-2,1,16,9};
  std::vector<int>::iterator max;

  max = std::max_element(example.begin(),example.end());

  std::cout << "max element: " << *max << '\n';
  std::cout << "index of max element: " << std::distance(example.begin(), max) << '\n'; 
}

std::merge

Két rendezett tartományt összefésül

//std::merge example
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> example1 = {2,8,3,10};
  std::vector<int> example2 = {5,13,9,1};

  std::sort(example1.begin(), example1.end());
  std::sort(example2.begin(), example2.end());

  std::vector<int> example3;
  std::merge(example1.begin(), example1.end(), example2.begin(), example2.end(), std::back_inserter(example3));

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

std::replace

Egy adott érték összes előfordulásának felülírása egy másik értékkel. Ebben a példában az 1-eseket kicseréljük -1-re.

//std::replace example
#include <algorithm>
#include <vector>
#include <iostream>

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

  std::replace(example.begin(), example.end(),1, -1);

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

std::reverse

Egy adatszerkezet elemeit fordított sorrendbe rendezi. Lehet az akár egy string is.

//std::reverse example
#include <iostream>
#include <string>
#include <algorithm>

int main() {
  std::string str = "something";

  std::reverse(str.begin(), str.end());

  std::cout << str << '\n';
}

std::shuffle

Elemek összekeverése.

//std::shuffle example
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

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

  std::random_device rnd_device;
  std::mt19937 rnd_generator(rnd_device());

  std::shuffle(example.begin(), example.end(), rnd_generator);

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

std::sort

Rendezés. Például egy std::vector elemeit tudjuk vele sorbarendezni.

//std::sort example
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> example = {9,6,1,13,-2};

  std::sort(example.begin(), example.end());

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

std::swap

2 változó vagy 2 adatszerkezet cseréje.

//std::swap example
#include <iostream>
#include <vector>
#include <algorithm>

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

  std::swap(example1, example2);

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

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

Az std::stringeknek van saját swap tagfüggvényük, ami optimálisabb megoldást nyújt. Ez esetben részesítsük előnyben a tagfüggvényt.

std::transform

Egy másik konténerbe előállítja az egyik konténer elemeinek módosított értékét.

//std::transform example
#include <iostream>
#include <vector>
#include <algorithm>

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

  std::transform(input.cbegin(), input.cend(), std::back_inserter(output), [](int number) {return 2*number;});

  for (const int& element : output) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}
//std::transform example
#include <iostream>
#include <cctype>
#include <vector>
#include <algorithm>

int main () {
  std::string input = "hello world!";
  std::string output{};

  std::transform(input.cbegin(), input.cend(), std::back_inserter(output), [](const unsigned char& c) {return toupper(c);});

  std::cout << output << '\n';
}

Egyéb tananyagok

előző tananyagrész: templatek
következő tananyagrész: programozási tételek

A bejegyzés trackback címe:

https://itkezdoknek.blog.hu/api/trackback/id/tr5217795497

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.
süti beállítások módosítása