CONTAINERE STL
Mihail Croitor
Cuprins
Iteratori
Proprietățile iteratorilor
Containere
Proprietăți comune ale containerelor
Containere consecutive
Containere asociative
Utilizarea containerelor
Recomandări
Legenda
Х – o clasă container;
u, a, b - obiecte clasei X;
r - iterator;
T – tipul elementelor containerului;
t – valoare de tip T;
n – număr întreg.
Iteratori
Iterator este un obiect special ce asigură acces la elemente din container și permite parcurgerea lor
TIPURI ale ITERATORILOR
Iterator de ieșireIterator de intrare
Iterator consecutiv
Iterator de acces liber
Iterator bidirecțional
Iteratori
Iterator de intrare (input iterator) – permite luarea valorii elementelor din container;
Iterator de ieșire (output iterator) – permite modificarea valorilor elementelor din container;
Iterator consecutiv (forward iterator) – permiteparcurgerea consecutivă a elementelor;
Iterator bidirecțional (bidirectional iterator) – permite parcurgerea consecutivă a elementelor din container cât în ordinea directă atât și în ordinea inversă;
Iterator de acces liber (random access iterator) –permite acces liber la orice element din container;
Proprietățile iteratorilor:iterator de intrare
Proprietate Explicație
X(a)X u(a);X u = a;
Constructor de copiere. Se presupune existența destructorului.
a = b; Operator de copiere
a==b;a != b;
Operator de comparare
*a; Operator de dereferențiere. Se returnează referința constantă la element din container.
++r;r++;
Parcurgerea directă a iteratorilor
NB: iteratori de intrare nu garantează că dacă a == b, atunci a++ == b++
Proprietățile interatorilor:iterator de ieșire
Proprietate Explicație
X(a)X u(a);X u = a;
Constructor de copiere. Se presupune existența destructorului.
*a = t; Operator de dereferențiere. Se returnează referința la element din container.
++r;r++;
Parcurgerea directă a iteratorilor
Proprietățile iteratorilor:iteratori consecutivi
Proprietate Explicație
Are toate proprietăți ale iteratorilor de intrare și de ieșire
a==b;a != b;
Operatori de comparare.a == b => ++a == ++b
Proprietățile iteratorilor:iteratori bidirecționale
Свойство Explicație
Are toate proprietăți ale iteratorilor consecutivi
--r;r--;
Parcurgerea inversă a iteratorilor
Proprietățile iteratorilor:iteratori de acces liber
Proprietate Explicație
Are toate proprietăți ale iteratorilor bidirecționale
r += n;r –= n;
Deplasarea cu n elemente a iteratorului r
r + n;n + r;r – n;
Deplasarea cu n elemente de la iterator a
b – a; Distanța dintre iteratori
a[n] Parcurgerea consecutivă a iteratorilor
a > b;a < b;a ≥ b;a ≤ b;
Operatori de ordonare.
Containere
Container este un obiect ce conține alte obiecte, de obicei de unul și același tip.
Acces la elemente din container se face prin iteratori.
Containeri С++ sunt realizate ca clase șabloane cu interfață de bază comună.
Containere
Lista (list)
Coada (deque)
Vector (vector)
Mulțime (set)
Vector asociativ (map)
Mulțime cu repetări(multiset)
Vector asociativ cu repetări (multimap)
Consecutive (de secvența) Asociative
Containere: Structura comună
proprietate comentariu
X::value_type Este egal cu tip T
X::reference Este egal cu tip T&
X::iterator Tipul iterator, care indică la X::reference
X::const_iterator Iterator constant
X() Constructor implicit
X(a) Constructor de copiere
a.begin() Returnează Iterator; const_iterator ce arată la primul element
a.end() Returnează Iterator; const_iterator ce arată după ultimul element
a.size() Returnează dimensiunea containerului
a.empty() Verifică dacă container este gol
… …
Containere consecutive:proprietăți comune
expresie comentariu
X(n, t)
X a(n, t);
După executare size() == n.
Crează container cu n copii t.
X(i, j)
X a(i, j);
După executare size() == distanța dintre i și j.
crează container cu copii de elemente din segment [i, j).
a.insert(p, t) Inserează copie t înainte de iterator p.
se returnează iterator ce arată la obiect inserat.
a.insert(p, n, t) Inserează n copii t înainte de iterator p.
a.insert(p, i, j) Inserează copii elementelor din segment [i, j) înainte de iterator p.
a.erase(q) Șterge element la care arată iteratorul q.
a.erase(ql, q2) Șterge elemente din diapazonul [ql, q2).
Containere consecutive:proprietăți adăugătoare
expresie semantica container
a.front() *a.begin() vector, list, deque
a.back() *(--a. end()) vector, list, deque
a.push_front(t) a.insert(a.begin(), t) list, deque
a.push_back(t) a.insert(a.end(), t) vector, list, deque
a.pop_front() a.erase(a.begin()) list, deque
a.pop_back() a.erase(-- a.end()) vector, list, deque
a[n] *(a.begin() + n) vector, deque
Containere asociative:proprietăți comune
proprietate Comentariu
X::key_type Tipul cheii
X::value_type Tipul valorii
X::key_compare Tipul funcției de comparare a cheilor (functor)
X(i, j), X(i, j, c) Crearea containerului cu valori din segment [i, j). c – obiectul de comparare
a.insert(t)a.insert(i, j)a.insert(p, t)
Inserarea elementului (segmentului)
a.erase(k);a.erase(q);
Eliminarea elementului după cheie sau iterator.
a.find(k) Căutarea valorii după cheie.
a.count(k) Подсчет элементов с ключом, равным к
… …
Utilizarea containerilor
Recomandări:alegerea tipului de container
Criteriu Recomandări
Posibilitatea inserării elementului nou în orice poziție a containerului
Alegeți containere consecutive (containere asociative nu sunt potrivite, deoarece aranjează elemente într-o ordine proprie).
Structura memoriei containerului trebuie să corespundă regulilor limbajului C
Numai vector
Viteza căutării este critică Considerați vectori ordonați sau containere asociative
Recomandări:utilizarea STL
Nu încercați să scrieți codul independent de tipul containerului;
Realizați operația de copiere rapidă și corectă în clasa elementelor containerului;
Nu utilizați iteratorii repetat;
Utilizați algoritmii în loc de cicluri;
Nu uitați să includeți fișiere-antet necesare;
Învățați-vă să citiți mesajele compilatorului