{"id":217,"date":"2021-12-27T13:23:43","date_gmt":"2021-12-27T13:23:43","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=217"},"modified":"2024-05-17T20:31:19","modified_gmt":"2024-05-17T20:31:19","slug":"stl-lectia-2-vector","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/stl-lectia-2-vector\/","title":{"rendered":"STL, lec\u021bia 2 – Vector"},"content":{"rendered":"\n

Vectorul din STL<\/a> este o metod\u0103 mai u\u0219oar\u0103 de a stoca un \u0219ir de elemente. Face acela\u0219i lucru ca un array, doar c\u0103 este mult mai bun, deoarece func\u021biile cu care vine v\u0103 vor u\u0219ura semnificativ munca depus\u0103 pentru rezolvarea unei probleme de informatic\u0103.<\/p>\n\n\n\n

Pentru \u00eenceput, s\u0103 vedem de ce este mai bun vectorul dec\u00e2t array-ul:<\/p>\n\n\n\n

Array<\/strong><\/td>Vector<\/strong><\/td><\/tr>
Num\u0103rul de elemente este stabilit obligatoriu la declara\u021bie (int v[255])<\/td>Num\u0103rul de elemente poate fi omis la declara\u021bie (vector<int> v)<\/td><\/tr>
Trebuie s\u0103 urm\u0103rim num\u0103rul de elemente de fiecare dat\u0103 c\u00e2nd introducem\/elimin\u0103m ceva<\/td>Num\u0103rul de elemente poate fi ob\u021binut oric\u00e2nd folosind func\u021bia .size()<\/td><\/tr>
Ad\u0103ugarea\/\u0219tergerea unui element dintr-o pozi\u021bie trebuie f\u0103cut\u0103 manual<\/td>Ad\u0103ugarea\/\u0219tergerea unui element se poate realiza folosind func\u021bia .insert()\/.erase()<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u00cen ceea ce prive\u0219te func\u021biile pe care le putem folosi, cele mai importante sunt:<\/p>\n\n\n\n

  1. size(), cu complexitatea O(1) – returneaza dimensiunea vectorului<\/li>
  2. clear(), cu complexitatea O(N) – \u0219terge toate elementele vectorului (N elemente)<\/li>
  3. empty(), cu complexitatea O(1) – returneaza 0 dac\u0103 vectorului con\u021bine cel pu\u021bin un element, 1 \u00een caz contrar<\/li>
  4. erase(), cu complexitatea O(N + M) – \u0219terge un singur element sau mai multe elemente(N) aflate pe pozi\u021bii consecutive. M reprezint\u0103 num\u0103rul de elemente mutate la \u0219tergere<\/li>
  5. insert(), cu complexitatea O(N + M) – adaug\u0103 un element sau mai multe elemente(N) la o anumit\u0103 pozi\u021bie. M reprezint\u0103 num\u0103rul de elemente mutate la ad\u0103ugare<\/li>
  6. push_back(), cu complexitatea O(1) – adaug\u0103 un element la sf\u00e2r\u0219itul vectorului<\/li>
  7. pop_back(), cu complexitatea O(1) – \u0219terge ultimul element din vector<\/li><\/ol>\n\n\n\n

    S\u0103 rezolv\u0103m o problem\u0103 de pe pbinfo pentru a vedea cum func\u021bioneaz\u0103 vectorul. Problema inserareDupa #159<\/a> ne cere s\u0103 inser\u0103m dup\u0103 fiecare element par dublul s\u0103u. Aceasta este rezolvarea problemei explicat\u0103 pas cu pas \u00een comentarii:<\/p>\n\n\n\n

    #include <iostream>\n#include <vector> \/\/ includem libraria ca sa putem folosi vectorul\nusing namespace std;\n\nint main()\n{\n   vector<int> v; \/\/ declaram vectorul v\n   int n, i, x;\n   cin >> n; \/\/ pe n il folosim doar ca sa stim cate numere sa citim.\n   \/\/ dupa citire, nu mai avem nevoie de n, pt ca avem functia v.size()\n\n   for (i = 0; i < n; ++i)\n   {\n      cin >> x; \/\/ citim un numar,\n      v.push_back(x); \/\/ ca mai apoi sa il punem la sfarsitul vectorului v.\n   }\n\n   \/\/ dupa fiecare inserare, ar trebui sa adunam pe n cu 1.\n   \/\/ dar, pentru ca folosim vector, nu mai trebuia sa avem grija de acest lucru.\n   \/\/ v.size() se schimba pentru fiecare inserare\/stergere!\n   for (i = 0; i < v.size(); ++i)\n      if (v[i] % 2 == 0)\n      {\n         \/\/ inseram pe iteratorul v.begin()+i+1 valoarea v[i]*2.\n         \/\/ tineti minte ca functia insert accepta ca pozitie un ITERATOR, nu un NUMAR.\n         v.insert(v.begin()+i+1, v[i]*2);\n         i++; \/\/ daca nu adunam pe i cu 1, la urmatoarea faza a for-ului ar verifica numarul introdus acum.\n      }\n\n   for (int elem : v) \/\/ pentru fiecare element din v,\n      cout << elem << ' '; \/\/ il afisam.\n   return 0;\n}<\/pre>\n\n\n\n
    Avantajele acestei solu\u021bii: \u00cen primul r\u00e2nd, dac\u0103 am fi lucrat cu array, ar fi trebuit s\u0103 preciz\u0103m dimensiunea 2*n. La vector nu preciz\u0103m nicio dimensiune. \u00cen al doilea r\u00e2nd, mecanismul de inserare a unui num\u0103r \u00een vector este deja implementat \u0219i trebuie scris\u0103 doar o linie de cod pentru a insera. Iar \u00een al treilea r\u00e2nd, dup\u0103 fiecare inserare nu trebuie s\u0103 cre\u0219tem pe n cu 1. Func\u021bia size() returneaz\u0103 tot timpul num\u0103rul de element.<\/p>\n\n\n\n
    Pozi\u021bia specificat\u0103 la func\u021bia insert() trebuie s\u0103 fie un iterator<\/a><\/strong>, ci nu un num\u0103r. Trebuie s\u0103 \u0219ti\u021bi c\u0103 iteratorii sunt ca ni\u0219te pointeri. Vom explica iteratorii \u0219i pointerii \u00eentr-o alt\u0103 lec\u021bie.<\/p>\n\n\n\n
    A doua \u0219i ultima problem\u0103 pe care o rezolv\u0103m \u00een acest articol este Unice1 #270<\/a>. Aceast\u0103 problem\u0103 cere afi\u0219area num\u0103rului de numere care apar o singur\u0103 dat\u0103 \u00eentr-un \u0219ir de numere.<\/p>\n\n\n\n
    #include <fstream>\n#include <vector>\n#include <algorithm> \/\/ de aici folosim find()\nusing namespace std;\n\nint main()\n{\n   ifstream cin (\"unice1.in\");\n   ofstream cout (\"unice1.out\");\n   vector<int> v;\n   int n, i, x, k;\n   cin >> n;\n\n   for (i = 0; i < n; ++i)\n   {\n      \/\/ cin >> v[i];  nu putem folosi aceasta citire!!\n      \/\/ pentru ca nu am specificat dimensiunea, v[i] nu exista cand vrem sa citim!!\n      cin >> x;\n      v.push_back(x);\n   }\n\n   k = 0;\n   for (i = 0; i < n; ++i)\n      if (find(v.begin(), v.begin()+i, v[i]) == v.begin()+i &&\n          find(v.begin()+i+1, v.end(), v[i]) == v.end())\n         k++;\n         \n   cout << k;\n   return 0;\n}<\/pre>\n\n\n\n
    Func\u021bia find() este o func\u021bie care se afl\u0103 \u00een libr\u0103ria <algorithm> \u0219i are la primii doi parametrii doi iteratori, \u0219i la al treilea parametru un num\u0103r \u00eentreg. Aceast\u0103 func\u021bie caut\u0103 \u00een intervalul impus de cei doi parametrii valoarea din al treilea parametru. De exemplu, un apel al func\u021biei de genul find(v.begin(), v.begin()+3, 10);<\/em> caut\u0103 \u00een primele 3 valori din vector valoarea 10, pentru c\u0103 intervalul este [v.begin(), v.begin()+3). Returneaz\u0103 un iterator la prima apari\u021bie a acestei valori. Dac\u0103 aceast\u0103 valoare nu apare deloc \u00een acest interval, returneaz\u0103 iteratorul precizat la al doilea parametru.<\/p>\n\n\n\n
    \u00cen aceast\u0103 problem\u0103 ne intereseaz\u0103 ca, la c\u0103utarea \u00een numerele din st\u00e2nga \u0219i din dreapta pozi\u021biei curente, s\u0103 nu existe alt num\u0103r la fel cu cel de pe pozi\u021bia i.<\/em> Cele dou\u0103 func\u021bii de find() caut\u0103 \u00een st\u00e2nga \u0219i \u00een dreapta lui i s\u0103 nu existe numere egale cu v[i].<\/p>\n\n\n\n
    \"\"
    Unde se afl\u0103 iteratorul end() \u00eentr-un vector de 4 elemente<\/figcaption><\/figure>\n\n\n\n
    Este important s\u0103 \u0219ti\u021bi s\u0103 lucra\u021bi cu vectorul din STL, deoarece acesta v\u0103 poate u\u0219ura munca depus\u0103 la rezolvarea unor probleme \u0219i, \u00een cele mai multe cazuri, va reduce probabilitatea de a produce erori. Sper c\u0103 a\u021bi \u00een\u021beles \u0219i c\u0103 v\u0103 va fi de folos aceast\u0103 lec\u021bie \u00een viitor. Spor la \u00eenv\u0103\u021bat!<\/p>\n","protected":false},"excerpt":{"rendered":"
    Vectorul din STL este o metod\u0103 mai u\u0219oar\u0103 de a stoca un \u0219ir de elemente. Face acela\u0219i lucru ca un … <\/p>\n","protected":false},"author":4,"featured_media":291,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43,44],"tags":[],"class_list":["post-217","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cpp","category-stl"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/217","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=217"}],"version-history":[{"count":9,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/217\/revisions"}],"predecessor-version":[{"id":283,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/217\/revisions\/283"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/291"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=217"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=217"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}