13.5.1. Foncteurs prédéfinis

La bibliothèque n'utilise, dans ses algorithmes, que des foncteurs qui ne prennent qu'un ou deux paramètres. Les foncteurs qui prennent un paramètre et un seul sont dits « unaires », alors que les foncteurs qui prennent deux paramètres sont qualifiés de « binaires ». Afin de faciliter la création de foncteurs utilisables avec ses algorithmes, la bibliothèque standard définit deux classes de base qui pour les foncteurs unaires et binaires. Ces classes de base sont les suivantes :

template <class Arg, class Result>
struct unary_function
{
    typedef Arg    argument_type;
    typedef Result result_type;
};

template <class Arg1, class Arg2, class Result>
struct binary_function
{
    typedef Arg1   first_argument_type;
    typedef Arg2   second_argument_type;
    typedef Result result_type;
};

La bibliothèque définit également un certain nombre de foncteurs standards qui encapsulent les opérateurs du langage dans cet en-tête. Ces foncteurs sont les suivants :

template <class T>
struct plus : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct minus : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct multiplies : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct divides : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct modulus : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct negate : unary_function<T, T>
{
    T operator()(const T &operande) const;
};

template <class T>
struct equal_to : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct not_equal_to : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct greater : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct less : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct greater_equal : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct less_equal : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

#include <iostream>
#include <functional>

using namespace std;

// Fonction template prenant en paramètre deux valeurs
// et un foncteur :
template <class T, class F>
T applique(T i, T j, F foncteur)
{
    // Applique l'opérateur fonctionnel au foncteur
    // avec comme arguments les deux premiers paramètres :
    return foncteur(i, j);
}

int main(void)
{
    // Construit le foncteur de somme :
    plus<int> foncteur_plus;
    // Utilise ce foncteur pour faire faire une addition
    // à la fonction "applique" :
    cout << applique(2, 3, foncteur_plus) << endl;
    return 0;
}

Dans l'exemple précédent, la fonction template applique prend en troisième paramètre un foncteur et l'utilise pour réaliser l'opération à faire avec les deux premiers paramètres. Cette fonction ne peut théoriquement être utilisée qu'avec des objets disposant d'un opérateur fonctionnel '()', et pas avec des fonctions normales. La bibliothèque standard fournit donc les adaptateurs suivants, qui permettent de convertir respectivement n'importe quelle fonction unaire ou binaire en foncteur :

template <class Arg, class Result>
class pointer_to_unary_function :
    public unary_function<Arg, Result>
{
public:
    explicit pointer_to_unary_function(Result (*fonction)(Arg));
    Result operator()(Arg argument1) const;
};

template <class Arg1, Arg2, Result>
class pointer_to_binary_function :
    public binary_function<Arg1, Arg2, Result>
{
public:
    explicit pointer_to_binary_function(Result (*fonction)(Arg1, Arg2));
    Result operator()(Arg1 argument1, Arg2 argument2) const;
};

template <class Arg, class Result>
pointer_to_unary_function<Arg, Result>
    ptr_fun(Result (*fonction)(Arg));

template <class Arg, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
    ptr_fun(Result (*fonction)(Arg1, Arg2));

#include <iostream>
#include <functional>

using namespace std;

template <class T, class F>
T applique(T i, T j, F foncteur)
{
    return foncteur(i, j);
}

// Fonction classique effectuant une multiplication :
int mul(int i, int j)
{
    return i * j;
}

int main(void)
{
    // Utilise un adaptateur pour transformer le pointeur
    // sur la fonction mul en foncteur :
    cout << applique(2, 3, ptr_fun(&mul)) << endl;
    return 0;
}
				

La bibliothèque standard C++ définit également des adaptateurs pour les pointeurs de méthodes non statiques de classes. Ces adaptateurs se construisent comme les adaptateurs de fonctions statiques classiques, à ceci près que leur constructeur prend un pointeur de méthode de classe et non un pointeur de fonction normale. Ils sont déclarés de la manière suivante dans l'en-tête functional :

