Créer une classe tableau

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:

---

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:

---

v=source.v;

---

à la place de la boucle sur i ?

Merci d'avance.

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:

---

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

Merci Niamorh.

Citation:

---

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:

---

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

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:

---

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

---

Citation:

---

Envoyé par rouliane

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.

Disons que mon prof fait tout tenir sur une seule ligne souvent donc je prend de mauvaises habitudes.:oops: 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:

---

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

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

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 )

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] 8O
Merci :D

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

Code:

---

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' ?

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

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

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

Code:

---

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:

---

delete [] v;

---

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

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

Code:

---

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:

---

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:

---

cout<<b[0]<<endl;

---

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

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

Merci 5hdumatin !

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

Code:

---

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.

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

Code:

---

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 :mrgreen:

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

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:

---

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 ?

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

Code:

---

var = tab[2];

---

et

Code:

---

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.

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:

---

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

Code:

---

tab[2] = var;

---

Une chose que tu ne semble pas avoir compris, c'est que ce code ne fait pas appel à l'opérateur = de ton tableau. tab[2] représente un int ici.

Code:

---

tab = autreTableau;

---

Dans ce code oui, il faudrait implémenter l'opérateur = car on affecte tout un tableau à un autre.

d'accord je vois.
Mais j'ai fait un constructeur par copie, donc c'est suffisant, non ?
Le voici :

Code:

---

1 2 3 4 5 6

tableau( const tableau & source ){ n=source.n; nx=source.nx; // v=source.v; NON ! for(int i =0;i<n;i++) v[i]=source.v[i]; }

---

Bonjour rouliane, alors désolé d'avoir supprimé le message que tu as mis en quote ! En le revoyant (et sachant qu'il était tard... euhh tot... euhh tard enfin bref), et voyant les 2 autres, je l'ai trouvé complètement inutile... Ravi qu'il t'aide!


Juste une précision sur une de tes dernière questions:

lvalue : une valeur "gauche" (left value) . C'est à dire un nom de variable (à entendre "l'adresse valide d'une variable" ). Bref une valeur qui permet d'en stocker une autre.

rvalue : une valeur droite, c'est à dire une constante, uns variable, l'adresse d'une variable, enfin bref : beaucoup plus de possibilité, mais ce n'est utilisé qu'en lecture.

par exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

int a, b;   b = 3; //valable a = 5; //valable   b = 10; //valable a = b; //valable a = b+3; //valable b+3 = a; // ERREUR ! b+3 n'est pas une lvalue 3 = b; // ERREUR ! 3 n'est pas une lvalue. //[EDIT : ]   int &alias= &a; // alias est maintenant un autre nom pour a (pas tout a fait sur de la syntaxe)   &a = &b; // erreur on ne peut pas modifier l'adresse attribuée a un nom de variable dans le code, &a est une rvalue mais pas une lvalue   // en général, toute constante ne peut etre que rvalue et pas lvalue

---

lorsqu'une fonction retourne un "&int", ça veut justement dire qu'elle doit renvoyer l'adresse d'une variable (valable, pas comme un *int qui peut être NULL), c'est à dire une valeur utilisable comme lvalue

ah merci !

J'essaye d'avance un peu dans l'exo, et on me demande de donner la complexité de l'algorithme suivant :

Code:

---

1 2 3

tableau a; for (int i=0; i<n; i++) a.push_back();

---

où on a :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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]; return v; }   else v[n++]=t; }

---

je dirais que c'est en O(n²) car on aura 2 boucles, mais je n'en suis pas sur.
On em demande ensuite comment faire pour avoir une complexité en O(nxln(n) ).
La je sais pas trop, j'ai lu quelques papiers sur les tris, c'est lié à ça ?

