Wanneer moet je std::set en wanneer std::unordered_set gebruiken in C++?

std::set en std::unordered_set worden gebruikt voor het opslaan van unieke elementen. De keuze tussen hen hangt af van de prioriteiten: ordening of prestaties bij toegang/invoeging/verwijdering.

std::set is gebaseerd op een gebalanceerde binaire zoekboom (meestal een rode-zwart boom).

Kenmerken van std::set:

• Elementen worden in gesorteerde volgorde opgeslagen.
• Invoegen, verwijderen en zoeken van elementen duren gemiddeld O(log N), waarbij N het aantal elementen is.
• Geschikt wanneer de gesorteerde volgorde van belang is of wanneer elementen in een bepaald bereik moeten worden verkregen.

std::unordered_set is gebaseerd op een hash-tabel.

Kenmerken van std::unordered_set:

• Elementen worden niet in gesorteerde volgorde opgeslagen.
• Invoegen, verwijderen en zoeken van elementen duren gemiddeld O(1), maar in het slechtste geval (bij veel collisions in de hash-functie) kunnen ze O(N) bereiken.
• Vereist dat het elementtype een hash-functie (std::hash) en een gelijkheidsoperator (operator==) heeft.
• Geschikt wanneer maximale snelheid bij invoegen, verwijderen en zoeken vereist is, en de volgorde van de elementen niet van belang is.

Samenvattingstabel:

Criteria	std::set	std::unordered_set
Interne structuur	Gebalanceerde boom	Hash-tabel
Volgorde van elementen	Gesorteerd	Niet gesorteerd
Gemiddelde zoektijd/invoegtijd/verwijderingstijd	O(log N)	O(1)
Worst-case zoektijd/invoegtijd/verwijderingstijd	O(log N)	O(N)
Vereisten voor het type	Operator <	std::hash, operator==

Voorbeeld van gebruik van std::set:

#include <iostream>
#include <set>

int main() {
    std::set<int> gesorteerde_set;
    gesorteerde_set.insert(5);
    gesorteerde_set.insert(2);
    gesorteerde_set.insert(8);

    // De elementen worden in volgorde weergegeven: 2 5 8
    for (int waarde : gesorteerde_set) {
        std::cout << waarde << " ";
    }
    std::cout << std::endl;

    return 0;
}

Voorbeeld van gebruik van std::unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> ongeordende_set;
    ongeordende_set.insert(5);
    ongeordende_set.insert(2);
    ongeordende_set.insert(8);

    // De volgorde van output kan variëren
    for (int waarde : ongeordende_set) {
        std::cout << waarde << " ";
    }
    std::cout << std::endl;

    return 0;
}