Cours de C/C++

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.

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 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.

• 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.

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▲

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

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

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

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

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

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

Ces classes sont définies dans l'en-tête functional.

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

Ces foncteurs permettent d'utiliser les principaux opérateurs du langage comme des fonctions classiques dans les algorithmes de la bibliothèque standard.

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

Les deux surcharges de la fonction template ptr_fun permettent de faciliter la construction d'un foncteur unaire ou binaire à partir du pointeur d'une fonction du même type.

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

Note : En réalité le langage C++ est capable d'appeler une fonction directement à partir de son adresse, sans déréférencement. De plus le nom d'une fonction représente toujours sont adresse, et est donc converti implicitement par le compilateur en pointeur de fonction. Par conséquent, il est tout à fait possible d'utiliser la fonction template applique avec une autre fonction à deux paramètres, comme dans l'appel suivant :

    applique(2, 3, mul);

Cependant, cette écriture provoque la conversion implicite de l'identificateur mul en pointeur de fonction prenant deux entiers en paramètres et renvoyant un entier, d'une part, et l'appel de la fonction mul par l'intermédiaire de son pointeur sans déréférencement dans la fonction template applique d'autre part. Cette écriture est donc acceptée par le compilateur par tolérance, mais n'est pas rigoureusement exacte.

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.

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

Ces foncteurs fonctionnent exactement comme les foncteurs vus dans la section précédente.

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

Les fonctions not1 et not2 servent à faciliter la construction d'un prédicat inverse pour les prédicats unaires et binaires.

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

La nature des choses veut que plus un programme a de données à traiter, plus il prend du temps pour le faire. Cependant, certains algorithmes se comportent mieux que d'autres lorsque le nombre des données à traiter augmente. Par exemple, un algorithme mal écrit peut voir son temps d'exécution croître exponentiellement avec la quantité de données à traiter, alors qu'un algorithme bien étudié aurait n'aurait été plus lent que proportionnellement à ce même nombre. En pratique, cela signifie que cet algorithme est tout simplement inutilisable lorsque le nombre de données augmente. Par exemple, le fait de doubler la taille de l'ensemble des données à traiter peut engendrer un temps de calcul quatre fois plus long, alors que le temps d'exécution de l'algorithme bien écrit n'aurait été que du double seulement. Et si le nombre de données est triplé et non doublé, cet algorithme demandera huit fois plus de temps, là où le triple seulement est nécessaire. Si l'on prend quatre fois plus de données, le temps sera multiplié par soixante-quatre. On voit clairement que les choses ne vont pas en s'améliorant quand le nombre de données à traiter augmente...

En réalité, il est relativement rare de considérer le temps d'exécution pour qualifier les performances d'un algorithme. En effet, le calcul du temps d'exécution n'est pas toujours possible d'une part, parce qu'il se base sur des paramètres a priori inconnus, et n'est pas toujours ce qui est intéressant au niveau du coût d'autre part. Pour illustrer ce dernier point, supposons que chaque opération effectuée par l'algorithme coûte une certaine quantité d'énergie. Dans certains contextes, il est plus important de s'intéresser à l'énergie dépensée qu'au temps passé pour effectuer l'ensemble des traitements. Or certaines opérations peuvent prendre relativement peu de temps, mais coûter très cher énergétiquement parlant, et l'optimisation du temps d'exécution ne donne pas forcément la meilleure solution. Un autre exemple est tout simplement celui de la lecture de secteurs sur un disque dur. La lecture de ces secteurs en soi ne prend pas tellement de temps, en revanche le déplacement de la tête de lecture se fait en un temps d'accès considérablement plus grand. Les algorithmes de gestion des entrées / sorties sur disque des systèmes d'exploitation cherchent donc naturellement à diminuer au maximum ces déplacements en réorganisant en conséquence les requêtes de lecture et d'écriture.

