IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
logo
Sommaire > La STL
        Qu'est-ce que la STL ?
        Qu'est-ce qu'un conteneur ?
        Qu'est-ce qu'un itérateur ?
        Comment créer et utiliser un tableau avec std::vector ?
        Dois-je effacer ce que j'ai stocké dans un vecteur ?
        Quel conteneur choisir pour stocker mes objets ?
        Comment supprimer correctement des éléments d'un conteneur ?
        Comment utiliser correctement les conteneurs standards avec du code C ?
        Qu'est-ce qu'un foncteur ?
        Qu'est-ce qu'un prédicat ?
        A quoi servent les fonctions bind1st et bind2nd ?
        [Exemple] Comment trier une séquence selon un critère personnalisé ?
        [Exemple] Comment détruire les pointeurs d'un conteneur ?
        Pourquoi ne puis-je pas trier une liste avec std::sort ?
        Comment fonctionnent les algorithmes de la STL ?



Qu'est-ce que la STL ?
Mise à jour le 19/10/2004[haut]
auteurs : LFE, Luc Hermitte, Aurélien Regat-Barrel
Le C++ possède une bibliothèque standard (on parle aussi de SL pour Standard Library) qui est composée, entre autre, d'une bibliothèque de flux, de la bibliothèque standard du C, de la gestion des exceptions, ..., et de la STL (Standard Template Library : bibliothèque de modèles standard). En fait, STL est une appellation historique communément acceptée et comprise. Dans la norme on ne parle que de SL.
Comme son nom l'indique cette bibliothèque utilise fortement les templates C++ et le concept de généricité. Elle définit ainsi de nombreux modèles de classes et de fonctions génériques parmi lesquelles les conteneurs (tableau, liste, pile, ensemble, ...) et les algorithmes (copie, tri, recherche, ...) les plus courants. Une particularité importante est son approche orientée itérateurs, ce qui permet par exemple d'utiliser ses algorithmes sur d'autres conteneurs que ceux qu'elle fournit.
L'un des avantages de la STL par rapport aux autres bibliothèques remplissant (plus ou moins) le même rôle est qu'elle est standard, et donc théoriquement portable (cependant les limites de certains compilateurs compliquent la chose). Un autre avantage important est son polymorphisme paramétrique qui assure un typage fort sans exigence syntaxique à l'utilisation, c'est-à-dire par exemple que l'on peut très simplement créer un tableau de ce que l'on veut sans devoir downcaster depuis un horrible type commun tel que void *.
Utiliser la STL permet donc d'augmenter de manière significative sa productivité en C++ en écrivant du code fiable, performant et portable.


Qu'est-ce qu'un conteneur ?
Mise à jour le 19/10/2004[haut]
auteurs : LFE, Aurélien Regat-Barrel, Luc Hermitte
Un conteneur (container) est, comme son nom l'indique, un objet qui contient d'autres objets. Il fournit un moyen de gérer les objets contenus (au minimum ajout / suppression, parfois insertion, tri, recherche, ...) ainsi qu'un accès à ces objets qui dans le cas de la STL consiste très souvent en un itérateur. Les itérateurs permettent de parcourir une collection d'objets sans avoir à se préoccuper de la manière dont ils sont stockés. Ceci permet aussi d'avoir une interface de manipulation commune, et c'est ainsi que la STL fournit des algorithmes génériques qui s'appliquent à la majorité de ses conteneurs (tri, recherche, ...).
Parmi les conteneurs disponibles dans la STL on trouve les tableaux (vector), les listes (list), les ensembles (set), les piles (stack), et beaucoup d'autres.


Qu'est-ce qu'un itérateur ?
Créé le 20/04/2003[haut]
auteur : LFE
Les itérateurs (iterator) sont une généralisation des pointeurs : ce sont des objets qui pointent sur d'autres objets. Comme son nom l'indique, les itérateurs sont utilisés pour parcourir une série d'objets de telle façon que si on incrémente l'itérateur, il désignera l'objet suivant de la série.


Comment créer et utiliser un tableau avec std::vector ?
Créé le 22/11/2004[haut]
auteur : Aurélien Regat-Barrel
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using std::cout;

