9. STL - Partea I

7/29/2019 9. STL - Partea I

1/48

1

STL

Partea 1

7/29/2019 9. STL - Partea I

2/48

D. Lucanu STL Partea 1 2

Cuprins

STL (Standard Template Library)

ce include

siruri

containere standard

sumar vectori liste tablouri asociative

tablouri asociative cu chei multiple

7/29/2019 9. STL - Partea I

3/48


STL::continut

biblioteci C

etc siruri ca obiecte

containere

etc

7/29/2019 9. STL - Partea I

4/48


STL::continut (cont.)

iteratori

algoritmi

intrari/iesiri

etc etc

7/29/2019 9. STL - Partea I

5/48


STL:: siruri::exemplu simplu

header

#include

spatiul de nume

using namespace std;

declaratii siruri

string s("Un text simplu.");

string tag("$tag$");

s Un text simplu.15

tag$tag$

5

7/29/2019 9. STL - Partea I

6/48


STL:: siruri::exemplu simplu

operatii peste siruri

s.insert(8, tag + ' ');

int start = s.find(tag);

s.replace(start, tag.size(), "foarte");

cout

7/29/2019 9. STL - Partea I

7/48


STL::containere::definitie

un obiect care contine alte obiecte (componentele) si

are metode de accesare a componentelor fiecare container are asociat un tip iteratorcu ajutorul

caruia se "merge" prin container

Container

Componenta

Iterator

1

*

1 0..*

7/29/2019 9. STL - Partea I

8/48


STL::secvente

suporta acces aleator la elemente, timp constant pentruinsertie 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

sau in interior

suporta acces (inserare si eliminare) la ambele capete

suporta inserare la un capat si eliminare la celalalt capat

suporta inserarea si eliminarea la acelasi capat

etc

7/29/2019 9. STL - Partea I

9/48


STL::containere asociative

suporta cautarea eficienta bazata pe chei

componentele sunt perechi cu cheie

unica (nu exista doua date cu aceeasi cheie)

componentele sunt perechi cu cheiemultipla (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 induplicat

etc

7/29/2019 9. STL - Partea I

10/48


STL:: containere::tipuri asociate

X::value_type

tipul obiectului memorat in container

X::allocator_type

tipul managerului de memorie

X::size_typetip pentru indici, numar de elemente etc

X::iterator

tip pentru iterator cu care se "merge" prin container

etc

7/29/2019 9. STL - Partea I

11/48


STL::containere:: iteratori

definitie: sint utilizati pentru a naviga prin

containeri, fara sa stim ce tip de data este utilizatpentru memorarea obiectelor

concepte cheie:

elementul curent la care face referire (p->, *p)

elementul urmator/precedent (++p, --p) comparatii (<

7/29/2019 9. STL - Partea I

12/48


STL::containere:: iteratori

O clasificare a iteratorilor

iteratori cu acces aleator== != < > >= [] =*p

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

== != ++ *p= -> =*p

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

7/29/2019 9. STL - Partea I

13/48


STL::iteratori constanti si mutabili

iterator constant: obiectul referit poate fi accesat dar nu se poateatribui o noua valoare prin acest iterator

typedef vector::const_iteratorVectIntConstIt;

Iterator mutable: sunt posibile ambele actiuni (acces si atribuirevaloare)

typedef vector::iterator VectIntIt;

exemplu

VectIntConstIt q;vectInt.erase(q);

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

// OK

7/29/2019 9. STL - Partea I

14/48


STL::containere:: acces la elemente

c.front()

primul element

c.back()

ultimul element

c[i]//

(nu pentru liste)

al i-lea element din secventa (NU se valideaza

valoarea lui i)

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

7/29/2019 9. STL - Partea I

15/48


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)

insereaza x la inceput

c.pop_front()

elimina de la inceput

7/29/2019 9. STL - Partea I

16/48


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)

elimina de la p

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

c.clear()

