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