Discussion :

[rouliane]

Bonjour,

Je m'entraine un peu au c++, et je dois définir une classe tableau qui vérifie les conditions suivantes :

• On modélise un tableau de type T donné ( par exemple int )

• Les objets de type T sont copiables par création et affectation

• Les operateur operator [] (int i ) et operator [] (int i ) const retournent l'élément i du tableau. ( version const ou non )

De plus la classe tableau doit contenir les champs suivant :

• int n; // nombre de valeurs utilisées dans le vecteur

• int nx; // nombre de valeurs allouées dans le vecteur ( n <=nx)

• T*v; // un pointeur sur le tableau de valeurs allouées

Avec un constructeur par défaut qui construit un tableau vide.

Premièrement, je n'ai pas trop compris l'histoire des nx et n : mon tableau sera de taille nx et j'utiliserai n valeurs, c'est ça ? Je vois pas trop ce qu'ils veulent qu'on fasse ?

Sinon pour le reste, j'ai fait ça :

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
typedef int T; // T de type int
class tableau
{
public:
          tableau() {};   // tableau vide 
          tableau (int n1) { v= new T[n=n1];}       
          tableau( const tableau & source ){ // constructeur par copie
          n=source.n;
          nx=source.nx;
          // v=source.v;
          for(int i =0;i<n;i++) v[i]=source.v[i];                 
                   }
          int& operator[] (int i) { return v[i];} // & pour avoir création et affectation
          int& operator[] (int i) const { return v[i];}
private:
           int n,nx;
           T*v;   
};

Pouvez-vous me dire si y'a des choses qui sont fausses ? Que l'on pourrait "mieux" écrire ?
Je sais pas du tout si le tableau vide est correct.
Je me demande aussi si je pouvais pas écrire :

Code :

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

v=source.v;

à la place de la boucle sur i ?

Merci d'avance.

[NiamorH]

Non ça ne va pas.

Alors déjà, ce qu'on a voulu te dire avec nx et n, c'est que nx représente la capacité totale de stockage de ton tableau (que tu donne visiblement dans le constructeur) tandis que n représente le nombre actuel d'éléments dans ton tableau (apparement on souhaite que tu gère les insertions d'éléments via une fonction Ajouter( T elem )).

Tu vas devoir initialiser nx avec la taille max du tableau, allouer le tableau avec new et cette fameuse taille, et initialiser n à zero au début (on suppose qu'un tableau tout juste construit est d'office vide). Lorsque tu appelleras la méthode ajouter, tu devras comparer n et nx pour voir si il reste de la place dans ton tableau avant d'y stocker le bon element.

Concernant ton constructeur par copie, tu ne peux pas écrire directement :

Code :

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

v=source.v;

car cela voudrait dire tout autre chose. Si tu veux t'affranchir de la boucle for, il existe dans la STL la fonction std::copy, il faut juste inclure <algorithm>.

[rouliane]

Merci Niamorh.

lors déjà, ce qu'on a voulu te dire avec nx et n, c'est que nx représente la capacité totale de stockage de ton tableau (que tu donne visiblement dans le constructeur) tandis que n représente le nombre actuel d'éléments dans ton tableau (apparement on souhaite que tu gère les insertions d'éléments via une fonction Ajouter( T elem )).
Tu vas devoir initialiser nx avec la taille max du tableau, allouer le tableau avec new et cette fameuse taille, et initialiser n à zero au début (on suppose qu'un tableau tout juste construit est d'office vide). Lorsque tu appelleras la méthode ajouter, tu devras comparer n et nx pour voir si il reste de la place dans ton tableau avant d'y stocker le bon element.

En effet, après on doit créer une méthode qui permettra d'insérer des élements.
Ok pour le nx et le n, mais donc mon constructeur va me donner :

Code :

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

tableau (int n1) { v= new T[nx=n1];}

Mais je vois pas où va intervenir le n dans ma classe ?
Je rajoute simplement "n=0;" dans mon constructeur ?
Et visiblement ça n'est qu'après que je l'utiliserais ( pour comparer avec nx) ...

[NiamorH]

Oui c'est ça.

