Ce este și ce face setul?
Setul din C++ este un container STL alocat dinamic. Este ca un vector, doar că are 2 proprietăți importante atunci când vrem să adăugăm un element în set:
- Elementul care urmează să fie inserat este plasat în set în așa fel încât toate elementele să fie în ordine crescătoare;
- Dacă elementul care urmează să fie inserat există deja în set, acesta nu va mai fi inserat.
Cu alte cuvinte, setul este echivalentul mulțimii din matematică. Elementele se păstrează în ordine crescătoare și sunt unice.
Singura modalitate de a accesa elementele dintr-un set este prin iteratori.
Cum folosim în cod un set?
Pentru a folosi un set, trebuie să includem librăria <set> iar apoi să declarăm setul. Pentru a declara un set, folosim structura set<tipData> numeVar;.
În poza de mai sus am declarat un set care acceptă doar valori de tipul int. Pe liniile 9, 10 și 11 am inserat în set numerele 9, 4, respectiv -155. Din observațiile făcute la primul paragraf, rezultă că în set avem numerele stocate în această ordine: {-155, 4, 9}. Pe linia 12 încercăm să ștergem numărul 5 din set. Cum acesta nu există, nu se va șterge nimic. Pe linia 13 încercăm să inserăm numărul 4 în set. Cum acesta există deja în set, nu se va insera nimic, elementele setului rămânând {-155, 4, 9}. Pe linia 14 încercăm să ștergem elementul 4, deci în set vor rămâne elementele {-155, 9}.
Liniile 16 și 17 afișează elementele rămase în set folosind iteratori. Nu voi explica în detaliu în acest articol ce sunt iteratorii. Voi spune doar că aceștia sunt ca pozițiile elementelor dintr-un vector normal (1, 2, …, n), iar valoarea memorată de aceste poziții (v[1], v[2], …, v[n]) se găsește folosind *it.
Funcții specifice și complexități
| begin() | O(1) | Returnează un iterator la primul element al setului (vezi poza 2) |
| end() | O(1) | Returnează un iterator la elementul inexistent din dreapta ultimului element al setului (vezi poza 2) |
| insert(valoare) insert(iterator) | O(logn) | Inserează un element în set |
| erase(valoare) | O(logn) | Șterge un element după valoarea lui din set |
| erase(iterator) | O(1) | Șterge un element după un iterator din set |
| clear() | O(n) | Șterge toate elementele din set |
| empty() | O(1) | Returnează true dacă setul nu conține elemente, altfel returnează false |
| size() | O(1) | Returnează numărul de elemente din set |
Informații suplimentare
- Oriunde am declara setul, acesta este inițial vid;
- Elementele acestui container sunt alocate dinamic. Ce înseamnă acest lucru? Să comparăm un vector(array) cu un set.
La declararea unui vector (int v[100]), se alocă automat 100 de spații din memorie pentru a putea fi folosite de acest vector. Este important de menționat că aceste spații de memorie sunt întotdeauna puse una după alta. Atunci când declarăm un set, se alocă spațiu pentru unele funcții precum size().
Atunci când inserăm un element în set, se alocă spațiu dinamic pentru acest element. Acesta poate fi plasat oriunde în memorie. Dar dacă memoria este aleasă aleatoriu pentru elemente, cum păstrăm ordinea elementelor? Aici intervin în discuție iteratorii. Fiecare element din set are câte un iterator care păstrează informații precum: adresa de memorie a elementului precedent, adresa de memorie a elementului următor și valoarea acestui element.
- Folosind observațiile făcute la punctul anterior și ideea că fiecare element este adăugat în set în așa fel încât acesta să rămână ordonat, putem deduce faptul că este imposibil să accesăm, de exemplu, al treilea element, printr-o sintaxă de genul v[3] (v[2]), ci doar cu iteratori.
- Putem specifica o funcție de comparare între elemente, astfel încât un element să fie inserat după un nou criteriu de ordonare.
Această funcție este specificată la declararea setului. Există deja 2 funcții predefinite, acestea sunt less<tipData>() și greater<tipData>().
- Este posibil să știți de la vectori(arrays) că aceștia se transmit automat prin adresă ca parametrii unor funcții, lucru care împiedică copierea tuturor elementelor și utilizarea memoriei (și timpului) degeaba. Acest lucru nu se întâmplă și cu containerele STL. Transmiterea unui set, de exemplu, ca parametru într-o funcție va determina copierea acestuia în întregime. Încercați pe cât posibil să evitați acest lucru folosind transmiterea prin adresă, cum am făcut și în poza a treia.
Concluzie
Sper că acest articol v-a fost de ajutor. Dacă sesizați greșeli de orice fel în acest articol sau aveți întrebări, scrieți în secțiunea de comentarii.
Mult succes!