Guru Of the Week n° 50 : utilisation de containers standards

Considérez le code suivant :

    void f( vector<char>& v ) {
      char* pc = &v[0];
      // ... later, uses pc ...
    }

1. Ce code est-il valide ?

2. Qu'il soit valide ou non, comment peut-on l'améliorer ?

3. Considérez le code suivant :

    template<class T = std::vector<T> >
    void f( T& t ) {
      typename T::value_type* p1 = &t[0];
      typename T::value_type* p2 = &*t.begin();
      // ... later, uses p1 and p2 ...
    }

Ce code est-il valide ? Discutez.

Nombreux sont les programmeurs surpris par ce type de code la première fois qu'ils en voient, mais il n'y a rien de mal dans cette technique en elle-même. Aussi longtemps que vous restez conscient du moment où les pointeurs risquent d'être invalidés, ce qui signifie en gros au moment où des itérateurs risquent d'être invalidés, cette technique n'est pas malfaisante, elle n'est pas immorale, et elle ne fait même pas grossir. Au contraire, elle peut être utile.

Il y a des cas où il peut être légal (et, plus précisément, où il est tout à fait approprié) de faire entrer des pointeurs ou des références dans des containers. Un cas courant est quand vous lisez une structure de données en mémoire au lancement d'un programme et qu'ensuite, vous ne le modifiez jamais, mais que vous avez besoin d'y accéder fréquemment de différentes façons. Dans de nombreux cas, il peut être pertinent d'entrer des structures de données supplémentaires qui contiennent des pointeurs dans le container principal pour optimiser différentes méthodes d'accès. Je vous en donnerai un exemple dans le cadre de la discussion de la question n°2.

2. Qu'il soit valide ou non, comment peut-on l'améliorer ?

Il y a deux principaux inconvénients potentiels à cette méthode. Si l'une des deux s'applique à votre cas, continuez avec les pointeurs :

1. Vous ne pouvez pas toujours utiliser de façon pratique un itérateur là où vous pouvez utiliser un pointeur (on verra un exemple plus bas).

2. L'utilisation d'itérateurs peut subir une perte de temps, de performances et d'espace supplémentaires, dans des cas où l'itérateur est un objet et non pas seulement un simple pointeur.

Exemple : Disons que vous avez un map<Name,PhoneNumber> qui, partant d'un nom, facilite la recherche d'un numéro de téléphone. Que faire si vous avez besoin de faire aussi la recherche inverse ? Une solution consiste à bâtir une seconde structure, peut-être un map<PhoneNumber*,Name*,DerefFunctor> qui permettra la recherche inversée mais évitera de doubler la perte de temps par stockage (pas besoin de stocker deux fois chaque nom et numéro de téléphone ; la seconde structure a simplement des pointeurs dans la première).

Notez que, dans l'exemple ci-dessus, il serait difficile d'utiliser des itérateurs à la place de pointeurs. Pourquoi ? Parce que l'itérateur qui est le candidat naturel pour cela, map<Name,PhoneNumber>::iterator, pointe sur pair<Name,PhoneNumber>, et il n'y a pas de façon commode d'obtenir un itérateur juste pour la partie nom ou numéro de téléphone individuellement.

Cela nous amène à la partie suivante (et à mon sens la plus intéressante) de la leçon d'aujourd'hui :

3. Considérez le code suivant :

    template<class T = std::vector<T> >

La ligne ci-dessus comporte deux problèmes :

a) Celui qui est facile à voir, c'est qu'il ne faut pas définir T à partir de lui-même. Cette grosse erreur bien évidente vous a peut-être empêché de voir un problème plus fondamental, à savoir :

b) Les templates de fonctions ne peuvent pas avoir d'arguments par défaut.

à présent, considérez le reste de la fonction comme s'il avait été introduit avec "template<class T>" seulement :

    void f( T& t ) {
      typename T::value_type* p1 = &t[0];
      typename T::value_type* p2 = &*t.begin();
      // ... later, uses p1 and p2 ...
    }

Ce code est-il valide ? Discutez.

La réponse courte est : parfois.

Une façon instructive de considérer ce problème est de penser à quels types de T et de t rendent le code valide. Au moment de la compilation, quelles caractéristiques et capacités T doit-il avoir ? Au moment du lancement, quelles caractéristiques t doit-il avoir ? Enquêtons un peu :

Au moment de la compilation :

a) Pour rendre l'expression &t[0] valide, T::operator[] doit exister et doit retourner quelque chose que operator& comprenne.

En particulier, c'est vrai des containeurs conformes aux exigences des containers standards et qui mettent en œuvre l'operator[] facultatif, parce que l'opérateur doit retourner une référence à l'objet contenu. Par définition, vous pourrez ensuite extraire l'adresse de l'objet contenu.

