La bibliothèque standard du C++

La déclaration d'un espace de nommage se fait par l'utilisation du mot clef namespace. Comme d'habitude avec le C++, il est possible de faire une déclaration de type « forward » :

namespace identificateur;

La syntaxe de définition d'un espace reprend celle d'un bloc du langage :

namespace identificateur
{
    // liste des entités regroupées dans l'espace de nommage
};

L'exemple suivant montre un espace de nommage regroupant deux classes et une constante :

namespace azedzed
{
    class A
    {
        // définition de la classe A
    };
    const double PI=3.1415927;
 
    class B
    {
        // définition de la classe B
    };
}

Tout d'abord, il faut savoir que chaque membre d'un même espace de nommage a une visibilité directe sur les identificateurs de tout l'espace. Dorénavant, nous ne nous intéresserons qu'à traiter les règles de visibilité depuis l'extérieur de l'espace.

II-A-3-b-i. Les noms qualifiés▲

EspNom1::ClasseA *obA;

EspNomExt::EspNomInt::ClasseB *obB;

II-A-3-b-ii. La clause using namespace▲

Il est parfois fastidieux d'utiliser des noms qualifiés qui peuvent s'avérer très longs. La clause using namespace permet d'obtenir la visibilité directe sur l'ensemble des entités déclarées dans un espace de nommage. La syntaxe en est la suivante : using namespace identificateur;

Il est important de noter que dans le cas où des espaces de nommage sont imbriqués, la clause using namespace ne donne qu'un seul niveau de visibilité. En outre, l'utiliser peut de nouveau faire surgir des problèmes de collision de noms, auquel cas, le compilateur vous en avertira.

En effet, considérez le cas suivant :

Programme 2.2 Exemple de collision entraînée par l'utilisation de la cause using namespace

Sélectionnez

namespace A
{
    class Erreur // ou tout autre nom courant
    {
    };
}
 
namespace B
{
    class Erreur // ou tout autre nom courant
    {
    };
}
 
class Erreur
{
};
 
int main(int,char**)
{
    Erreur e1; // Pas de probleme quoique ::Erreur e1 eut ete preferable
    A::Erreur e2; // Pas de probleme classe Erreur de l'espace A
    B::Erreur e3; // Pas de probleme classe Erreur de l'espace B
 
    using namespace A;
 
    Erreur e4; // Ambiguite entre ::Erreur et A::Erreur
 
    using namespace B;
 
    Erreur e5; // ambiguite entre ::Erreur, A::Erreur et B::Erreur
 
    return 0;
}

Autre cas vicieux. Considérez trois espaces de nommage avec les relations indiquées par la figure suivante :

Il existe un espace de nommage A, un espace imbriqué A::B et un espace B.

Considérez le fragment de code suivant :

 

Sélectionnez

using namespace A; // Ok, délivre la visibilité sur les éléments de A
using namespace B; // ??? est-ce A::B ou bien B?

Le résultat de la dernière est laissé à vérifier en exercice. Il était possible de lever l'ambiguïté en précisant, soit using namespace A::B soit using namespace ::B pour l'espace de nommage non imbriqué.

II-A-3-b-iii. La clause using identificateur▲

#include <iostream>
 
namespace BASE
{                        
    class ErreurBase
    {
        public:
        virtual void show(void)=0;
    };
}
 
namespace A
{
    class Erreur : public BASE::ErreurBase
    {
        public:
            virtual void show(void)
            {
                cout << " A :: Erreur " << endl;
            }
    };
}
 
class Erreur : public BASE::ErreurBase
{
    public:
        virtual void show(void)
        {
            cout << " :: Erreur " << endl;
        }
};
 
int main(int, char**)
{
    Erreur e1; // ::Erreur
    À::Erreur e2; // A::Erreur
 
    using A::Erreur;
    Erreur e3; // A::Erreur masque ::Erreur
 
    e1.show();
    e2.show();
    e3.show();
 
    return 0;
}

II-A-3-b-iv. Conclusion sur l'accès aux membres et alias d'espaces de nommage▲

namespace nomAlias = nomEspaceOriginel ;

namespace local = EspaceExterne::EspaceInterne::EspacePlusInterne ;

#include <iostream>
namespace BASE
{
    class ErreurBase
    {
        public:
            virtual void show(void)=0;
    };
}
 
namespace NomTropLong
{
    class Erreur : public BASE::ErreurBase
    {
        public:
            virtual void show(void)
            {
                cout << "NomTropLong :: Erreur " << endl;
            }
    };
 
    namespace EncorePlusLong
    {
        class Erreur : public BASE::ErreurBase
        {
            public:
            virtual void show(void)
            {
                cout << "NomTropLong :: EncorePlusLong :: Erreur " << endl;
            }
        };
    }
}
 
class Erreur : public BASE::ErreurBase
{
    public:
        virtual void show(void)
        {
            cout << " :: Erreur " << endl;
        }
};
 
int main(int, char**)
{
    namespace A = NomTropLong;
    namespace B = A::EncorePlusLong;
 
    // Etant declares a l'interieur de main les noms d'alias
    // sont locaux et donc non exportes !
 
    Erreur                                 e1; // ::Erreur
    NomTropLong::Erreur                 e2;
    NomTropLong::EncorePlusLong::Erreur e3;
    À::Erreur                             e4; // ni ambigue ni fastidieux !
    B::Erreur                             e5; // idem
 
    e1.show();
    e2.show();
    e3.show();
    e4.show();
    e5.show();
 
    return 0;
}

En plus des méthodes c_str et data, et comme l'on peut légitimement s'y attendre il est tout à fait possible d'accéder aux différents caractères composant une chaîne à l'aide de l'opérateur d'indexation [].

En outre, il existe la méthode at(int position) qui permet d'effectuer grosso modo la même opération que l'opérateur d'indexation. La principale différence tient à la gestion des dépassements de range.