Il est donc généralement beaucoup plus simple de compter le nombre d'opérations que les algorithmes effectuent lors de leur déroulement, car cette donnée est bien moins spécifique au contexte d'utilisation de l'algorithme. Bien entendu, toutes les opérations effectuées par un algorithme n'ont pas le même coût dans un contexte donné, et de plus ce coût varie d'un contexte d'utilisation à un autre. La complexité d'un algorithme doit donc toujours s'exprimer en nombre d'opérations élémentaires d'un certain type, étant entendu que les opérations de ce type sont celles qui coûtent le plus cher selon les critères choisis...

Remarquez que les opérations qui sont réalisées par un algorithme peuvent être elles-mêmes relativement complexes. Par exemple, un algorithme qui applique une fonction sur chaque donnée à traiter peut utiliser une fonction inimaginablement complexe. Cependant, cela ne nous intéresse pas dans la détermination de la complexité de cet algorithme. Bien entendu, ce qu'il faut compter, c'est le nombre de fois que cette fonction est appelée, et la complexité de l'algorithme doit se calculer indépendamment de celle de cette fonction. L'opération élémentaire de l'algorithme est donc ici tout simplement l'appel de cette fonction, aussi complexe soit-elle.

Le nombre des opérations élémentaires effectuées par un algorithme est une fonction directe du nombre de données à traiter. La complexité d'un algorithme est donc directement reliée à cette fonction : plus elle croît rapidement avec le nombre de données à traiter, plus la complexité de l'algorithme est grande.

En réalité, la fonction exacte donnant le nombre d'opérations élémentaires effectuées par un algorithme n'est pas toujours facile à calculer. Cependant, il existe toujours une fonction plus simple qui dispose du même comportement que la fonction du nombre d'opérations de l'algorithme quand le nombre de données à traiter augmente. Cette « forme simplifiée » n'est en fait rien d'autre que la partie croissant le plus vite avec le nombre de données, car lorsque celui-ci tend vers l'infini, c'est elle qui devient prédominante. Cela signifie que si l'on trace le graphe de la fonction, sa forme finit par ressembler à celle de sa forme simplifiée lorsque le nombre de données à traiter devient grand.

La formulation complète de la fonction du nombre d'opérations réalisées par un algorithme n'importe donc pas tant que cela, ce qui est intéressant, c'est sa forme simplifiée. En effet, non seulement elle est plus simple (à exprimer, à manipuler et bien évidemment à retenir), mais en plus elle caractérise correctement le comportement de l'algorithme sur les grands nombres. La complexité d'un algorithme est donc, par définition, le terme prépondérant dans la fonction donnant le nombre d'opérations élémentaires effectuées par l'algorithme en fonction du nombre des données à traiter.

Mathématiquement parlant, le fait que la forme simplifiée d'une fonction se comporte comme la fonction elle-même à l'infini se traduit simplement en disant que les termes d'ordre inférieurs sont écrasés par le terme de premier ordre. Par conséquent, si l'on divise une fonction par l'autre, les termes d'ordre inférieur deviennent négligeables et la valeur du rapport tend à se stabiliser vers les grand nombres. Autrement dit, il est possible de trouver deux constantes A et B positives et non nulles telles que, à partir d'une certaine valeur de n, la triple inéquation 0 ? A×c(n) ? f(n) ? B×c(n), dans laquelle c(n) est la forme simplifiée de la fonction f(n), est toujours vérifiée. La fonction f(n) est donc, en quelque sortes, encadrée par deux « gendarmes » qui suivent le même « trajet » : celui de la fonction c(n).

Note : Notez que cette formulation n'utilise pas le rapport des fonctions f(n) et c(n) directement. Elle est donc toujours valide, même lorsque ces deux fonctions sont nulles, ce qui aurait posé des problèmes si l'on avait utilisé un rapport.

En fait, la limite inférieure A×c(n) ne nous intéresse pas spécialement. En effet, seul le coût maximal d'un algorithme est intéressant, car s'il coûte moins cher que prévu, personne ne s'en plaindra... Il est donc courant d'utiliser une formulation plus simple et plus connue des mathématiciens, dans laquelle seule la dernière inéquation est utilisée. On dit alors que la fonction f(n) est en grand O de c(n) (ce qui se note « O(c(n)) »). Cela signifie qu'il existe une constante A telle que, pour toutes les valeurs de n supérieures à une valeur suffisamment grande, la double inéquation 0 ? f(n) ? A×c(n) est toujours vérifiée.

