Limbile
Pagini
Legal
STLSTL
Partea 1
1
Cuprins
STL (Standard Template Library)ce includesiruri containere standard• sumar• vectori• liste• liste • tablouri asociative • tablouri asociative cu chei multipletablouri asociative cu chei multiple
D. Lucanu STL – Partea 1 2
STL::continutbiblioteci C•<cstring>•<cstdlib>•<cstdlib>• etc
siruri ca obiecte•<string>containere• t•<vector>•<list>•<queue><queue>•<stack>•<map>
D. Lucanu STL – Partea 1 3
• etc
STL::continut (cont.)
iteratori•<iterator>
algoritmi•<algorithm>•<cstdlib>
intrari/iesiri•<iostream>•<iostream>•<istream>• etcetc
etc
D. Lucanu STL – Partea 1 4
STL:: siruri::exemplu simplu
header#include <string>
spatiul de numeusing namespace std;
declaratii sirurideclaratii siruristring s("Un text simplu.");string tag("$tag$");g g( $ g$ );
s Un text simplu.s 15
t$tag$
D. Lucanu STL – Partea 1 5
tagg
5
STL:: siruri::exemplu simplu
operatii peste siruris.insert(8, tag + ' ');int start = s.find(tag);s.replace(start, tag.size(), "foarte");cout << s c str();cout << s.c_str();
Un text foarte simplu.
Un text simplu.s 15Un text $tag$ simplu.
2122
tag $tag$
5
D. Lucanu STL – Partea 1 6
STL::containere::definitieun obiect care contine alte obiecte (componentele) si are metode de accesare a componentelorfi 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
11 0..*
Componenta
*
D. Lucanu STL – Partea 1 7
STL::secvente<vector>
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
<list><list>suporta parcurgerea in ambele sensuri, timp constant
(amortizat) pentru insertie si eliminare la inceput, la sfarsit i i t isau in interior
<deque>suporta acces (inserare si eliminare) la ambele capete
< ><queue>suporta inserare la un capat si eliminare la celalalt capat
<stack>
D. Lucanu STL – Partea 1 8
suporta inserarea si eliminarea la acelasi capatetc
STL::containere asociativesuporta cautarea eficienta bazata pe chei
<map>componentele sunt perechi <cheie, data> cu cheie
unica (nu exista doua date cu aceeasi cheie)<multimap>p
componentele sunt perechi <cheie, data> cu cheie multipla (pot exista mai multe date cu aceeasi cheie)
<set><set>componentele sunt doar de tip cheie si NU pot exista in
duplicat <multiset>
componentele sunt doar de tip cheie si POT exista in duplicat
D. Lucanu STL – Partea 1 9
duplicatetc
STL:: containere::tipuri asociateX::value_type
tipul obiectului memorat in containerX::allocator_type
tipul managerului de memorieX::size_type
tip pentru indici, numar de elemente etc X::iteratorX::iterator
tip pentru iterator cu care se "merge" prin containeretcetc
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 obiectelorconcepte cheie:• elementul curent la care face referire (p->, *p)elementul curent la care face referire (p >, p)• elementul urmator/precedent (++p, --p)• comparatii (< <= ==)
alti iteratoribegin()end()rbegin() // reverse beginrend() // reverse end
D. Lucanu STL – Partea 1 11
rend() // reverse end
STL::containere:: iteratori
O clasificare a iteratorilor• iteratori cu acces aleator
== != < > >= <= ++ -- + - += -= *p= -> [] =*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 mutabiliiterator constant: obiectul referit poate fi accesat dar nu se poate atribui o noua valoare prin acest iterator
typedef vector<int>::const iteratortypedef vector<int>::const_iterator VectIntConstIt;
Iterator “mutable”: sunt posibile ambele actiuni (acces si atribuire valoare)valoare)
typedef vector<int>::iterator VectIntIt;
exemplupVectIntConstIt q; vectInt.erase(q);
// error: no matching function ...VectIntIt p;vectInt.erase(p);
// OK
D. Lucanu STL – Partea 1 13
STL::containere:: acces la elementec.front()
primul elementc.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 listac.insert(p, x)
insereaza x inaintea lui pc.insert(p, n, x)
insereaza n copii ale lui x inaintea lui pc.insert(p, first, last)
adauga elementele din [first, last) inaintea lui pc erase(p)c.erase(p)
elimina de la pc.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 operatiic.size() // numarul de elementec.empty() // este c vid?c.capacity() // (numai pentru vector) spatiul alocatc.reserve(n) // (numai pentru vector) aloca spatiuc resize() // (numai pentru vector) adauga elemente lac.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 de egalitate!= // testul diferit< // relatia de ordine lexicografica
D. Lucanu STL – Partea 1 17
STL::containere:: constructoricontainer()
containerul vidcontainer(n)
containerul cu n elemente cu valoare implicita( t i ti )container(n, x)(nu pt asociative)
containerul cu n copii ale lui xcontainer(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:: atribuirioperator=(c)
copie din containerul cassign(n) //(nu pentru asociative)
atribuie n elemente cu valoare implicita//( t i ti )assign(n, x) //(nu pentru asociative)
atribuie n copii ale lui xassign(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 kfind(k)find(k)
gaseste componenta cu cheia klower_bound(k)
gaseste primul element cu cheia kgaseste primul element cu cheia kupper_bound(k)
gaseste primul element cu cheia mai mare decat kl (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 T,class A = allocator<T>>
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 <T> Intrare
AgTel
D. Lucanu STL – Partea 1 23
vector::exemplu::agenda telefonica
header#include <vector>
intrare in agenda = structuraclass 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 agendatypedef vector<Intrare> 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 telefonicarealizarea unei copiiAgTel copie = agTel;
accesul la componentecopie[0].afiseaza();copie[10].afiseaza();
D. Lucanu STL – Partea 1 26
STL::vector::agenda telefonica
declarare tip iteratoritypedef AgTel::iterator AgTelIterator;AgTelIterator i;
afisare agendafor (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 iteratoriagTel.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. Lucanu STL – Partea 1 28
STL::vector::agenda telefonica
Recomandare: utilizeaza numai iteratori!
agTel.clear();agTel.push_back(Intrare("Ionescu", 123456));T l h b k(I t ("P " 654321))agTel.push_back(Intrare("Popescu", 654321));
for (i=agTel.begin(); i != agTel.end(); ++i)i->afiseaza();()
D. Lucanu STL – Partea 1 29
STL::containere::liste:: declarare
template <class T,class A = allocator<T>>
class std::list{public:typedef T value type;typedef T value_type;//. . .iterator begin();te ato beg ();//. . .
}
D. Lucanu STL – Partea 1 30
STL::containere::liste::reprezentare
rep
elemente
D. Lucanu STL – Partea 1 31
liste::exemplu::agenda telefonica
list<T> Intrare
AgTel
D. Lucanu STL – Partea 1 32
STL::liste::agenda telefonicaheader
#include <list>declarare agendadeclarare agenda
typedef list<Intrare> AgTel;AgTel agTel;AgTel agTel;typedef AgTel::iterator AgTelIterator;
D. Lucanu STL – Partea 1 33
STL::liste::agenda telefonicaadaugarea unei intrari la inceput
Intrare x("Ionescu", 123456);agTel.push_front(x);
adaugarea unei intrari la sfarsitadaugarea unei intrari la sfarsitIntrare y("Popescu", 654321);agTel.push_back(y);
parcurgerea agendeifor (AgTelIterator i=agTel begin();for (AgTelIterator i=agTel.begin();
i!=agTel.end();++i)cout << (*i).getNume() << (*i).getNr();
D. Lucanu STL – Partea 1 34
STL:: liste sau vectori?
Acelasi program poate merge la fel debine daca schimbam listele cu vectoriiDemo (stdlib3.cpp, stdlib3_1.cpp)
D. Lucanu STL – Partea 1 35
STL::tablouri asociative (map):: declarare
template <class Key, class T,class Cmp = less<Key>,p y ,class A = allocator<T>>
class std::map{public:typedef T data type;typedef T data_type;typedef pair<Key, T> value_type;//. . .iterator find(const key_type& k);//. . .
}
D. Lucanu STL – Partea 1 36
}
STL::tablouri asociative:: reprezentare
rep. . .
hi ( h i d )perechi (cheie, data)
D. Lucanu STL – Partea 1 37
STL::tablouri asociative::ag. tel.
header#include <map>
declarare agenda• cheia = numele• data = numarul de telefon
map<string long> agTel;map<string, long> agTel;
adaugarea de intrari dupa cheieadaugarea de intrari dupa cheieagTel["Ionescu"] = 123456;agTel["Popescu"] = 654321;
D. Lucanu STL – Partea 1 38
STL::tablouri asociative::ag. tel.
declarare iteratortypedef map<string, long>::const_iterator MI;
parcurgere agendafor (MI p=agTel.begin(); p!=agTel.end(); ++p)cout << p->first << ' ' << p->second;
modificarea numarului lui IonescuagTel["Ionescu"] = 567890;agTel[ Ionescu ] 567890;
D. Lucanu STL – Partea 1 39
STL::perechitemplate<class T, class U>struct pair{ typedef T first_type; typedef U second_type T first;U second;U second; pair();pair(const T& x, const U& y);pa (co st & , co st U& y);template<class V, class W> pair(const pair<V, W>& pr);
D. Lucanu STL – Partea 1 40
};
STL::tablouri asociative ::ag. tel.inserare ca pereche
pair <MI, bool> pb = \T l i t( k i ( t i ("Z l") \agTel.insert(make_pair(string("Zorzonel"),\
123543));if (pb.second){
cout << "Zorzonel a fost inserat.";}}else{
t << "Z l t d j i t "cout << "Zorzonel este deja inserat.";}
D. Lucanu STL – Partea 1 41
STL::tablouri asociative ::ag. tel.
cauta in agenda si elimina (daca gaseste)
MI q = agTel.find("Ropescu");if ( q == agTel.end()){{cout << "Nu este in carte." << endl;
}else{agTel erase(q);agTel.erase(q);
}
D. Lucanu STL – Partea 1 42
STL::containere::multimap:: declararetemplate <class Key, class T,
class Cmp = less<Key>,class A = allocator<T>>
class std::multimap{{public:typedef T value_type;//. . .iterator insert(const value_type&);////. . .
}
D. Lucanu STL – Partea 1 43
STL::multimap:: reprezentare
rep. . .
perechi (cheie, val)
D. Lucanu STL – Partea 1 44
STL::multimap::exemplu::ag.tel
header#include <map>p
declarare agenda telefonica• cheia = numele• data = numarul de telefon
td lti t i l T lstd::multimap<string, long> agTel;inserareconst string ionescu("Ionescu");const string ionescu( Ionescu );agTel.insert(agTel.end(), \
make pair(ionescu, 123543));
D. Lucanu STL – Partea 1 45
_p ( , ));
STL::multimap::exemplu::ag.tel
sterge toti PopestiiagTel.erase(string("Popescu"));
cauta si sterge numai primul Popescuq = agTel.find(string("Popescu"));if ( q != agTel.end()){{
agTel.erase(q);}}
D. Lucanu STL – Partea 1 46
STL::multimap::exemplu::ag.tel
declarare iteratoritypedef multimap<string, long>::iterator MI;MI p, q;
afisarea numai a PopestilorMI p, q;p, q;p = agTel.find(string("Popescu"));if ( p != agTel.end())ddo{
cout << p->first << ' ' << p->second;p p++p;
} while ((p != agTel.end()) && \(p >first == Popescu"));
D. Lucanu STL – Partea 1 47
(p->first == Popescu"));
STL::multimap::exemplu::ag.tel
creeaza o agenda numai cu Popestiip = agTel.lower_bound(string("Popescu"));q = agTel.upper_bound(string("Popescu"));multimap<string, long> temp(p, q);
mai eficient:pair<MI, MI> pit =
agTel equal range(string("Popescu"));agTel.equal_range(string( Popescu ));p = pit.first; q = pit.second;
afiseaza agenda temporaraafiseaza agenda temporarafor (p = temp.begin(); p != temp.end(); ++p)
cout << p->first << ' ' << p->second;
D. Lucanu STL – Partea 1 48
Top Related