Discussion :

[Nykoo]

Bonjour,

Pour tester les templates je réinvente la roue en créant un conteneur.

Ma classe contient un pointeur (m_elemPointer) sur les éléments qu'elle contient et un entier non signé (m_nbElem) qui indique le nombre d'élements pointés.

J'ajoute des éléments à mon conteneur de cette manière:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include "container.h"
#define MAX_VALUE 6
 
using namespace std;
 
int main(void)
{
    Container<int> vect;
    for(size_t i = 0; i < MAX_VALUE; i++)
        //operateur << ajoute des éléments à la suite
        vect << 2*i;
    for(size_t i = 0; i < MAX_VALUE+3; i++)
        //operateur [] lit le nème élément
        cout << vect[i] << "\n";
 
    return 0;
}

Il m'affiche:

4007160
2
4
6
8
10
10
10
10

La 1ère valeur devrait être de 0!

Ma fonction qui sert à ajouter un élément:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template<class elemType>
void Container<elemType>::add(elemType element)
{
    this->allocate(m_nbElem+1);
    m_elemPointer[m_nbElem] = element;//Affectation non réalisé
    m_nbElem++;
}

En fait c'est la 2ème ligne qui pose problème. Lors du 1er appel de la fonction add() l'affectation n'est pas effective, mais seulement pour le 1er appel. Lors des appels suivants les autres affectations sont bien faites. C'est pour ça que ma 1ère valeur n'est pas de 0.

La fonction allocate() à bien remplit son rôle pourtant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class elemType>
void Container<elemType>::allocate(size_t size)
{
    elemType * tmp = new elemType[size];
 
    for(size_t i = 0; (i < m_nbElem) && (i < size); i++)
        tmp[i] = m_elemPointer[i];
    if(size > m_nbElem)
        for(size_t i = m_nbElem; i < size; i++)
        {
            elemType null_value;
            tmp[i] = null_value;
        }
 
    delete [] m_elemPointer;
 
    m_elemPointer = tmp;
}

Voiçi la définition complète de ma classe:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#ifndef CONTAINER_H
#define CONTAINER_H
 
 
template <class elemType>
class Container
{
public:
    Container();
    ~Container();
 
    //Ajouter element
    void add(elemType);
    Container operator<<(elemType);
 
    //Lire valeur element
    elemType at(size_t) const;
    elemType operator[](size_t) const;
 
    //Changer valeur element
    void change(size_t,elemType);
 
private:
    //Gestion memoire
    void allocate(size_t);
 
    elemType * m_elemPointer;
    size_t m_nbElem;
};
 
//Contructeurs Destructeurs ----------------------------------------------------
//------------------------------------------------------------------------------
template<class elemType>
Container<elemType>::Container()
{
    m_elemPointer = NULL;
    m_nbElem = 0;
}
 
template<class elemType>
Container<elemType>::~Container()
{
    delete [] m_elemPointer;
}
 
//Ajout ------------------------------------------------------------------------
//------------------------------------------------------------------------------
template<class elemType>
void Container<elemType>::add(elemType element)
{
    this->allocate(m_nbElem+1);
    m_elemPointer[m_nbElem] = element;
    m_nbElem++;
}
 
template<class elemType>
Container<elemType> Container<elemType>::operator<<(elemType element)
{
    this->add(element);
    return *this;
}
 
//Lecture ----------------------------------------------------------------------
//------------------------------------------------------------------------------
template<class elemType>
elemType Container<elemType>::at(size_t indice) const
{
    elemType result;
    if(indice < m_nbElem)
        result = m_elemPointer[indice];
    return result;
}
 
template<class elemType>
elemType Container<elemType>::operator[](size_t indice) const
{
    return this->at(indice);
}
 
//Modification -----------------------------------------------------------------
//------------------------------------------------------------------------------
template<class elemType>
void Container<elemType>::change(size_t indice,elemType element)
{
    if(indice < m_nbElem)
        m_elemPointer[indice] = element;
}
 
//Gestion mémoire --------------------------------------------------------------
//------------------------------------------------------------------------------
template<class elemType>
void Container<elemType>::allocate(size_t size)
{
    elemType * tmp = new elemType[size];
 
    for(size_t i = 0; (i < m_nbElem) && (i < size); i++)
        tmp[i] = m_elemPointer[i];
    if(size > m_nbElem)
        for(size_t i = m_nbElem; i < size; i++)
        {
            elemType null_value;
            tmp[i] = null_value;
        }
 
    delete [] m_elemPointer;
 
    m_elemPointer = tmp;
}
 
 
#endif /*CONTAINER_H*/

Donc si quelqu'un voit quelque chose je le remercie d'avance

[ac_wingless]