int main()
{
    // créer un tableau d'entiers vide
    std::vector<int> v;
    
    // ajouter l'entier 10 à la fin
    v.push_back( 10 );

    // afficher le premier élément (10)
    cout << v.front() << '\n';

    // afficher le dernier élément (10)
    cout << v.back() << '\n';

    // enlever le dernier élément
    v.pop_back(); // supprime '10'

    // le tableau est vide
    if ( v.empty() )
    {
        cout << "Tout est normal : tableau vide\n";
    }

    // redimensionner le tableau
    // resize() initialise tous les nouveaux entiers à 0
    v.resize( 10 );
    
    // quelle est sa nouvelle taille ?
    cout << v.size() << '\n'; // affiche 10

    // sa taille est de 10 : on peut accéder directement aux
    // 10 premiers éléments
    v[ 9 ] = 5;

    // intitialiser tous les éléments à 100
    std::fill( v.begin(), v.end(), 100 );

    // vider le tableau
    v.clear(); // size() == 0

    // on va insérer 50 éléments
    // réserver (allouer) de la place pour au moins 50 éléments
    v.reserve( 50 );

    // véridier que la taille n'a pas bougé (vide)
    cout << v.size() << '\n';

    // capacité du tableau = nombre d'éléments qu'il peut stocker
    // sans devoir réallouer (modifié grâce à reserve())
    cout << v.capacity() << '\n'; // au moins 50, sûrement plus

    for ( int i = 0; i < 50; ++i )
    {
        // grâce à reserve() on économise de multiples réallocations
        // du fait que le tableau grossit au fur et à mesure
        v.push_back( i );
    }

    // afficher la nouvelle taille
    cout << v.size() << '\n'; // affiche 50

    // rechercher l'élément le plus grand (doit être 49)
    cout << *std::max_element( v.begin(), v.end() ) << '\n';

    // tronquer le tableau à 5 éléments
    v.resize( 5 );

    // les trier par ordre croissant
    std::sort( v.begin(), v.end() );

    // parcourir le tableau
    for ( size_t i = 0, size = v.size(); i < size; ++i )
    {
        // attention : utilisation de l'opérateur []
        // les accès ne sont pas vérifiés, on peut déborder !
        cout << v[ i ] << '\t';        
    }
    cout << '\n';

    // utilisation de at() : les accès sont vérifiés
    try
    {
        v.at( v.size() ) = 10; // accès en dehors des limites !
    }
    catch ( const std::out_of_range & )
    {
        cout << "at() a levé une exception std::out_of_range\n";
    }

    // parcours avec un itérateur en inverse
    for ( std::vector<int>::reverse_iterator i = v.rbegin();
          i != v.rend();
          ++i )
    {
        cout << *i << '\t';
    }
    cout << '\n';

    // on crée un tableau v2 de taille 10
    std::vector<int> v2( 10 );
    v2.at( 9 ) = 5; // correct, le tableau est de taille 10

    // on crée un tableau v3 de 10 éléments initialisés à 20
    std::vector<int> v3( 10, 20 );

    // faire la somme de tous les éléments de v3
    // on doit obtenir 200 (10 * 20)
    cout << std::accumulate( v3.begin(), v3.end(), 0 ) << '\n';

    // on recopie v3 dans v
    v = v3;

    // on vérifie la recopie
    if ( std::equal( v.begin(), v.end(), v3.begin() ) )
    {
        cout << "v est bien une copie conforme de v3\n";
    }
}

Dois-je effacer ce que j'ai stocké dans un vecteur ?
Créé le 09/10/2003[haut]
auteur : LFE
La réponse dépend de la nature de ce qui est stocké dans un vecteur.
S'il s'agit d'un objet, il n'est pas utile de le détruire, il le sera lorsqu'il est retiré du vecteur, ou lorsque le vecteur est détruit.
Par contre, s'il s'agit d'un pointeur sur un objet, il faut le détruire car un pointeur n'est pas un objet. Si cette destruction n'est pas faite, le programme présentera une fuite de mémoire.