template <class Result, class Class>
class mem_fun_t :
    public unary_function<Class *, Result>
{
public:
    explicit mem_fun_t(Result (Class::*methode)());
    Result operator()(Class *pObjet);
};

template <class Result, class Class, class Arg>
class mem_fun1_t :
    public binary_function<Class *, Arg, Result>
{
public:
    explicit mem_fun1_t(Result (Class::*methode)(Arg));
    Result operator()(Class *pObjet, Arg argument);
};

template <class Result, class Class>
class mem_fun_ref_t :
    public unary_function<Class, Result>
{
public:
    explicit mem_fun_ref_t(Result (Class::*methode)());
    Result operator()(Class &objet);
};

template <class Result, class Class, class Arg>
class mem_fun1_ref_t :
    public binary_function<Class, Arg, Result>
{
public:
    explicit mem_fun1_ref_t(Result (Class::*methode)(Arg));
    Result operator()(Class &objet, Arg argument);
};

template <class Result, class Class>
mem_fun_t<Result, Class> mem_fun(Result (Class::*methode)());

template <class Result, class Class, class Arg>
mem_fun1_t<Result, Class> mem_fun(Result (Class::*methode)(Arg));

template <class Result, class Class>
mem_fun_ref_t<Result, Class> mem_fun_ref(Result (Class::*methode)());

template <class Result, class Class, class Arg>
mem_fun1_ref_t<Result, Class>
    mem_fun_ref(Result (Class::*methode)(Arg));

Comme vous pouvez le constater d'après leurs déclarations les opérateurs fonctionnels de ces adaptateurs prennent en premier paramètre soit un pointeur sur l'objet sur lequel le foncteur doit travailler (adaptateurs mem_fun_t et mem_fun1_t), soit une référence sur cet objet (adaptateurs mem_fun_ref_t et mem_fun1_ref_t). Le premier paramètre de ces foncteurs est donc réservé pour l'objet sur lequel la méthode encapsulée doit être appelée.

En fait, la liste des adaptateurs présentée ci-dessus n'est pas exhaustive. En effet, chaque adaptateur présenté est doublé d'un autre adaptateur, capable de convertir les fonctions membres const. Il existe donc huit adaptateurs au total permettant de construire des foncteurs à partir des fonctions membres de classes. Pour diminuer cette complexité, la bibliothèque standard définit plusieurs surcharges pour les fonctions mem_fun et mem_fun_ref, qui permettent de construire tous ces foncteurs plus facilement, sans avoir à se soucier de la nature des pointeurs de fonction membre utilisés. Il est fortement recommandé de les utiliser plutôt que de chercher à construire ces objets manuellement.

13.5.2. Prédicats et foncteurs d'opérateurs logiques

Les foncteurs qui peuvent être utilisés dans une expression logique constituent une classe particulière : les prédicats. Un prédicat est un foncteur dont l'opérateur fonctionnel renvoie un booléen. Les prédicats ont donc un sens logique, et caractérisent une propriété qui ne peut être que vraie ou fausse.

La bibliothèque standard fournit des prédicats prédéfinis qui effectuent les opérations logiques des opérateurs logiques de base du langage. Ces prédicats sont également déclarés dans l'en-tête functional :

template <class T>
struct logical_and :
    binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

template <class T>
struct logical_or :
    binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

La bibliothèque standard définit aussi deux foncteurs particuliers, qui permettent d'effectuer la négation d'un autre prédicat. Ces deux foncteurs travaillent respectivement sur les prédicats unaires et sur les prédicats binaires :

template <class Predicate>
class unary_negate :
    public unary_function<typename Predicate::argument_type, bool>
{
public:
    explicit unary_negate(const Predicate &predicat);
    bool operator()(const argument_type &argument) const;
};