operator << renvoie un élément temporaire, donc à chaque passage de boucle, le destructeur de ce temporaire est appelé, mais comme l'opérateur de copie n'est pas écrit, le compilateur crée un constructeur de copie par défaut, et donc le temporaire a la même adresse de tableau que l'élément externe à la boucle. Boum garanti, avé les étincelles et tout.
Il y a peut-être 47 fautes dans ce petit bout de programme, mais c'est effectivement une bonne idée en démarrant de s'attaquer à la réécriture d'un truc maitrisable comme ce conteneur. Pas de chance, vous avez créé un bug plutôt coriace qui cache un peu la forêt.
Ça me rappelle dans un bouquin de Herb Sutter où il décortique une classe Complex bourrée de petits bugs graves et moins graves, s'en servant dans un but didactique mais avertissant qu'il faut bien sûr réutiliser ce qui existe (la classe complex dans son cas, la classe vector ici) une fois la phase d'apprentissage terminée.

Quelques petits conseils:
- l'appel de "this" est inutile et perturbant au niveau du style (quand on voit "this" apparaitre dans un code, on s'attend à une utilisation non triviale)
- il faut au maximum éviter de gérer sa mémoire, mais si c'est le but de l'exercice comme c'est le cas ici, alors outre le constructeur et le destructeur, il faut impérativement penser au constructeur de copie et à l'opérateur =.
- l'allocation realloue, détruit et recopie tout ce qui existe à chaque ajout. S'inspirer plutôt des croissances de vector. Pire que l'inefficacité, le déplacement d'objets en mémoire à l'insu de l'utilisateur est malvenu, et doit être évité dans la mesure du possible, ou très fortement documenté: ici, tous les pointeurs vers des élements déjà insérés et tous les itérateurs (!) sont détruit au moindre ajout d'élément...
- l'affectation par défaut devrait être laissée à new. mais si on veut absolument explicitement assigner la valeur par défaut, préférer ElemType() plutôt que de créer une variable locale qui sera ensuite assignée. Les debuggers mettent des valeurs magiques dans ces variables précisément pour détecter les valeurs non initialisées
- utiliser au maximum "const ElemType&" pour les passages d'argument, on ne sait pas à quel type on a affaire pour un type paramétré... ne pas faire de temporaires pour rien.
- surtout dans le cas de conteneurs, attention à la création accidentelle de temporaires. L'opérateur << devrait en particulier ici renvoyer une référence.

Enfin, une suggestion: pourquoi ne pas profiter de cet exercice, une fois qu'il marche, pour le rendre compatible avec les algorithmes de la STL? implémenter cela revient à faire une check-list de toutes les bonnes pratiques. En effet, la conception d'un conteneur de qualité n'est pas si triviale qu'elle le semble.

Bon courage.

[Nykoo]

Ton message me montre qu'il me reste beaucoup à apprendre (je commence le c++).

Je vais voir les notions qui m'échappent dans ton message pour pouvoir te poser des questions.

Merci pour cette réponse complète.

[Nykoo]

operator << renvoie un élément temporaire, donc à chaque passage de boucle, le destructeur de ce temporaire est appelé, mais comme l'opérateur de copie n'est pas écrit, le compilateur crée un constructeur de copie par défaut, et donc le temporaire a la même adresse de tableau que l'élément externe à la boucle. Boum garanti, avé les étincelles et tout.

L'élément temporaire c'est quoi? element ou *this?
Quand vous parlez du constructeur de copie c'est celui de element?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
template<class elemType>
Container<elemType> Container<elemType>::operator<<(elemType &element)
{
    add(element);
    return *this;
}

Si vect est une instance de Container<classe_a>:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
for(;;){
    classe_a a = 2;
    vect << a;
}

Pour moi a est détruit à chaque retour de boucle. Donc il faut que j'utilise un contructeur de copie de element comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template<class elemType>
Container<elemType> Container<elemType>::operator<<(elemType &element)
{
    elemType new_element = element;
    add(new_element);
    return *this;
}

Comme ça si element est détruit pas de problème. Mais du coup c'est new_element qui est temporaire. Comment s'en sortir?

Ah finalement avec tes autres réponses j'en déduit qu'il faut remplacer:
elemType new_element = element;
par:
elemType & new_element = element;

Suis-je dans le bon?

- l'appel de "this" est inutile et perturbant au niveau du style (quand on voit "this" apparaitre dans un code, on s'attend à une utilisation non triviale)

Ok il suffisait d'utiliser la fonction toute seule je savais pas.

- il faut au maximum éviter de gérer sa mémoire, mais si c'est le but de l'exercice comme c'est le cas ici, alors outre le constructeur et le destructeur, il faut impérativement penser au constructeur de copie et à l'opérateur =.

Ok

