{"id":162,"date":"2021-10-28T11:08:28","date_gmt":"2021-10-28T11:08:28","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=162"},"modified":"2024-05-17T20:31:19","modified_gmt":"2024-05-17T20:31:19","slug":"stl","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/stl\/","title":{"rendered":"STL \u00een C++"},"content":{"rendered":"\n

STL (Standard Template Library)<\/strong> reprezint\u0103 structuri, func\u021bii \u0219i algoritmi care pot fi de ajutor atunci c\u00e2nd avem nevoie s\u0103 cre\u0103m algoritmi rapizi. C\u00e2teva libr\u0103rii din STL sunt <vector><\/em>, <set><\/em>, <unordered_multiset><\/em>, <map><\/em>, \u00eens\u0103 \u00een acest articol vom discuta doar despre primele dou\u0103.<\/p>\n\n\n\n

Folosind libr\u0103ria <vector><\/em>, putem face un vector<\/strong><\/a> care vine automat cu c\u00e2teva func\u021bii ajut\u0103toare. Foarte important este c\u0103 vectorul pe care \u00eel \u0219tie toat\u0103 lumea (int v[50]<\/em>) se nume\u0219te de fapt array<\/strong><\/a> \u0219i nu este la fel cu vectorul din STL. Pentru a include aceast\u0103 libr\u0103rie trebuie s\u0103 introducem #include <vector><\/em> la \u00eenceputul sursei, iar ca s\u0103 declar\u0103m un vector scriem vector<int> v;<\/em>. Aceast\u0103 scriere va crea un vector numit v<\/em> care va con\u021bine doar elemente de tip int<\/em>. Observ\u0103m c\u0103, la declararea vectorilor \u00een STL, nu trebuie specificat\u0103 dimensiunea vectorului, spre deosebire de declararea unui array. Pentru a accesa elemente \u0219i a atribui valori \u00een vector, sintaxa este la fel ca la un array.<\/p>\n\n\n\n

\"\"
Exemplu de algoritm care folose\u0219te vectorii din STL<\/figcaption><\/figure><\/div>\n\n\n\n
\"\"
Exemplu de date de intrare \u0219i afi\u0219area datelor de ie\u0219ire pentru algoritmul de mai sus<\/figcaption><\/figure><\/div>\n\n\n\n

\u00cenainte de descrierea algoritmului de mai sus, trebuie s\u0103 \u0219ti\u021bi c\u0103 vectorii din STL trebuie s\u0103 porneasc\u0103 de la indicele 0 pentru a func\u021biona corespunz\u0103tor. Dac\u0103 prima valoare din vector este pe pozi\u021bia 1, unele func\u021bii nu vor mai returna rezultatul dorit. La \u00eenceputul sursei, se includ libr\u0103riile <iostream><\/em> \u0219i <vector><\/em> pentru a putea citi \u0219i afi\u0219a pe ecran \u0219i pentru a folosi vectorii din STL. \u00cen func\u021bia main, se declar\u0103 un vector \u00een STL v<\/em> care va avea doar elemente de tipul int<\/em>, \u0219i 3 variabile de tipul int<\/em>: n<\/em>, i<\/em> \u0219i x<\/em>. Citim n<\/em> de la tastatur\u0103, care va reprezenta num\u0103rul de elemente pe care le vom citi \u00een continuare. Apoi, de la i=0<\/em> p\u00e2n\u0103 la i=n-1<\/em>, vom citi un num\u0103r \u00een variabila x<\/em>, \u0219i \u00eel vom pune la sf\u00e2r\u0219itul vectorului folosind func\u021bia v.push_back(x)<\/em><\/strong>. Dup\u0103 ce se termin\u0103 bucla anterioar\u0103, elimin\u0103m ultimul element din vector folosind func\u021bia v.pop_back()<\/em><\/strong> \u0219i ad\u0103ug\u0103m la sf\u00e2r\u0219itul vectorului valoarea 5. Practic, \u00eenlocuim ultima valoare cu 5. Dup\u0103 aceasta, elementului de pe pozi\u021bia 2, adic\u0103 elementului al treilea din vector (pentru c\u0103 indexarea \u00eencepe de la 0) i se va atribui valoarea 1, iar apoi se va face afi\u0219area elementelor vectorului astfel: \u201epentru fiecare element nr<\/em> din vectorul v<\/em>, afi\u0219eaz\u0103 nr\u201d. Aceast\u0103 scriere poate fi folositoare, \u0219i uneori obligatorie. auto nr \u00eenseamn\u0103 c\u0103 nu i-am specificat tipul de dat\u0103 variabilei nr \u0219i compilatorul trebuie s\u0103 \u00ee\u0219i dea seama singur ce tip de dat\u0103 are. Sigur c\u0103 auto nr putea fi \u00eenlocuit cu int nr<\/em>, doar c\u0103 acea scriere este mai folosit\u0103, mai ales atunci c\u00e2nd avem de-a face cu iteratori.<\/p>\n\n\n\n

La fiecare tip de dat\u0103 din STL exist\u0103 o func\u021bie numit\u0103 size()<\/em><\/strong> care returneaz\u0103 num\u0103rul de elemente din acea structur\u0103 (v.size()<\/em>).<\/p>\n\n\n\n

Un set<\/strong><\/a> <\/em>este tot o structur\u0103 de date care memoreaz\u0103 valori, \u00eens\u0103 aceste valori sunt ordonate automat la introducerea lor \u00een acea structur\u0103; de asemenea, dac\u0103 un element introdus exist\u0103 deja \u00een set, nu va mai fi introdus. Cu alte cuvinte, set<\/em> memoreaz\u0103 valori ordonate \u0219i distincte. Exist\u0103 \u0219i unordered_set<\/em><\/strong> (memoreaz\u0103 valori distincte, neordonate), multiset<\/em><\/strong> (memoreaz\u0103 toate valorile, ordonate) \u0219i unordered_multiset<\/em><\/strong> (memoreaz\u0103 toate valorile, neordonate).<\/p>\n\n\n\n

La structura STL set<\/em>, accesarea \u0219i atribuirea elementelor nu se mai poate face cu indici (v[5] = 62<\/em>), ci se face doar prin func\u021bii \u0219i prin iteratori.<\/p>\n\n\n\n

Un iterator<\/strong><\/a> reprezint\u0103 o por\u021biune din memorie care poate s\u0103 succede sau s\u0103 precede \u00een memorie. Iteratorii sunt specifici pentru fiecare structur\u0103 \u0219i fiecare tip de dat\u0103 din structur\u0103, \u0219i se declar\u0103 cu urm\u0103toarea form\u0103: structur\u0103stl<tipdedat\u0103>::iterator numeiterator;<\/em><\/strong>. Pentru a crea un iterator pentru structura set \u0219i tipul de date int<\/em>, scriem set<int>::iterator itr;<\/em>.<\/p>\n\n\n\n

\"\"
Exemplu de algoritm care folose\u0219te structura set din STL<\/figcaption><\/figure><\/div>\n\n\n\n
\"\"
Exemplu de date de intrare \u0219i afi\u0219area datelor de ie\u0219ire la programul din exemplul de mai sus<\/figcaption><\/figure><\/div>\n\n\n\n

La \u00eenceput, algoritmul de mai sus include libr\u0103riile iostream<\/em> \u0219i set<\/em>. Apoi, \u00een main, se declar\u0103 un set v <\/em>care con\u021bine valori int<\/em>, un iterator itr <\/em>pentru acest set \u0219i 3 variabile int<\/em>: n<\/em>, x<\/em> \u0219i i<\/em>. Dup\u0103 ce se cite\u0219te n <\/em>de la tastatur\u0103, mergem cu un for<\/em> de la i=0<\/em> p\u00e2n\u0103 la i=n-1<\/em>, citim x <\/em>de la tastatur\u0103 \u0219i \u00eel inser\u0103m \u00een set folosind func\u021bia v.insert(x)<\/em><\/strong>. Atunci c\u00e2nd se insereaz\u0103 un element \u00eentr-un set, elementul este a\u0219ezat automat \u00eentr-o pozi\u021bie astfel \u00eenc\u00e2t numerele s\u0103 fie ordonate. Dup\u0103 aceast\u0103 bucl\u0103 for<\/em>, afi\u0219\u0103m n <\/em>\u0219i v.size() <\/em>pentru a compara num\u0103rul de elemente de la \u00eenceput \u0219i num\u0103rul de elemente de la sf\u00e2r\u0219it. La afi\u0219area datelor de ie\u0219ire, observ\u0103m c\u0103 n <\/em>este diferit de v.size()<\/em>. Aceasta se datoreaz\u0103 faptului c\u0103 exist\u0103 2 numere identice \u00een datele de intrare care, odat\u0103 cu \u00eencercarea introducerii am\u00e2ndurora \u00een set, unul nu se va mai insera. Putem vedea acest lucru \u0219i la afi\u0219area elementelor din set, num\u0103rul 56 nefiind afi\u0219at de dou\u0103 ori. \u00cenapoi la algoritm \u2014 observ\u0103m un for <\/em>care atribuie valoarea v.begin()<\/em><\/strong> lui itr<\/em>, compar\u0103 valoarea lui itr <\/em>cu v.end()<\/em><\/strong> \u0219i incrementeaz\u0103 pe itr<\/em> cu 1. Mai jos este o imagine care reprezint\u0103 elementele din set dup\u0103 ce au fost inserate, precum \u0219i unde se afl\u0103 v.begin()<\/em> \u0219i v.end()<\/em>. Un lucru important de re\u021binut este c\u0103 v.begin()<\/em> \u0219i v.end()<\/em> nu sunt valori<\/span><\/strong>. Acestea reprezint\u0103 doi iteratori cu ajutorul c\u0103rora putem parcurge set-ul, adic\u0103 dou\u0103 puncte \u00een memorie.<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Atribuim iteratorului nostru itr <\/em>valoarea v.begin()<\/em>, adic\u0103 \u00eei ar\u0103t\u0103m \u00een memorie de unde s\u0103 \u00eenceap\u0103 for<\/em>-ul. Iteratorii pot fi incrementa\u021bi cu 1 folosind operatorul ++, deci \u00eencepem de la v.begin()<\/em>, adun\u0103m iteratorul cu 1 de fiecare dat\u0103, \u0219i trebuie s\u0103 ne oprim cu aceast\u0103 parcurgere atunci c\u00e2nd itr <\/em>ajunge la v.end()<\/em>, deci, ca condi\u021bie pentru for<\/em>, itr != v.end()<\/em>. Forma final\u0103 a for<\/em>-ului este prezentat\u0103 \u00een imaginea cu codul surs\u0103 de mai sus. Pentru a afi\u0219a valoarea iteratorului la care suntem \u00een for<\/em>, folosim asterisk-ul (*) \u00eenaintea iteratorului<\/strong>. Folosind aceast\u0103 nota\u021bie, compilatorul va \u0219ti c\u0103 vrem valoarea numeric\u0103 din iterator, \u0219i nu locul \u00een memorie unde se afl\u0103 iteratorul. De aceea, \u00een for <\/em>d\u0103m cout <\/em>la *itr<\/em><\/strong>, adic\u0103 la num\u0103rul din locul unde se afl\u0103 iteratorul.<\/p>\n\n\n\n

Foarte important de cunoscut este \u0219i structura map<\/strong><\/a>. Exist\u0103 mult mai multe tipuri de structuri de date \u00een STL, o list\u0103 cu ele o pute\u021bi g\u0103si aici<\/a>.<\/p>\n\n\n\n

STL-ul este foarte rapid ca timp de execu\u021bie \u0219i este important s\u0103 \u0219ti\u021bi s\u0103 \u00eel folosi\u021bi c\u00e2nd v\u0103 afla\u021bi la olimpiade sau concursuri de informatic\u0103, sau chiar atunci c\u00e2nd face\u021bi probleme de informatic\u0103 de acas\u0103. Pentru c\u0103 acesta nu se pred\u0103, de obicei, \u00een \u0219coli, trebuie s\u0103 citi\u021bi \u0219i s\u0103 \u00eenv\u0103\u021ba\u021bi de pe internet aceste no\u021biuni elementare ale limbajului C++. Spor la \u00eenv\u0103\u021bat!<\/p>\n","protected":false},"excerpt":{"rendered":"

Acest articol prezint\u0103 c\u00e2teva noi tipuri de date care sunt de ajutor la rezolvarea problemelor de informatic\u0103.<\/p>\n","protected":false},"author":4,"featured_media":188,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43,44],"tags":[39,19,38,36,37],"class_list":["post-162","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cpp","category-stl","tag-array","tag-c","tag-set","tag-stl","tag-vector"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/162","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/comments?post=162"}],"version-history":[{"count":14,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/162\/revisions"}],"predecessor-version":[{"id":271,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/162\/revisions\/271"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/188"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}