b) Pour rendre l'expression &*t.begin() valide, T::begin() doit exister, doit retourner quelque chose que operator* comprenne, et qui à son tour doit retourner quelque chose que operator& comprenne.

Par la suite, au moment du lancement :

c) Pour rendre l'expression &t[0] conforme, l'objet t doit être dans un état adéquat pour appeler t[0]. En particulier, si T est quelque chose comme std::vector<int>, le vecteur ne doit pas être vide.

d) Pour rendre l'expression &*t.begin() conforme, l'objet t doit être dans un état adéquat pour appeler t.begin() et déréférencer le résultat. En particulier, si T est quelque chose comme std::vector<int>, le vecteur doit être non-vide.

Le code dans la question n°3 fonctionnera pour tout container dans la librairie standard qui supporte operator[] - et, si vous enlevez la ligne qui contient "&t[0]", il fonctionnera pour tout container dans la librairie standard, sans exception - EXCEPTé pour std::vector<bool>. En fait, le template suivant:

    template<class T>
    void g( vector<T>& v ) {
      T* p = &*t.begin();
      // ... do something with p ...
    }

fonctionne avec tous les types EXCEPTé bool. Si ça vous paraît un peu étrange, vous n'êtes pas le seul.

Malheureusement, il y a quelque chose d'un peu embarrassant à propos de la librairie standard de C++ : Parmi tous les templates qu'elle définit et qui ressemblent à des containers, tous ne sont pas réellement des containers. En particulier,

std::vector<bool> n'est pas un container

(Si quelqu'un d'autre avait écrit vector<bool>, il aurait été appelé "non-conforme" et "non-standard". Certes, c'est dans la norme, aussi est-il un peu plus difficile de le qualifier ainsi à ce moment, mais certains d'entre nous essayeront de toute façon dans l'espoir qu'il sera nettoyé au bout du compte. La bonne solution consiste à éliminer les exigences de spécialiser de vector<bool> pour que vector<bool> soit réellement un vecteur de bon vieux booléens. à côté de cela, c'est largement redondant : std::bitset a été conçu pour ce genre de choses).

La raison pour laquelle std::vector<bool> est non-conforme est qu'il fait un certain nombre de choses de façon cachée pour essayer d'optimiser l'espace : Au lieu de stocker un caractère complet ou un entier complet pour chaque booléen[1] (ce qui prend au moins 8 fois plus de place sur des plateformes à caractères 8-bits), il comprime les données booléennes et les stocke sous forme de bits individuels (inside, say, chars) dans sa représentation interne. Une conséquence de cela est qu'il ne peut pas simplement retourner un bool& normal à partir de son operator[] ou ses itérateurs[2] déréférencés ; au lieu de cela, il doit se contenter d'une classe helper "proxy" class qui ressemble à un booléen mais qui n'est pas un booléen. Malheureusement, cela signifie aussi que l'accès à un vecteur vector<bool> est plus lent, parce qu'on doit traiter avec des proxies au lieu de traiter de pointeurs et de références directs.

Toutes ces astuces ci-dessus ont les inconvénients suivants :

1. std::vector<bool> n'est pas un container.

2. std::vector<bool> tente d'illustrer comment écrire des containers avec proxy et traitements cachés. Malheureusement, ce n'est pas une bonne idée, parce que par définition, cela viole les exigences relatives aux containers. (cf. question n°1) (les exigences relatives aux containers n'ont jamais été modifiées pour permettre la conformité des containers à proxy, et pour autant que je le sache, cette décision était délibérée).

3. Le nom de std::vector<bool> est trompeur, parce que ce qu'il y a à l'intérieur, ce ne sont pas vraiment des booléens standards. Un booléen standard est au moins aussi gros qu'un caractère pour pouvoir être utilisé "normalement". Aussi, en fait, std::vector<bool> ne stocke pas des booléens, malgré son nom.

4. std::vector<bool> force une optimisation spécifique sur tous les utilisateurs en l'incorporant dans la norme. Ce n'est pas une bonne idée ; différents utilisateurs ont différentes exigences, et à présent tous les utilisateurs de vector<bool> doivent payer le prix en termes de pertes des performances même s'ils en veulent pas ou n'ont pas besoin d'économiser de la place.

Dernière ligne : Si vous vous préoccupez davantage de vitesse que de taille, vous ne devriez pas utiliser std::vector<bool>. à la place, vous devriez vous passer de cette optimisation en utilisant un std::vector<char> ou quelque chose de similaire à la place : c'est malheureux, mais c'est quand même le mieux que vous puissiez faire.