- l'allocation realloue, détruit et recopie tout ce qui existe à chaque ajout. S'inspirer plutôt des croissances de vector. Pire que l'inefficacité, le déplacement d'objets en mémoire à l'insu de l'utilisateur est malvenu, et doit être évité dans la mesure du possible, ou très fortement documenté: ici, tous les pointeurs vers des élements déjà insérés et tous les itérateurs (!) sont détruit au moindre ajout d'élément...

Comment faire? La fonction realloc n'a pas d'équivalent en C++? J'ai essayer de voir comment fonctionne vector, mais rien pour l'instant.

- l'affectation par défaut devrait être laissée à new. mais si on veut absolument explicitement assigner la valeur par défaut, préférer ElemType() plutôt que de créer une variable locale qui sera ensuite assignée. Les debuggers mettent des valeurs magiques dans ces variables précisément pour détecter les valeurs non initialisées

Ok

- utiliser au maximum "const ElemType&" pour les passages d'argument, on ne sait pas à quel type on a affaire pour un type paramétré... ne pas faire de temporaires pour rien.

Ok

- surtout dans le cas de conteneurs, attention à la création accidentelle de temporaires. L'opérateur << devrait en particulier ici renvoyer une référence.

Ah ça répond à ma 1ère question peut être.

elemType new_element = element;
Enfin, une suggestion: pourquoi ne pas profiter de cet exercice, une fois qu'il marche, pour le rendre compatible avec les algorithmes de la STL? implémenter cela revient à faire une check-list de toutes les bonnes pratiques. En effet, la conception d'un conteneur de qualité n'est pas si triviale qu'elle le semble.

Bon courage.

Je vois pas ce que vous voulez dire par rendre compatible avec la STL.

Merci encore.

[ac_wingless]

Désolé du manque de clarté de ma description du bug. Comme illustré dans votre réponse, une boucle for crée effectivement un bloc local de variables à l'intérieur de sa boucle:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for(size_t i = 0; i < MAX_VALUE; i++)
        //operateur << ajoute des éléments à la suite
        vect << 2*i;

équivaut en fait à:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
for(size_t i = 0; i < MAX_VALUE; i++)
{
        vect << 2*i;
}

On voit donc plus clairement qu'à chaque itération, toute variable créée par "vect << 2*i;" sera aussitôt détruite dès la fin de la ligne, soit avant la prochaine itération. Je ne parle pas des locales à l'implémentation de <<, mais bien de cette ligne "vect << 2*i;". Etant donné la définition de <<, un object temporaire de type container est effectivement créé lors de l'éxécution de la ligne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
template<class elemType>
Container<elemType> Container<elemType>::operator<<(elemType element)
{
    this->add(element);
    return *this;
}

return (*this) est neutre en soi, et pourrait renvoyer soit une référence, soit une valeur. Le choix d'interprétation est déterminé par le type de retour demandé, en l'occurrence "Container<elemType>", donc valeur. Donc ce qui se passe durant la ligne:
- on déroule l'opérateur <<
- Il appelle add
- il crée une copie de *this pour satisfaire au type de retour
- cette valeur retournée est aussitôt détruite lors du passage à l'itération suivante de for.

La copie de *this se fait par un constructeur de copie automatiquement généré, puisqu'aucun n'est défini. Il s'agit donc d'une copie brute membre à membre, en particulier le pointeur est recopié tel quel, et est donc identique dans la variable vect extérieure à la boucle for, et dans la copie temporaire. Lors de la destruction de la variable temporaire, le tableau est détruit. La variable externe contient donc un pointeur invalide dès la deuxième itération. La recopie des éléments existants qu'effectue allocate se fait donc depuis une zone mémoire marquée disponible, avec donc un comportement indéfini.
Le problème des comportements indéfinis est que dans les petits exemples, ça peut faire croire que ça marche. Une pratique courante est donc d'affecter 0 à un pointeur effacé par delete pour que ça saute aux yeux dès la première utilisation (en gros ça force le comportement indéfini à se dévoiler dans toute son horreur, ici la recopie dans allocate crasherait sur un pointeur nul). Une petite remarque: delete ne le fait pas automatiquement pour de bonnes raisons.

Si on avait un constructeur de copie, le temporaire détruit ne serait qu'une copie et donc n'affecterait pas la variable externe à la boucle. Cependant, je suppose que l'opérateur << est là pour permettre une écriture "vect << 3 << 4 << 5;". Avec l'implémentation renvoyant un temporaire, les ajouts se feraient dans les tableaux temporaires, et bien sûr les ajouts de 4 et 5 seraient immédiatement annulés.

On doit donc réécrire l'opérateur << comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template<class elemType>
Container<elemType>& Container<elemType>::operator<<(const elemType& element)
{
    add(element);
    return *this;
}

