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
D. Lucanu STL Partea 1 3
STL::continut
biblioteci C
etc siruri ca obiecte
containere
etc
7/29/2019 9. STL - Partea I
4/48
D. Lucanu STL Partea 1 4
STL::continut (cont.)
iteratori
algoritmi
intrari/iesiri
etc etc
7/29/2019 9. STL - Partea I
5/48
D. Lucanu STL Partea 1 5
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
D. Lucanu STL Partea 1 6
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
D. Lucanu STL Partea 1 7
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
D. Lucanu STL Partea 1 8
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
D. Lucanu STL Partea 1 9
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
D. Lucanu STL Partea 1 10
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
D. Lucanu STL Partea 1 11
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
D. Lucanu STL Partea 1 12
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
D. Lucanu STL Partea 1 13
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
D. Lucanu STL Partea 1 14
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
D. Lucanu STL Partea 1 15
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
D. Lucanu STL Partea 1 16
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
D. Lucanu STL Partea 1 17
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
D. Lucanu STL Partea 1 18
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
D. Lucanu STL Partea 1 19
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
D. Lucanu STL Partea 1 20
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
D. Lucanu STL Partea 1 21
STL::vector:: declarare
template
class std::vector
{
public:
typedef T data_type;
//. . .
iterator begin();//. . .
}
7/29/2019 9. STL - Partea I
22/48
D. Lucanu STL Partea 1 22
STL::vector:: reprezentare
size
rep
elemente spatiu extra
7/29/2019 9. STL - Partea I
23/48
D. Lucanu STL Partea 1 23
vector::exemplu::agenda telefonica
vector Intrare
AgTel
7/29/2019 9. STL - Partea I
24/48
D. Lucanu STL Partea 1 24
vector::exemplu::agenda telefonica
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
vector::exemplu::agenda telefonica
declarare agenda
typedef vector AgTel;
AgTel agTel(20);
adaugarea de intrari pe pozitii aleatoare
agTel[0] = Intrare("Ionescu", 123456);
agTel[10] = Intrare("Popescu", 654321);
D. Lucanu STL Partea 1 25
7/29/2019 9. STL - Partea I
26/48
D. Lucanu STL Partea 1 26
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
D. Lucanu STL Partea 1 27
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();
7/29/2019 9. STL - Partea I
28/48
D. Lucanu STL Partea 1 28
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)
i->afiseaza();
nu afiseaza nimic
7/29/2019 9. STL - Partea I
29/48
STL::vector::agenda telefonica
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();
D. Lucanu STL Partea 1 29
7/29/2019 9. STL - Partea I
30/48
D. Lucanu STL Partea 1 30
STL::containere::liste:: declarare
template
class std::list
{
public:
typedef T value_type;
//. . .
iterator begin();//. . .
}
7/29/2019 9. STL - Partea I
31/48
D. Lucanu STL Partea 1 31
STL::containere::liste::reprezentare
rep
elemente
7/29/2019 9. STL - Partea I
32/48
D. Lucanu STL Partea 1 32
liste::exemplu::agenda telefonica
list Intrare
AgTel
7/29/2019 9. STL - Partea I
33/48
D. Lucanu STL Partea 1 33
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
D. Lucanu STL Partea 1 34
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
D. Lucanu STL Partea 1 35
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
D. Lucanu STL Partea 1 36
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
D. Lucanu STL Partea 1 37
STL::tablouri asociative:: reprezentare
rep
. . .
perechi (cheie, data)
7/29/2019 9. STL - Partea I
38/48
D. Lucanu STL Partea 1 38
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
D. Lucanu STL Partea 1 39
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
D. Lucanu STL Partea 1 40
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
D. Lucanu STL Partea 1 41
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
D. Lucanu STL Partea 1 42
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
D. Lucanu STL Partea 1 43
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
D. Lucanu STL Partea 1 44
STL::multimap:: reprezentare
rep
. . .
perechi (cheie, val)
7/29/2019 9. STL - Partea I
45/48
D. Lucanu STL Partea 1 45
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
D. Lucanu STL Partea 1 46
STL::multimap::exemplu::ag.tel
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
D. Lucanu STL Partea 1 47
STL::multimap::exemplu::ag.tel
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
STL::multimap::exemplu::ag.tel
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