C++ STL: std::set

De Wiki de Calcul Québec
Aller à : Navigation, rechercher
Cette page est une traduction de la page C++ STL : std::set et la traduction est complétée à 100 % et à jour.

Autres langues :anglais 100% • ‎français 100%

C++ STL: Storing an ordered list with std::set

The STL std::set class is a container designed for storing an ordered collection of elements where insertions and deletions are frequent. In this context, the set class is much more efficient than the better known std::vector and std::list classes. For example, with an ordered vector or list, adding an element in the right position is an O(N) operation; the set class in contrast does this with O(log(N)) complexity because its internal structure is a binary tree.

In the small program below, we assemble a list of names in alphabetical order. Note that the operator "<" determines the ordering of the set elements. If the items stored are instances of a class, then the "<" operator must be overloaded in order to permit this comparison.

File : set_example.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;
    }
}


As output, we obtain:

Ada
Blaise
Moe
Zébulon

Another particularity of the set class is that it permits rapid O(log(N)) searching for an element.

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

Variantes
Actions
Navigation
Ressources de Calcul Québec
Outils
Partager