Quel conteneur choisir pour stocker mes objets ?
Créé le 17/10/2005[haut]
auteur : Laurent Gomila
La panoplie de conteneurs proposée par la STL est conséquente : conteneurs ordonnés, associatifs, listes chaînées, ...
Le choix de la bonne structure dépend principalement des opérations que l'on va effectuer sur nos données : suppression, ajout, recherche, ...
Voici un schéma récapitulatif qui vous aidera à y voir plus clair :

Pour stocker des chaînes de caractères, std::string sera le conteneur le plus approprié. Il fournit des fonctions de recherche, de découpage, et des opérateurs surchargés pour une manipulation plus intuitive (voir Y a-t-il un type chaîne de caractères en C++ ?). std::string n'étant qu'un typedef sur std::basic_string<char>, pour manipuler d'autres types de caractères (unicode par exemple, ou ne tenant pas compte de la casse) il suffit d'utiliser le type approprié (voir Comment manipuler des chaînes de caractères Unicode ? et Comment manipuler des chaînes de caractères ne tenant pas compte de la casse ?).

A noter qu'il existe également une classe pour manipuler les champs de bits : std::bitset.

On peut aussi trouver dans certaines versions de la STL d'autres conteneurs, non standards mais bien connus : tables de hachage, listes simplements chaînées, etc. Leur utilisation est en général similaire à celle des autres conteneurs standards, mais pensez tout de même à bien vous documenter avant de les utiliser !


Comment supprimer correctement des éléments d'un conteneur ?
Mise à jour le 17/03/2008[haut]
auteur : Laurent Gomila
Effacer des éléments d'un conteneur est une tâche fréquente, mais souvent mal réalisée.

L'approche la plus naïve est de parcourir le conteneur à l'aide d'une boucle, et de supprimer (via la fonction membre erase) les éléments concernés. Mais attention, il faut veiller à bien manipuler l'itérateur afin de ne pas oublier d'éléments ou de pointer en dehors du conteneur.
Le méthode correcte est la suivante :

#include <vector>

std::vector<int> s;
for (std::vector<int>::iterator it = s.begin(); it != s.end(); )
{
    if (*it == 5)
        it = s.erase(it);
    else
        ++it;
}
A noter que cette méthode ne fonctionne pas avec les conteneurs associatifs (set, map, multiset, multimap) : leur fonction erase ne renvoie rien.

