STL (Standard Template Library)

download STL (Standard Template Library)

of 94

  • date post

    13-Jan-2016
  • Category

    Documents

  • view

    38
  • download

    0

Embed Size (px)

description

STL (Standard Template Library). Curs 14. STL. biblioteca C++ care contine clase pentru containere, algoritmi si iteratori Furnizeaza majoritatea algoritmilor de baza si structurilor de date necesare in dezvoltarea de programe - PowerPoint PPT Presentation

Transcript of STL (Standard Template Library)

  • STL (Standard Template Library)Curs 14

  • STLbiblioteca C++ care contine clase pentru containere, algoritmi si iteratori

    Furnizeaza majoritatea algoritmilor de baza si structurilor de date necesare in dezvoltarea de programe

    STL este o bibiblioteca generica componentele sunt parametrizate aproape fiecare componenta din STL este template

  • ContainereVectorListDeque

    QueueStackPriority queue

    SetMapMultisetMultimapBitsetContainere secventialeAdaptori de containereContainere asociative (cheie-valoare)

  • VectorElimina problema realocarii dinamice a spatiului de memorie

    Se redimensioneaza in partea finala astfel incat sa poata fi realizata adaugarea de noi elemente

    Compusi dintr-un bloc de memorie alocata secvential

    Folosit cand se fac adaugari/stergeri de la sfarsit

    Ineficient cand depasirile de memorie alocata pot determina copierea intregului vector

    Constrangeri asupra lui T: T();T(const T&); ~T(); T& operator=(const T&);

    #include std::vector myvector;

    std:: vector::iterator it; Declaratie vector de intregiDeclaratie iterator pe vector de intregi

  • Operatii pe vector

  • Operatii pe vector

  • Operatii pe vector

  • ListCompuse din obiecte care au anterior-info-urmator

    Nu detin ownership asupra elementelor

    Folosite cand se fac inserari/stergeri oriunde in cadrul listei

    Cerinte pentru tipul T:

    T(); T(const T&); ~T(); T& operator=(const T&); T* operator&(); int operator < (const T&, const T&); int operator==(const T&, const T&); #include std::list identifier;

    std::list::iterator identifier;

    Declaratie lista de intregiDeclaratie iterator pe lista de intregi

  • Operatii pe tipul list

  • Operatii pe tipul list

  • Operatii pe tipul list

  • Deque (deck)deque=double ended queue

    Nu e FIFO

    Permite adaugarea/stergerea elementelor la ambele capete

    Permite inserarea sau stergerea de elemente la pozitii arbitrare

    Accesul la elemente de poate realiza similar vectorilor, cu operatorul [] sau metoda at()Declaratie coada de intregiDeclaratie iterator coada de intregi#include std::deque dequeOfIntegers; std::deque::iterator itr;

  • Deque

  • Deque

  • Deque

  • Vector sau deque?Deque permite inserarea/stergerea elementelor de la inceputul/sfarsitul cozii in timp constant

    Vectorul permite inserarea/stergerea elementelor doar la sfarsit in timp constant

    Deque permite inserarea/stergerea de elemente la pozitii arbitrare mai eficient decat vectorul, dar nu in timp constant

    Accesul aleator la elemente este mai rapid la vector decat la deque

    Pentru secvente mari de elemente vectorul va aloca o zona mare de memorie contigua, pe cand deque va aloca mai multe blocuri de memorie de dimensiuni mai mici mai eficient din punctul de vedere al sistemelor de operare

    Deque se comporta atat ca o stiva, cat si ca o coada

    Deque se expandeaza mai eficient decat vectorii

  • StackLIFOCa implementare, in STL, o stiva e un adaptor (implementare a sablonului de proiectare Adapter vezi curs 11) preia ca parametru al templateului un container secvential si lasa vizibile doar operatiile care sunt asociate unei stive#include #include - C containerul care dorim sa fie adaptat la stiva

    #include #include std::stack myStack; Implicit deque (lista consuma prea multa memorie, vectorii de expandeaza costisitor)std::stack myStack;

  • Stack

  • SetCotainer in care toate elementele sunt distinctePastreaza elementele sortate!!Functia find() are complexitate logaritmica#include std::set s;std::set::iterator it=s.begin();Declaratie multime de intregiDeclaratie iterator multime de intregi#include #include using namespace std;

    int main(){set intSet;for(int i=0;i

  • MultisetAccepta aparitii multiple ale unui element0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 44 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 66 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 78 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 99 9 9 9 9 9 9 9 9 9#include #include using namespace std;

    int main(){multiset intSet;for(int i=0;i

  • Operatii pe Set

  • Operatii pe Set

  • MapAsociaza chei de un anumit tip cu valori de alt tipElementele sunt accesate direct, pe baza cheiiaMap["John Doe"] = 3.2; Cheile trebuie sa fie unice

    Atentie la utilizarea operatorului [] algoritm:Cauta cheia in dictionarDaca e gasita se returneaza o referinta spre valoarea asociataDaca nu e gasita se creeaza un nou obiect de tipul valorii si se returneaza o referinta spre elPentru a verifica apartenenta unui element la dictionar se foloseste metoda find() nu creeaza un obiect daca cheia nu existaFind returneaza un iterator pe o pereche de obiecte (cheie, valoare) daca cheia exista, altfel returneaza end()

    #include std::map aMap;std::map::iterator it;

    Declaratie dictionarDeclaratie iterator pe dictionar

  • Map-pairpair este o clasa template care are doua date membre publice accesbile folosind pair::first (cheia), respectiv pair::second (valoarea)Definita in Pentru a crea un obiect de tip pair functia template make_pair care are 2 parametri

    Cerinte asupra tipului cheilor/valorilor sa aiba operatorul = supraincarcatTipul cheilor trebuie sa respecte urmatoarele constrangeri (ordine stricta):a

  • Operatii pe Map

  • Operatii pe Map

  • MultimapPermite existenta aceleiasi chei de mai multe ori

    Pentru a gasi toate perechile cheie valoare corespunzatoare unei chei, vom folosi 2 iteratori-unul setat pe prima pereche din dictionar si altul setat pe ultima pereche din dictionar care corespunde cheii#include

    multimap mMap; multimap::iterator itr;

    multimap::iterator itr; multimap::iterator lastElement; itr = mMap.find(key); if (itr == mMap.end()) return; cout

  • Operatii pe multimap

  • Operatii pe multimap

  • IteratoriSimilari pointerilor in sensul ca elementele indicate sunt accesate indirect

    o abstractizare intre container si utilizatorul sau (putem scrie algoritmi pe containere fara sa stim reprezentarea acestora)

    Determina reducerea cuplarii (GRASP-low coupling) intre functii si containere accesate de acestea

    Pentru a accesa elementul, iteratorul trebuie dereferentiat

    Clase de iteratori:Inainte (forward)-operator ++ - 3 categorii:Input (read-only)Output(write-only)Random access (read/write)Bidirectional permit traversarea inainte/inapoi operatorii ++/--, acces read/writeAcces aleator (random access) permite acces la oricare element al containerului folosind operatorii +/- si ++/--

  • IteratoriMajoritatea containerelor accepta iteratori, cu exceptia stivei, cozii si cozii cu prioritati

    Parcurgerea elementelor containerului folosind iteratori:

    Accesul la elementul curent:Folosind * sau -> (daca obiectul referit este un agregat)*itr=3;struct pair { int first, second; }; itr->first = 5; itr->second = 6;

    ::iterator::const_iteratorDeclaratie iteratorifor (itr = container.begin(); itr!=container.end(); ++itr) @proceseaza(*itr);

  • Iteratori pe containere reversibileContainer reversibil produce iteratori care merg de la sfarsit spre inceput

    Toate containerele standard permit existenta iteratorilor reversibili

    Pentru initializare: rbegin(), rend()

    #include #include using namespace std;

    int main(){ vector v; v.push_back(3); v.push_back(4); v.push_back(5); vector::reverse_iterator rit=v.rbegin(); while (rit

  • Iteratori pe streamuriDestinati automatizarii unor sarcini comune (curente)

    STL furnizeaza metode de aplicare a unor algoritmi generici care sa inlocuiasca nevoia de a itera prin containere

    Un iterator pe stream foloseste un stream fie pentru intrare, fie pentru iesire

    ostream_iteratoristream_iterator

    #include #include #include #include using namespace std;

    int main () { vector myvector; int value; cout

  • Iteratori de inserare (insertion/insert iterators)x iterator*x=3Daca x e un insert iterator *x=3 genereaza adaugarea elementului 3 la secventa pe care itereaza

    Necesari unor algoritmi care au scopul de umplere a containerele, nu de suprascriere

    insert_iterator permite inserarea de elemente in mijlocul unei secvente

    2 clase adaptor: front_inserter containerul trebuie sa aiba metoda push_frontback_inserter - containerul trebuie sa aiba metoda push_back

    Constructorii iau un container secvential (vector, list,deque) si produc un iterator care apeleaza push_back sau push_frontSuprascrie valoarea existenta

  • back_insert_iterator#include #include #include using namespace std;

    int main () { vector firstvector, secondvector; for (int i=1; i back_it (firstvector);

    copy (secondvector.begin(),secondvector.end(),back_it);

    ostream_iterator out_it (cout,", "); copy ( firstvector.begin(), firstvector.end(), out_it );

    return 0;}1 2 3 4 510 20 30 40 50firstsecond1, 2, 3, 4, 5, 10, 20, 30, 40, 50firstback_it

  • front_insert_iterator#include #include #include using namespace std;

    int main () { deque firstdeque, seconddeque; for (int i=1; i front_it (firstdeque);

    copy (seconddeque.begin(),seconddeque.end(),front_it);

    deque::iterator it; ostream_iterator oit(cout,","); copy(first