elimina toate elementele

7/29/2019 9. STL - Partea I

17/48


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 spatiuc.resize() // (numai pentru vector) adauga elemente la

// sfarsitmax_size() // (numai pentru vector) dim celui mai mare

// vector posibilswap(c1, c2) // intershimba continuturile a 2 containere

== // testul de egalitate!= // testul diferit

< // relatia de ordine lexicografica

7/29/2019 9. STL - Partea I

18/48


STL::containere:: constructori

container()

containerul vid

container(n)

containerul cu n elemente cu valoare implicita

container(n, x)(nu pt asociative)

containerul cu n copii ale lui x

container(first, last)

containerul cu elemente din intervalul [first, last)

container(c)constructorul de copiere

~container()

destructor

7/29/2019 9. STL - Partea I

19/48


STL::containere:: atribuiri

operator=(c)

copie din containerul c

assign(n) //(nu pentru asociative)

atribuie n elemente cu valoare implicitaassign(n, x) //(nu pentru asociative)

atribuie n copii ale lui xassign(first, last)

atribuie din intervalul [first, last)

7/29/2019 9. STL - Partea I

20/48


STL::containere:: operatii asociative

operator[](k)

acceseaza elementul cu cheia kfind(k)

gaseste componenta cu cheia klower_bound(k)

gaseste primul element cu cheia k

upper_bound(k)gaseste primul element cu cheia mai mare decat k

equal_range(k)

gaseste lower_bound() si upper_bound()pentru cheiak

key_comp()

componenta cheie

value_comp()

componenta valoare (data)

7/29/2019 9. STL - Partea I

21/48


STL::vector:: declarare

template

class std::vector

{

public:

typedef T data_type;

//. . .

iterator begin();//. . .

}

7/29/2019 9. STL - Partea I

22/48


STL::vector:: reprezentare

size

rep

elemente spatiu extra

7/29/2019 9. STL - Partea I

23/48


vector::exemplu::agenda telefonica

vector Intrare

AgTel

7/29/2019 9. STL - Partea I

24/48



header

#include

intrare in agenda = structuraclass Intrare {

public:Intrare(char *un_s="\0", long un_n=0);void afiseaza() const;

...

private:string nume;

long nr;

};

7/29/2019 9. STL - Partea I

25/48


declarare agenda

typedef vector AgTel;

AgTel agTel(20);

adaugarea de intrari pe pozitii aleatoare

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

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


7/29/2019 9. STL - Partea I

26/48


STL::vector::agenda telefonica

realizarea unei copiiAgTel copie = agTel;

accesul la componentecopie[0].afiseaza();

copie[10].afiseaza();

7/29/2019 9. STL - Partea I

27/48



declarare tip iteratori

typedef AgTel::iterator AgTelIterator;

AgTelIterator i;

afisare agenda

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

i->afiseaza();

7/29/2019 9. STL - Partea I

28/48



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)

i->afiseaza();

nu afiseaza nimic

7/29/2019 9. STL - Partea I

29/48


Recomandare: utilizeaza numai iteratori!

agTel.clear();

agTel.push_back(Intrare("Ionescu", 123456));

agTel.push_back(Intrare("Popescu", 654321));

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

i->afiseaza();


7/29/2019 9. STL - Partea I

30/48


STL::containere::liste:: declarare

template

class std::list

{

public:

typedef T value_type;

//. . .

iterator begin();//. . .

}

7/29/2019 9. STL - Partea I

31/48


STL::containere::liste::reprezentare

rep

elemente

7/29/2019 9. STL - Partea I

32/48


liste::exemplu::agenda telefonica

list Intrare

AgTel

7/29/2019 9. STL - Partea I

33/48


STL::liste::agenda telefonica

header

#include declarare agenda

typedef list AgTel;

AgTel agTel;

typedef AgTel::iterator AgTelIterator;

7/29/2019 9. STL - Partea I

34/48