Il existe cependant des fonctions plus appropriées pour chaque conteneur.
Pour vector et string, on utilise ce qu'on appelle l'idiome erase-remove : on appelle std::remove (ou std::remove_if qui va prendre en paramètre un prédicat plutôt qu'une valeur -- voir Qu'est-ce qu'un prédicat ?) qui va déplacer les éléments à supprimer à la fin du conteneur, puis la fonction membre erase qui va les supprimer définitivement.

#include <string>
#include <vector>
#include <algorithm>

std::string s = "blah blah";
s.erase(std::remove(s.begin(), s.end(), 'h'), s.end());

std::vector v;
v.erase(std::remove_if(v.begin(), v.end(), std::bind2nd(std::greater<int>(), 3)), v.end());
Pour list, on utilise plus simplement la fonction membre remove (ou remove_if) qui contrairement à std::remove va bien supprimer les éléments.

std::list<int> l;
l.remove(5);
l.remove_if(std::bind2nd(std::greater<int>(), 3));
Pour les [multi]set et les [multi]map il existe la fonction membre erase, qui remplit exactement le même rôle que list::remove (attention aux noms, cela peut facilement porter à confusion). A noter que pour les [multi]map, erase prend en paramètre la clé à effacer, non la valeur.

#include <map>
#include <string>

std::map<std::string, int> m;
m.erase("toto");

Comment utiliser correctement les conteneurs standards avec du code C ?
Créé le 17/10/2005[haut]
auteur : Laurent Gomila
L'utilisation de code C dans un projet C++ est parfois inévitable, si l'on doit manipuler des bibliothèques écrites en C ou encore des fonctions codées dans un mauvais style. Il convient dans ce cas de prendre quelques précautions si l'on manipule des tableaux.

- Utilisez std::vector si vous devez passer un tableau à une fonction C, car seul ce conteneur garantit la contiguïté des données en mémoire.

void Fonction_C(const int* Tableau, unsigned int Taille);

std::vector<int> v;
Fonction_C(&v[0], v.size());
- Si vous devez alimenter un conteneur avec les données d'un tableau C, la STL fournit tout ce qu'il faut pour le faire proprement.

int* Fonction_C(int* Taille); // Renvoie un tableau et sa taille

int Taille = 0;
int* Tableau = Fonction_C(&Taille);

// Méthode 1 : utilisation du constructeur prenant en paramètre une paire d'itérateurs
std::set<int> s(Tableau, Tableau + Taille);

// Méthode 2 : utilisation de la fonction membre assign
std::list<int> l;
l.assign(Tableau, Tableau + Taille);

// Méthode 3 : utilisation de std::copy
std::vector<int> v;
std::copy(Tableau, Tableau + Taille, std::back_inserter(v));
- Pour les chaînes de caractères, std::string permet d'obtenir une chaîne C (caractères contigüs et '\0' final) via sa fonction membre c_str(). Attention cependant : la chaîne renvoyée peut très bien être temporaire et ne pas survivre à l'appel, il ne faut donc jamais stocker le pointeur retourné pour l'utiliser ultérieurement.
Voir Comment convertir un char* en un string ? et Comment convertir une string en char* ?.


Qu'est-ce qu'un foncteur ?
Mise à jour le 18/04/2005[haut]
auteur : Laurent Gomila
Toute classe surchargeant l'opérateur d'appel de fonction operator() est qualifiée de classe foncteur (functor class). Les objets instanciés d'une telle classe sont appelés objets fonctionnels (function objects) ou foncteurs (functors). La STL utilise beaucoup ce concept pour personnaliser le comportement de ses classes/fonctions.
Notez qu'on peut tout à fait utiliser des pointeurs sur fonction au lieu de foncteurs (il suffit de pouvoir appliquer l'opérateur () à l'objet passé en paramètre), mais on préfèrera les foncteurs car ils offrent plus de performances et de flexibilité. En effet operator() peut être entièrement inliné, et on peut passer des paramètres au foncteur via son constructeur pour plus de souplesse.
Voici un exemple typique de foncteurs tiré de la question [Exemple] Comment trier une séquence selon un critère personnalisé ?:
struct A 
{ 
    int Number; 
    std::string String; 
}; 
   
// Définition du foncteur servant à trier nos objets selon le nombre 
struct SortByNumber 
{ 
    bool operator ()( const A & a1, const A & a2 ) const 
    { 
        return a1.Number < a2.Number; 
    } 
}; 

// Définition du foncteur servant à trier nos objets selon la chaîne 
struct SortByString 
{ 
    bool operator ()( const A & a1, const A & a2 ) const 
    { 
        return a1.String < a2.String; 
    } 
};
Les foncteurs sont en particulier utilisés dans le cadre des prédicats (lire Qu'est-ce qu'un prédicat ?).


Qu'est-ce qu'un prédicat ?
Créé le 18/04/2005[haut]
auteur : Aurélien Regat-Barrel
Les prédicats (predicate) sont un type particulier de foncteurs qui renvoient un booléen ou quelque chose de convertible en booléen ce qui les rend utilisables dans des expressions logiques. Il existe un certain nombre de prédicats prédéfinis dans la STL, en particulier en ce qui concerne les opérateurs logiques et arithmétiques élémentaires :
int a = 2; 
    if ( std::greater<int>()( a, 1 ) ) 
    { 
        // ce test est vrai car a > 1 
    }
L'intérêt des prédicats est qu'ils peuvent être utilisés comme critère d'évaluation dans bon nombre d'algorithmes et conteneurs de la STL. Par exemple le conteneur std::set utilise par défaut le prédicat std::less afin d'organiser ses éléments de manière croissante. Il est facile de changer ce critère pour créer un std::set organisé de manière décroissante en spécifiant std::greater.
std::set< std::greater<int> > entiersTriesParOrdreDecroissant;
Mais les prédicats révèlent toute leur puissance lorsqu'ils sont utilisés conjointement avec les foncteurs réducteurs std::bind1st et std::bind2nd. Pour plus d'informations lire A quoi servent les fonctions bind1st et bind2nd ?.


A quoi servent les fonctions bind1st et bind2nd ?
Créé le 18/04/2005[haut]
auteur : Aurélien Regat-Barrel
std::bind1st et std::bind2nd sont un type particulier de foncteurs appelés foncteurs réducteurs. Ils permettent de facilement créer un prédicat unaire (c.a.d acceptant un seul paramètre) à partir d'un prédicat binaire (en acceptant 2 paramètres). Ceci est fait en figeant la valeur d'un des deux paramètres du prédicat binaire (c.a.d à le remplacer par une valeur fixe).
Soit l'exemple suivant où le prédicat plus_grand_que_10 est créé afin de compter grâce à std::count_if le nombre de valeurs supérieures à 10 dans un conteneur :
#include <iostream> 
#include <vector> 
#include <algorithm> 

// prédicat personnalisé permettant de tester si un 
// entier est strictement supérieur à 10 
struct plus_grand_que_10 
{ 
    bool operator ()( int N ) const 
    { 
        return N > 10; 
    } 
}; 

int main() 
{ 
    std::vector<int> v; 
    v.push_back( 0 ); 
    v.push_back( 5 ); 
    v.push_back( 10 ); 
    v.push_back( 15 ); 
    v.push_back( 20 ); 

    // compter le nombre de valeurs > 10 
    int n = std::count_if( 
        v.begin(), 
        v.end(), 
        plus_grand_que_10() ); // utilisation de notre prédicat 

    std::cout << n << '\n'; // affiche 2 
}
plus_grand_que_10 est un prédicat unaire obtenu en figeant le second argument de l'opérateur de comparaison supérieur à la valeur 10. On aurait pu aussi obtenir le même résultat en figeant le premier paramètre de l'opérateur inférieur cette fois-ci:
struct plus_grand_que_10 
{ 
    bool operator ()( int N ) const 
    { 
        return 10 < N; 
    } 
};
bind1st et bind2nd permettent de simplifier cette tâche fastidieuse de définition d'un prédicat binaire.
bind1st permet de figer le premier argument d'un prédicat binaire.
bind2nd permet de figer le second argument d'un prédicat binaire.
Ils s'utilisent de cette manière :
<bind>( <foncteur>, <valeur du paramètre à figer> );
L'exemple précédent peut alors être simplifié ainsi:
#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <functional> 

int main() 
{ 
    std::vector<int> v; 
    v.push_back( 0 ); 
    v.push_back( 5 ); 
    v.push_back( 10 ); 
    v.push_back( 15 ); 
    v.push_back( 20 ); 

    // compter le nombre de valeurs > 10 
    
    // méthode 1 : utilisation de bind2nd pour 
    // la création d'un prédicat x > 10 
    int n = std::count_if( 
        v.begin(), 
        v.end(), 
        std::bind2nd( std::greater<int>(), 10 ) ); 

    std::cout << n << '\n'; // affiche 2 

    // méthode 2 : utilisation de bind1st pour 
    // la création d'un prédicat 10 < x 
    n = std::count_if( 
        v.begin(), 
        v.end(), 
        std::bind1st( std::less<int>(), 10 ) );      

    std::cout << n << '\n'; // affiche 2 
}

[Exemple] Comment trier une séquence selon un critère personnalisé ?
Créé le 19/10/2004[haut]
auteur : Laurent Gomila
#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <string> 
#include <set> 

// Définition de notre structure à trier 
struct A 
{ 
   A(int i, std::string s) : Number(i), String(s) {} 

   int Number; 
   std::string String; 
}; 

// Surcharge de l'opérateur << pour afficher nos A 
std::ostream& operator <<(std::ostream& Stream, const A& a) 
{ 
   return Stream << a.Number << " " << a.String; 
} 
    
// Définition du foncteur servant à trier nos objets selon le nombre 
struct SortByNumber 
{ 
   bool operator ()(const A& a1, const A& a2) const 
   { 
      return a1.Number < a2.Number; 
   } 
}; 

// Définition du foncteur servant à trier nos objets selon la chaîne 
struct SortByString 
{ 
   bool operator ()(const A& a1, const A& a2) const 
   { 
      return a1.String < a2.String; 
   } 
}; 

int main() 
{ 
   // Création d'un tableau de A 
   std::vector<A> v; 
   v.push_back(A(1, "salut")); 
   v.push_back(A(5, "hello")); 
   v.push_back(A(2, "buenos dias")); 

   // Tri selon leur numéro 
   std::sort(v.begin(), v.end(), SortByNumber()); 
   std::copy(v.begin(), v.end(), std::ostream_iterator<A>(std::cout, "\n")); 
   std::cout << std::endl; 

   // Tri selon leur chaîne de caractères 
   std::sort(v.begin(), v.end(), SortByString()); 
   std::copy(v.begin(), v.end(), std::ostream_iterator<A>(std::cout, "\n")); 
   std::cout << std::endl; 

   // On peut également personnaliser le comportement des conteneurs triés 
   std::set<A, SortByString> s; 
   s.insert(A(1, "salut")); 
   s.insert(A(5, "hello")); 
   s.insert(A(2, "buenos dias")); 

   // Les éléments du conteneurs sont automatiquement triés selon leur chaîne grâce à notre foncteur
   std::copy(s.begin(), s.end(), std::ostream_iterator<A>(std::cout, "\n")); 

   return 0; 
}

[Exemple] Comment détruire les pointeurs d'un conteneur ?
Créé le 19/10/2004[haut]
auteur : Laurent Gomila

#include <list> 
#include <algorithm>

// Foncteur servant à libérer un pointeur - applicable à n'importe quel type
struct Delete 
{ 
   template <class T> void operator ()(T*& p) const 
   { 
      delete p;
      p = NULL;
   } 
}; 

int main() 
{ 
   // Création d'une liste de pointeurs 
   std::list<int*> l; 
   l.push_back(new int(5)); 
   l.push_back(new int(0)); 
   l.push_back(new int(1)); 
   l.push_back(new int(6)); 

   // Destruction de la liste : attention il faut bien libérer les pointeurs avant la liste ! 
   std::for_each(l.begin(), l.end(), Delete()); 

   return 0; 
}


Pourquoi ne puis-je pas trier une liste avec std::sort ?
Créé le 15/10/2009[haut]
auteur : Laurent Gomila
La fonction std::sort de la bibliothèque standard n'est compatible qu'avec les itérateurs à accès direct (ceux pour lesquels les opérateurs + et - sont définis), c'est-à-dire les itérateurs de std::vector, std::string, std::deque et les pointeurs bruts. En effet, l'accès direct est l'un des prérequis de l'algorithme de tri.

Pour trier un conteneur de type std::list, il faut utiliser la fonction membre std::list::sort :

std::list<int> mylist;
mylist.sort();
 
// Ou alors, avec un foncteur :
std::list<int> mylist;
mylist.sort(MonFoncteur());
Notez que cette version particulière sera plus lente que la version générique.

Pour les utilisateurs de Visual C++ 6, la STL de ce dernier ne définit pas la version prenant en paramètre un foncteur (à cause du manque de support des fonctions membres templates). Dans ce cas, une solution peut être de passer par un vecteur :

// Copie de la liste dans un nouveau vecteur
std::vector v(mylist.begin(), mylist.end());
 
// Tri du vecteur
std::sort(v.begin(), v.end(), MonFoncteur());
 
// Recopie du vecteur dans la liste originale
mylist.clear();
std::copy(v.begin(), v.end(), std::back_inserter(mylist));

Comment fonctionnent les algorithmes de la STL ?
Créé le 15/10/2009[haut]
auteur : r0d
Tout cela est expliqué dans le tutoriel de r0d : http://r0d.developpez.com/articles/algos-stl-fr/



Consultez les autres F.A.Q.


Valid XHTML 1.0 TransitionalValid CSS!

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2008 Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.