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
Tartalom
- STL adatszerkezetek:
std::array és std::vector, std:list, std::set, std::map, std::stack, std::queue, std::deque, std::pair, std::tuple - STL algoritmusok:
végiglépkedés az elemeken, std::accumulate, std::copy, std::copy_if, std::count, std::count_if, std::iota, std::equal, std::fill, std::find, std::find_if, std::generate, std::max_element, std::min_element, std::merge, std::replace, std::reverse, std::search, std::shuffle, std::sort, std::swap, std::transform
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::array, std::vector
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::map, std::set, 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 fordítási időben nem ismert (pl. ha az elemszámot a felhasználótól kérjük be, vagy fájlból olvassuk be).
Ebben a tananyagrészben viszonylag részletesen tárgyaltuk a használatukat:
std::list
A C++ nyelvben a std::list egy doubly linked list (egyszeresen láncolt lista az std::forward_list). Végeredményben hasonló az std::vector-hoz, elemeket lehet benne tárolni, módosítani, törölni, viszont az elemek tárolása máshogy van megvalósítva, mint az std::vector esetén.
Míg az std::vector esetén egy egybefüggő memóriaterületen tároljuk az elemeket (emiatt mondhatjuk, hogy az std::vector egy tömbszerű adatszerkezet), addig az std::list esetén az elemek a memóriában szétszórtan helyezkednek el, és minden elem (ha úgy tetszik node) a háttérben tárolja azt is, hogy a következő elem hol található a memóriában... illetve mivel doubly linked listről van szó, azt is tárolja, hogy az előző elem hol helyezkedik el. Az első és az utolsó elemet kivéve. Nyilván az első elem nem tudja tároln, hogy az előző elem hol helyezkedik el a memóriában, az utolsó elem pedig azt nem tudja tárolni, hogy a következő elem hol helyezkedik el 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.
A használata az std::vector helyett akkor lehet indokolt, ha tudjuk, hogy a memóriában nincs egy std::vector számára lefoglalható egybefüggő terület, vagy akkor, ha többször használjuk az új elem hozzáadása műveletet mint egy adott elem elérését.
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::map
Asszociatív tömb, dictionary, kulcs-érték párok tárolására alkalmas. Másképp fogalmazva egy olyan tömb, ahol az indexek nem feltétlenül számok 0-tól elemszám-1-ig, hanem tetszőleges típusúak, például karakter vagy std::string típusúak.
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
A program futtatásakor 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>
//define print map
void print(const std::pair<char,int>& p) {
std::cout << p.first << ':' << p.second << '\n';
}
int main() {
//define map
std::map<char,int> example;
//process the input from user
char ch;
while(std::cin >> ch) {
++example[ch];
}
//print map
std::for_each(example.begin(), example.end(), print);
}std::stack
Verem adatszerkezet. LIFO-nak szokták nevezni (last in first out, az utoljára belerakott (másképp fogalmazva a legfelső) elemet lehet kivenni belőle először).
Nem lehet elérni egyszerre az összes elemét (pl. ranged for ciklussal kiíratni), hanem mindig csak azt, amit utoljára beletettünk. Másképp fogalmazva, alapvetően csak a legtetején lévő elemet lehet kiiratni, a többit csak akkor, ha kiveszünk belőle további elemeket.
Felmerülhet, hogy miért jó a std::stack, ha korlátozottabb műveletei vannak, mint pl. az std::vector-nak? Erre az egyszerű válasz az, hogy olyan műveletek végzésére van optimalizálva, mindig csak a legfelső elemre van szükség, illetve a többire csak akkor, ha azokat egyenként kiszedegetjök.
C++ nyelvben a top() tagfüggvény adja vissza a legfelső elem értékét, a pop() tagfüggvény pedig nem ad vissza semmit, hanem eltávolítja a legutoljára belerakott elemet, ezért ezeket gyakran együtt szoktuk használni.
Könnyen előfordulhat, hogy ez más programozási nyelvekben nem így van, hanem a pop() egyúttal vissza is adja a kivett elemet.
//std::stack example
#include <iostream>
#include <stack>
int main() {
std::stack<int> example;
example.push(5);
example.push(2);
example.push(1);
std::cout << example.top() << '\n'; //1
//removes the 1 value
example.pop();
std::cout << example.top() << '\n'; //2
}Érdemes lehet tudni, hogy a C++-ban a std::stack egy úgynevezett adaptor adatszerkezet, ami a std::stack esetén azt jelenti, hogy egy másik adatszerkezetből (ami alapbeállítás szerint a std::deque) LIFO működést kényszerít ki.
std::queue
Sor adatszerkezet. A verem ellentéte. FIFO-nak szokták nevezni (first in first out, az először belerakott elemet lehet kivenni belőle először).
A többi dologban hasonló, mint az std::stack.
//std::queue example
#include <iostream>
#include <queue>
int main() {
std::queue<int> example;
example.push(5);
example.push(2);
example.push(1);
std::cout << example.front() << '\n'; //5
//removes the 5 value
example.pop();
std::cout << example.front() << '\n'; //2
}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::deque example
#include <iostream>
#include <deque>
int main() {
std::deque<int> example;
example.push_front(5);
example.push_front(4);
example.push_front(3);
example.push_front(2);
example.push_front(1);
std::cout << example.front() << '\n'; //1
//removes the 1 value
example.pop_front();
std::cout << example.front() << '\n'; //2
std::cout << example.back() << '\n'; //5
//removes the 5 value
example.pop_back();
std::cout << example.back() << '\n'; //4
}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
for ciklus + iterátor
//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 függvény + iterátor
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 << ' ';});
}std::for_each függvény + reverse iterátor
//std::for_each example
#include <iostream>
#include <string>
#include <algorithm>
int main() {
std::string str_example = "something";
std::string str_reverse = "";
std::for_each(
str_example.rbegin(), str_example.rend(), [&str_reverse](const char& element) {str_reverse += element;}
);
std::cout << str_reverse << '\n';
}Természetesen ranged for ciklussal is végiglépkedhetünk STL adatszerkezetek elemein, de ebben a tananyagrészben ez azért nincs itt felsorolva, mert a ranged for ciklus nem STL algoritmus. A használatát ebben a tananyagrészben tárgyaltuk:
A lentebbi példákban is (pl. az eredmény kiíratásakor) előfordul a ranged for ciklus használata.
std::accumulate
Tipikusan egy adatszerkezet elemeinek ö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);
int prod = std::accumulate(example.begin(), example.end(), 1, std::multiplies<int>());
std::cout << "sum: " << sum << '\n';
std::cout << "prod: " << prod << '\n';
}De használhatjuk például egy olyan string legyártásához is, ahol mondjuk vesszővel elválasztva szerepelnek az elemek.
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).
A neve alapján esetleg összekeverhető a nem szabványos itoa függvénnyel, ami egy int típusú értéket C stílusú stringgé alakít.
//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 it_max;
it_max = std::max_element(example.begin(),example.end());
std::cout << "max element: " << *it_max << '\n';
std::cout << "index of max element: " << std::distance(example.begin(), it_max) << '\n';
}std::min_element
Minimumkeresés
//std::min_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 it_min;
it_min = std::min_element(example.begin(),example.end());
std::cout << "min element: " << *it_min << '\n';
std::cout << "index of min element: " << std::distance(example.begin(), it_min) << '\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::search
Egy STL adatszerkezet tartalmazz-e egy másik STL adatszerkezet elemeit. Ha több elemet vizsgálunk, akkor számít az elemek sorrendje.
//std::search example
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::cout.setf(std::ios::boolalpha);
std::vector<int> find_in = {9, 8, 7, 6, 5};
std::vector<int> find_what = {7};
//text output
std::cout << "Does {";
std::for_each(find_in.begin(), find_in.end(),[](const int& element){ std::cout << element << ' ';});
std::cout << "} includes ";
std::for_each(find_what.begin(), find_what.end(),[](const int& element){ std::cout << element << "? ";});
//search
std::cout << (std::search(find_in.begin(), find_in.end(), find_what.begin(), find_what.end()) != find_in.end()) << '\n';
}std::shuffle
Elemek összekeverése.
//std::shuffle example
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
int main() {
std::random_device rnd_device;
std::mt19937 rnd_generator(rnd_device());
std::vector<int> example = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
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');
}A fordított sorrendben szeretnénk rendezni az elemeket, akkor ahhoz elég az interátorokat kicserélni reverse iterátorra, vagyis begin() helyett rbegin(), end() helyett pedig rend()
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.
Számok kétszerese
//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');
}Nagybetűsítés
//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';
}random nagybetűsítés vagy kisbetűsítés
//std::transform example
#include <iostream>
#include <random>
#include <cctype>
#include <vector>
#include <algorithm>
//random number, 0 or 1
int rnd_number() {
static std::mt19937 rnd_generator( std::random_device{}());
std::uniform_int_distribution<int> int_dist(0,1);
return int_dist(rnd_generator);
}
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 rnd_number() ? toupper(c) : tolower(c);});
std::cout << output << '\n';
}Egyéb tananyagok
- sandordargo.com - The big STL Algorithms tutorial
- 105 STL Algorithms in Less Than an Hour (videó)
- freeCodeCamp.org - Data Structures - Full Course Using C and C++ (videó)
- Data Structures and Algorithms in C++ (videó)
- Constructing Generic Algorithms: Principles and Practice (videó)
előző tananyagrész: templatek
következő tananyagrész: programozási tételek
