Guru of the week #74 - abus de std::vector - Page 1

Bon j'ai pas plus inventé la poudre que pour le précédent, c'est l'épisode 74 sorti en septembre 2000.

Niveau initié

1. Quelle est la différence entre la ligne A et la ligne B ?

    // Example 1: [] vs. at()
    //
    void f( vector<int>& v )
    {
      v[0];      // A
      v.at(0);   // B
    }

Niveau gourou

2. Examinez le code suivant:

    // Example 2: Some fun with vectors
    //
    vector<int> v;

    v.reserve( 2 );
    assert( v.capacity() == 2 );
    v[0] = 1;
    v[1] = 2;
    for( vector<int>::iterator i = v.begin();
         i < v.end(); i++ )
    {
      cout << *i << endl;
    }

    cout << v[0];
    v.reserve( 100 );
    assert( v.capacity() == 100 );
    cout << v[0];

    v[2] = 3;
    v[3] = 4;
    // ...
    v[99] = 100;
    for( vector<int>::iterator i = v.begin();
         i < v.end(); i++ )
    {
      cout << *i << endl;
    }

Trouvez les erreurs d'implémentation et les erreurs de modélisation, ainsi que les problèmes de performance. En question annexe : qu'est-ce que le programme va afficher sur sa sortie standard ?

Et tant qu'à faire, autant mettre les citations correctement : le texte ci dessus est l'oeuvre de Herb Sutter, les quelques lignes d'énoncés modestement traduites par moi....sans permission je dois l'avouer.

[
remarque: je choisis ceux que je poste comme ça :
1) j'ai planché dessus assez longtemps (presque tous en fait, le gars qui fait ces articles c'est un bon, il donne pas mal de fil à retordre)
2) faut pas que ça prenne 20 pages
3) faut pas que l'explication soit longue
4) dans la mesure du possible, faut que ça reste proche de ce qu'on peut croiser tous les jours, genre là le std::vector, et le précédent, les fautes de frappe vicieuses.
]

1 diff A/B : avec .at(), il y a une vérification pour savoir si l'index est bien dans les bornes du tableau si je ne me trompe pas