En effet, l'opérateur [] renvoie une constante prédéfinie alors que at lance une exception de type range_error.

Il convient ici de bien faire la différence entre la longueur logique de la chaîne et sa capacité en caractères. La seconde est physique et rend compte de l'espace alloué dans le conteneur de la chaîne alors que la première témoigne du nombre de caractères réellement présents.

Pour établir un parallèle, en C la longueur logique serait renvoyée par strlen alors que la capacité serait le nombre de caractères fourni à malloc ou placé entre les crochets lors de l'allocation statique d'une chaîne

Tableau 2.1 méthodes agissant sur la taille des chaînes de caractères

La classe basic_string est équipée d'un opérateur d'affectation dont l'implémentation a tendance à varier en fonction du fournisseur. Il agit toujours par recopie du membre de droite vers le membre gauche, mais, dans certains cas, il ne modifie la capacité de la chaîne cible que lorsque cela s'avère nécessaire.

À mon avis, de nombreux implémenteurs ont codé cet opérateur en utilisant des compteurs de référence et des recopies tardives : seul un pointeur est recopié lors de l'affectation, la structure de données sous-jacente n'est recopiée que si l'une des deux chaînes est modifiée. Cette astuce assure des gains de performance non négligeables dans de nombreuses situations et est encouragée par, excusez du peu, Scott Meyers et Steve Coplien - ce qui est bon pour les dieux doit bien l'être pour nous autres, pauvres mortels !

La classe basic_string dispose de méthodes très intéressantes et d'ordre très général permettant d'ajouter des séquences dans une chaîne. Nous n'en donnons ici qu'une description assez sommaire.

Tableau 2.2 les méthodes générales d'ajout dans les séquences

Les vecteurs de la STL sont tout à fait semblables aux tableaux que l'on a l'habitude de manipuler en C++. Ils sont néanmoins encapsulés dans des classes pour leur fournir des capacités supplémentaires, en particulier, la croissance dynamique. Leurs principales caractéristiques sont les suivantes :

• accès indexé aux éléments en O(1) ;
• ajout ou suppression d'un élément à la fin du vecteur sans redimensionnement en O(1) ;
• ajout ou suppression d'un élément à la fin du vecteur avec redimensionnement en O(n) ;
• ajout ou suppression d'un élément au milieu du vecteur en O(n) où n est la taille du vecteur ;
• ajout ou suppression d'un élément à la fin du vecteur en O(1) amorti.

Il convient de mettre un bémol concernant l'ajout d'un élément à la fin d'un vecteur. En effet, les vecteurs sont à croissance dynamique. Autrement dit, si vous décidez d'ajouter un élément dans un vecteur déjà plein à l'aide de la méthode push_back (détaillée plus bas), celui-ci sera agrandi, ce qui nécessite trois opérations :

1. Allocation d'un nouveau vecteur ;
2. Recopie des éléments depuis l'ancien vecteur vers le nouveau ;
3. Suppression de l'ancien vecteur.

Or, ces opérations peuvent être coûteuses, au pire en O(n). Se pose également la question du choix de la future taille. Andrew Koenig nous explique que la technique la plus efficace consiste à utiliser un redimensionnement exponentiel i.e. à chaque réallocation, la taille du vecteur est multipliée par un facteur (1 + a) où a est un nombre strictement positif. Ainsi, plus le vecteur devient grand, plus il s'agrandira rapidement.

Cette stratégie a l'avantage de rendre les redimensionnements de moins en moins fréquents au détriment d'un encombrement parfois exagéré de la mémoire. Du fait de la fréquence faible des redimensionnements, on peut considérer que la complexité asymptotique (ou amortie) de l'opération d'ajout d'un élément en bout de tableau est en O(1).

Elles modélisent le type liste chaînée habituel. Contrairement aux vecteurs, elles ne possèdent pas d'opérateur d'indexation, mais permettent d'ajouter ou de supprimer un élément à n'importe quelle position en O(1).

Bien qu'il n'y ait jamais de place morte dans une liste, mais, du fait de la structure de chaîne, l'occupation en mémoire d'une liste est le plus souvent supérieure à celle d'un vecteur pour le même nombre d'éléments stockés.

Les DQ sont la séquence élémentaire la plus délicate à cerner, car Intermédiaire entre une liste et un vecteur.

• Elle est très efficace dès lors qu'il s'agit d'ajouter ou de retirer une valeur à l'une de ses extrémités.
• Elle possède un opérateur d'indexation de complexité o(log(n)) amortie.
• Les insertions en milieu de séquence sont plus rapides que sur un vecteur sans pour autant atteindre le niveau de performances des listes.

Tableau 3.2 Méthodes spécifiques à vector

En outre, il faut savoir que si vous créez un vecteur avec une dimension initiale supérieure à 0, le constructeur par défaut du type élément est appelé pour créer un premier élément et le tableau est ensuite rempli par des appels au constructeur de recopie.

Afin de bien comprendre les mécanismes de création d'objets, que ce soit par le constructeur par défaut ou par appel au constructeur de recopie, nous utilisons la classe suivante qui encapsule les entiers :

// Fichier d'entete Entier.hxx
#ifndef __Entier__
#define __Entier__
 
class Entier
{
    private:
        static unsigned NbEntiers_;
        static unsigned NbRecopies_;
 
        int         val_;
    public:
        explicit Entier(int valeur=0) : val_(valeur)
        {
            NbEntiers_++;
        }
        Entier (const Entier &a)
        {
            val_=a.val_;
            NbRecopies_++;
        }
 
        int val(void) const
        {
            return val_;
        }
 
        static int NbEntiers(void)
        {
            return NbEntiers_;
        }
 
    static int NbRecopies(void)
    {
        return NbRecopies_;
    }
};
 
class ostream;
 
ostream &operator<<(ostream &a,const Entier &b);
bool operator==(const Entier &a, const Entier &b);
bool operator<(const Entier &a, const Entier &b);
 
#endif
 
