• Abstaction des pointeurs : les itérateurs

    13.4. Abstraction des pointeurs : les itérateurs

    La bibliothèque standard définit un certain nombre de structures de données évoluées, qui permettent de stocker et de manipuler les objets utilisateur de manière optimale, évitant ainsi au programmeur d'avoir à réinventer la roue. On appelle ces structures de données des conteneurs. Ces conteneurs peuvent être manipulés au travers de fonctions spéciales, selon un grand nombre d'algorithmes possibles dont la bibliothèque dispose en standard. L'ensemble des fonctionnalités fournies par la bibliothèque permet de subvenir au besoin des programmeurs dans la majorité des cas. Nous détaillerons la notion de conteneur et les algorithmes disponibles plus loin dans ce document.

    La manière d'accéder aux données des conteneurs dépend bien entendu de leur nature et de leur structure. Cela signifie qu'en théorie, il est nécessaire de spécialiser les fonctions permettant d'appliquer les algorithmes pour chaque type de conteneur existant. Cette technique n'est ni pratique, ni extensible, puisque les algorithmes fournis par la bibliothèque ne pourraient dans ce cas pas travailler sur des conteneurs écrits par le programmeur. C'est pour cette raison que la bibliothèque standard utilise une autre technique pour accéder aux données des conteneurs. Cette technique est basée sur la notion d'itérateur.

    13.4.1. Notions de base et définition

    Un itérateur n'est rien d'autre qu'un objet permettant d'accéder à tous les objets d'un conteneur donné, souvent séquentiellement, selon une interface standardisée. La dénomination d'itérateur provient donc du fait que les itérateurs permettent d'itérer sur les objets d'un conteneur, c'est-à-dire d'en parcourir le contenu en passant par tous ses objets.

    Comme les itérateurs sont des objets permettant d'accéder à d'autres objets, ils ne représentent pas eux-mêmes ces objets, mais plutôt le moyen de les atteindre. Ils sont donc comparables aux pointeurs, dont ils ont exactement la même sémantique. En fait, les concepteurs de la bibliothèque standard se sont basés sur cette propriété pour définir l'interface des itérateurs, qui sont donc une extension de la notion de pointeur. Par exemple, il est possible d'écrire des expressions telles que « *i » ou « ++i » avec un itérateur i. Tous les algorithmes de la bibliothèque, qui travaillent normalement sur des itérateurs, sont donc susceptibles de fonctionner avec des pointeurs classiques.

    Bien entendu, pour la plupart des conteneurs, les itérateurs ne sont pas de simples pointeurs, mais des objets qui se comportent comme des pointeurs et qui sont spécifiques à chaque conteneur. Ainsi, les algorithmes sont écrits de manière uniforme, et ce sont les conteneurs qui fournissent les itérateurs qui leur sont appropriés afin de permettre l'accès à leurs données.

    Il n'y a que trois manières d'obtenir un itérateur. Les itérateurs qui sont effectivement des pointeurs peuvent être obtenus naturellement en prenant l'adresse de l'élément auquel ils donnent accès. Les pointeurs ne doivent être utilisés en tant qu'itérateurs que pour accéder aux données d'un tableau, car la sémantique de l'arithmétique des pointeurs suppose que les éléments référencés successivement par un pointeur sont stockés en des emplacements contigus de la mémoire. Pour les itérateurs de conteneurs en revanche, il faut impérativement utiliser des méthodes spécifiques du conteneur pour obtenir des itérateurs. La plupart des conteneurs fournissent une méthode pour obtenir un itérateur initial, qui référence le premier élément du conteneur, et une méthode pour obtenir la valeur de l'itérateur lorsque le parcours du conteneur est achevé. Enfin, certains algorithmes et certaines méthodes des conteneurs peuvent retourner un itérateur à l'issu de leur traitement.

    Quelle que soit la manière d'obtenir les itérateurs, leur validité est soumise à des limites. Premièrement, ils deviennent obligatoirement invalides dès lors que le conteneur auquel ils permettent d'accéder est détruit. De plus, les conteneurs gèrent leur structure de données de manière dynamique, et sont susceptibles de la réorganiser dès qu'on les manipule. On veillera donc à ne plus utiliser les itérateurs d'un conteneur dès qu'une méthode permettant de le modifier aura été appelée. Ne pas respecter cette règle conduirait, dans le meilleur des cas, à ne pas parcourir complètement l'ensemble des objets du conteneur, et dans le pire des cas, à planter immédiatement le programme.

    13.4.2. Classification des itérateurs

    La bibliothèque définit plusieurs catégories d'itérateurs qui contiennent des itérateurs plus ou moins puissants. Le comportement des itérateurs les plus puissants se rapproche beaucoup des pointeurs classiques, et quasiment toutes les opérations applicables aux pointeurs peuvent l'être à ces itérateurs. En revanche, les itérateurs des classes plus restrictives ne définissent qu'un sous-ensemble des opérations que les pointeurs supportent, et ne peuvent donc être utilisés que dans le cadre de ce jeu d'opérations réduit.

    Les algorithmes de la bibliothèque n'utilisent que les itérateurs des classes les plus faibles permettant de réaliser leur travail. Ils s'imposent ces restrictions afin de garantir leur utilisation correcte même avec les itérateurs les plus simples. Bien entendu, comme les pointeurs disposent de toutes les fonctionnalités définies par les itérateurs, même les plus puissants, les algorithmes standards fonctionnent également avec des pointeurs. Autrement dit, la bibliothèque standard est écrite de façon à n'utiliser qu'une partie des opérations applicables aux pointeurs, afin de garantir que ce qui fonctionne avec des itérateurs fonctionne avec des pointeurs.

    Les itérateurs de chaque catégorie possèdent toutes les propriétés des itérateurs des catégories inférieures. Il existe donc une hiérarchie dans la classification des itérateurs. Les catégories définies par la bibliothèque standard sont les suivantes :

    • les itérateurs de la catégorie « Output » sont utilisés pour effectuer des affectations de valeurs aux données qu'ils référencent. Ces itérateurs ne peuvent donc être déréférencés par l'opérateur '*' que dans le cadre d'une affectation. Il est impossible de lire la valeur d'un itérateur de type Output, et on ne doit écrire dans la valeur qu'ils référencent qu'une fois au plus. Les algorithmes qui utilisent ces itérateurs doivent donc impérativement ne faire qu'une seule passe sur les données itérées ;

    • les itérateurs de la catégorie « Input » sont similaires aux itérateurs de type Output, à ceci près qu'ils ne peuvent être déréférencés que pour lire une valeur. Contrairement aux itérateurs de type Output, il est possible de comparer deux itérateurs. Cependant, le fait que deux itérateurs soient égaux ne signifie aucunement que leurs successeurs le seront encore. Les algorithmes qui utilisent les itérateurs de type Input ne peuvent donc faire aucune hypothèse sur l'ordre de parcours utilisé par l'itérateur. Ce sont donc nécessairement des algorithmes en une passe ;

    • les itérateurs de la catégorie « Forward » possèdent toutes les fonctionnalités des itérateurs de type Input et de type Output. Comme ceux-ci, ils ne peuvent passer que d'une valeur à la suivante, et jamais reculer ou revenir à une valeur déjà itérée. Les algorithmes qui utilisent des itérateurs de cette catégorie s'imposent donc de ne parcourir les données des conteneurs que dans un seul sens. Cependant, la restriction imposée sur l'égalité des opérateurs de type Input est levée, ce qui signifie que plusieurs parcours successifs se feront dans le même ordre. Les algorithmes peuvent effectuer plusieurs parcours, par exemple en copiant la valeur initiale de l'itérateur et en parcourant le conteneur plusieurs fois avec chaque copie ;

    • les itérateurs de la catégorie « Bidirectionnal » disposent de toutes les fonctionnalités des itérateurs de type Forward, mais lèvent la restriction sur le sens de parcours. Ces itérateurs peuvent donc revenir sur les données déjà itérées, et les algorithmes qui les utilisent peuvent donc travailler en plusieurs passes, dans les deux directions ;

    • enfin, les itérateurs de la catégorie « RandomAccess » sont les plus puissants. Ils fournissent toutes les fonctionnalités des itérateurs de type Bidirectionnal, plus la possibilité d'accéder aux éléments des conteneurs par l'intermédiaire d'un index en un temps constant. Il n'y a donc plus de notion de sens de parcours, et les données peuvent être accédées comme les données d'un tableau. Il est également possible d'effectuer les opérations classiques de l'arithmétique des pointeurs sur ces itérateurs.

    Tous les itérateurs de la bibliothèque standard dérivent de la classe de base suivante :

    template <class Category,
    class T, class Distance = ptrdiff_t,
    class Pointer = T*, class Reference = T &>
    struct iterator
    {
    typedef T value_type;
    typedef Distance difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category;
    };
    Cette classe est déclarée dans l'en-tête iterator.

    Cette classe définit les types de base des itérateurs, à savoir : le type des valeurs référencées, le type de la différence entre deux itérateurs dans les calculs d'arithmétique des pointeurs, le type des pointeurs des valeurs référencées par l'itérateur, le type des références pour ces valeurs et la catégorie de l'itérateur. Ce dernier type doit être l'une des classes suivantes, également définies par la bibliothèque standard :

    • input_iterator_tag, pour les itérateurs de la catégorie des itérateurs de type Input ;

    • output_iterator_tag, pour les itérateurs de la catégorie des itérateurs de type Output ;

    • forward_iterator_tag, pour les itérateurs de la catégorie des itérateurs de type Forward ;

    • bidirectionnal_iterator_tag, pour les itérateurs de la catégorie des itérateurs bidirectionnels ;

    • random_access_iterator_tag, pour les itérateurs de la catégorie des itérateurs à accès complet.

    Notez que le type par défaut pour la différence entre deux pointeurs est le type ptrdiff_t, qui est utilisé classiquement pour les pointeurs normaux. De même, le type pointeur et le type référence correspondent respectivement, par défaut, aux types T * et T &. Pour les itérateurs pour lesquels ces types n'ont pas de sens, le type utilisé est void, ce qui permet de provoquer une erreur de compilation si on cherche à les utiliser.

    Ces types sont utilisés par les itérateurs nativement, cependant, ils ne le sont généralement pas par les algorithmes. En effet, ceux-ci sont susceptibles d'être appelées avec des pointeurs normaux, et les pointeurs ne définissent pas tous ces types. C'est pour cette raison qu'une classe de traits a été définie pour les itérateurs par la bibliothèque standard. Cette classe est déclarée comme suit dans l'en-tête iterator :

    template <class Iterator>
    struct iterator_traits
    {
    typedef Iterator::value_type value_type;
    typedef Iterator::difference_type difference_type;
    typedef Iterator::pointer pointer;
    typedef Iterator::reference reference;
    typedef Iterator::iterator_category iterator_category;
    };

    La classe des traits permet donc d'obtenir de manière indépendante de la nature de l'itérateur la valeur des types fondamentaux de l'itérateur. Comme ces types n'existent pas pour les pointeurs classiques, cette classe est spécialisée de la manière suivante :

    template <class T>
    struct iterator_traits<T *>
    {
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T *pointer;
    typedef T &reference;
    typedef random_access_iterator_tag iterator_category;
    };
    Ainsi, le type iterator_traits<itérateur>::difference_type renverra toujours le type permettant de stocker la différence entre deux itérateurs, que ceux-ci soient des itérateurs ou des pointeurs normaux.

    Pour comprendre l'importance des traits des itérateurs, prenons l'exemple de deux fonctions fournies par la bibliothèque standard permettant d'avancer un itérateur d'un certain nombre d'étapes, et de calculer la différence entre deux itérateurs. Il s'agit respectivement des fonctions advance et distance. Ces fonctions devant pouvoir travailler avec n'importe quel itérateur, et n'importe quel type de donnée pour exprimer la différence entre deux itérateurs, elles utilisent la classe des traits. Elles sont déclarées de la manière suivante dans l'en-tête iterator :

    template <class InputIterator, class Distance>
    void advance(InputIterator &i, Distance n);

    template <class InputIterator>
    iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);
    Notez que le type de retour de la fonction distance est Iterator::difference_type pour les itérateurs normaux, et ptrdiff_t pour les pointeurs.

    Note : Ces deux méthodes ne sont pas très efficaces avec les itérateurs de type Forward, car elles doivent parcourir les valeurs de ces itérateurs une à une. Cependant, elles sont spécialisées pour les itérateurs de type plus évolués (en particulier les itérateurs à accès complet), et sont donc plus efficaces pour eux. Elles permettent donc de manipuler les itérateurs de manière uniforme, sans pour autant compromettre les performances.

    13.4.3. Itérateurs adaptateurs

    Les itérateurs sont une notion extrêmement utilisée dans toute la bibliothèque standard, car ils regroupent toutes les fonctionnalités permettant d'effectuer un traitement séquentiel des données. Cependant, il n'existe pas toujours d'itérateur pour les sources de données que l'on manipule. La bibliothèque standard fournit donc ce que l'on appelle des itérateurs adaptateurs, qui permettent de manipuler ces structures de données en utilisant la notion d'itérateur même si ces structures ne gèrent pas elles-mêmes la notion d'itérateur.

    13.4.3.1. Adaptateurs pour les flux d'entrée / sortie standards

    Les flux d'entrée / sortie standards de la bibliothèque sont normalement utilisés avec les opérations '>>' et '<<', respectivement pour recevoir et pour envoyer des données. Il n'existe pas d'itérateur de type Input et de type Output permettant de lire et d'écrire sur ces flux. La bibliothèque définit donc des adaptateurs permettant de construire ces itérateurs.

    L'itérateur adaptateur pour les flux d'entrée est implémenté par la classe template istream_iterator. Cet adaptateur est déclaré comme suit dans l'en-tête iterator :

    template <class T, class charT, class traits = char_traits<charT>,
    class Distance=ptrdiff_t>
    class istream_iterator :
    public iterator<input_iterator_tag, T, Distance,
    const T *, const T &>
    {
    public:
    typedef charT char_type;
    typedef traits trait_type;
    typedef basic_istream<char, traits> istream_type;
    istream_iterator();
    istream_iterator(istream_iterator &flux);
    istream_iterator(const istream_iterator<T, charT, traits,
    Distance> &flux);
    ~istream_iterator();
    const T &operator*() const;
    const T *operator->() const;
    istream_iterator<T, charT, traits, Distance> &operator++();
    istream_iterator<T, charT, traits, Distance> operator++(int);
    };
    Les opérateurs d'égalité et d'inégalité sont également définis pour cet itérateur.

    Comme vous pouvez le constater d'après cette déclaration, il est possible de construire un itérateur sur un flux d'entrée permettant de lire les données de ce flux une à une. S'il n'y a plus de données à lire sur ce flux, l'itérateur prend la valeur de l'itérateur de fin de fichier pour le flux. Cette valeur est celle qui est attribuée à tout nouvel itérateur construit sans flux d'entrée. L'exemple suivant présente comment faire la somme de plusieurs nombres lus sur le flux d'entrée, et de l'afficher lorsqu'il n'y a plus de données à lire.

    Exemple 13-2. Itérateurs de flux d'entrée

    #include <iostream>
    #include <iterator>

    using namespace std;

    int main(void)
    {
    double somme = 0;
    istream_iterator<double, char> is(cin);
    while (is != istream_iterator<double, char>())
    {
    somme = somme + *is;
    ++is;
    }
    cout << "La somme des valeurs lue est : " <<
    somme << endl;
    return 0;
    }

    Vous pourrez essayer ce programme en tapant plusieurs nombres successivement puis en envoyant un caractère de fin de fichier avec la combinaison de touches CTRL + Z. Ce caractère provoquera la sortie de la boucle while et affichera le résultat.

    L'itérateur adaptateur pour les flux de sortie fonctionne de manière encore plus simple, car il n'y a pas à faire de test sur la fin de fichier. Il est déclaré comme suit dans l'en-tête iterator :

    template <class T, class charT = char, class traits = char_traits<charT> >
    class ostream_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
    {
    public:
    typedef charT char_type;
    typedef traits trait_type;
    typedef basic_ostream<charT, traits> ostream_type;
    ostream_iterator(ostream_type &flux);
    ostream_iterator(ostream_type &flux, const charT *separateur);
    ostream_iterator(const ostream_iterator<T, charT, traits> &flux);
    ~ostream_iterator();
    ostream_iterator<T, charT, traits> &operator=(const T &valeur);
    ostream_iterator<T, charT, traits> &operator*();
    ostream_iterator<T, charT, traits> &operator++();
    ostream_iterator<T, charT, traits> &operator++(int);
    };

    Cet itérateur est de type Output, et ne peut donc être déréférencé que dans le but de faire une écriture dans l'objet ainsi obtenu. Ce déréférencement retourne en fait l'itérateur lui-même, si bien que l'écriture provoque l'appel de l'opérateur d'affectation de l'itérateur. Cet opérateur envoie simplement les données sur le flux de sortie que l'itérateur prend en charge et renvoie sa propre valeur afin de réaliser une nouvelle écriture. Notez que les opérateurs d'incrémentation existent également, mais ne font strictement rien. Ils ne sont là que pour permettre d'utiliser ces itérateurs comme de simples pointeurs.

    L'itérateur ostream_iterator peut envoyer sur le flux de sortie un texte intercalaire entre chaque donnée qu'on y écrit. Ce texte peut servir à insérer des séparateurs entre les données. Cette fonctionnalité peut s'avérer très pratique pour l'écriture de données formatées. Le texte à insérer automatiquement doit être passé en tant que deuxième argument du constructeur de l'itérateur.

    Exemple 13-3. Itérateur de flux de sortie

    #include <iostream>
    #include <iterator>

    using namespace std;

    const char *texte[6] = {
    "Bonjour", "tout", "le", "monde", "!", NULL
    };

    int main(void)
    {
    ostream_iterator<const char *, char> os(cout, " ");
    int i = 0;
    while (texte[i] != NULL)
    {
    *os = texte[i]; // Le déréférencement est facultatif.
    ++os; // Cette ligne est facultative.
    ++i;
    }
    cout << endl;
    return 0;
    }

    Il existe également des adaptateurs pour les tampons de flux d'entrée / sortie basic_streambuf. Le premier adaptateur est implémenté par la classe template istreambuf_iterator. Il permet de lire les données provenant d'un tampon de flux basic_streambuf aussi simplement qu'en manipulant un pointeur et en lisant la valeur de l'objet pointé. Le deuxième adaptateur, ostreambuf_iterator, permet quant à lui d'écrire dans un tampon en affectant une nouvelle valeur à l'objet référencé par l'itérateur. Ces adaptateurs fonctionnent donc exactement de la même manière que les itérateurs pour les flux d'entrée / sortie formatés. En particulier, la valeur de fin de fichier que prend l'itérateur d'entrée peut être récupérée à l'aide du constructeur par défaut de la classe istreambuf_iterator, instanciée pour le type de tampon utilisé.

    Note : L'opérateur de d'incrémentation suffixé des itérateurs istreambuf_iterator a un type de retour particulier qui permet de représenter la valeur précédente de l'itérateur avant incrémentation. Les objets de ce type sont toujours déréférençables à l'aide de l'opérateur '*'. La raison de cette particularité est que le contenu du tampon peut être modifié après l'appel de l'opérateur 'operator ++(int)', mais l'ancienne valeur de cet itérateur doit toujours permettre d'accéder à l'objet qu'il référençait. La valeur retournée par l'itérateur contient donc une sauvegarde de cet objet et peut se voir appliquer l'opérateur de déréférencement '*' par l'appelant afin d'en récupérer la valeur.

    La notion de tampon de flux sera présentée en détail dans la section 15.2.

    13.4.3.2. Adaptateurs pour l'insertion d'éléments dans les conteneurs

    Les itérateurs fournis par les conteneurs permettent d'en parcourir le contenu et d'obtenir une référence sur chacun de leurs éléments. Ce comportement est tout à fait classique et constitue même une des bases de la notion d'itérateur. Toutefois, l'insertion de nouveaux éléments dans un conteneur ne peut se faire que par l'intermédiaire des méthodes spécifiques aux conteneurs. La bibliothèque standard C++ définit donc des adaptateurs pour des itérateurs dits d'insertion, qui permettent d'insérer des éléments dans des conteneurs par un simple déréférencement et une écriture. Grâce à ces adaptateurs, l'insertion des éléments dans les conteneurs peut être réalisée de manière uniforme, de la même manière qu'on écrirait dans un tableau qui se redimensionnerait automatiquement, à chaque écriture.

    Il est possible d'insérer les nouveaux éléments en plusieurs endroits dans les conteneurs. Ainsi, les éléments peuvent être placés au début du conteneur, à sa fin, ou après un élément donné. Bien entendu, ces notions n'ont de sens que pour les conteneurs qui ne sont pas ordonnés, puisque dans le cas contraire, la position de l'élément inséré est déterminée par le conteneur lui-même.

    La classe template back_insert_iterator est la classe de l'adaptateur d'insertion en fin de conteneur. Elle est déclarée comme suit dans l'en-tête iterator :

    template <class Container>
    class back_insert_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
    {
    public:
    typedef Container container_type;
    explicit back_insert_iterator(Container &conteneur);
    back_insert_iterator<Container> &
    operator=(const typename Container::value_type &valeur);
    back_insert_iterator<Container> &operator*();
    back_insert_iterator<Container> &operator++();
    back_insert_iterator<Container> operator++(int);
    };
    Comme vous pouvez le constater, les objets des instances cette classe peuvent être utilisés comme des itérateurs de type Output. L'opérateur de déréférencement '*' renvoie l'itérateur lui-même, si bien que les affectations sur les itérateurs déréférencés sont traitées par l'opérateur 'operator=' de l'itérateur lui-même. C'est donc cet opérateur qui ajoute l'élément à affecter à la fin du conteneur auquel l'itérateur permet d'accéder, en utilisant la méthode push_back de ce dernier.

    De même, la classe template front_insert_iterator de l'adaptateur d'insertion en tête de conteneur est déclarée comme suit dans l'en-tête iterator :

    template <class Container>
    class front_insert_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
    {
    public:
    typedef Container container_type;
    explicit front_insert_iterator(Container &conteneur);
    front_insert_iterator<Container> &
    operator=(const typename Container::value_type &valeur);
    front_insert_iterator<Container> &operator*();
    front_insert_iterator<Container> &operator++();
    front_insert_iterator<Container> operator++(int);
    };
    Son fonctionnement est identique à celui de back_insert_iterator, à ceci près qu'il effectue les insertions des éléments au début du conteneur, par l'intermédiaire de sa méthode push_front.

    Enfin, la classe template de l'adaptateur d'itérateur d'insertion à une position donnée est déclarée comme suit :

    template <class Container>
    class insert_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
    {
    public:
    typedef Container container_type;
    insert_iterator(Container &conteneur,
    typename Container::iterator position);
    insert_iterator<Container> &
    operator=(const typename Container::value_type &valeur);
    insert_iterator<Container> &operator*();
    insert_iterator<Container> &operator++();
    insert_iterator<Container> operator++(int);
    };
    Le constructeur de cette classe prend en paramètre, en plus du conteneur sur lequel l'itérateur d'insertion doit travailler, un itérateur spécifiant la position à laquelle les éléments doivent être insérés. Les éléments sont insérés juste avant l'élément référencé par l'itérateur fourni en paramètre. De plus, ils sont insérés séquentiellement, les uns après les autres, dans leur ordre d'affectation via l'itérateur.

    La bibliothèque standard C++ fournit trois fonctions template qui permettent d'obtenir les trois types d'itérateur d'insertion pour chaque conteneur. Ces fonctions sont déclarées comme suit dans l'en-tête iterator :

    template <class Container>
    back_insert_iterator<Container>
    back_inserter(Container &conteneur);

    template <class Container>
    front_insert_iterator<Container>
    front_inserter(Container &conteneur);

    template <class Container, class Iterator>
    insert_iterator<Container>
    inserter(Container &conteneur, Iterator position);

    Le programme suivant utilise un itérateur d'insertion pour remplir une liste d'élément, avant d'en afficher le contenu.

    Exemple 13-4. Itérateur d'insertion

    #include <iostream>
    #include <list>
    #include <iterator>

    using namespace std;

    // Définit le type liste d'entier :
    typedef list<int> li_t;

    int main()
    {
    // Crée une liste :
    li_t lst;
    // Insère deux éléments dans la liste de la manière classique :
    lst.push_back(1);
    lst.push_back(10);
    // Récupère un itérateur référençant le premier élément :
    li_t::iterator it = lst.begin();
    // Passe au deuxième élément :
    ++it;
    // Construit un itérateur d'insertion pour insérer de nouveaux
    // éléments avant le deuxième élément de la liste :
    insert_iterator<li_t> ins_it = inserter(lst, it);
    // Insère les éléments avec cet itérateur :
    for (int i = 2; i < 10; ++i)
    {
    *ins_it = i;
    ++ins_it;
    }
    // Affiche le contenu de la liste :
    it = lst.begin();
    while (it != lst.end())
    {
    cout << *it << endl;
    ++it;
    }
    return 0;
    }

    La manière d'utiliser le conteneur de type list sera décrite en détail dans le chapitre 17.

    13.4.3.3. Itérateur inverse pour les itérateurs bidirectionnels

    Les itérateurs bidirectionnels et les itérateurs à accès aléatoire peuvent être parcourus dans les deux sens. Pour ces itérateurs, il est donc possible de définir un itérateur associé dont le sens de parcours est inversé. Le premier élément de cet itérateur est donc le dernier élément de l'itérateur associé, et inversement.

    La bibliothèque standard C++ définit un adaptateur permettant d'obtenir un itérateur inverse facilement dans l'en-tête iterator. Il s'agit de la classe template reverse_iterator :

    template <class Iterator>
    class reverse_iterator :
    public iterator<
    iterator_traits<Iterator>::iterator_category,
    iterator_traits<Iterator>::value_type,
    iterator_traits<Iterator>::difference_type,
    iterator_traits<Iterator>::pointer,
    iterator_traits<Iterator>::reference>
    {
    public:
    typedef Iterator iterator_type;
    reverse_iterator();
    explicit reverse_iterator(Iterator iterateur);
    Iterator base() const;
    Reference operator*() const;
    Pointer operator->() const;
    reverse_iterator &operator++();
    reverse_iterator operator++(int);
    reverse_iterator &operator--();
    reverse_iterator operator--(int);
    reverse_iterator operator+(Distance delta) const;
    reverse_iterator &operator+=(Distance delta);
    reverse_iterator operator-(Distance delta) const;
    reverse_iterator &operator-=(Distance delta);
    Reference operator[](Distance delta) const;
    };
    Les opérateurs de comparaison classiques et d'arithmétique des pointeurs externes operator+ et operator- sont également définis dans cet en-tête.

    Le constructeur de cet adaptateur prend en paramètre l'itérateur associé dans le sens inverse duquel le parcours doit se faire. L'itérateur inverse pointera alors automatiquement sur l'élément précédent l'élément pointé par l'itérateur passé en paramètre. Ainsi, si on initialise l'itérateur inverse avec la valeur de fin de l'itérateur direct, il référencera le dernier élément que l'itérateur direct aurait référencé avant d'obtenir sa valeur finale dans un parcours des éléments du conteneur. La valeur de fin de l'itérateur inverse peut être obtenue en construisant un itérateur inverse à partir de la valeur de début de l'itérateur direct.

    Note : Notez que le principe spécifiant que l'adresse suivant celle du dernier élément d'un tableau doit toujours être une adresse valide est également en vigueur pour les itérateurs. La valeur de fin d'un itérateur est assimilable à cette adresse, pointant sur l'emplacement suivant le dernier élément d'un tableau, et n'est pas plus déréférençable, car elle se trouve en dehors du tableau. Cependant, elle peut être utilisée dans les calculs d'arithmétique des pointeurs, et c'est exactement ce que fait l'adaptateur reverse_iterator.

    La méthode base permet de récupérer la valeur de l'itérateur direct associé à l'itérateur inverse. On prendra garde que l'itérateur renvoyé par cette méthode ne référence pas le même élément que celui référencé par l'itérateur inverse. En effet, l'élément référencé est toujours l'élément suivant l'élément référencé par l'itérateur inverse, en raison de la manière dont cet itérateur est initialisé. Par exemple, l'itérateur inverse référence le dernier élément du conteneur lorsqu'il vient d'être intialisé avec la valeur de fin de l'itérateur directe, valeur qui représente le dernier élément passé. De même, lorsque l'itérateur inverse a pour valeur sa valeur de fin d'itération (ce qui représente l'élément précédent le premier élément du conteneur en quelque sorte), l'itérateur direct référence le premier élément du conteneur.

    En fait, les itérateurs inverses sont utilisés en interne par les conteneurs pour fournir des itérateurs permettant de parcourir leurs données dans le sens inverse. Le programmeur n'aura donc généralement pas besoin de construire des itérateurs inverses lui-même, il utilisera plutôt les itérateurs fournis par les conteneurs.

    Exemple 13-5. Utilisation d'un itérateur inverse

    #include <iostream>
    #include <list>
    #include <iterator>

    using namespace std;

    // Définit le type liste d'entier :
    typedef list<int> li_t;

    int main(void)
    {
    // Crée une nouvelle liste :
    li_t li;
    // Remplit la liste :
    for (int i = 0; i < 10; ++i)
    li.push_back(i);
    // Affiche le contenu de la liste à l'envers :
    li_t::reverse_iterator rev_it = li.rbegin();
    while (rev_it != li.rend())
    {
    cout << *rev_it << endl;
    ++rev_it;
    }
    return 0;
    }

  • Commentaires

    Aucun commentaire pour le moment

    Suivre le flux RSS des commentaires


    Ajouter un commentaire

    Nom / Pseudo :

    E-mail (facultatif) :

    Site Web (facultatif) :

    Commentaire :