| Page d'accueil | Description du projet |
Une "Expanding Table" est un tableau dont la taille augmente en fonction des besoins. Cependant, si à chaque fois qu'on ajoute un élément, on réalloue la mémoire nécessaire au tableau, alors il faut recopier tous les éléments à chaque fois et la structure devient inefficace au possible.
Pour éviter cela, on utilise une règle simple : dès qu'on ajoute un élément au-delà de la taille courante du tableau, on commence par doubler la taille de ce dernier. Pour que les suppressions soient aussi efficaces, on attend que seulement un quart du tableau soit occupé pour diviser le nombre d'emplacements disponibles par 2.
De cette façon, on peut montrer que le coût amorti d'une insertion ou d'une suppression est en O(1)
La classe "Vector" implémente la notion d'"Expanding Table". Après compilation, il suffit de copier l'archive "Vector.a" et les fichier "Vector.h" et "Object.h" pour utiliser la classe dans une autre application. Si vous avez déjà une classe mère de toutes les autres, il suffit qu'elle dispose d'un destructeur virtuel, et des fonctions virtuelles value() et Print() (cf. Object.h) pour qu'elle puisse remplacer la classe Object dans les Vectors. Le plus simple est sans doute de la faire hériter de "Object.h".
Alors que la structure de "vector.h" de la STL base sa généricité sur l'utilisation de template, j'ai préféré utiliser la notion d"héritage : les objets manipulés par mes "Vector" sont des pointeurs sur une classe mère universelle "Object" (Equivalent au java.lang.object). Toute classe héritant publiquement de "Object" peut donc être insérée dans le "Vector".
Autre différence avec les "vector" STL, les objets ne sont pas possédés par le Vector. La destruction du Vector n'entraîne pas la destruction de ce qu'il contient. Je fournis tout de même une fonction pour détruire tous les éléments d'un coup.
La classe "Object" possède une méthode virtuelle "double value()". Cette méthode est utilisée par la méthode de tri de "Vector". Toute classe héritant de "Object" peut donc redéfinir "value" pour appeler ensuite la méthode de tri. Le tri utilisé est le tri fusion (quelles que soient les données, sa complexité ne change pas, contrairement au QuickSort).
Enfin, pour être efficace, la suppression ne conserve pas l'ordre. En effet, pour éviter de déplacer tous les éléments, lors de la suppression de l'élément i, ce dernier est échangé avec le dernier élément, avant d'être enlevé du tableau.Attention, il n'est pas détruit.
Ex : T : [........i........n-1] delete(i) : Echange T : [........n-1........i] Reduction T : [........n-1........]Cependant, il est possible de faire un parcours linéaire du tableau en ne supprimant que certains éléments (ceux d'indice pair, par exemple) mais sans traiter deux fois le même élément. Pour cela, il suffit de parcourir le tableau en partant de la fin. Dans ce cas, la suppression d'un élément ne modifie pas l'ordre des éléments qui restent à traiter.
Voici le résultat de la commande "make test" sur ma machine :
Insertion de 24 nbs aléatoires
[|0 ; 118 ; 895 ; 186 ; 366 ; 996 ; 689 ; 21 ; 612 ; 346 ; 873 ; 521 ; 121 ; 729 ; 485 ; 704 ; 822 ; 231 ; 462 ; 553 ; 588 ; 674 ; 324 ; 969 ;|]
Après Tri :
[|0 ; 21 ; 118 ; 121 ; 186 ; 231 ; 324 ; 346 ; 366 ; 462 ; 485 ; 521 ; 553 ; 588 ; 612 ; 674 ; 689 ; 704 ; 729 ; 822 ; 873 ; 895 ; 969 ; 996 ;|]
Suppression d'un élément sur 2.
La suppression ne conserve pas l'ordre
Les objects ne sont pas détruits lors de la suppression,
seulement supprimés du tableau
[|0 ; 553 ; 118 ; 729 ; 186 ; 612 ; 324 ; 969 ; 366 ; 689 ; 485 ; 873 ;|]
Destruction de tous les éléments
[|]
Terminé
> tar zxf Vector.tgz > cd Vector > make > make test