Note : La notion de grand O permet donc de donner une borne supérieure de la complexité de la fonction. En fait, si f(n) est en O(c(n)), elle l'est pour toutes les fonctions plus grandes que c(n). Toutefois, en général, on cherche à déterminer la plus petite fonction c(n) qui est un grand O de f(n).

Il est évident que si une fonction f(n) dispose d'une forme simplifiée c(n), elle est en O(c(n)). En effet, l'inéquation supérieure est toujours vérifiée, on ne fait ici qu'ignorer la deuxième inéquation de la définition de la forme simplifiée.

Toutes ces notions peuvent vous paraître assez abstraites, mais il est important de bien comprendre ce qu'elles signifient. Il est donc peut-être nécessaire de donner quelques exemples de complexité parmi celles que l'on rencontre le plus couramment.

Tout d'abord, une complexité de 1 pour un algorithme signifie tout simplement que son coût d'exécution est constant, quel que soit le nombre de données à traiter. Notez bien ici que l'on parle de coût d'exécution et non de durée. Le coût est ici le nombre d'opérations élémentaires effectuées par cet algorithme. Les algorithmes de complexité 1 sont évidemment les plus intéressants, mais ils sont hélas assez rares ou tout simplement triviaux.

Généralement, les algorithmes ont une complexité de n, leur coût d'exécution est donc proportionnel au nombre de données à traiter. C'est encore une limite acceptable, et généralement acceptée comme une conséquence « logique » de l'augmentation du nombre de données à traiter. Certains algorithmes sont en revanche nettement moins performants et ont une complexité en n², soit le carré du nombre des éléments à traiter. Cette fois, cela signifie que leur coût d'exécution a tendance à croître très rapidement lorsqu'il y a de plus en plus de données. Par exemple, si l'on double le nombre de données, le coût d'exécution de l'algorithme ne double pas, mais quadruple. Et si l'on triple le nombre de données, ce coût devient neuf fois plus grand. Ne croyez pas pour autant que les algorithmes de ce type soient rares ou mauvais. On ne peut pas toujours, hélas, faire autrement...

Il existe même des algorithmes encore plus coûteux, qui utilisent des exposants bien supérieurs à 2. Inversement, certains algorithmes extrêmement astucieux permettent de réduire les complexités n ou n² en ln(n) ou n×ln(n), ils sont donc nettement plus efficaces.

Note : La fonction ln(n) est la fonction logarithmique, qui est la fonction inverse de l'exponentielle, bien connue pour sa croissance démesurée. La fonction logarithme évolue beaucoup moins vite que son argument, en l'occurrence n dans notre cas, et a donc tendance à « écraser » le coût des algorithmes qui l'ont pour complexité.

Enfin, pour terminer ces quelques notions de complexité algorithmique, sachez que l'on peut évaluer la difficulté d'un problème à partir de la complexité du meilleur algorithme qui permet de le résoudre. Par exemple, il a été démontré que le tri d'un ensemble de n éléments ne peut pas se faire en mieux que n×ln(n) opérations (et on sait le faire, ce qui est sans doute le plus intéressant de l'affaire). Malheureusement, il n'est pas toujours facile de déterminer la complexité d'un problème. Il existe même toute une classe de problèmes extrêmement difficiles à résoudre pour lesquels on ne sait même pas si leur solution optimale est polynomiale ou non. En fait, on ne sait les résoudre qu'avec des algorithmes de complexité exponentielle (si vous ne savez pas ce que cela signifie, en un mot, cela veut dire que c'est une véritable catastrophe). Cependant, cela ne veut pas forcément dire qu'on ne peut pas faire mieux, mais tout simplement qu'on n'a pas pu trouver une meilleure solution, ni même prouver qu'il y en avait une ! Toutefois, tous ces problèmes sont liés et, si on trouve une solution polynomiale pour l'un d'entre eux, on saura résoudre aussi facilement tous ses petits camarades. Ces problèmes appartiennent tous à la classe des problèmes dits « NP-complets ».