template <class Predicate>
class binary_negate :
    public binary_function<typename Predicate::first_argument_type,
        typename Predicate::second_argument_type, bool>
{
public:
    explicit binary_negate(const Predicate &predicat);
    bool operator()(const first_argument_type &argument1,
        const second_argument_type &argument2) const;
};

template <class Predicate>
unary_negate<Predicate> not1(const Predicate &predicat);

template <class Predicate>
binary_negate<Predicate> not2(const Predicate &predicat);

13.5.3. Foncteurs réducteurs

Nous avons vu que la bibliothèque standard ne travaillait qu'avec des foncteurs prenant au plus deux arguments. Certains algorithmes n'utilisant que des foncteurs unaires, ils ne sont normalement pas capables de travailler avec les foncteurs binaires. Toutefois, si un des paramètres d'un foncteur binaire est fixé à une valeur donnée, celui-ci devient unaire, puisque seul le deuxième paramètre peut varier. Il est donc possible d'utiliser des foncteurs binaires même avec des algorithmes qui n'utilisent que des foncteurs unaires, à la condition de fixer l'un des paramètres.

La bibliothèque standard définit des foncteurs spéciaux qui permettent de transformer tout foncteur binaire en foncteur unaire à partir de la valeur de l'un des paramètres. Ces foncteurs effectuent une opération dite de réduction car ils réduisent le nombre de paramètres du foncteur binaire à un. Pour cela, ils définissent un opérateur fonctionnel à un argument, qui applique l'opérateur fonctionnel du foncteur binaire à cet argument et à une valeur fixe qu'ils mémorisent en donnée membre.

Ces foncteurs réducteurs sont déclarés, comme les autres foncteurs, dans l'en-tête fonctional :

template <class Operation>
class binder1st :
    public unary_function<typename Operation::second_argument_type,
        typename Operation::result_type>
{
protected:
    Operation op;
    typename Operation::first_argument_type value;
public:
    binder1st(const Operation &foncteur,
        const typename Operation::first_argument_type &valeur);
    result_type operator()(const argument_type &variable) const;
};

template <class Operation>
class binder2nd :
    public unary_function<typename Operation::first_argument_type,
        typename Operation::result_type>
{
protected:
    Operation op;
    typename Operation::second_argument_type value;
public:
    binder2nd(const Operation &foncteur,
        const typename Operation::second_argument_type &valeur);
    result_type operator()(const argument_type &variable) const;
};

template <class Operation, class T>
binder1st<Operation> bind1st(const Operation &foncteur, const T &valeur);

template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation &foncteur, const T &valeur);

Il existe deux jeux de réducteurs, qui permettent de réduire les foncteurs binaires en fixant respectivement leur premier ou leur deuxième paramètre. Les réducteurs qui figent le premier paramètre peuvent être construits à l'aide de la fonction template bind1st, et ceux qui figent la valeur du deuxième paramètre peuvent l'être à l'aide de la fonction bind2nd.

#include <iostream>
#include <functional>

using namespace std;

// Fonction template permettant d'appliquer une valeur
// à un foncteur unaire. Cette fonction ne peut pas
// être utilisée avec un foncteur binaire.
template <class Foncteur>
typename Foncteur::result_type applique(
    Foncteur f,
    typename Foncteur::argument_type valeur)
{
    return f(valeur);
}

int main(void)
{
    // Construit un foncteur binaire d'addition d'entiers :
    plus<int> plus_binaire;
    int i;
    for (i = 0; i < 10; ++i)
    {
        // Réduit le foncteur plus_binaire en fixant son
        // premier paramètre à 35. Le foncteur unaire obtenu
        // est ensuite utilisé avec la fonction applique :
        cout << applique(bind1st(plus_binaire, 35), i) << endl;
    }
    return 0;
}

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 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;
};

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);

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.

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);
};

#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;
}

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);
};

#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;
}

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);
};

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);
};

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);
};

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);

#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;
}

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;
};

#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;
}