Noter le type de retour référence, qui évite la création du temporaire dans la boucle for, et le passage de l'argument en "const elemType&", qui évite la construction d'un temporaire tout en maintenant la sémantique du conteneur: on ajoute une photo instantanée de l'objet au conteneur, pas une référence vers l'objet. Si on utilisait "elemType&", on éviterait bien la création du temporaire, mais on rend flou le principe de fonctionnement du conteneur. Si je crée une chaine, que je l'ajoute au conteneur, puis que je modifie la chaine initiale, la chaine dans le tableau est-elle modifiée? Ce n'est pas clair pour l'utilisateur à la seule lecture de l'interface publique.
Au passage: on évite la création de temporaire même quand ce ne serait pas faux du point de vue de la signification du programme (attention, ce n'est pas le cas de l'opérateur << ci-dessus, qui créait un temporaire de façon fausse), car cela peut être couteux si l'objet est gros ou que sa copie est couteuse (par exemple utilisant un mutex). Dans le cas d'un conteneur générique en particulier, on ne peut pas faire d'hypothèse raisonnable sur le type du contenu.

Pour ce qui concerne l'allocation. On peut mettre en place des techniques plus économes que la destruction et recopie totale au moindre ajout. Par exemple, on peut allouer 5 éléments, les remplir. Au sixième ajout, on passe à 10, au 11ème, on passe à 20, 40 etc. Cela assure qu'au moins la moitié de la mémoire est effectivement utilisée, tout en divisant énormément le cout de croissance pour les gros tableaux. Par ailleurs, en général on propose une fonction "reserve" à l'utilisateur qui connait à peu près la taille finale.
Enfin, il faut se poser une question: les pointeurs ou itérateurs doivent-ils survivre aux ajouts? Certains conteneurs l'assurent, en général c'est non. Si on veut l'assurer, il faut créer des listes de tableaux, et fournir des itérateurs qui savent changer de tableau quand ils arrivent à une extrémité. C'est complexe, mais ça permet d'avoir une occupation mémoire quasi parfaite, un cout d'itération minime lors des parcours non aléatoires du tableau. En revanche la classe d'itérateur est compliquée, et l'accès aléatoire est plus lent.

La STL est la librairie standard du C++. Elle est cruciale pour une bonne utilisation du langage. La philosophie de conception du C++ privilégie en effet l'utilisation de librairies à la modification ou sécurisation des caractéristiques intrinsèquement dangereuses du langage. Par exemple, les pointeurs sont dangereux. Ils sont cependant inutiles dès qu'on peut utiliser la STL. Si on ne peut pas utiliser la STL (ce qui peut arriver, en général en cas de besoin de performance extrême, car la STL est sacrément bien implémentée), alors on doit payer le coût en termes de complexité de programmation. L'inconvénient est qu'on peut le faire, et qu'il n'y a pas de signe "Attention, route dangereuse" pour prévenir (voire votre programme). L'avantage est qu'on peut le faire (programmation système, jeux, hautes performances, conception des librairies puissantes sans ajout au langage).

Un autre avantage de la librairie STL est qu'elle est foncièrement générique. En particulier, elle utilise le "duck typing" (si ça fait coin-coin, alors c'est un canard), ce qui fait que tout conteneur ressemblant à un canard (c'est à dire en l'occurrence implémentant les pré-requis de l'algorithme concerné en termes d'itérateurs) peut quasiment s'intégrer sans bavure dans la librairie. C'est ce que je suggérais dans mon post.

Vous avez visiblement suffisamment de connaissance d'un autre langage pour plonger directement dans les concepts avancés de C++, y compris ces fameux requis des itérateurs pour la STL, c'est pourquoi je vous conseille les livres de Scott Meyer, Herb Sutter, Bjarne Stroustrup, etc. (voir rubrique livres C++ de developpez.com).

[Nykoo]

Un grand merci j'ai eu droit à un vrai cours plus qu'a un post. Pour le langage que je pratique d'habitude c'est tout simplement le C. Et justement j'ai tendance à penser aux références comme avec des pointeurs et ça me joue des tours.

Le coup du delete sans conditions j'y avait pas pensé.

Je comprends tout à fait l'intérêt de la STL, et mon but n'est bien sûr pas de créer un conteneur qui soit aussi bien. J'ai seulement voulu créer un début de conteneur, car c'est la 1ère chose qui m'ait venu à l'esprit pour pratiquer les templates et voir si je les avais bien compris.

Mais après toutes vos remarques j'ai appris beaucoup de choses, et je vois les points que je dois travailler.

Merci pour tous ces conseils.

[Nykoo]

En passant merci pour le site http://www.research.att.com/~bs/bs_faq2.html avec ces notes très intéressantes. C'est un peu l'équivalent du site d' Emmanuel Delahaye pour les C++.