Candale Silviu (silviu) Containerele STL set<> și map<> sunt containere asociative sortate. Fiecare element din container este caracterizat prin două componente:
- cheia, care stabilește ordinea de stocare a elementelor în container
- valoare, care reprezintă valoarea stocată, asociată cu cheia corespunzătoare
Observații:
- Valorile memorate în acestea nu sunt identificate prin poziția lor în container, ci prin intermediul cheilor.
- Operațiile de inserare, ștergere și căutare se efectuează eficient.
- Complexitatea operațiilor este \( O(\log n) \), deoarece aceste containere sunt implementate prin intermediul arborilor binari echilibrați.
- Parcurgerea elementelor din container obține elementele în ordinea (strict) crescătoare a cheilor.
- Dacă ordinea cheilor nu este importantă, se pot folosi containerele
unordered_set<>șiunordered_map<>. Ele sunt implementate cu ajutorul tabelelor de dispersie (hash), iar complexitatea operațiilor de inserare, ștergere și căutare este \( O(1) \).
Containerul set<>
Containerul set stochează elementele într-o anumită ordine; el reprezintă o mulțime. Cheia de ordonare este identică cu valoarea stocată. Într-un container de tip set elementele nu se pot repeta. Dacă se dorește repetarea lor, se poate folosi multiset.
Inițializări
Includem header-ul necesar:
#include <set>
Declarăm un set care va conține valori întregi:
set<int> S;
Adăugarea elementelor
Adaugăm un element:
S.insert(x);
Dacă valoarea deja există în set, nu se va mai adăuga.
Sunt disponibile mai multe variante ale funcției insert(). Mai multe detalii aici: https://en.cppreference.com/w/cpp/container/set/insert.
Eliminarea elementelor
Eliminăm elementul cu valoarea x:
S.erase(x);
Eliminăm elementul dat prin iteratorul I:
S.erase(I);
Eliminăm toate elementele din intervalul [st, dr), unde st și dr sunt iteratori:
S.erase(st , dr);
Dacă valoarea nu există în set, nu se va întâmpla nimic.
Mai multe informatii despre eliminare: https://en.cppreference.com/w/cpp/container/set/erase.
Căutarea elementelor
Cautăm un element în set:
set<int>::iterator I = S.find(x);
if(I == S.end())
cout << x << " nu apare in set";
else
cout << x << " apare in set";
Funcția S.find(x) returnează un iterator la elementul cu valoarea x, sau la S.end(), dacă nu există un asemenea element.
Parcurgerea containerului set<>
Parcurgem elementele din set:
for(set<int>::iterator I = S.begin(); I != S.end(); I ++)
cout << * I << " ";
sau
for(auto I = S.begin(); I != S.end(); I ++)
cout << * I << " ";
sau
for(auto x : S)
cout << x << " ";
Mai mult
Mai multe informații sunt disponibile aici:
Containerul map<>
Containerul map memorează perechi cheie – valoare, în ordinea strictă a cheilor. Cheile nu se pot repeta – nu putem avea mai multe elemente cu aceeași cheie. Dacă avem nevoie de mai multe elemente cu aceeași cheie putem folosi containerul multimap. Dacă ordinea elementelor nu este importantă, putem folosi containerele unordered_map, unordered_multimap.
Inițializări
Includem header-ul necesar:
#include <map>
Declarăm un map care va conține elemente cu chei și valori întregi:
map<int, int> M;
Accesarea elementelor
M[x]
returnează o referință la valoarea din elementul cu cheia x, dacă acesta există. În caz contrar se adaugă un element cu cheia x și valoarea 0, iar rezultatul este o referință la valoarea acestuia.
M.at(x)
returnează o referință la valoarea din elementul cu cheia x, dacă acesta există. În caz contrar, se ridică o execepție, fără a se adăuga un nou element în container.
Inserarea elementelor
Adaugăm un element, cu cheia x și valoarea v :
M[x] = v;
sau
M.insert(make_pair(x,v));
Dacă în map există deja cheia x, atunci M[x] = v modifică elementul respectiv, în timp ce M.insert(make_pair(x,v)) returnează false.
Mai multe informații despre inserare: https://en.cppreference.com/w/cpp/container/map/insert.
Eliminarea elementelor
Eliminăm elementul cu cheia x:
M.erase(x);
Eliminăm elementul dat prin iteratorul I:
M.erase(I);
Eliminăm toate elementele din intervalul [st, dr), unde st și dr sunt iteratori:
M.erase(st , dr);
Dacă valoarea nu există în set, nu se va întâmpla nimic.
Mai multe informatii despre eliminare: https://en.cppreference.com/w/cpp/container/map/erase.
Căutarea după cheie
Numărarea elementelor cu cheia dată:
M.count(x)
Determină câte elemente din container au cheia x. Valorile sunt 0 sau 1 pentru containerele map și unordered_map, respectiv 0, 1 sau mai mari pentru multimap și unordered_multimap.
Căutarea/accesarea unui element, după cheia x:
cout << M[x];
Dacă în map nu există element cu cheia x, se va insera un asemenea element cu valoarea 0.
sau
map<int,int>::iterator I = M.find(x);
if(I == M.end())
cout << "nu exista";
else
cout << I->second;
Parcurgerea elementelor
Parcurgem elementele dintr-un map – afișăm cheile și valorile:
for(map<int, int>::iterator I = M.begin(); I != M.end(); I ++)
cout << I -> first << " " << I -> second << endl;
sau
for(auto I : M)
cout << I.first << " " << I.second << endl;
Dacă dorim să modificăm valorile elementelor parcurse:
for(auto & I : M)
I.second += 10;