// fichier Entier.cpp
 
#include "Entier.hxx"
#include <iostream>
 
ostream &operator<<(ostream &a,const Entier &b)
{
    a << b.val();
    return a;
}
 
bool operator<(const Entier &a, const Entier &b)
{
    return a.val() < b.val();
}
 
bool operator==(const Entier &a, const Entier &b)
{
    return a.val() == b.val();
}
 
unsigned int Entier::NbEntiers_=0;
unsigned int Entier::NbRecopies_=0;

Le point intéressant réside dans l'utilisation des attributs de classe NbEntiers_ et NbRecopies_ comptant respectivement le nombre d'appels au constructeur « de création » et le nombre d'appels au constructeur de recopie. Nous pourrons donc suivre à la trace ces opérations.

En outre, cela nous permet de voir les prérequis nécessaires à l'utilisation d'une classe par la STL :

• constructeur par défaut ;
• constructeur par recopie. Ici, le constructeur par recopie généré automatiquement était suffisant, nous ne l'avons construit nous même que pour utiliser le comptage des appels
• opérateur d'affectation, ici celui fourni automatiquement par le compilateur ;
• opérateur de sortie sur flux ;
• opérateur de comparaisons.
  Les autres étant automatiquementconstruits par template.

operator int (void)
{
return val_;
}

Toutefois, il me paraît préférable de laisser le soin à l'utilisateur de réaliser les conversions de façon explicite lorsqu'il en a lui même besoin !

Il est important de noter que le redimensionnement du tableau - que ce soit par un appel direct à reserve où automatiquement lorsque l'on arrive en limite de capacité n'implique pas de création d'objets, mais uniquement de la réservation de mémoire. En outre, ces opérations n'affectent que la capacité et en aucun cas la taille.

En revanche, resize, en mode accroissement, conjugue réservation de mémoire et création d'objets comme en témoignent les augmentations de taille (size)

#include <vector>
#include <iostream>
#include "Entier.hxx&#8221;
 
// Permet d'afficher les caracs du vecteur
// et le nombre d'entiers
template <class T>
void affichage(const T &a)
{
    static int numeroLigne=1;
    cout << '(' << numeroLigne++ << ") Capacite " << a.capacity();
    cout << " Taille " << a.size();
    cout << " Nb entiers " << Entier::NbEntiers() << endl << flush;
}
 
int main(int, char**)
{
    typedef std::vector<Entier> VecInt;
    VecInt v1;                     // Creation d'un vecteur vide
    affichage(v1);                 // (1)
    v1.push_back(Entier(1));     // insertion d'un element
    affichage(v1);                 // (2)
    v1.reserve(100);             // la capacite est portee a 100
    affichage(v1);                 // (3)
    v1.resize(200);             // capacite et taille portees a 200
    affichage(v1);                 // (4)
 
    VecInt v2; // Nouveau vecteur vide
 
    for (int i=0;i<20;i++) // Remplissage avec redimensionnements
    {
        v2.push_back(Entier(i));
        affichage(v2); // (5 -> 24)
    }
 
    for (int i=0;i<20;i++) // Affichage par indexation (25)
        cout << v2[i] << " ";
    cout << endl;
 
    // Affichage avec parcours d'iterateur (26)
    VecInt::iterator courant=v2.begin();
    while (courant != v2.end())
    {
        cout << *courant << " ";
        ++ courant; // Je me souviens du cours de C++ avance
        // utiliser si possible l'operateur prefixe !
    }
    cout << endl;
 
    // Affichage avec iterateur de flux (27)
    copy(v2.begin(),
        v2.end(),
        ostream_iterator<Entier>(cout," "));
    cout << endl;
 
    return 0;
}

Le résultat d'exécution est le suivant :

Commentons une par une ces quelques lignes de sortie. Les commentaires du code font référence aux lignes de sortie.

1. Le tableau est vide, sa capacité et sa taille sont nulles : prévisible.
2. On ajoute un élément, la capacité et la taille passent à 1, et l'on a alloué un entier : toujours prévisible.
   Le nombre de recopies augmente d'une unité : ceci signifie que l'opération de recopie de l'ancien vecteur lors d'un redimensionnement se fait par appel à l'opérateur de construction par recopie.
3. La capacité passe à 100 alors que la taille ne bouge pas, c'est typique du fonctionnement de reserve. Le fait que le nombre de créations d'entier n'ait pas bougé atteste du fait que reserve se contente d'allouer de la mémoire sans créer un seul objet. Le nombre de recopies augmente d'une unité pour la raison évoquée au point précédent.
4. La capacité passe à 200 ainsi que la taille, c'est le rôle de resize : amener la taille à la valeur spécifiée en augmentant si nécessaire la capacité. En revanche, le point intéressant concerne le nombre d'entiers : un seul nouvel entier a été créé par le constructeur par défaut, les autres ont été générés par recopie comme l'atteste la brusque montée du nombre de recopies !

5. Les lignes 5 à 24 permettent de bien voir le mécanisme de redimensionnement à partir d'un tableau vide. Dans ce cas (gcc), le redimensionnement est double à chaque étape. Eussions-nous utilisé la Rogue Wave que la capacité serait passée de 0 à 256 avant d'être doublée à chaque étape :

   1. d'une part lors des redimensionnements (voir point 2) ;
   2. par chaque opération push_back : l'élément passé à push_back (par référence constante pour éviter une recopie de plus) est recopié à son emplacement dans le vecteur.

6. Finalement, nous procédons à l'affichage des valeurs contenues dans le vecteur par trois méthodes différentes :

   1. ligne 25 : accès avec l'opérateur d'indexation (méthode classique) ;
   2. ligne 26 : parcours avec itérateurs ;
   3. ligne 27 : utilisation d'un itérateur de flux ;
   4. vous remarquerez que nous obtenons trois fois de suite la même solution, ce qui est très rassurant !