STL::liste::agenda telefonica

adaugarea unei intrari la inceputIntrare x("Ionescu", 123456);agTel.push_front(x);

adaugarea unei intrari la sfarsitIntrare y("Popescu", 654321);agTel.push_back(y);

parcurgerea agendei

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

cout

7/29/2019 9. STL - Partea I

35/48


STL:: liste sau vectori?

Acelasi program poate merge la fel debine daca

schimbam listele cu vectorii Demo (stdlib3.cpp, stdlib3_1.cpp)

7/29/2019 9. STL - Partea I

36/48


STL::tablouri asociative (map):: declarare

template

class std::map

{

public:

typedef T data_type;

typedef pair value_type;

//. . .

iterator find(const key_type& k);

//. . .

}

7/29/2019 9. STL - Partea I

37/48


STL::tablouri asociative:: reprezentare

rep

. . .

perechi (cheie, data)

7/29/2019 9. STL - Partea I

38/48


STL::tablouri asociative::ag. tel.

header

#include

declarare agenda

cheia = numele data = numarul de telefon

map agTel;

adaugarea de intrari dupa cheieagTel["Ionescu"] = 123456;

agTel["Popescu"] = 654321;

7/29/2019 9. STL - Partea I

39/48


STL::tablouri asociative::ag. tel.

declarare iterator

typedef map::const_iterator MI;

parcurgere agenda

for (MI p=agTel.begin(); p!=agTel.end(); ++p)

cout first

7/29/2019 9. STL - Partea I

40/48


STL::perechi

template

struct pair{

typedef T first_type;

typedef U second_type

T first;

U second;

pair();

pair(const T& x, const U& y);template

pair(const pair& pr);

};

7/29/2019 9. STL - Partea I

41/48


STL::tablouri asociative ::ag. tel.

inserare ca perechepair pb = \

agTel.insert(make_pair(string("Zorzonel"),\

123543));

if (pb.second)

{

cout

7/29/2019 9. STL - Partea I

42/48


STL::tablouri asociative ::ag. tel.

cauta in agenda si elimina (daca gaseste)

MI q = agTel.find("Ropescu");

if ( q == agTel.end())

{

cout

7/29/2019 9. STL - Partea I

43/48


STL::containere::multimap:: declarare

template

class std::multimap

{

public:typedef T value_type;

//. . .

iterator insert(const value_type&);

//. . .}

7/29/2019 9. STL - Partea I

44/48


STL::multimap:: reprezentare

rep

. . .

perechi (cheie, val)

7/29/2019 9. STL - Partea I

45/48


STL::multimap::exemplu::ag.tel

header

#include

declarare agenda telefonica

cheia = numele

data = numarul de telefon

std::multimap agTel;

inserareconst string ionescu("Ionescu");agTel.insert(agTel.end(), \

make_pair(ionescu, 123543));

7/29/2019 9. STL - Partea I

46/48



sterge toti Popestii

agTel.erase(string("Popescu")); cauta si sterge numai primul Popescu

q = agTel.find(string("Popescu"));

if ( q != agTel.end())

{

agTel.erase(q);

}

7/29/2019 9. STL - Partea I

47/48



declarare iteratori

typedef multimap::iterator MI;MI p, q;

afisarea numai a PopestilorMI p, q;

p = agTel.find(string("Popescu"));if ( p != agTel.end())

do{

cout first first == Popescu"));

7/29/2019 9. STL - Partea I

48/48


creeaza o agenda numai cu Popestii

p = agTel.lower_bound(string("Popescu"));q = agTel.upper_bound(string("Popescu"));

multimap temp(p, q);

mai eficient:

pair pit =

agTel.equal_range(string("Popescu"));

p = pit.first; q = pit.second;

afiseaza agenda temporarafor (p = temp.begin(); p != temp.end(); ++p)

cout first

9. STL - Partea I

Documents

Transcript of 9. STL - Partea I