Set & Map

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<> și unordered_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 << " ";

for(auto I = S.begin(); I != S.end(); I ++)
        cout << * I << " ";

for(auto x : S)
        cout << x << " ";

Mai mult

Mai multe informații sunt disponibile aici:

set	https://en.cppreference.com/w/cpp/container/set
multiset	https://en.cppreference.com/w/cpp/container/multiset
unordered_set	https://en.cppreference.com/w/cpp/container/unordered_set
unordered_multiset	https://en.cppreference.com/w/cpp/container/unordered_multiset

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;

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.

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;

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;

Mai mult

map	https://en.cppreference.com/w/cpp/container/map
multimap	https://en.cppreference.com/w/cpp/container/multimap
unordered_map	https://en.cppreference.com/w/cpp/container/unordered_map
unordered_multimap	https://en.cppreference.com/w/cpp/container/unordered_multimap