Comment réaliser et utiliser une liste sur base d'un tableau dynamique ?
Les tableaux de données dynamiques sont des structures de données utiles lorsqu'il est impossible de déterminer à l'avance le nombre d'éléments contenus. Un tel conteneur de données est souvent encapsulé dans une classe pour les raisons classiques de facilités de maintenance du code, réutilisabilité et masquage d'implémentation. Les termes suivants — liste non exhaustive — désignent une telle structure de données : Tableau dynamique, ArrayList — en référence aux classes du même nom présentes dans la JRE et le .Net framework, Extendable Array, Growable Array. Dans la suite de cet article nous emploierons le terme d'ArrayList. Les fonctionnalités implémentées peuvent varier fortement en fonction des besoins. En voici quelques exemples : Insertion au milieu d'une liste, suppression au milieu d'une liste, tris des éléments, pré-allocation de mémoire. Structure d'une ArrayListUne ArrayList est un objet effectuant des opérations sur un tableau interne et proposant au moins des accesseurs aux éléments du tableau. D'autres méthodes typiques des listes, telles que l'ajout, l'insertion et la suppression d'éléments sont généralement proposées. L'insertion ou la suppression d'un élément dans une ArrayList est coûteuse en temps d'exécution puisque, comme pour la manipulation classique d'un tableau, certains éléments devront être déplacés. Au contraire, l'accès à un élément de position donnée reste très rapide. Lorsque l'entière capacité du tableau est utilisée, il est nécessaire de redimensionner ce dernier. Ceci passe par la ré-allocation de suffisamment de mémoire et la copie des données précédentes. Il est important d'effectuer le moins de ré-allocations possibles, pour des raisons de performances, tout en occupant un espace mémoire raisonnable. VariantesBien qu'elles puisse être implémentées sur base d'autres structures de données, les listes triées, ou sorted list, sont souvent implémentées sur base d'un tableau. Ce type de liste peut soit insèrer directement les éléments ajoutés à l'endroit approprié. Une autre manière d'aborder le problème est d'exposer une méthode supplémentaire permettant le tri des éléments contenus, à la demande. Au contraire les listes liées, les listes basées sur des tableaux ont souvent pour premier élément celui de position 0, en référence au tableau sous-jacent. Différentes implémentations peuvent cependant changer d'indice de base. Tout comme les listes liées, les ArrayList des frameworks modernes allouent dynamiquement la mémoire utilisée en fonction des ajouts (et éventuellement des suppressions) d'éléments. Il est néanmoins possible d'utiliser un tableau alloué statiquement pour réaliser une ArrayList. Il est alors important de prévoir un mécanisme pour avertir l'utilisateur de la classe lorsque la capacité maximale est atteinte. RéalisationL'implémentation proposée est volontairement simple et n'est pas conçue pour offrir les meilleures performances. Nous implémentons une ArrayList pré-allouant la mémoire par bloc de taille constante. Les méthodes suivantes, où nous choisissons Data de type Long, seront implémentées. Il est bien entendu possible d'implémenter la même structure pour stocker tout autre type de données. - Add(Data) : Ajoute un élément (Data) en fin de liste
- Insert(Data, index) : Ajoute un élément (Data) à la position (index) indiquée
- Item(Index) : Retrouve l'élément à la position (index) donnée
- Remove(Index) : Supprime l'élément à la position (index) donnée
- Count : Détermine le nombre d'éléments dans la liste
- AllocateElements : Permet d'allouer des éléments avant ajout
- Clear : Supprime tous les éléments présents
Les points importants, afin de comprendre l'implémentation, sont les suivants : - L'allocation est réalisée par Redim Preserve. Cette opération est publique, mais est appelée en privé dans toutes les méthodes qui réalisent un ajout.
- Les méthodes d'insertion et de suppression réalisent des déplacements de partie entières de tableau. Le sens de parcours pour les déplacements est différent, afin de ne pas écraser des données existantes.
- Une première allocation est réalisée à l'initialisation (à l'aide de Clear) afin faciliter la suite des opérations.
Option Explicit Private mData() As Long Private mLength As Long Private Const mChunkLength As Long = 256
Public Sub Add(Value As Long) AllocateElements 1 mData(mLength) = Value mLength = mLength + 1 End Sub
Public Sub AllocateElements(ByVal Count As Long) If Count <> 0 Then Count = Count - (UBound(mData) - mLength + 1) If (Count > 0) Then RedimArray UBound(mData) + (Int(Count / mChunkLength) + 1) * mChunkLength End If End If End Sub
Private Sub RedimArray(NewSize As Long) If NewSize < 0 Then ReDim mData(0) Else ReDim Preserve mData(NewSize) End If End Sub
Public Sub Insert(Value As Long, Index As Long) Dim i As Long If Index >= 0 And Index < mLength Then AllocateElements 1 For i = mLength - 1 To Index Step -1 mData(i + 1) = mData(i) Next i mData(Index) = Value mLength = mLength + 1 End If End Sub
Public Sub Remove(Index As Long) If Index >= 0 And Index < mLength Then Dim i As Long
For i = Index + 1 To mLength - 1 mData(i - 1) = mData(i) Next i
mLength = mLength - 1 End If End Sub
Public Function Item(Index As Long) As Long Item = mData(Index) End Function
Public Property Get Count() As Long Count = mLength End Property
Public Sub Clear() Erase mData ReDim mData(mChunkLength - 1) mLength = 0 End Sub
Private Sub Class_Initialize() Clear End Sub La fonction suivante présente un exemple d'utilisation : Private Sub Test() Dim a As ArrayList Dim i As Long Set a = New ArrayList a.Add 10 a.Add 20 a.Add 40 a.Add 30 For i = 0 To a.Count - 1 Debug.Print a.Item(i); Next i Debug.Print a.Insert 15, 1 a.Insert 35, 3 a.Remove 5 For i = 0 To a.Count - 1 Debug.Print a.Item(i); Next i Debug.Print End Sub Voir aussi : |