Les opérations spécifiques sur les listes concernent essentiellement l'insertion et la suppression en tête de liste, le transfert d'éléments entre listes avec une méthode spécifique (splice), ainsi que le réordonnement de la collection.

Tableau 3.3 Opérations spéficiques à list

Suit un petit exemple montrant l'utilisation des éléments spécifiques au type list.

#include <list>
#include <iostream>
#include <algo.h>
 
#include "Entier.hxx"
#include "Genera.hxx"
 
// Predicat fonction
bool estPair(const Entier &a)
{
    return ((a.val() % 2) == 0);
}
// Predicat foncteur
class EstImpair
{
    public:
    bool operator()(const Entier &a)
    {
        return ((a.val() % 2) != 0);
    }
};
 
int main(int, char**)
{
    typedef std::list<Entier> ListEnt;
    typedef ListEnt::iterator ListEntIt;
 
    ListEnt l1;
    ostream_iterator<Entier> sortie(cout, " ");    
 
    cout << "Generation aleatoire d'une liste de 10 entiers" << endl;
    l1.resize(10);
    generate(l1.begin(), l1.end(), GenAlea());
 
    cout << "Affichage de l'ordre initial" << endl;
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
 
    cout << "Apres tri" << endl;
    l1.sort();
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
 
    cout << "Apres renversement" << endl;
 
    l1.reverse();
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
 
    cout << "Generation lineaire des 10 premiers entiers" << endl;
 
    generate(l1.begin(), l1.end(), GenLin());
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
 
    cout << "Obtention de deux iterateurs sur le 3 et sur le 8" << endl;
    cout << "Construction d'une seconde liste puis splice " << endl;
 
    // notez ici que nous sommes obliges d'utiliser Entier(3) pour chercher le 3
    // cette conversion aurait ete implicite si le constructeur d'entier
    // n'avait pas ete marque explicit
    // je prefere toutefois controler ce que fait mon programme et faire l'effort
    // de l'appel de constructeur moi meme
    ListEntIt gauche=find(l1.begin(),l1.end(),Entier(3));
    ListEntIt droite=find(l1.begin(),l1.end(),Entier(8));
 
    ListEnt l2;
    l2.splice(l2.begin(),l1,gauche,++droite);
 
    cout << "Liste initiale : ";
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
 
    cout << "Seconde liste : ";
    copy(l2.begin(),l2.end(),sortie);
    cout << endl;
 
    cout << "Creation d'une liste des elements pairs par suppression des impairs";
    cout << endl;
 
    l1.resize(10);
    generate(l1.begin(),l1.end(),GenLin());
    l1.remove_if(EstImpair());
 
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
    cout << "Creation d'une liste des elements impairs par suppression des pairs";
    cout << endl;
    l2.resize(10);
    generate(l2.begin(),l2.end(),GenLin());
    l2.remove_if(estPair);
    copy(l2.begin(),l2.end(),sortie);
    cout << endl;
 
    cout << "Apres Merge" << endl;                    
    l1.merge(l2);
    copy(l1.begin(),l1.end(),sortie);
    cout << endl;
 
    return 0;
}

Quelques commentaires s'imposent aussi bien sur le programme que sur son résultat.

