C++ STL : std::set

De Wiki de Calcul Québec
Aller à : Navigation, rechercher
Autres langues :anglais 100% • ‎français 100%

C++ STL : maintenir une liste ordonnée avec std::set

La classe std::set<T> de la STL est un conteneur tout indiqué lorsqu'il faut maintenir une collection ordonnée d'éléments où les insertions et suppressions sont fréquentes. Dans ce contexte, le « set » est beaucoup plus efficace que les conteneurs mieux connus std::vector<T> et std::list<T>. Par exemple, avec un « vector » ou « list » ordonné, l'ajout d'un élément au bon rang est une opération d'ordre N. Le « set » fait le travail en O(log(N)) (sa structure interne est un arbre binaire).

Dans le petit programme ci-dessous, on bâtit une liste de noms en ordre alphabétique. Remarquez que c'est l'opérateur « < » qui détermine le classement des éléments. Si les items stockés sont les instances d'une classe, l'opérateur « < » doit obligatoirement être surchargé pour permettre la comparaison.

Fichier : exemple_set.cpp
#include <set>
#include <string>
#include <iostream>
 
using namespace std;
 
int main()
{
    set<string> noms;
 
    noms.insert("Zébulon");
    noms.insert("Blaise");
    noms.insert("Moe");
    noms.insert("Ada");
 
    for (set<string>::const_iterator i = noms.begin(); i != noms.end(); ++i)
    {
        cout << *i << endl;
    }
}


En sortie, on obtient ceci :

Ada
Blaise
Moe
Zébulon

Une autre particularité du « set » est qu'il permet de repérer un élément très rapidement en O(log(N)).

if (noms.count("Ronald") == 0)
{
    cout << "Ronald est absent !" << endl;
}
Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Ressources de Calcul Québec
Outils
Partager