 |
|
 |  |
| Aeronautica | Comunicatii | Drept | Informatica | Nutritie | Sociologie |
| Tehnica mecanica |
Informatica
|
Qdidactic » stiinta & tehnica » informatica Biblioteca de sabloane standard - containere si vectori |
Biblioteca de sabloane standard - containere si vectori
Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala prin intermediul algoritmilor.
Programele dezvoltate folosind STL beneficiaza de o viteza de dezvoltare si o viteza de executie sporite. Ele sunt mai eficiente, mai robuste, mai portabile, mai usor de modificat si intretinut.
Componentele STL sunt: containerele, iteratorii, algoritmii, functorii (obiectele functii) si adaptorii.
Containere.
Un container este un obiect care pastreaza o colectie de alte obiecte. Containerele (exceptand string si ) sunt clase generice (parametrizate)
In STL se folosesc doua tipuri de containere:
- containere secventiale (vector, lista, coada cu doua capete - deque)
- containere asociative (multime, relatie)
Un container secvential pastreaza colectia de obiecte intr-o ordine strict liniara.
Containerele asociative pastreaza informatiile din colectie sortate, ceea ce permite regasirea rapida a obiectelor din colectie, pe baza unei chei.
Vectorul (vector)
|
Constructor |
Efect |
Complexitate |
|
vector<T>v |
creaza un vector vid |
O(1) |
|
vector<T>v(n) |
creaza un vector cu n elemente |
O(n) |
|
vector<T>v(n,val) |
creaza un vector cu n elemente initializate cu val |
O(n) |
|
vector<T>v(v1) |
creaza un vector initializat cu vectorul v1 |
O(n) |
|
Accesor |
Efect |
Complexitate |
|
v[i] |
intoarce elementul i |
O(1) |
|
v.front() |
intoarce primul element |
O(1) |
|
v.back() |
intoarce ultimul element |
O(1) |
|
v.capacity() |
intoarce numarul maxim de elemente |
O(1) |
|
v.size() |
intoarce numarul curent de elemente |
O(1) |
|
v.empty() |
intoarce true daca vectorul este vid |
O(1) |
|
v.begin() |
intoarce un iterator la inceputul vectorului |
O(1) |
|
v.end() |
intoarce un iterator dupa sfarsitul vectorului |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
v.push_back(val) |
adauga o valoare la sfarsit |
O(1) |
|
v.insert(iter,val) |
insereaza valoarea in pozitia indexata de iterator |
O(n) |
|
v.pop_back() |
sterge valoarea de la sfarsit |
O(1) |
|
v.erase(iter) |
sterge valoarea indexata de iterator |
O(n) |
|
v.erase(iter1,iter2) |
sterge valorile din domeniul de iteratori |
O(n) |
Coada cu doua capete (deque)
|
Constructor |
Efect |
Complexitate |
|
deque<T>d |
creaza un deque vid |
O(1) |
|
deque<T>d(n) |
creaza un deque cu n elemente |
O(n) |
|
deque<T>d(n,val) |
creaza un deque cu n elemente initializate cu val |
O(n) |
|
deque<T>d(d1) |
creaza un deque initializat cu deque-ul d |
O(n) |
|
Accesor |
Efect |
Complexitate |
||||
|
d[i] |
intoarce elementul i |
O(1) |
||||
|
d.front() |
intoarce primul element |
O(1) |
||||
|
d.back() |
intoarce ultimul element |
O(1) |
||||
|
d.capacity() |
intoarce numarul maxim de elemente |
O(1) |
||||
|
d.size() |
intoarce numarul curent de elemente |
O(1)
|
||||
|
d.empty() |
intoarce true daca deque-ul este vid |
O(1) |
||||
|
d.begin() |
intoarce un iterator la inceputul deque-ului |
O(1) |
||||
|
d.end() |
intoarce un iterator dupa sfarsitul deque-ului |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
d.push_back(val) |
adauga o valoare la sfarsit |
O(1) sau O(n) |
|
d.insert(iter,val) |
insereaza valoarea in pozitia indexata de iterator |
O(n) |
|
d.pop_back() |
sterge valoarea de la sfarsit |
O(1) |
|
d.erase(iter) |
sterge valoarea indexata de iterator |
O(n) |
|
d.erase(iter1,iter2) |
sterge valorile din domeniul de iteratori |
O(n) |
Lista (list)
|
Constructor |
Efect |
Complexitate |
|
list<T>L |
creaza o lista vida |
O(1) |
|
list <T>L(L1) |
creaza o lista initializata cu lista L1 |
O(n) |
|
Accesor |
Efect |
Complexitate |
|
L.front() |
intoarce primul element |
O(1) |
|
L.back() |
intoarce ultimul element |
O(1) |
|
L.size() |
intoarce numarul curent de element |
O(1) |
|
L.empty() |
intoarce true daca lista este vida |
O(1) |
|
L.begin() |
intoarce un iterator la inceputul listei |
O(1) |
|
L.end() |
intoarce un iterator dupa sfarsitul liste |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
L.push_front(val) |
adauga o valoare la inceput |
O(1) |
|
L.push_back(val) |
adauga o valoare la sfarsit |
O(1) |
|
L.insert(iter,val) |
insereaza valoarea in pozitia indexata de iterator |
O(1) |
|
L.pop_front() |
sterge valoarea de la inceput |
O(1) |
|
L.pop_back() |
sterge valoarea de la sfarsit |
O(1) |
|
L.erase(iter) |
sterge valoarea indexata de iterator |
O(1) |
|
L.erase(iter1,iter2) |
sterge valorile din domeniul de iteratori |
O(1) |
|
L.remove(val) |
sterge toate aparitiile lui val in lista |
O(n) |
|
L.remove_if(pred) |
sterge toate elementelele care satisfac predicatul |
O(n) |
|
L.reverse(pred) |
inverseaza lista |
O(n) |
|
L.sort() |
sorteaza lista |
O(nlogn) |
|
L.sort(comp) |
sorteaza lista folosind functia de comparatie |
O(nlogn) |
|
L.merge(L1) |
interclaseaza doua liste sortate |
O(n) |
Stiva (stack)
|
Constructor |
Efect |
Complexitate |
|
stack<T>s |
creaza o stiva vida |
O(1) |
|
Accesor |
Efect |
Complexitate |
|
s.top() |
intoarce elementul din varf |
O(1) |
|
s.size() |
intoarce numarul curent de elemente |
O(1) |
|
s.empty() |
intoarce true daca stiva este vida |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
s.push(val) |
pune o valoare in varful stivei |
O(1) |
|
s.pop() |
sterge valoarea din varful stivei |
O(1) |
Coada (queue)
|
Constructor |
Efect |
Complexitate |
|
queue<T>q |
creaza o coada vida |
O(1) |
|
Accesor |
Efect |
Complexitate |
|
q.front() |
intoarce elementul din fata cozii |
O(1) |
|
q.back() |
intoarce elementul din spatele cozii |
O(1) |
|
q.size() |
intoarce numarul curent de elemente |
O(1) |
|
q.empty() |
intoarce true daca coada este vida |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
q.push(val) |
pune o valoare in spatele cozii |
O(1) |
|
q.pop() |
sterge valoarea din fata cozii |
O(1) |
Coada prioritara(priority queue)
|
Constructor |
Efect |
Complexitate |
|
priority_queue<T,comp>q |
creaza o coada prioritaravida, sortata cu comp |
O(1) |
|
Accesor |
Efect |
Complexitate |
|
q.top() |
intoarce elementul "cel mai prioritar" (mai "mare") |
O(1) |
|
q.size() |
intoarce numarul curent de elemente |
O(1) |
|
q.empty() |
intoarce true daca coada prioritara este vida |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
q.push(val) |
insereaza o valoare in coada prioritara |
O(logn) |
|
q.pop() |
scoate elementul cel mai "mare" din coada prioritara |
O(1) |
Multimi si multimultimi (set)
Multimile pastreaza obiecte sortate cu operatorul < (care poate fi supraincarcat), pentru a fi regasite rapid. Intr-o multime, un element apare o singura data. Intr-o multimultime pot apare mai multe copii ale unui element.
|
Constructor |
Efect |
Complexitate |
|
set<tip_ch,comp_ch>m |
creaza o multime vida; sortarea elementelor se face cu comp_ch |
O(1) |
|
Accesor |
Efect |
Complexitate |
|
m.find(ch) |
intoarce un iterator la aparitia cheii in m (m.end(), daca gaseste cheia in m) |
O(log n) |
|
m.lower_bound(ch) |
intoarce un iterator la prima aparitie a cheii in m (m.end(), daca nu gaseste cheia in m) |
O(log n) |
|
m.upper_bound(ch) |
intoarce un iterator la primul element mai mare ca cheia in m (m.end(), daca nu exista un asemenea element) |
O(log n) |
|
m.equal_range(ch) |
intoarce pair<lower_bound(ch),upper_bound(ch)> |
O(log n) |
|
m.count(ch) |
intoarce numarul de elemente egale cu cheia ch in m |
O(log n) |
|
m.size() |
intoarce numarul curent de elemente |
O(1) |
|
m.empty() |
intoarce true daca coada prioritara este vida |
O(1) |
|
m.begin() |
intoarce un iterator la primul element (cel mai mic)din m |
O(1) |
|
m.end() |
intoarce un iterator la ultimul element (cel mai mare)din m |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
m.insert(iter,ch) |
insereaza un element ch in m. Intoarce iterator la elementul ch din m |
O(log n) |
|
m.insert(ch) |
insereaza un element ch in m.Intoarce pair<iterator,bool> bool este true daca inserarea a avut loc. Iterator indica cheia inserata |
O(log n) |
Relatii si multirelatii (map)
Relatiile pot fi privite ca vectori generalizati, in care locul indicelui intreg il ia cheia, care poate fi de orice tip, motiv pentru care relatiile se mai numesc si tabele asociative. Memorarea unei perechi <cheie, valoare> poate fi facuta prin atribuirea map[ch]=val. Relatiile se implementeaza cu arbori de cautare echilibrati (de exemplu arbori rosii-negri), care asigura timpi de cautare-regasire logaritmici.. Daca perechea <cheie, valoare> nu exista in relatie, indexarea map[ch] creaza o intrare falsa in relatie, motiv pentru care se cauta cheia in prealabil cu map.find(ch).
|
Constructor |
Efect |
Complexitate |
|
map<tip_ch,tip_val,comp_ch>r |
creaza o relatie vida; sortarea elementelor dupa cheie se face cu comp_ch |
O(1) |
|
Accesor |
Efect |
Complexitate |
|
r[ch] |
intoarce valoarea accesata prin cheie |
O(log n) |
|
r.find(ch) |
intoarce un iterator la perechea cheie-valoare (r.end(), daca nu gaseste cheia in r) |
O(log n) |
|
r.size() |
intoarce numarul curent de elemente |
O(1) |
|
r.empty() |
intoarce true daca relatia este vida |
O(1) |
|
r.begin() |
intoarce un iterator la prima pereche din r |
O(1) |
|
r.end() |
intoarce un iterator la ultima pereche din r |
O(1) |
|
Modificator |
Efect |
Complexitate |
|
r[ch]=val |
memoreaza perechea cheie-valoare in r |
O(log n) |
|
m.insert(pereche) |
are acelasi efect |
O(log n) |
| Contact |- ia legatura cu noi -| |  |
| Adauga document |- pune-ti documente online -| |  |
| Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -| |  |
| Copyright © |- 2024 - Toate drepturile rezervate -| |  |
 |
||||||||||||||||||||||||
|
||||||||||||||||||||||||
|
||||||||||||||||||||||||
Analize pe aceeasi tema | ||||||||||||||||||||||||
|
| ||||||||||||||||||||||||
|
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||