• Tout d'abord, nous utilisons l'algorithme generate pour générer (on s'en doutait un peu -) des valeurs dans les listes.
  Les emplacements doivent déjà être réservés ! generate n'ajoutera pas d'éléments dans votre liste, mais écrase les valeurs déjà présentes. D'ailleurs, generate utilise une paire d'itérateurs pour spécifier les éléments à remplir.
  L'algorithme generate utilise un objet foncteur dont l'opérateur fonction (operator ()) ne doit pas prendre de paramètre et renvoyer un objet compatible avec le type présent dans la liste. Ici nous utilisons deux classes d'objets foncteurs : GenAlea et GenLin. Le programme suivant fournit leur code :

#ifndef __Genera_hxx__
#define __Genera_hxx__
 
#include "Entier.hxx"
 
class GenAlea
{
    private:
        static const unsigned long m=259200UL;
        static const unsigned long a=5141UL;
        static const unsigned long c=73141UL;
 
        unsigned long x;
 
    public:
        explicit GenAlea(unsigned long t=0) : x(t) {};
        Entier operator()(void)
    {
        x=(x*a+c)%m;
        return Entier(x);
    }
};
 
class GenLin
{
    private:
        int prochain;
 
    public:
        explicit GenLin(int leProchain=0) : prochain(leProchain) {};
        Entier operator()(void)
    {
        return Entier(prochain++);
    }
};
#endif

Les deux classes proposées sont les suivantes :

GenAlea est un générateur de nombres pseudo aléatoires simpliste

GenLin crée des entiers dans l'ordre croissant à partir de la valeur passée à son constructeur et par défaut égale à 0.

• Autre point notable, l'utilisation de splice. Ici, nous utilisons l'algorithme find qui permet de recherche une valeur parmi les éléments contenus dans un intervalle spécifié par une paire d'itérateurs.
  Nous désirons transférer les éléments de 3 à 8 vers une autre liste. Nous recherchons donc ces deux éléments avec find de manière à obtenir des itérateurs respectivement nommés gauche et droite. Or si nous avions passé la commande :

l2.splice(l2.begin(),l1,gauche,droite);

Nous n'aurions transféré que les éléments [3, prédécesseur de 8] vers l2, car le second itérateur est une borne non incluse.

Afin de transférer jusqu'à droite inclus, nous utilisons l'opérateur ++ sur l'itérateur droite, soit :

l2.splice(l2.begin(),l1,gauche,++droite);

• La méthode remove_if permet de supprimer des éléments d'une liste en fonction d'un critère passé sous forme de prédicat. Celui-ci peut prendre deux formes :

  • une fonction bool ;
  • un objet foncteur dont l'opérateur fonction (operator ()) renvoie bool

Notre exemple illustre ces deux possibilités en fournissant une fonction de test de parité et un foncteur qui teste l'inverse !

• Finalement, nous utilisons merge pour rassembler deux listes

Les opérations spécifiques aux DQ concernent l'insertion et la suppression en tête de conteneur. Opérations qui sont ici particulièrement optimisées ! On note également la présence d'un opérateur d'accès indexé relativement performant.

Tableau 3.4 Opérations spécifiques au type deque

L'utilisation du type deque ne présente aucune difficulté, un exemple ne s'impose donc pas. En fait, vous utiliserez deque lorsque vous avez besoin à la fois de l'indexation et de l'accès aux éléments extrêmes d'une collection.

À l'instar des autres conteneurs de la STL, les méthodes size et empty renvoient respectivement un entier indiquant le nombre d'éléments présents dans le conteneur et un booléen signalant si le conteneur est vide.

En outre, aucun de ces trois types ne supporte les itérateurs. Aussi, les algorithmes généraux (que nous verrons dans un prochain chapitres) seront ils généralement inutilisables sur ce genre de conteneurs ce qui n'est pas sans poser certains problèmes de compatibilité.

Les types files et piles ne posant pas de problèmes particuliers, nous ne donnerons pas ici d'exemple particulier. L'exemple final sur les graphes donnera deux utilisations sur les parcours de graphe en profondeur d'abord ou en largeur d'abord.

Les files sont associées au modèle d'accès premier arrivé, premier traité, à l'image, par exemple, d'une file d'attente à un guichet. Les opérations offertes sont très limitées, car elles permettent d'ajouter un élément à la fin, consulter l'élément présent à chaque bout, retirer l'élément en tête de file.

Deux particularités notables sur les files :

• elles ne possèdent pas d'autre constructeur que celui par défaut (sans argument) ;
• afin de fonctionner correctement, les opérations == et
  sont requises sur letype T des éléments que l'on souhaite loger dans la file.

Les files effectuant des accès fréquents aux deux extrémités de la structure de donnée sous-jacent ne doivent pas être construites sur un vecteur (le retrait d'un élément en tête serait trop lent), mais plutôt sur une liste ou une DQ. Toutefois, il est conseillé d'utiliser une DQ qui offre de meilleurs temps de réponse pour les opérations d'ajout et de suppression aux deux extrémités. D'ailleurs, si votre compilateur accepte les template avec valeur par défaut, la construction se fait automatiquement sur une DQ.

La déclaration d'une file obéit au prototype suivant :

template <class T, class Container = deque<T> >
class queue
{ // etc

L'on y retrouve le type T des éléments stockés dans la file ainsi que le type de la structure de données de base sous-jacente initialisée par défaut à une DQ sur T. Les opérations suivantes sont disponibles sur une file :

Tableau 3.5 Opérations disponibles sur une file

Les piles sont associées au modèle d'accès aux données dernier arrivé premier sorti. En d'autres termes, le premier élément à être entré dans la pile sera le premier utilisé. Le modèle tire son nom de l'analogie avec une pile d'assiettes où l'on accède toujours au même élément : celui du dessus que ce soit par empilage ou dépilage. Il est possible de baser une pile sur tous les types de structures élémentaires.

On notera toutefois qu'utiliser une liste s'avère peu judicieux, car l'on accède qu'à l'élément final. Aussi on se limitera aux vecteurs et aux DQ. Les « gourous » de la STL assurent qu'utiliser une DQ se révèle très légèrement plus performant (un fait que je n'ai pas pu établir personnellement, les différences de temps étant trop faibles pour être significatives) et, d'ailleurs, si votre compilateur accepte les template avec valeur par défaut, une DQ sera utilisée par défaut.

À l'instar des files, les piles n'ont qu'un constructeur par défaut, il n'est pas possible d'obtenir d'itérateurs sur les piles, et le type des éléments que vous souhaitez loger dans une pile doit supporter les opérations == et <=.

La déclaration d'une pile obéit au prototype suivant :

template <class T, class Container = deque<T> >
class stack
{ // etc

L'on y retrouve le type T des éléments stockés dans la pile ainsi que le type de la structure de données de base sous-jacente initialisée par défaut à une DQ sur T. Les opérations disponibles sur une pile sont les suivantes :

Tableau 3.6 Opérations disponibles sur les piles

Le petit fragment de code suivant montre la différence de gestion des piles et des files.

#include <deque>
#include <queue> // pour les files
#include <stack> // pour les piles
#include <iostream>
#include <algo.h>
 
#include "Entier.hxx"
#include "Genera.hxx"
 
int main(int, char**)
{
    const int TAILLE=10;
    Entier i;
    GenAlea g;
 
    stack<Entier,deque<Entier> > pile;
    queue<Entier,deque<Entier> > file;
 
    cout << "Ordre d'entree : ";
    for (int j=0;j<TAILLE;j++)
    {
        i=g();
        cout << i << " ";
        pile.push(i);
        file.push(i);
    }
 
    cout << endl;
    cout << "Ordre de sortie pour la pile : ";
    while (!pile.empty())
    {
        cout << pile.top() << " ";
        pile.pop();
    }                    
    cout << endl;
 
    cout << "Ordre de sortie pour la file : ";
    while (!file.empty())
    {
        cout << file.front() << " ";
        file.pop();
    }
 
    cout << endl;
 
    return 0;
}

Ce programme montre bien que les éléments de la file ressortent dans leur ordre d'arrivée alors qu'ils en ressortent dans l'ordre inverse pour une pile. La section sur les graphes montrera une autre application des piles et des files.

Les files à priorité (ou tas) sont des collections ordonnées d'éléments qui ne donnent accès qu'à un seul élément : le plus prioritaire. La priorité est déterminée en fonction d'un prédicat passé au constructeur de la structure.

Les utilisations des files à priorité sont multiples. Citons par exemple l'ordonnancement des processus dans un système d'exploitation. L'algorithme du tri en tas peut être divisé en deux phases : construction d'un tas puis extraction du meilleur élément tant que le tas n'est pas vide.

Les files à priorité doivent être basées sur une structure indexée - ce qui élimine les listes d'entrée de jeu ! Si l'occupation mémoire n'est pas votre souci majeur, vous aurez intérêt à choisir une DQ qui autorise des opérations plus rapides. En outre, si votre compilateur autorise les valeurs par défaut pour les templates, votre file à priorité sera construite par défaut sur une DQ.

Examinons d'un peu plus près la déclaration du type priority_queue :

template <class T,
class Container = vector<T>,
class Compare = less<Container::value_type> >
class priority_queue
{ // etc

En plus du type des éléments (T) et du type du conteneur de base (Container dont la valeur par défaut est une DQ basée sur T) on remarque la présence d'un troisième paramètre template nommé Compare : le type du prédicat de comparaison.

Celui-ci prend comme valeur par défaut la comparaison inférieure ce qui fait de la priority_queue par défaut un tas min !

Contrairement aux types file et pile, la classe priority_queue dispose de deux constructeurs :

• un constructeur par défaut de prototype :

explicit priority_queue (const Compare& x = Compare());

Vous noterez que les concepteurs de la STL ont pris soin de déclarer ce constructeur à un paramètre explicit afin d'éviter d'éventuelles conversions implicites erronées depuis un prédicat vers un tas !

Le paramètre par défaut de ce constructeur est un objet directement instancié à partir de la classe comparateur. Certains compilateurs ne supportent pas cette opération et exigent que vous construisiez vous même cet objet.

• Un constructeur permettant de construire un tas à partir d'une séquence d'éléments en provenance d'un conteneur et délimitée par une paire d'itérateurs :

template <class InputIterator>
priority_queue (InputIterator first,
InputIterator last,
const Compare& x = Compare());

Les opérations disponibles sur les files à priorité sont les suivantes :

Tableau 3.7 Opérations disponibles sur une file à priorité

Pour finir, nous noterons l'existence de l'algorithme générique make_heap dont le but est de fournir une structure de tas à une structure de données indexée (essentiellement vecteur ou DQ). Les structures obtenues se manipulent à l'aide de deux fonctions spécialisées nommées push_heap et pop_heap. Bien que ces fonctionnalités puissent paraître attractives, il faut les utiliser avec parcimonie, car leurs performances sont nettement inférieures à celles du type priority_queue.

Concluons l'étude des files à priorité par un petit exemple : nous souhaitons créer un petit programme qui génère argv[1] nombres pseudo aléatoires triés dans l'ordre décroissant. Une fois de plus, nous utilisons les classes Entier et GenAlea.

Le déroulement du programme est très simple.

1. Déclaration d'un type file à priorité sur le type Entier, basé sur une DQ d'Entier et utilisant la comparaison par valeur inférieure.
2. Remplissage de la file à priorité avec les valeurs issues du générateur de nombres pseudo-aléatoires.
3. Tant que la file à priorité n'est pas vide, affichage du meilleur élément puis extraction de cet élément.

#include <stdlib.h>
#include <iostream>
#include <queue>
#include <deque>
 
#include "Entier.hxx"
#include "Genera.hxx"
 
int main(int argc, char *argv[])
{
      typedef std::priority_queue<Entier,
                            deque<Entier>,
                            less<Entier>
                            > FilePrioInt;
    FilePrioInt     fileAlea;
    GenAlea         generateur(time(0));
    int             nbAlea=((argc > 1) ? atoi(argv[1]) : 10);
 
    for (int compteurAlea=0;compteurAlea<nbAlea;compteurAlea++)
    {
        fileAlea.push(generateur());
    }
 
    while (!fileAlea.empty())
    {
        cout << fileAlea.top() << " ";
        fileAlea.pop();
    }
 
    cout << endl;
    return 0;
}

La sortie de ce programme est très simple : il s'agit tout simplement d'une ligne d'entiers triés par ordre décroissant.

Accessible via #include <utility> le type pair est des plus précieux lors de la manipulation des types associatifs.

Il est rare que vous déclariez vous même un type pair. En effet, vous l'utiliserez plus souvent de façon implicite au retour d'une méthode de la STL ou via les typedef value_type des map.

Voici la définition du type pair (rappelons qu'en C++ une struct est une classe dont tous les membres sont publics par défaut) :

template <class T1, class T2>
struct pair
{
    T1 first;
    T2 second;
    pair (const T1& x, const T2& y);
};

Le type pair ne possède pas de fonction membre, mais un constructeur ; l'accès aux deux membres respectivement nommés first et second se faisant de manière directe.

Les opérateurs == et < sont redéfinis pour les types pairs avec les comportements habituels.

Notons également l'existence de la fonction make_pair permettant de construire une paire à partir de deux valeurs quelconques et définie par :

template <class T1, class T2>
pair<T1,T2> make_pair (const T1 &a, const T2 &b)
{
    return pair<T1,T2>(a,b);
}

Cette fonction est vraiment pratique, car elle permet de créer une paire sans avoir à spécifier explicitement le type de cette dernière (c'est la fonction qui s'en charge). Le (micro) fragment de programme suivant montre qu'il est vraiment facile de créer une paire quelconque à l'aide de cette fonction.

#include <utility>
#include <string>
#include <iostream>
 
int main(int, char**)
{
    int i=3;
    string s("Chaîne&#8221;);
    cout << make_pair(i,s).second << endl;
        // le retour de make_pair de type pair<int,string>
        // l'affichage concernera donc uniquement la chaine
    return 0;
}

Bien qu'ils soient inadaptés à la plupart des algorithmes génériques (du fait de leur structure particulière), les conteneurs associatifs ne sont pas allergiques, loin de la, à la notion d'itérateur.

Les conteneurs associatifs peuvent fournir des itérateurs bidirectionnels à l'aide des méthodes habituelles (begin, end, rbegin, rend).

En outre, les méthodes de recherche d'éléments, telles que, par exemple, find renvoient également ce genre d'itérateurs.

Du fait de leurs grandes ressemblances, les opérations disponibles sur les types set et map sont très semblables. Collections ordonnées d'éléments, les types set et map n'autorisent que des opérations limitées sur les éléments :

• insertion d'un ou plusieurs éléments ;
• retrait d'un ou plusieurs éléments ;
• recherche d'éléments.

Toutes ses opérations sont prévues pour être exécutées avec une complexité au pire logarithmique !

Quelques petites différences nous empêchent de rassembler toutes les fonctionnalités dans un même tableau. Nous ne donnerons dans cette rubrique que les méthodes rigoureusement identiques à la signification de value_type et key_type près ! Nous rappelons également que dans le cas d'un set, les notions de clef et de valeur sont confondues.

Tableau 3.8 Opérations identiques sur les deux conteneurs set et map

Voici le descriptif des fonctions membres spécifiques à set :

Tableau 3.9 Les fonctions membres spécifiques à set

En outre, en plus des habituels tests d'égalité et d'infériorité (== et <), la plupart des opérations sur les ensembles sont fournies en tant que fonctions externes. Toutes ces fonctions ont, à l'exception de includes qui renvoie un booléen, la même signature, laquelle se décline en deux versions :

itérateurSortie fonction(itérateur debutGauche, itérateur finGauche,
                         itérateur debutDroite, itérateur finDroite)
itérateurSortie fonction(itérateur debutGauche, itérateur finGauche,
                         itérateur debutDroite, itérateur finDroite,
prédicat comp)

Bien entendu, il faut que les itérateurs soient positionnés sur des ensembles pour que cela fonctionne correctement. Attention ! (piège à c- -), par défaut, tout ce beau monde travaille avec l'opérateur < quel que soit l'opérateur fourni pour la construction des set. Toutefois, il est possible de changer ce comportement en ajoutant un prédicat en dernier argument (deuxième forme).

Tableau 3.10 Fonctions globales s'appliquant au type set

Le type map est un peu plus compliqué que set et possède donc plus de méthodes propres. En outre, nous avons pu remarquer dans les paragraphes précédents que la gestion de la constitude sur les accès aux éléments est plus compliquée que dans le cas de set. En effet, toutes les méthodes d'accès sont doublées selon qu'elles renvoient ou non des itérateurs const.

Plus fort encore , le type map simple redéfinit l'opérateur crochet de manière à renvoyer la valeur d'un élément accédé par sa clef. En sus du côté éminemment pratique ce cet opérateur, le fonctionnement du conteneur devient par certains côtés similaire à celui d'un vecteur ou d'une DQ et les « map » deviennent donc utilisables par tous les algorithmes utilisant de l'indexation pure ! En particulier (ne le dites à personne) l'auteur arrive à utiliser les « map » comme base pour des tas au prix d'une certaine gymnastique il est vrai !

Voici donc la liste des méthodes spécifiques au type map :

Tableau 3.11 Opérations spécifiques à map

L'exemple suivant crée une map associant une chaîne à un entier. Il illustre l'utilisation de l'indexation, de find et de count. L'utilisation de equal_range, lower_bound et upper_bound est laissée à l'exemple suivant sur les multimap. Les commentaires du programme sont affichés par le programme et donc directement inclus dans sa sortie écran, (figure suivant le programme)

#include <string>
#include <map>
#include <iostream>
 
typedef std::map<int, string, less<int> > MapIntString;
typedef MapIntString::iterator MapIntStringIt;
typedef MapIntString::value_type PairIntString;
 
ostream &operator<<(ostream &a, const PairIntString &b)
{
    a << "Clef : " << b.first << " Valeur : " << b.second;
    return a;
}
 
int main(int, char**)
{
    MapIntString map1;
    MapIntStringIt itCourant;
 
    map1[1]="premier";
    map1[2]="second";
    map1[3]="troisieme";
 
    cout << " Affichage avec acces indexe" << endl;
    for (int compteur=0;compteur<4;compteur++)
        cout << map1[compteur] << " zz ";
 
    cout << endl;
 
    cout << " Affichage avec une paire d'iterateurs " << endl;
    itCourant=map1.begin();
    while (itCourant != map1.end())
        cout << *(itCourant++) << " zz ";
 
    cout << endl;
 
    cout << " Affichage avec copy " << endl;
 
    std::copy(map1.begin(),
             map1.end(),
             ostream_iterator<PairIntString>(cout, " ZZ "));
 
    cout << "Tentative d'acces a un element non present : index 17" << endl;
    cout << map1[17] << endl;
 
    cout << "Affichage : remarquez la presence d'un element fictif sur la
clef 17 insere pas l'operateur []" << endl;
 
    std::copy(map1.begin(),
            map1.end(),
            ostream_iterator<PairIntString>(cout, " ZZ "));
 
    cout << endl;
 
    cout << "Recherche avec find des elements presents " << endl;
 
    cout << "Recherche de la clef 3 : pas de probleme ";
    MapIntString::iterator itRecherche=map1.find(3);
 
    if (itRecherche != map1.end())
    {
        cout << (*itRecherche).second << endl;
    }
    else
    {
        cout << "Pas trouve" << endl;
    }
 
    cout << "Recherche de la clef 13 non presente ";
    itRecherche=map1.find(13);
 
    if (itRecherche != map1.end())
    {
        cout << (*itRecherche).second << endl;
    }
    else
    {
        cout << "Pas trouve" << endl;
    }
 
    cout << "Autre technique : utilisez count" << endl;
 
    cout << "Nb de clefs 1 " << map1.count(1) << endl;
    cout << "Nb de clefs 13 " << map1.count(13) << endl;
    cout << "Plus interessant : Nb de clefs 17 " << map1.count(17) << endl;
    cout << "Constatation : le systeme a ajoute des valeurs nulles
(constructeur par defaut) aux emplacements vides" << endl;
    cout << "Moralite : toujours verifier par un appel a find ou count la
presence d'un element" << endl;
 
    cout << "Effacage de l'element fictif 17" << endl;
 
    map1.erase(17);
 
    cout << "Affichage pour verifier : " << endl;
 
    std::copy(map1.begin(),
              map1.end(),
              ostream_iterator<PairIntString>(cout, " zz "));
 
    cout << endl;
    cout << "Il a bien disparu !" << endl;
 
    cout << "Tentative d'insertion d'un element dont la clef est deja
presente " << endl;
    cout << "Tentative de remplacement de (2,second) par (2,zzDeux) " <<
endl;
 
    map1.insert(MapIntString::value_type(2,"zzDeux"));
 
    cout << "Affichage pour verifier" << endl;
 
    std::copy(map1.begin(),
              map1.end(),
              ostream_iterator<PairIntString>(cout, " ZZ "));
 
    cout << endl;
 
 
        cout << "Comme vous pouvez le voir, ca ne change rien du tout :( " <<
endl;
cout << "En revanche, il est possible d'ajouter ou de modifier une
valeur a l'aide de l'indexation" << endl;
 
    map1[2]="deuxieme";
    map1[5]="cinquieme";
 
    copy(map1.begin(), map1.end(),
        ostream_iterator<PairIntString>(cout, " ZZ "));
 
    cout << endl;
 
    return 0;
}

Et voici la sortie écran :

L'exemple suivant traite d'une base de données de communes indexées par le code postal. Elle montre comment utiliser find, equal_range, lower_bound et upper_bound. Selon l'implémentation de la STL dont vous disposez, il vous faudra peut être utiliser #include <multimap> en lieu et place de #include <map> pour cet exemple.

Lorsque vous cherchez des éléments avec equal_range, il est possible de savoir si la recherche a échoué en comparant le résultat obtenu avec la paire (conteneur.end(), conteneur.end()). Il est également possible de tester la présence d'un ou plusieurs éléments avec count.

#include <string>
#include <map>
#include <iostream>
 
// multi map associant plusieurs chaines (les noms des communes)
// à un entier (le code postal)
 
typedef std::multimap<int, std::string, std::less<int> > MultiMapIntString;
typedef MultiMapIntString::iterator MultiMapIntStringIt;
 
typedef MultiMapIntString::value_type PairIntString;
typedef std::pair<MultiMapIntStringIt, MultiMapIntStringIt> PaireIterateurs;
 
// Opérateur d'affichage d'une paire (entier, chaîne)
ostream &operator<<(ostream &a, const PairIntString &b)
{
    a << "Clef : " << b.first << " Valeur : " << b.second;
return a;
}
 
// Opérateur d'affichage permettant de "dumper&#8221; l'intégralité des valeurs
// comprises entre deux itérateurs
ostream &operator<<(ostream &a, const PaireIterateurs &b)
{
    std::copy(b.first,
              b.second,
              ostream_iterator<PairIntString>(a," "));
    return a;
}
 
int main(int, char**)
{
    MultiMapIntString map1;
    MultiMapIntString::iterator itCourant;
    MultiMapIntString::iterator itFin;
    PaireIterateurs its;
 
    // Remplissage de la "base&#8221;
    map1.insert(MultiMapIntString::value_type(63000,"Clermont Ferrand"));
    map1.insert(MultiMapIntString::value_type(63100,"Montferrand"));
    map1.insert(MultiMapIntString::value_type(63100,"Les Vergnes"));
    map1.insert(MultiMapIntString::value_type(63100,"La Plaine"));
    map1.insert(MultiMapIntString::value_type(63400,"Chamalieres"));
    map1.insert(MultiMapIntString::value_type(63400,"Voie Romaine"));
    map1.insert(MultiMapIntString::value_type(63800,"Cournon d'Auvergne"));
    map1.insert(MultiMapIntString::value_type(63800,"Perignat sur Allier"));
    map1.insert(MultiMapIntString::value_type(63800,"Saint Georges sur Allier"));
 
    // Affichage de la multimap par une boucle sur les itérateurs
    itCourant=map1.begin();
    itFin=map1.end();
 
    while (itCourant != itFin)
    {
        cout << (*itCourant).second << " zz ";
        itCourant++;
    }
 
    cout << endl;
 
// Affichage de la multimap par une copie sur itérateur de flux en sortie
 
    std::copy (map1.begin(),
            map1.end(),
            ostream_iterator<PairIntString>(cout, " zz "));
    cout << endl;
 
    // Recherche du premier élément associé à clef 63800
    cout << "Resultat de find sur la clef 63800" << *(map1.find(63800)) << endl;
 
    // Recherche de tous les éléments associés à la clef 63800
    cout << "Resultat de equal_range sur la clef 63800 " ;
 
    cout << map1.equal_range(63800) << endl;
 
    // Recherche d'un élément avec equal_range
    its=map1.equal_range(3000);
    if (its == PaireIterateurs(map1.end(),map1.end()))
        {
            cout << "Pas Trouve" << endl;
        }
 
    its=map1.equal_range(63100);
        if (its == PaireIterateurs(map1.end(),map1.end()))
        {
            cout << "Pas Trouve" << endl;
        }
    else
        {
            cout << its << endl;
        }
 
    // Utilisation de lower et upper bound
    cout << "Tentative de lower/upper bound" << endl;
    its.first=map1.lower_bound(63100);
    its.second=map1.upper_bound(63400);
    cout << its << endl;
 
    // (lower_bound(i), upper_bound(i)) == equal_range(i)
    cout << "Simulation de equal_range avec lower/upper bound" << endl;
 
    cout << "Equal range " << map1.equal_range(63400) << endl;
    cout << "Lower/upper " << PaireIterateurs(map1.lower_bound(63400),
                                              map1.upper_bound(63400)) << endl;
    return 0;
}

Le résultat à l'écran est le suivant :