STL - Alexandru Ioan Cuza University dlucanu/cursuri/poo/resurse/STL_ ¢  Cuprins zSTL...

download STL - Alexandru Ioan Cuza University dlucanu/cursuri/poo/resurse/STL_ ¢  Cuprins zSTL (Standard Template

of 48

  • date post

    21-Jan-2020
  • Category

    Documents

  • view

    12
  • download

    0

Embed Size (px)

Transcript of STL - Alexandru Ioan Cuza University dlucanu/cursuri/poo/resurse/STL_ ¢  Cuprins zSTL...

  • STLSTL

    Partea 1

    1

  • Cuprins

    STL (Standard Template Library) ce include siruri containere standard • sumar • vectori • liste• liste • tablouri asociative • tablouri asociative cu chei multipletablouri asociative cu chei multiple

    D. Lucanu STL – Partea 1 2

  • STL::continut biblioteci C• •• • etc

    siruri ca obiecte• containere• t• • • • •

    D. Lucanu STL – Partea 1 3

    • etc

  • STL::continut (cont.)

    iteratori •

    algoritmi • •

    intrari/iesiri •• • • etcetc

    etc

    D. Lucanu STL – Partea 1 4

  • STL:: siruri::exemplu simplu

    header #include

    spatiul de nume using namespace std;

    declaratii sirurideclaratii siruri string s("Un text simplu."); string tag("$tag$");g g( $ g$ );

    s Un text simplu.s 15

    t $tag$

    D. Lucanu STL – Partea 1 5

    tag g

    5

  • STL:: siruri::exemplu simplu

    operatii peste siruri s.insert(8, tag + ' '); int start = s.find(tag); s.replace(start, tag.size(), "foarte"); cout

  • STL::containere::definitie un obiect care contine alte obiecte (componentele) si are metode de accesare a componentelor fi t i i t ti it t j t lfiecare container are asociat un tip iterator cu ajutorul caruia se "merge" prin container

    Container IteratorContainer Iterator

    1 1 0..*

    Componenta

    *

    D. Lucanu STL – Partea 1 7

  • STL::secvente

    suporta acces aleator la elemente, timp constant pentru insertie si eliminarea componentelor de la sfarsit timpinsertie si eliminarea componentelor de la sfarsit, timp liniar pentru inserarea si eliminarea elementelor de la inceput si interior

    suporta parcurgerea in ambele sensuri, timp constant

    (amortizat) pentru insertie si eliminare la inceput, la sfarsit i i t isau in interior

    suporta acces (inserare si eliminare) la ambele capete

    < > suporta inserare la un capat si eliminare la celalalt capat

    D. Lucanu STL – Partea 1 8

    suporta inserarea si eliminarea la acelasi capat etc

  • STL::containere asociative suporta cautarea eficienta bazata pe chei

    componentele sunt perechi cu cheie

    unica (nu exista doua date cu aceeasi cheie) p

    componentele sunt perechi cu cheie multipla (pot exista mai multe date cu aceeasi cheie)

    componentele sunt doar de tip cheie si NU pot exista in

    duplicat

    componentele sunt doar de tip cheie si POT exista in duplicat

    D. Lucanu STL – Partea 1 9

    duplicat etc

  • STL:: containere::tipuri asociate X::value_type

    tipul obiectului memorat in container X::allocator_type

    tipul managerului de memorie X::size_type

    tip pentru indici, numar de elemente etc X::iteratorX::iterator

    tip pentru iterator cu care se "merge" prin container etcetc

    D. Lucanu STL – Partea 1 10

  • STL::containere:: iteratori

    definitie: sint utilizati pentru a naviga prin containeri, fara sa stim ce tip de data este utilizat pentru memorarea obiectelorpentru memorarea obiectelor concepte cheie: • elementul curent la care face referire (p->, *p)elementul curent la care face referire (p >, p) • elementul urmator/precedent (++p, --p) • comparatii (<

  • STL::containere:: iteratori

    O clasificare a iteratorilor • iteratori cu acces aleator

    == != < > >= [] =*p

    • iteratori bidirectionali == != ++ -- *p= -> =*p

    • iteratori “forward”• iteratori forward == != ++ *p= -> =*p

    • iteratori de intrare: == != ++ -> =*piteratori de intrare: ! ++ > p • iteratori de iesire: ++ *p=

    D. Lucanu STL – Partea 1 12

  • STL::iteratori constanti si mutabili iterator constant: obiectul referit poate fi accesat dar nu se poate atribui o noua valoare prin acest iterator

    typedef vector::const iteratortypedef vector::const_iterator VectIntConstIt;

    Iterator “mutable”: sunt posibile ambele actiuni (acces si atribuire valoare)valoare)

    typedef vector::iterator VectIntIt;

    exemplup VectIntConstIt q; vectInt.erase(q);

    // error: no matching function ... VectIntIt p; vectInt.erase(p);

    // OK

    D. Lucanu STL – Partea 1 13

  • STL::containere:: acces la elemente c.front()

    primul element c.back()

    ultimul element //( t li t )c[i] //(nu pentru liste)

    al i-lea element din secventa (NU se valideaza valoarea lui i)valoarea lui i)

    c.at(i) //(nu pentru liste) al i-lea element din secventa (SE valideaza (

    valoarea lui i)

    D. Lucanu STL – Partea 1 14

  • STL::operatii de tip stiva si coada

    c.push_back(x) insereaza x la sfarsit

    c.pop_back() elimina de la sfarsit

    c push front(x)c.push_front(x) insereaza x la inceput

    c.pop_front() _ elimina de la inceput

    D. Lucanu STL – Partea 1 15

  • STL::containere:: operatii de tip lista c.insert(p, x)

    insereaza x inaintea lui p c.insert(p, n, x)

    insereaza n copii ale lui x inaintea lui p c.insert(p, first, last)

    adauga elementele din [first, last) inaintea lui p c erase(p)c.erase(p)

    elimina de la p c.erase(first, last) c.e ase( st, ast)

    elimina elementele din [first, last) c.clear()

    D. Lucanu STL – Partea 1 16

    elimina toate elementele

  • STL::containere:: alte operatii c.size() // numarul de elemente c.empty() // este c vid? c.capacity() // (numai pentru vector) spatiul alocat c.reserve(n) // (numai pentru vector) aloca spatiu c resize() // (numai pentru vector) adauga elemente lac.resize() // (numai pentru vector) adauga elemente la

    // sfarsit max_size() // (numai pentru vector) dim celui mai mare

    // vector posibil swap(c1, c2) // intershimba continuturile a 2 containere == // testul de egalitate== // testul de egalitate != // testul diferit < // relatia de ordine lexicografica

    D. Lucanu STL – Partea 1 17

  • STL::containere:: constructori container()

    containerul vid container(n)

    containerul cu n elemente cu valoare implicita ( t i ti )container(n, x)(nu pt asociative)

    containerul cu n copii ale lui x container(first last)container(first, last)

    containerul cu elemente din intervalul [first, last) container(c)co ta e (c)

    constructorul de copiere ~container()

    D. Lucanu STL – Partea 1 18

    destructor

  • STL::containere:: atribuiri operator=(c)

    copie din containerul c assign(n) //(nu pentru asociative)

    atribuie n elemente cu valoare implicita //( t i ti )assign(n, x) //(nu pentru asociative)

    atribuie n copii ale lui x assign(first last)assign(first, last)

    atribuie din intervalul [first, last)

    D. Lucanu STL – Partea 1 19

  • STL::containere:: operatii asociative operator[](k)

    acceseaza elementul cu cheia k find(k)find(k)

    gaseste componenta cu cheia k lower_bound(k)

    gaseste primul element cu cheia kgaseste primul element cu cheia k upper_bound(k)

    gaseste primul element cu cheia mai mare decat k l (k)equal_range(k)

    gaseste lower_bound() si upper_bound() pentru cheia k

    key_comp() componenta cheie

    value_comp()

    D. Lucanu STL – Partea 1 20

    componenta valoare (data)

  • STL::vector:: declarare

    template

    class std::vector { public: typedef T data type;typedef T data_type; //. . . iterator begin();te ato beg (); //. . .

    }

    D. Lucanu STL – Partea 1 21

  • STL::vector:: reprezentare

    size

    rep

    l t ti telemente spatiu extra

    D. Lucanu STL – Partea 1 22

  • vector::exemplu::agenda telefonica

    vector Intrare

    AgTel

    D. Lucanu STL – Partea 1 23

  • vector::exemplu::agenda telefonica

    header #include

    intrare in agenda = structura class Intrare { public: Intrare(char *un_s="\0", long un_n=0); void afiseaza() const;void afiseaza() const; ...

    private:p ate: string nume; long nr;

    D. Lucanu STL – Partea 1 24

    };

  • vector::exemplu::agenda telefonica

    declarare agenda typedef vector AgTel; AgTel agTel(20);

    adaugarea de intrari pe pozitii aleatoare

    agTel[0] = Intrare("Ionescu" 123456);agTel[0] = Intrare( Ionescu , 123456); agTel[10] = Intrare("Popescu", 654321);

    D. Lucanu STL – Partea 1 25

  • STL::vector::agenda telefonica realizarea unei copii AgTel copie = agTel;

    accesul la componente copie[0].afiseaza(); copie[10].afiseaza();

    D. Lucanu STL – Partea 1 26

  • STL::vector::agenda telefonica

    declarare tip iteratori typedef AgTel::iterator AgTelIterator; AgTelIterator i;

    afisare agenda for (i = agTel.begin(); i != agTel.end(); ++i)

    i->afiseaza();i->afiseaza();

    D. Lucanu STL – Partea 1 27

  • STL::vector::agenda telefonica

    Combinatie nefericita intre acces direct si iteratori agTel.clear(); agTel[0] = Intrare("Ionescu", 123456); agTel[10] = Intrare("Popescu", 654321); for (i=agTel begin(); i != agTel end(); ++i)for (i=agTel.begin(); i != agTel.end(); ++i)

    i->afiseaza();

    nu afiseaza nimicnu afiseaza nimic

    D.