Mulțimi

O mulțime (set) este un container care poate stoca doar valori unice. În general, mulțimile sunt folosite pentru a crea colecții care nu trebuie să conțină duplicate.

Mulțimile sunt reprezentate de tipul std::set<>, care este definit în fișierul antet <set>. Crearea unei mulțimi goale:

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers;   // mulțime goală de numere întregi
}

Deoarece std::set este un șablon (template), între parantezele unghiulare se specifică tipul elementelor pe care le va conține mulțimea. În exemplul de mai sus, mulțimea va conține numere de tip int.

De asemenea, putem inițializa o mulțime cu altă mulțime sau cu o listă de inițializare:

std::set<int> numbers {1, 2, 3, 4, 5};

Dimensiunea mulțimii

Funcția size() returnează numărul de elemente din mulțime. De asemenea, cu ajutorul funcției empty() putem verifica dacă mulțimea este goală (returnează true dacă este goală):

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{1, 2, 3};
 
    std::cout << "Empty: " << std::boolalpha <<  numbers.empty() << std::endl;    // Empty: false
    std::cout << "Size: " << numbers.size() << std::endl;     // Size: 3
}

Parcurgerea mulțimii

Pentru a parcurge o mulțime putem folosi bucle for, de exemplu în stilul for-each:

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{1, 2, 3, 4, 5};
 
    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Adăugarea elementelor

Pentru adăugare se folosește funcția insert():

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{3, 4, 5};
 
    numbers.insert(1);
    numbers.insert(2);
    numbers.insert(2);
    numbers.insert(2);
    numbers.insert(6);
 
    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Mulțimea stochează doar valori unice, deci apeluri repetate la insert(2) nu vor adăuga de mai multe ori valoarea 2 — aceasta va apărea o singură dată.

Un alt aspect important este că mulțimea ordonează automat elementele. În mod implicit, acestea sunt aranjate în ordine crescătoare. Așadar, ieșirea în consolă va fi:

1	2	3	4	5	6

Ștergerea elementelor

Pentru a șterge un element din mulțime se folosește funcția erase():

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{2, 3, 4, 5};
 
    numbers.erase(1);
    numbers.erase(2);
    numbers.erase(3);
 
    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Ștergerea unui element inexistent (cum ar fi erase(1)) nu afectează în niciun fel mulțimea. Ieșirea în consolă:

4	5

Verificarea existenței unui element

Funcția count() verifică dacă o valoare se află în mulțime. Dacă există, returnează 1; dacă nu, returnează 0:

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{2, 3, 4, 5};
 
    std::cout << "10 is in set: " << numbers.count(10) << std::endl;    // 10 is in set: 0
    std::cout << "2 is in set: " << numbers.count(2) << std::endl;      // 2 is in set: 1
}

Începând cu standardul C++20, putem folosi și funcția contains() pentru a verifica prezența unui element. Aceasta returnează true dacă elementul există, și false în caz contrar:

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{2, 3, 4, 5};
 
    std::cout << "10 is in set: " << std::boolalpha << numbers.contains(10) << std::endl;    // 10 is in set: false
    std::cout << "2 is in set: " << std::boolalpha << numbers.contains(2) << std::endl;      // 2 is in set: true
}

Mulțime neordonată unordered_set

Mai sus am discutat despre std::set<>, care este o mulțime ordonată, adică își aranjează automat elementele (în mod implicit în ordine crescătoare). Totuși, în biblioteca standard C++ există și std::unordered_set<>, definit în <unordered_set>, care nu ordonează elementele.

Funcțional, este aproape identică cu set, dar elementele nu sunt aranjate. De exemplu:

#include <iostream>
#include <set>
 
int main()
{
    std::set<int> numbers{3, 2, 5, 4};
 
    numbers.insert(1);
    numbers.insert(6);
 
    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Ieșirea va fi ordonată:

1	2	3	4	5	6

Acum, folosind unordered_set:

#include <iostream>
#include <unordered_set>
 
int main()
{
    std::unordered_set<int> numbers{3, 2, 5, 4};
 
    numbers.insert(1);
    numbers.insert(6);
 
    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Ieșirea nu va fi ordonată și poate fi, de exemplu:

6	1	4	5	2	3

De reținut: funcția insert() în unordered_set poate introduce elementele într-o poziție aparent aleatoare, deoarece acestea sunt gestionate intern cu ajutorul unui tabel hash.