Par contre ça me fait vraiment mal de te voir apprendre le C++ avec le style jefaistouttenirsuruneseuleligne. Lorsque tu devras te relire, et pire, si quelqu'un d'autre doit te relire, c'est pas un cadeau que tu lui fera.
Prends le temps d'écrire du code bien présenté, espace ton code, n'hésite pas à utiliser des variables temporaires dont tu choisiras un nom explicite (evite les notations hongroises style lpcstrMaChaine c'est très lourd pour rien), commente ton code, utilise les listes d'initialisation.

Code :

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

1
2
3
4
5
6
7
8
tableau (int n1)
 : nx( n1 ),
   n ( 0 )
{
  // Allocation de l'espace mémoire pour le tableau
  // Capacité : nx éléments
  v = new T[ nx ];
}

Mais je vois pas où va intervenir le n dans ma classe ?
Je rajoute simplement "n=0;" dans mon constructeur ?
Et visiblement ça n'est qu'après que je l'utiliserais ( pour comparer avec nx) ...

Oui, il va beaucoup te servir en fait :
Tu as pour le moment un tableau dont la mémoire a juste été réservée, les valeurs ne sont pas initialisées.

Que se passe-t-il si tu accèdes aux éléments maintenant via l'opérateur[] ? Et bien tu vas lire ce qui se trouve dans la mémoire non initialisée, c'est à dire les valeurs qui s'y trouvaient au moment de ta demande d'allocation.
Il faut que tu teste, avant de renvoyer la valeur, si l'index du tableau est valide ou non. Il est valide si il est positif ET inférieur au nombre d'éléments présents dans ton tableau, c'est à dire n. Pour t'assurer que l'index demandé est positif, tu peux imposer le passage d'un size_t à la place d'un int car size_t est non signé. Comme ça tu n'as plus qu'à faire le test si ( i < n ), si ce n'est pas vrai, tu lance une exception std::out_of_range.

[rouliane]

Disons que mon prof fait tout tenir sur une seule ligne souvent donc je prend de mauvaises habitudes. Mais je vais faire attention.

Je vais essayer de faire ce que tu me dis conçernant l'index du tableau ( je peux mettre aussi une ligne du style assert( i>=0 et i<=nx); je crois )

Par contre, y'a quelque chose qui me chagrine avec l'opérateur [] justement.
Par exemple je déclare b un tableau :

Code :

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

tableau b(2);

je vais donc avoir un tableau de 2 éléments.
Mais je me demandais donc ce que ça faisait si j'écrivais b[10]=5.
Et là j'ai aucun problème à la compilation b[10] est bien affectée à 5 : mais comment cette valeur existe-t-elle alors que la commande b(2) a alloué un tableau de 2 entiers ??

[Pacorabanix]

Bonjour,

J'aimerai te redire ce que NiamorH a écrit d'une autre manière, peut être que cela t'éclairera les idées, et tu comprendras que finalement, ça ne cause pas de problème tordus à résoudre, les choses devraient t'apparaitre plus simplement.

Répondons à la question : Pourquoi séparer la taille du vecteur en pratique (= son nombre d'éléments), et le nombre maximum de places possibles ?

En effet ça pourrait etre plus simple de dire : si le tableau doit grossir, alors on réalloue la mémoire pile poil sur ce qu'il faut, et c'est tout :

Il y aurait donc juste un seul n (pas de nx), qui est à la fois la taille allouée en mémoire et la taille du tableau rempli.

Quand on ajoute un élément, on augment la taille de 1. Et donc fatalement lorsqu'on ajoute un élément il faut réallouer un tableau entier avec new et une copie (cette fois avec une valeur plus grande de 1 élément).

Pareil quand on supprime, on devra réallouer en mémoire avec new et une copie un nouveau tableau de taille juste plus petite de 1 élément.


Le problème avec cette méthode, ce sont toutes ces rallocations mémoire. Trouver de la place pour un tableau n'est pas chose complètement simple pour la système : les tableaux de base en C/C++ sont continus en mémoire : si le tableau a une taille de 20 alors il faut trouver une place assez grande pour stocker tous les éléments à la suite.


Mais par exemple, si le système a accordé cette place, mais que tu ajoutes ne serait-ce qu'un élément : il va falloir réallouer la mémoire, et rien ne te promet que ce sera au meme endroit ! Il y a peut etre deja qqchose utilisé par le système après les 20 places. Donc le système va trouver l'allocation peut être ailleurs et donc tu devras également recopier tout le tableau original dans la nouvelle place allouée.

Et ensuite, si tu veux réajouter un élément, meme problème, a priori il va falloir recopier encore tout le tableau dans une nouvelle place à 22 éléments.

Sans parler que pour etre cohérent il faut aussi réallouer de la place (plus petite) quand on supprime un élément (alors qu'il n'y en as pas besoin).

Donc imagine si ton tableau fait 10000 élément : il faudra recopier 10000 éléments pour en ajouter 1 : ce n'est pas efficace.



Voila pourquoi on sépare : au début, à la création, on alloue une grosse place (nx==100 par exemple) avec un new. Mais en fait le tableau ne contient rien (n==0). Puis on le remplit en ajoutant des éléments (et n==1, puis n==2, puis n==3 ...), mais pas besoin d'allocation mémoire car le new a deja été fait. Alors bien sur, beaucoup de place est "gachée" ainsi ! Mais on peut se permettre d'avoir cette marge, car elle nous économise énormément d'opérations mémoires (les réallocations, copie)

Au bout d'un moment quand meme, si on veut ajouter un élément alors que le tableau est plein (c'est a dire si n == 100 dans mon exemple), alors a ce moment la, on doit évidemment réallouer de la mémoire pour avoir la place de mettre les éléments suivants. (ou alors ta classe peut aussi l'interdire, demandant de réallouer assez de place avant de façon explicite)



Donc résumons : maintenant ajouter un élément fait ceci : vérifier que le tableau n'est pas plein (que n <= nx) : Si c'est bon on ajoute simplement l'élément a la suite des autres et on incrémente n (pour se souvenir de combien d'éléments on a mis en vrai), sinon, il faut réallouer assez de place (donc augmenter nx) avant, ou alors simplement renvoyer une errreur par exemple.

(C'est en fait exactement ce qui se passe dans le std::vector de la bibliotheque de modèles standards du C++, le tableau qu'on utilise habituellement pour pas mal de choses simples).


EDIT : pfff j'ai écrit un paté et y'a eu des réponses entre temps, mes excuses, c'est deja résolu la question apparemment

[rouliane]

Merci pacorabanix, c'est très clair !
Je vais essayer de faire ça ( je dois en fait créer une méthode push_back pour ajouter un élément si n==nx )

[rouliane]

Je remonte ce post , parce que je comprends toujours pas mon problème avec l'opérateur [].
Même en créant un tableau 'tab' de 2 entiers, je peux accéder à l'élément tab[10]
Merci

[rouliane]

Sinon j'ai rajouté la méthode push_back :

Code :

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

1
2
3
4
          T * push_back( const T & t ) {
          if (nx==n) { nx++;}
          else {v[n++]=t;}               
          }

Seulement le cas nx==n ne change rien j'ai l'impression, comment dire que mon tableau va etre incrémenté d'une valeur, il faut que je passe par un 'new' ?

[Invité]

Tout à fait. Ton nx doit toujours refléter la taille physique du tableau. Pas l'inverse!

Il faut donc réallouer un tableau plus grand que l'original (mettons avec 32 cases en plus, ou alors tu peux carrément doubler la taille à chaque fois), copier tous les éléments, libérer l'ancien tableau et finalement faire l'ajout.

Carl

[rouliane]

ah d'accord !
Je vais faire ça. Merci.

[rouliane]

J'ai essayé de le faire, mais je crois que c'est pas encore ça :

Code :

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

1
2
3
4
5
6
7
8
          T * push_back( const T & t ) {
            if (nx==n) 
            { nx=nx+1;
              T*w=new T[nx];
              for (int i=0;i<n;i++) w[i]=v[i];
              w[n++]=t;                            
            }
          else {v[n++]=t;}

En fait je vois pas comment je peux faire parce que c'est v que je dois modifier, et là pour l'instant j'ai crée un nouveau tableau w.
Il va falloir que je mette aussi un

Code :

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

delete [] v;

quelque part mais le problème c'est que je dois retourner v à un moment...

[rouliane]

sinon j'aimerais bien pouvoir incrémenter n à chaque fois que j'affecte une valeur à mon tableau , par exemple si j'écris :

Code :

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

1
2
tableau b(2);
b[0]=4;

Il faudrait que j'incrémente le n pour signaler que j'ai une valeur d'allouée dans mon tableau. Pour celà j'ajoute un n++ dans l'operateur [] :

Code :

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

1
2
3
4
5
          int& operator[] (int i) 
          { 
               n++; 
               return v[i];
          }

Le problème c'est que si j'écris par exemple :

Code :

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

cout<<b[0]<<endl;

Ben le n est aussi incrémenté alors que j'ai rien alloué.
Savez-vous comment remedier à cela ?

[Invité]

Hello rouliane,

Il est presque l'heure de mon pseudo, alors pardonne-moi si je ne suis pas clair.

Je te laisse chercher un peu pour les questions de ton avant-dernier message. Je te fais juste remarquer qu'incrémenter la capacité du tableau de 1 rend inutile l'utilisation de nx. Mieux vaut incrémenter la capacité par blocs plus gros.

Pour ta dernière question, le conseille que je te donne est: ne laisse pas ton tableau de redimensionner comme cela. Ton accesseur "operator[]" devrait toujours recevoir un indice valide. Si tu as besoin de redimensionner ton tableau, il vaut mieux fournir une fonction à cette fin.

Cheers,

Carl

[rouliane]

Merci 5hdumatin !

Alors j'ai changé mon operateur [] comme ceci :

Code :

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

1
2
3
4
5
6
7
8
          int& operator[] (int i) { 
               n++; 
               if( i>=0 && i<nx)  return v[i];
               else  { 
                    assert (0);
                    abort();   
                    }          
              }

Je vais réfléchir à l'histoire des n à incrémenter, que j'ai toujours pas trouvé, et mon plus gros problème : la méthode push_back où j'ai toujours le même problème.

[rouliane]

Bon alors j'ai essayé de faire cette méthode push_back, voilà ce que j'ai :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
          T * push_back( const T & t ) {
 
            if (nx==n) 
                { nx=nx+20;
                  T*w=new T[nx];
                  for (int i=0;i<n;i++) w[i]=v[i];
                  w[n++]=t;
                  delete [] v;                
                  v=&w[0];                          
                }
 
            else v[n++]=t;      
          }

Ca a l'air de marcher, mais ça veut pas dire que c'est forcément comme celà qu'il fallait faire

[Invité]

Je ne vois toujours pas pourquoi tu incrémentes "n" dans ton operator[]. Cela veut dire que tu t'attends à ce que cet opérateur ajoute des éléments à ton tableau. Laisse push_back() faire cela, et contente-toi de donner accès aux éléments existants dans ton tableau.

Carl

[rouliane]

ah d'accord, en fait j'avais mal compris mon problème, je pensais que l'opérateur [] devait permettre aussi d'affecter une valeur à l'élément tableau[i]. ( en ecrivant par exemple b[2]=5; )

Il faut donc enlever le & ce qui nous donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
          int operator[] (int i) { 
 
               if( i>=0 && i<nx)  
               {
                   return v[i];
               }    
               else  { 
                    assert (0);
                    abort();   
                    }          
              }

Mais la méthode push_back est correcte ou pas ?

[Davidbrcz]

rouliane >> L'opéateur [] doit permettre les deux !!
En effet, on veut pouvoir faire à la fois :

Code :

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

var = tab[2];

et

Code :

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

tab[2]= var.

Pour cela, il faut qu'une surcharge de operator [] fournisse à la fois une lvalue pour le 2eme code et une rvalue pour permettre le 2eme code.

[rouliane]

ah c'est donc bien ça.

Je sais pas trop ce que sont les rvalue et lvalue, mais avec ce code là ça marche ( c'ets ce que j'avais fait au début ) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
          int& operator[] (int i) { 
 
               if( i>=0 && i<nx)  
               {
                   return v[i];
               }    
               else  { 
                    assert (0);
                    abort();   
                    }          
              }

Seulement j'ai pas fait d'opérateur '=', et je sais toujours pas comment gérer l'incrémentation de mon n.