{"id":316,"date":"2022-04-16T16:03:08","date_gmt":"2022-04-16T16:03:08","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=316"},"modified":"2024-05-17T20:31:18","modified_gmt":"2024-05-17T20:31:18","slug":"stl-lectia-3-set","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/stl-lectia-3-set\/","title":{"rendered":"STL, lec\u021bia 3 \u2013 Set"},"content":{"rendered":"\n<p><mark data-darkreader-inline-bgcolor=\"\" style=\"background-color: rgba(0, 0, 0, 0); --darkreader-inline-bgcolor:rgba(6, 6, 6, 0);\" class=\"has-inline-color has-black-color\"><strong>Ce este \u0219i ce face setul?<\/strong><\/mark><\/p>\n\n\n\n<p>Setul din C++ este un container STL alocat dinamic. Este ca un vector, doar c\u0103 are 2 propriet\u0103\u021bi importante atunci c\u00e2nd vrem s\u0103 ad\u0103ug\u0103m un element \u00een set:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Elementul care urmeaz\u0103 s\u0103 fie inserat este plasat \u00een set \u00een a\u0219a fel \u00eenc\u00e2t toate elementele s\u0103 fie \u00een ordine cresc\u0103toare;<\/li><li>Dac\u0103 elementul care urmeaz\u0103 s\u0103 fie inserat exist\u0103 deja \u00een set, acesta nu va mai fi inserat.<\/li><\/ul>\n\n\n\n<p>Cu alte cuvinte, setul este echivalentul mul\u021bimii din matematic\u0103. Elementele se p\u0103streaz\u0103 \u00een ordine cresc\u0103toare \u0219i sunt unice.<\/p>\n\n\n\n<p>Singura modalitate de a accesa elementele dintr-un set este prin iteratori.<\/p>\n\n\n\n<p><strong>Cum folosim \u00een cod un set?<\/strong><\/p>\n\n\n\n<p>Pentru a folosi un set, trebuie s\u0103 includem libr\u0103ria &lt;set&gt; iar apoi s\u0103 declar\u0103m setul. Pentru a declara un set, folosim structura <em>set&lt;tipData&gt; numeVar;<\/em>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-1.png\" alt=\"\" class=\"wp-image-326\" width=\"720\" height=\"445\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-1.png 804w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-1-300x185.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-1-768x475.png 768w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-1-500x309.png 500w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><figcaption><em>Program care folose\u0219te set \u0219i func\u021bii specifice setului. (poza 1)<\/em><\/figcaption><\/figure>\n\n\n\n<p>\u00cen poza de mai sus am declarat un set care accept\u0103 doar valori de tipul int. Pe liniile 9, 10 \u0219i 11 am inserat \u00een set numerele 9, 4, respectiv -155. Din observa\u021biile f\u0103cute la primul paragraf, rezult\u0103 c\u0103 \u00een set avem numerele stocate \u00een aceast\u0103 ordine: {-155, 4, 9}. Pe linia 12 \u00eencerc\u0103m s\u0103 \u0219tergem num\u0103rul 5 din set. Cum acesta nu exist\u0103, nu se va \u0219terge nimic. Pe linia 13 \u00eencerc\u0103m s\u0103 inser\u0103m num\u0103rul 4 \u00een set. Cum acesta exist\u0103 deja \u00een set, nu se va insera nimic, elementele setului r\u0103m\u00e2n\u00e2nd {-155, 4, 9}. Pe linia 14 \u00eencerc\u0103m s\u0103 \u0219tergem elementul 4, deci \u00een set vor r\u0103m\u00e2ne elementele {-155, 9}.<\/p>\n\n\n\n<p>Liniile 16 \u0219i 17 afi\u0219eaz\u0103 elementele r\u0103mase \u00een set folosind iteratori. Nu voi explica \u00een detaliu \u00een acest articol ce sunt iteratorii. Voi spune doar c\u0103 ace\u0219tia sunt ca pozi\u021biile elementelor dintr-un vector normal (1, 2, &#8230;, n), iar valoarea memorat\u0103 de aceste pozi\u021bii (v[1], v[2], &#8230;, v[n]) se g\u0103se\u0219te folosind *it.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Untitled-1.png\" alt=\"\" class=\"wp-image-179\" width=\"515\" height=\"236\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Untitled-1.png 877w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Untitled-1-300x138.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Untitled-1-768x352.png 768w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/10\/Untitled-1-500x229.png 500w\" sizes=\"auto, (max-width: 515px) 100vw, 515px\" \/><figcaption><em>Unde se afl\u0103 iteratorii begin() \u0219i end(). (poza 2)<\/em><\/figcaption><\/figure>\n\n\n\n<p><strong>Func\u021bii specifice \u0219i complexit\u0103\u021bi<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table is-style-regular\"><table><tbody><tr><td>begin()<\/td><td>O(1)<\/td><td>Returneaz\u0103 un iterator la primul element al setului (vezi poza 2)<\/td><\/tr><tr><td>end()<\/td><td>O(1)<\/td><td>Returneaz\u0103 un iterator la elementul inexistent din dreapta ultimului element al setului (vezi poza 2)<\/td><\/tr><tr><td>insert(valoare)<br>insert(iterator)<\/td><td>O(logn)<\/td><td>Insereaz\u0103 un element \u00een set<\/td><\/tr><tr><td>erase(valoare)<\/td><td>O(logn)<\/td><td>\u0218terge un element dup\u0103 valoarea lui din set<\/td><\/tr><tr><td>erase(iterator)<\/td><td>O(1)<\/td><td>\u0218terge un element dup\u0103 un iterator din set<\/td><\/tr><tr><td>clear()<\/td><td>O(n)<\/td><td>\u0218terge toate elementele din set<\/td><\/tr><tr><td>empty()<\/td><td>O(1)<\/td><td>Returneaz\u0103 true dac\u0103 setul nu con\u021bine elemente, altfel returneaz\u0103 false<\/td><\/tr><tr><td>size()<\/td><td>O(1)<\/td><td>Returneaz\u0103 num\u0103rul de elemente din set<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Informa\u021bii suplimentare<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Oriunde am declara setul, acesta este ini\u021bial vid;<\/li><li>Elementele acestui container sunt alocate dinamic. Ce \u00eenseamn\u0103 acest lucru? S\u0103 compar\u0103m un vector(array) cu un set.<br>La declararea unui vector (int v[100]), se aloc\u0103 automat 100 de spa\u021bii din memorie pentru a putea fi folosite de acest vector. Este important de men\u021bionat c\u0103 aceste spa\u021bii de memorie sunt \u00eentotdeauna puse una dup\u0103 alta. Atunci c\u00e2nd declar\u0103m un set, se aloc\u0103 spa\u021biu pentru unele func\u021bii precum size().<br>Atunci c\u00e2nd inser\u0103m un element \u00een set, se aloc\u0103 spa\u021biu <strong>dinamic<\/strong> pentru acest element. Acesta poate fi plasat oriunde \u00een memorie. Dar dac\u0103 memoria este aleas\u0103 aleatoriu pentru elemente, cum p\u0103str\u0103m ordinea elementelor? Aici intervin \u00een discu\u021bie iteratorii. Fiecare element din set are c\u00e2te un iterator care p\u0103streaz\u0103 informa\u021bii precum: adresa de memorie a elementului precedent, adresa de memorie a elementului urm\u0103tor \u0219i valoarea acestui element.<br><\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-2.png\" alt=\"\" class=\"wp-image-334\" width=\"690\" height=\"645\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-2.png 980w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-2-300x280.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-2-768x718.png 768w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-2-500x467.png 500w\" sizes=\"auto, (max-width: 690px) 100vw, 690px\" \/><figcaption><em>Program folosit pentru a afla loca\u021biile unde se memoreaz\u0103 elementele unui set. (poza 3)<\/em><\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3-1024x186.png\" alt=\"\" class=\"wp-image-335\" width=\"841\" height=\"152\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3-1024x186.png 1024w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3-300x55.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3-768x140.png 768w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3-1536x279.png 1536w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3-500x91.png 500w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-3.png 1782w\" sizes=\"auto, (max-width: 841px) 100vw, 841px\" \/><figcaption><em>Output-ul programului. Pute\u021bi observa cum adresele de memorie nu sunt alocate una dup\u0103 alta. (poza 4)<\/em><\/figcaption><\/figure>\n\n\n\n<ul class=\"wp-block-list\"><li>Folosind observa\u021biile f\u0103cute la punctul anterior \u0219i ideea c\u0103 fiecare element este ad\u0103ugat \u00een set \u00een a\u0219a fel \u00eenc\u00e2t acesta s\u0103 r\u0103m\u00e2n\u0103 ordonat, putem deduce faptul c\u0103 este imposibil s\u0103 acces\u0103m, de exemplu, al treilea element, printr-o sintax\u0103 de genul v[3] (v[2]), ci doar cu iteratori.<\/li><li>Putem specifica o func\u021bie de comparare \u00eentre elemente, astfel \u00eenc\u00e2t un element s\u0103 fie inserat dup\u0103 un nou criteriu de ordonare.<br>Aceast\u0103 func\u021bie este specificat\u0103 la declararea setului. Exist\u0103 deja 2 func\u021bii predefinite, acestea sunt less&lt;tipData&gt;() \u0219i greater&lt;tipData&gt;().<br><\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"454\" src=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-4-1024x454.png\" alt=\"\" class=\"wp-image-336\" srcset=\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-4-1024x454.png 1024w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-4-300x133.png 300w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-4-768x340.png 768w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-4-500x222.png 500w, https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2022\/04\/image-4.png 1178w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption><em>Folosirea func\u021biilor de comparare definite \u0219i predefinite. (poza 5)<\/em><\/figcaption><\/figure>\n\n\n\n<ul class=\"wp-block-list\"><li>Este posibil s\u0103 \u0219ti\u021bi de la vectori(arrays) c\u0103 ace\u0219tia se transmit automat prin adres\u0103 ca parametrii unor func\u021bii, lucru care \u00eempiedic\u0103 copierea tuturor elementelor \u0219i utilizarea memoriei (\u0219i timpului) degeaba. Acest lucru nu se \u00eent\u00e2mpl\u0103 \u0219i cu containerele STL. Transmiterea unui set, de exemplu, ca parametru \u00eentr-o func\u021bie va determina copierea acestuia \u00een \u00eentregime. \u00cencerca\u021bi pe c\u00e2t posibil s\u0103 evita\u021bi acest lucru folosind transmiterea prin adres\u0103, cum am f\u0103cut \u0219i \u00een poza a treia.<\/li><\/ul>\n\n\n\n<p><strong>Concluzie<\/strong><\/p>\n\n\n\n<p>Sper c\u0103 acest articol v-a fost de ajutor. Dac\u0103 sesiza\u021bi gre\u0219eli de orice fel \u00een acest articol sau ave\u021bi \u00eentreb\u0103ri, scrie\u021bi \u00een sec\u021biunea de comentarii.<\/p>\n\n\n\n<p>Mult succes!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ce este \u0219i ce face setul? Setul din C++ este un container STL alocat dinamic. Este ca un vector, doar &hellip; <\/p>\n","protected":false},"author":4,"featured_media":366,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43,44],"tags":[19,38,36],"class_list":["post-316","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cpp","category-stl","tag-c","tag-set","tag-stl"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/316","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=316"}],"version-history":[{"count":45,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/316\/revisions"}],"predecessor-version":[{"id":381,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/316\/revisions\/381"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/366"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}