Je rajoute donc un conseil : il faut 2 versions de operator[]. Une qui retourne une lvalue Type& (celui que tu as essayé de faire, mais il faut retourner l'adresse de v[i] et non sa valeur).

Et une qui retourne une rvalue (on veut juste lire la variable) : const Type&.

Pour un int, la fonction [] qui lit pourrait simplement etre "const Type", voir "Type", mais pour rester général et permettre de faire un tableau avec des types plus compliqués il faut bien retourner un const Type&, pour éviter la copie complète de l'objet.

Citation:

---

Envoyé par rouliane

ah merci !

J'essaye d'avance un peu dans l'exo, et on me demande de donner la complexité de l'algorithme suivant :

Code:

---

1 2 3

tableau a; for (int i=0; i<n; i++) a.push_back();

---

...

je dirais que c'est en O(n²) car on aura 2 boucles, mais je n'en suis pas sur.
On em demande ensuite comment faire pour avoir une complexité en O(nxln(n) ).
La je sais pas trop, j'ai lu quelques papiers sur les tris, c'est lié à ça ?

---

La complexité peut etre étudiée pour tout algorithme (=série d'opérations) qui dépend d'un nombre (ici n). Les tris sont un exemple assez primaire d''algorithme, mais là le code que tu as c'est celui là qu'il faut étudier.

De façon assez simple : compte le nombre d'opérations.

Tu ne fais absloument pas toujours 2 boucles ! tu fais une deuxième boucle seulement si le n doit dépasser nx

donc jusqu'à n=20, il n'y a que 20 opérations !
Pour aller à n=21 par contre on en fait :
20 (celles d'avant), une réallocation (donc 20 copies), et un ajout. = 41 !
n= 22 -> 42
...
n= 40 -> 60
n=41 -> 60 (d'avant) plus une réallocation (60 copies) et un ajout, donc 121.

après c'est des maths pour trouver une formule qui exprime cela.

il y aura toujours n ajout. Mais tous les 20 n on fait encore n opérations. Il y a donc Ncarré/20 copie en tout selon moi (pas tout à fait sur). La formule est est de toute façon pas exacte, car j'insinue qu'il y a des "20ème de réallocations", mais globalement ça revient à ça mathématiquement (ça se trouve en écrivant des "sommes" et en simplifiant les formules, c'est des maths)

Ce qui fait qu'on "simplifie" : O(n+ncarré/20) = O(ncarré). Tu avais juste.


En fait, ce qu'il faut comprendre, c'est que malgré le fait qu'on économise pas mal d'opérations en faisant des réallocations par "paquet de 20" et non a chaque fois, au niveau de la *complexité* ça ne change rien, c'est toujours O(ncarré) comme tu dis, c'est toujours *désastreux* (si ton tableau a 10000 éléments... nb d'opérations = 10'000 + 1'000'000'000/20 = 500'010'000 ... n2 = 1'000'000'000, c'est donc une bonne approximation au niveau des ordres de grandeur)


L'idée pour obtenir une variation n * log(n) au lieu de ncarré, c'est de faire de moins en moins de réallocations au fur et a mesure que le tableau grossi. Ici on en fait en fait tous les 20, on en fait donc toujours autant. Il faudrait que le nombre que tu ajoutes à nx (20) dépende de sa taille actuelle.

Un indice : la solution a deja été proposée par quelqu'un ici ;)

[EDIT] Beaucoup moins désastreux le n x log(n) : dans l'exemple donnée : (132 880 opérations seulement, 1000 fois moins, pour log en base 2...)

Pour te donner un exemple complet de calcul de complexité, et pour corriger mon estimation : je me suis mis au papier et au crayon pour calculer correctement le nombre d'opérations :


un exemple avec n=1000 :

1000 (affectations) + (20 + 40 + 60 + ... + 1000) (copies des tableau lors des réallocations)

ça donne avec des n :

n + (20 + 40 + 60 + ... + n)
= n + 20 * (1+2+3+...+ n/20)
= n + 20 * SOMME(de k=1 jusqu'à k=n/20) de k
ici j'utilise le fait que 1+2+3+...+QQCHOSE = QQCHOSE * (QQCHOSE + 1) / 2
= n + 20 * ( n/20 * (n+20 + 1) / 2 )
=n + nCarré/40 + n/2
= 3n/2 + nCarré/40

Le push_back() de std::vector est en moyenne en O(1), donc n push_back() n'aura qu'une complexité linéaire, on peut faire mieux que le n ln(n) (d'ailleurs d'ou vient ce résultat ?), en allouant de manière géométrique.

d'accord, je comprends mieux.
Je voyais bien qu'on ne faisait pas toujours n² boucle, mais on sent bien que ça va etre en n² même si c'est mieux de le vérifier parcque c'est pas si évident le calcul.
J'ai essayé de voir pour l'histoire de diminuer la valeur qu'on ajoute à chauqe fois. Il faut donc que la valeur qu'on ajoute ( appelons la val) soit fonction du nombre d'appels de la méthode push_back ?

Citation:

---

Envoyé par HanLee

Le push_back() de std::vector est en moyenne en O(1), donc n push_back() n'aura qu'une complexité linéaire, on peut faire mieux que le n ln(n) (d'ailleurs d'ou vient ce résultat ?), en allouant de manière géométrique.

---

C'est une question qui m'est posée dans l'exercice.
je vais voir ce que sont les méthodes géométriques, merci.

Citation:

---

Envoyé par rouliane

J'ai essayé de voir pour l'histoire de diminuer la valeur qu'on ajoute à chauqe fois. Il faut donc que la valeur qu'on ajoute ( appelons la val) soit fonction du nombre d'appels de la méthode push_back ?

---

Non pas par rapport à la boucle, mais par rapport a qqchose d'interne au tableau. La boucle, c'est juste une utilisation du tableau avec plein de push back. A priori tu ne dois pas pouvoir savoir comment on utilise ton tableau.

Il faut que tu réalloues selon *la taille actuelle du tableau* (c'est justement cela "de manière géométrique")

Citation:

---

Envoyé par Pacorabanix

Non pas par rapport à la boucle, mais par rapport a qqchose d'interne au tableau. La boucle, c'est juste une utilisation du tableau avec plein de push back. A priori tu ne dois pas pouvoir savoir comment on utilise ton tableau.

Il faut que tu réalloues selon *la taille actuelle du tableau* (c'est justement cela "de manière géométrique")

---

Ca doit donc etre fonction de nx ?

exactement ! Après, de quelle façon c'est comme tu veux. val = nx, val = 2*nx, 3*nx ...


Donc la taille du tableau va évoluer en doublant (ou triplant, quadruplant) a chaque fois ! (de manière géométrique, comme les suites du meme nom ;) )

Citation:

---

Envoyé par Pacorabanix

exactement ! Après, de quelle façon c'est comme tu veux. val = nx, val = 2*nx, 3*nx ...


Donc la taille du tableau va évoluer en doublant (ou triplant, quadruplant) a chaque fois ! (de manière géométrique, comme les suites du meme nom ;) )

---

Je comprends pas : avec ce que tu me dis, si la taille de mon tableau croit, val croit aussi, donc la réallocation aussi.:?
Faudrait pas plutot diviser quelque chose par nx ?

non oublie le message précédent, je viens de comprendre :mrgreen:
Merci beaucoup !

Citation:

---

Envoyé par HanLee

Le push_back() de std::vector est en moyenne en O(1), donc n push_back() n'aura qu'une complexité linéaire, on peut faire mieux que le n ln(n) (d'ailleurs d'ou vient ce résultat ?), en allouant de manière géométrique.

---

Donc en effet, je me suis encore gouré (il *faut* toujours faire confiance aux maths plutot qu'à une simple intuition ;) ), le fait de faire des réallocations de manière géométrique faitg qu'au final l'insertion de n nouveau éléments est de complexité O(n) = n et non pas n*log(n) comme je pensais !


Je suis très curieux de savoir quelle est la solution de ton prof, où si lui aussi a confondu (ce qui serait inquiétant). Si tu y penses rouliane, indique-nous stp!

Ce qui est amusant, c'est que mathématiquement, c'est parce que l'ajout 1 à 1 de n éléments est en O(n) que l'on dit que l'ajout d'un élément est en O(1) amorti, et non pas parce qu'un ajout est en O(1) amorti que l'on pourrait déduire que n ajouts sont en O(n)...

Maintenant, un algo en O(n) est aussi en O(n ln n) ou en O(n^n) ou... donc le prof qui dit que la méthode avec l'allocation géométrique qui a une complexité en O(n) est en O(n ln n) n'a pas entièrement tort... ;)

Le raisonnement erroné qui abouti à ça consiste à dire qu'avec la méthode indiquée, pour faire n ajouts, le nombre d'agrandissement du tableau sera en O(ln n), chaque agrandissement étant lui même en O(n), on a une complexité totale en O(n ln n). Mais les premiers agrandissements sont plus petits que les derniers, on peut donc avoir une meilleure approximation.

Le bon raisonnement est donc de dire que l'on part d'une taille initiale (mettons 1 pour simplifier, ça n'a pas d'importance, c'est juste un coefficient constant dans le calcul du O), et posons a comme facteur d'agrandissement. On va donc faire :
1 copie pour insérer
1 copie pour réallouer
a-1 copies pour insérer
a copies pour réallouer
a² - a copies pour insérer
a² copies pour réallouer
a^3 - a² copies pour insérer
a^3 copies pour réallouer
...
a^j copies pour réallouer
n -a^(j-1) copies pour insérer

Avec j le plus petit nombre tel que a^j > n (et donc de l'ordre de log_a(n))

En simplifiant, le nombre d'insertion est toujours plus faible que le nombre de copies pour réallocation, on ne va donc garder que ce dernier (avec un facteur 2 constant qu'on ignore). On a donc un nombre d'opérations total en :
O(1 + a + a² + a^3 + ... + a^j)
= O((1-a^(j+1)) / (1-a)) = O(a^j) = O(n).



Un point intéressant est le choix du coefficient d'agrandissement. Certaines valeurs ont pour propriétés de ne pas trop fragmenter la mémoire.