Standard Template Library (STL)

download Standard Template Library (STL)

of 31

  • date post

    16-Mar-2016
  • Category

    Documents

  • view

    31
  • download

    1

Embed Size (px)

description

Standard Template Library (STL). Programarea calculatoarelor şi limbaje de programare II Capitolul 9. Obiective. Înţelegerea noţiunii de container şi folosirea containerilor STL Folosirea algoritmilor STL în programe - PowerPoint PPT Presentation

Transcript of Standard Template Library (STL)

  • Standard Template Library (STL)Programarea calculatoarelor i limbaje de programare II

    Capitolul 9

  • Obiectivenelegerea noiunii de container i folosirea containerilor STLFolosirea algoritmilor STL n programenelegerea modului n care algoritmii folosesc iteratori pentru a accesa elementele unui container STL

  • SumarIntroducereContaineriContaineri secvenContaineri asociativiAdaptori containeri IteratoriAlgoritmiContaineri secvenContainerul secven vectorContainerul secven listContainerul secven deque

  • IntroducereStandard Template Library (STL) o bibliotec standard care cuprinde o colecie foarte cuprinztoare de componente reutilizabile Componentele cheie ale acestei biblioteci containerii (structuri de date sub form de template-uri)iteratoriialgoritmii

  • IntroducereEvoluia componentelor reutilizabileAnii 70 - componentele folosite n programe erau sub forma structurilor de control i a funciilor Anii 80 - au nceput s se foloseasc componente sub form de clase dintr-o gam larg de biblioteci dependente de platform Ultima parte a anilor 90 - odat cu apariia STL se introduce un nou nivel de folosire a componentelor prin clase independente de platform

  • IntroducereStructurile de date sunt colecii de date sau containeri organizate dup diverse reguli n programarea orientat pe obiecte structurile de date sunt obiecte care conin colecii de obiecte ExempluAm putea extinde tipul de data Array pentru valori int la Array astfel nct s putem implementa Array, Array, Array sau, n general, tablouri de orice tip de dat

  • Introduceren C i C++ obinuim s accesm elementele unui tablou folosind pointerin C++ STL, accesm elementele containerilor prin obiecte iterator arat ca pointerii, dar se comport mai inteligent

  • ContaineriContainerii secvenvector implementarea unui tablou dinamic, cu redimensionare automat la inserarea unui nou element sau la tergerea unui elementlist list dublu nlnuit cu inserare i tergere rapiddeque coad n care elementele pot fi adugate sau terse din ambele capete; difer de coada obinuit prin faptul c acolo adugarea i tergerea elementelor se face la un singur capt

  • ContaineriContainerii asociativimap pstreaz asocieri ntre perechi de valori i chei, mapare unu-la-unumultimap este similar cu map, dar accept duplicate, mapare unu-la-mai multeset cheile sunt chiar valorile pstratemultiset este similar cu set, dar accept duplicate

  • ContaineriAdaptori containerstack implementeaz o stiv last-in-first-out (LIFO)queue implementeaz o coad first-in-first-out (FIFO)priority_queue coad n care elementul cu prioritatea cea mai mare este ntotdeauna primul element extras

  • ContaineriConinutul tuturor fiierelor header n care sunt inclui containerii face parte din namespace stdContainerii secven i cei asociativi sunt grupai generic sub denumirea first-class containersContainerii STL au fost proiectai n aa fel nct dispun de o serie de funcionaliti comune

  • ContaineriFuncionaliti ale containerilor:- constructor implicit- constructor de copiere- destructor- empty funcie care returneaz true dac sunt elemente n container i false n caz contrar- operator=, operator=, operator==, operator!=- erase funcie care terge unul sau mai multe elemente din container (doar n first-class containers)- clear funcie care terge toate elementele din container (doar n first-class containers)

  • IteratoriUn iterator este un obiect care permite programatorului s parcurg toate elementele unei colecii, indiferent de implementarea acesteia ExempluDemonstreaz citirea datelor folosind istream_iterator de la intrarea standard care poate fi privit ca o secven de date de intrare n programIlustreaz tiprirea datelor folosind ostream_iterator la ieirea standard care poate fi privit ca o secven de date de ieire din program

  • Iteratori#include ...#include int main(){ cout
  • Iteratori...int main(){ ... cout
  • IteratoriCategoriile de iteratori folosii n STL sunt urmtoarele:input pentru citirea unui element dintr-un containeroutput pentru scrierea unui element ntr-un containerforward combin capacitile primelor dou categorii de iteratoribidirectional - combin capacitile unui iterator forward cu posibilitatea de a se deplasa n ambele direciirandom-access - combin capacitile iteratorului bidirectional cu posibilitatea de a accesa direct un element din container, adic de a se deplasa inainte sau napoi cu un numr arbitrar de elemente

  • IteratoriExemple de operaii care pot fi folosite de un iterator:Toi iteratorii++p preincrementarea unui iteratorp++ postincrementarea unui iteratorIteratorii de tip input*p dereferenierea unui iterator pentru a fi folosit ca rvaluep = p1 asignarea unui iterator altui iteratorp == p1 compararea iteratorilor pentru egalitatep != p1 compararea iteratorilor pentru inegalitateIteratorii de tip output*p dereferenierea unui iterator pentru a fi folosit ca lvalueIteratorii de tip forward --p predecrementarea unui iteratorp-- postdecrementarea unui iterator

  • IteratoriIteratorii de tip random-access p += i incrementarea iteratorului p cu i poziiip -= i decrementarea iteratorului p cu i poziiip + i iteratorul este poziionat la p incrementat cu i poziiip - i iteratorul este poziionat la p decrementat cu i poziiip[i] returneaz o referin la elementul deplasat de la p cu i poziiip < p1 returneaz true dac iteratorul p este naintea lui p1 n containerp p1 returneaz true dac iteratorul p este dup p1 n containerp >= p1 returneaz true dac iteratorul p este dup p1 sau pe aceeai poziie n container

  • Algoritmi STL ofer algoritmi care pot fi folosii generic pentru o mare varietate de containeri: inserarestergerecutaresortare etc. STL include aproximativ 70 de algoritmi standardAlgoritmii opereaz asupra elementelor unei secvene doar indirect, prin intermediul iteratorilorDeoarece STL este extensibil, se pot aduga cu uurin noi algoritmi fr a opera nicio modificare asupra containerilor

  • AlgoritmiAlgoritmii STL sunt de dou tipurimutating-sequence fac modificri asupra containerilor pe care sunt aplicatinon-mutating-sequence se execut fr a schimba coninutul containerilorCiva dintre algoritmii care fac parte din fiierul header sunt:copy()fill()replace()swap()count()find()search()

  • SumarIntroducereContaineriContaineri secvenContaineri asociativiAdaptori containeri IteratoriAlgoritmiContaineri secvenContainerul secven vectorContainerul secven listContainerul secven deque

  • Containeri secven C++ STL ofer trei containeri secvenvector - implementare a unui tablou care permite asignarea tablourilor i verificare ncadrrii indicilor n limitelist - structur de dat de tip list nlnuitdeque - structur de dat de tip coad dublOperaii comune tuturor containerilor secven:front returnarea unei referine la primul element din containerback returnarea unei referine la ultimul element din containerpush_back inserarea unui element nou pe ultima poziie din containerpop_back tergerea ultimului element din container

  • Containerul vectorUn vector (tablou) este o structur de dat n care datele sunt stocate ntr-o zon contigu de memorieAceast organizare a datelor permite accesul direct la elementele vectorului prin operatorul []Atunci cnd memoria obiectului de tip vector nu mai este suficientse aloc o zon mai mare de memorie contiguse copiaz elementele originale n noua zon de memoriese dealoc vechea zon de memorie

  • Containerul vectorUn vector suport iteratorul random-accessadic poate fi folosit mpreun cu orice operator prezentat mai devremeIteratorii pentru un vector sunt implementai ca pointeri la elementele vectorului ExempluProgramul urmtor prezint cteva dintre funcionalitile clasei template vector, multe dintre aceste funcii fiind ns utilizabile de orice container STL de tip first-class

  • Containerul vector#includeusing std::cout;using std::cin;using std::endl;#include int main(){ const int SIZE = 6; int a[SIZE] = {1, 2, 3, 4, 5, 6}; std::vector v; cout
  • Containerul vector...int main(){ ... v.push_back(2); //metoda push_back se gaseste v.push_back(3); //in orice colectie secventa v.push_back(4); cout
  • Containerul vector...int main(){ ... cout
  • Containerul vectorExempluProgramul prezint funcii care permit diverse manipulri ale valorilor unui obiect de tip vector

  • Containerul vector...#include #include #include #include int main(){ const int SIZE = 6; int a[SIZE] = {1, 2, 3, 4, 5, 6}; std::vector v(a, a+SIZE); std::ostream_iterator output(cout, " "); cout
  • Containerul vector...int main(){ ... v[0] = 7; v.at(2) = 10; v.insert(v.begin()+1, 22); cout
  • Containerul vector...int main(){ ... v.erase(v.begin()); cout