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