2
plutôt utiliser un const iterator ?
i != v.end() ?
reserve + assert je ne sais pas (je ne connais pas reserve (d'une manière générale je connais mal le c++ et STL))

./2> En effet ^^
Le at() génère une exception si l'indice déborde du tableau.

on gagne quoi ? un bon point ?

./3> si tu connais mal les STL, le 2 n'est pas pour toi je pense.
Cela dit le 1) non plus, et tu as quand même trouvé la réponse, donc....

Note : le 2 contient de très nombreuses erreurs et fautes de style. Y'a quasiment une erreur par ligne.

Non, c'est pour ta culture perso
En tous cas moi j'aime bien.

HS : je ne sais pas si vous savez, mais il parait que std::endl fait un flush en plus du retour chariot (et que par consequent, dans le cas général, il est préferable d'utiliser \n /HS

spectras :
Non, c'est pour ta culture perso
En tous cas moi j'aime bien.

oué ça peut apprendre des trucs (par contre le ';' derrière le for dans l'autre question c'est un peu inutile à mon avis, c'est juste qu'on ne fait pas attention en lisant mais quelqu'un de normal n'écrit pas ça )

à priori dans les assert il faudrait un >=, pas un ==

(et puis on peut se demander l'utilité d'un reserve(2) peut etre (encore pour le 100, c'est déjà moins ridicule)

Pen^2 :
HS : je ne sais pas si vous savez, mais il parait que std::endl fait un flush en plus du retour chariot (et que par consequent, dans le cas général, il est préferable d'utiliser \n /HS

Oui on sait, mais c'est pas pour autant qu'il est forcément préférable d'utiliser \n.
La plupart des utilisations de endl se font avec stdout.
Si tu n'utilises pas endl, tu délayes l'affichage de tes données. Dans le cas d'une utilisation interactive (un utilisateur regarde au fur et à mesur) de ton programme, c'est très gênant.
En plus en cas de plantage, avec des \n tu ne sais pas où le programme a planté. Avec des endl tu as la garantie que si la ligne ne s'est pas affichée, c'est que ça a planté avant.

oué ça peut apprendre des trucs (par contre le ';' derrière le for dans l'autre question c'est un peu inutile à mon avis, c'est juste qu'on ne fait pas attention en lisant mais quelqu'un de normal n'écrit pas ça )

Ben euh...sisi ça arrive, notamment pour des boucles de recherche, où il n'y a rien d'autre à faire que la comparaison. Mais on essaie de mettre le ; en évidence dans ces cas là, ou d'écrire la boucle différemment.
De toutes façons ce n'était pas vraiment important, vu que le x++ était commenté. S'il n'y avait pas eu le ; la programme aurait quand même affiché 1....mais il aurait affiché 100 lignes de 1.

Bah les valeurs sont pas importantes, c'est un programme d'exemple. Ce qui est important c'est le concept.
Et là je t'isole l'erreur =>

 v.reserve( 2 ); 
 assert( v.capacity() == 2 ); 

Ca ça ne marche pas.

spectras
:

Pen^2 :
HS : je ne sais pas si vous savez, mais il parait que std::endl fait un flush en plus du retour chariot (et que par consequent, dans le cas général, il est préferable d'utiliser \n /HS

Oui on sait, mais c'est pas pour autant qu'il est forcément préférable d'utiliser \n.
La plupart des utilisations de endl se font avec stdout.
Si tu n'utilises pas endl, tu délayes l'affichage de tes données. Dans le cas d'une utilisation interactive (un utilisateur regarde au fur et à mesur) de ton programme, c'est très gênant.

oui mais bon typiquement il vaut mieux faire un flush à la fin d'une boucle qu'à chaque itération

En plus en cas de plantage, avec des \n tu ne sais pas où le programme a planté. Avec des endl tu as la garantie que si la ligne ne s'est pas affichée, c'est que ça a planté avant.

oui à la rigueur ça donne une bonne raison de contredire ce que je viens d'écrire

oué ça peut apprendre des trucs (par contre le ';' derrière le for dans l'autre question c'est un peu inutile à mon avis, c'est juste qu'on ne fait pas attention en lisant mais quelqu'un de normal n'écrit pas ça )

Ben euh...sisi ça arrive, notamment pour des boucles de recherche, où il n'y a rien d'autre à faire que la comparaison. Mais on essaie de mettre le ; en évidence dans ces cas là, ou d'écrire la boucle différemment.

oui je sais bien, mais dans ce cas là il y a une raison et on n'indente pas la ligne suivante (ce que je voulais dire c'est que là c'est de la recherche d'erreur à la con et que ça n'apprend rien si on connait un minimum le C/C++ (dans le même genre d'idées, un copain m'a raconté qu'en TP il s'amusait parfois à emmerder le monde en leur mettant un ";" trop loin pour qu'il soit affiché à l'écran, le tout avec un éditeur pourri qui n'avait pas de barre de scroll ni de retour à la ligne auto ))

De toutes façons ce n'était pas vraiment important, vu que le x++ était commenté. S'il n'y avait pas eu le ; la programme aurait quand même affiché 1....mais il aurait affiché 100 lignes de 1.

oué

Pour le 2 je ne vois que ça :
- v.capacity() >= 2, mais pas forcément ==...
- le vecteur est vide du début jusqu'à la fin, donc les v[0]/v[1]/... sont interdits, et les boucles n'afficheront rien (par contre si en remplaçait reserve() par resize() ça marcherait)
mais ça fait pas une erreur par ligne

(i < v.end() n'est p-ê pas très joli puisque c'est réservé aux itérateurs à accès aléatoire, mais c'est censé marcher je crois...)

Ben entre autres erreurs (les fautes de style et de performance comptent aussi) :

Rien que sur la boucle :

- vector<int>::iterator => devrait être vector<int>::const_iterator vu qu'il l'utilise comme tel
- i++ => devrait être ++i (là c'est un type non trivial et la différence sera flagrante...me rappelle une discussion récente ça )
- i < v.end() => v.end() devrait être stocké dans une variable avant la boucle, et la comparaison se faire sur la variable. Là on force la construction, comparaison et destruction d'un itérateur à chaque tour de boucle.

(i < v.end() n'est p-ê pas très joli puisque c'est réservé aux itérateurs à accès aléatoire, mais c'est censé marcher je crois...)

ça tombe bien, vector<T>::iterator est un itérateur à accès aléatoire. Mais de toutes manière en terme de style de développement, le != est mieux, puisque c'est ça qui est réellement testé, et que ça marche avec tous types d'itérateurs.


Et de toutes façons l'utilisation d'une boucle est fortement inappropriée. Dans la mesure du possible, on recommande l'utilisation des fonctions de programmation générique, for_each et copy par exemple =>
copy( v.begin(), v.end(), ostream_iterator<int>(cout, "\n") );


[note : ce numéro est aussi par nostalgie, on me l'a posé lors d'un entretien pour mon stage de fin d'études (c'est à cette occasion que j'ai découvert le guru of the week, d'ailleurs)]

spectras :
Ben entre autres erreurs (les fautes de style et de performance comptent aussi) :

Rien que sur la boucle :

- vector<int>::iterator => devrait être vector<int>::const_iterator vu qu'il l'utilise comme tel
- i++ => devrait être ++i (là c'est un type non trivial et la différence sera flagrante...me rappelle une discussion récente ça )
- i < v.end() => v.end() devrait être stocké dans une variable avant la boucle, et la comparaison se faire sur la variable. Là on force la construction, comparaison et destruction d'un itérateur à chaque tour de boucle.

(i < v.end() n'est p-ê pas très joli puisque c'est réservé aux itérateurs à accès aléatoire, mais c'est censé marcher je crois...)

ça tombe bien, vector<T>::iterator est un itérateur à accès aléatoire. Mais de toutes manière en terme de style de développement, le != est mieux, puisque c'est ça qui est réellement testé, et que ça marche avec tous types d'itérateurs.

Je suis bien d'accord avec tout ce que tu dis, mais ce code ne me choque pas particulièrement, y compris en termes de performances. On manipule des pointeurs complètement triviaux, du coup toutes tes critiques n'ont aucun sens, du moins pour un compilo qui optimise un minimum... D'ailleurs je viens de vérifier, et avec GCC -O2 le code est exactement équivalent même en appliquant toutes tes "optimisations" (i.e. c'est exactement le même code que si on avait utilisé des bêtes pointeurs)

Disons que c'est peut-être une bonne habitude à prendre, mais je trouve ça stupide d'être psychorigide quand ces "bonnes habitudes" n'ont aucune incidence sur la réalité Donc pour moi, non ce n'est pas une faute.

Et de toutes façons l'utilisation d'une boucle est fortement inappropriée. Dans la mesure du possible, on recommande l'utilisation des fonctions de programmation générique, for_each et copy par exemple =>
copy( v.begin(), v.end(), ostream_iterator<int>(cout, "\n") );

(mais tu oublies de flusher cout #chieur# )

- Bah de toutes façons déjà pour le const c'est pas une question de performances. Le const sert à éviter des erreurs humaines, le compilo ça lui sert à rien. Le seul cas que je vois où le const peut servir au compilo pour optimiser, c'est pour éviter une construction quand on passe un objet constant par valeur, et que le corps de la fonction n'utilise pas de const_cast ni de membre mutable.

- On manipule un itérateur, pas un pointeur. C'est un concept. Il se trouve que pour l'implémentation faite par GCC, cet itérateur est implémenté sous forme d'un int* et v.end() est une fonction inline, ce qui lui permet de faire un certain nombre d'optimisations. Mais dans le cas général, si v.end() n'était pas inline par exemple, il n'aurait pas d'autre choix que l'appeler à chaque tour de boucle, vu qu'il peut pas deviner qu'elle va renvoyer la même chose à chaque itération.

En bref : si tu n'écris pas correctement, tu dépends de l'implémentation STL que tu utilises. Pour peu qu'ils n'utilisent pas un int* mais un objet, et t'es mort pour le i++. Si en plus v.end() n'est pas inline, tu fais le grand chelem.

1°) Si le vecteur est vide, le [] fera une segfault (ou une STATUS_ACCESS_VIOLATION selon l'OS, ou rien du tout si on a/n'a pas de chance --> comportement indéfini) alors que le at() fera une exception C++.

2°) Connais pas assez la STL pour voir ça. Mais pour le coup du v.end(), c'est bon à savoir.

PS: donc, \n ne fait pas de flush en C++ ? (contrairement au fprintf() du langage C)

Enfait, c zarb quand tu dis "erreurs", ce ne sont généralement pas des erreurs de code, mais de manière d'utiliser la STL en l'occurence.
Donc, je coup de l'iterator non const_iterator... ca ne doit pas etre une "erreur"

nEUrOO> oui, ce sont des erreurs de logique / style. Le code compile correctement, et....s'exécute hélas sans problème sur la majorité des systèmes.
Link> en C++, il n'est plus supposé que la sortie standard soit impérativmeent une sortie texte, donc le flush sur \n n'a pas de sens. L'utilisation de marqueurs spéciaux sous forme d'opérateurs surchargés rend les choses nettement plus propres.