Quand doit-on utiliser std::set et quand…

std::set et std::unordered_set sont utilisés pour stocker des éléments uniques. Le choix entre eux dépend des priorités : ordonnancement ou performance d'accès/insertion/suppression.

std::set est basé sur un arbre binaire de recherche équilibré (généralement un arbre rouge-noir).

Caractéristiques de std::set :

Les éléments sont stockés dans un ordre trié.
L'insertion, la suppression et la recherche d'éléments prennent en moyenne O(log N), où N est le nombre d'éléments.
Convient lorsque l'ordre des éléments est important ou lorsque l'on souhaite obtenir des éléments dans un intervalle spécifique.

std::unordered_set est basé sur une table de hachage.

Caractéristiques de std::unordered_set :

Les éléments ne sont pas stockés dans un ordre trié.
L'insertion, la suppression et la recherche d'éléments prennent en moyenne O(1), mais dans le pire cas (avec beaucoup de collisions de la fonction de hachage) peuvent atteindre O(N).
Nécessite que le type d'élément ait une fonction de hachage (std::hash) et un opérateur de comparaison d'égalité (operator==).
Convient lorsque l'on souhaite des opérations d'insertion, de suppression et de recherche très rapides, sans importance de l'ordre des éléments.

Tableau récapitulatif :

Critère	`std::set`	`std::unordered_set`
Structure interne	Arbre équilibré	Table de hachage
Ordre des éléments	Trié	Non trié
Temps de recherche/insertion/suppression (moyenne)	O(log N)	O(1)
Temps de recherche/insertion/suppression (pire cas)	O(log N)	O(N)
Exigences du type	Opérateur `<`	`std::hash`, `operator==`

Exemple d'utilisation de std::set :

#include <iostream>
#include <set>

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

    // Les éléments seront affichés dans l'ordre : 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Exemple d'utilisation de std::unordered_set :

#include <iostream>
#include <unordered_set>

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

    // L'ordre d'affichage peut varier
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Quand doit-on utiliser std::set et quand std::unordered_set en C++?