Share
Parfois, vous souhaitez dimensionner de manière flexible et utiliser facilement une liste chaînée, mais vous devez disposer de l'indexation directe (en temps constant) d'un tableau. Dans ces cas, un ArrayList peut fournir un terrain d'entente raisonnable.
ArrayList est une collection qui implémente le IListe interface, mais est soutenu par un tableau plutôt que par une liste chaînée. Comme une liste chaînée, un nombre arbitraire d'éléments peut être ajouté (limité uniquement par la mémoire disponible), mais se comporte comme un tableau à tous les égards..
La classe ArrayList implémente le IListe interface. IListe fournit toutes les méthodes et propriétés de ICollection tout en ajoutant également l'indexation directe et l'insertion et la suppression basées sur l'index. L'exemple de code suivant contient des stubs générés à l'aide de la commande Implement Interface de Visual Studio 2010..
L'exemple de code suivant inclut également trois ajouts aux stubs générés:
Accentsconagua
T (articles). Ce tableau contiendra les éléments de la collection.ArrayList classe pour minimiser le nombre de fois que le tableau interne doit être réaffecté.Classe publique ArrayList: System.Collections.Generic.IList T [] _items; public ArrayList (): this (0) public ArrayList (int length) if (length < 0) throw new ArgumentException("length"); _items = new T[length]; public int IndexOf(T item) throw new NotImplementedException(); public void Insert(int index, T item) throw new NotImplementedException(); public void RemoveAt(int index) throw new NotImplementedException(); public T this[int index] get throw new NotImplementedException(); set throw new NotImplementedException(); public void Add(T item) throw new NotImplementedException(); public void Clear() throw new NotImplementedException(); public bool Contains(T item) throw new NotImplementedException(); public void CopyTo(T[] array, int arrayIndex) throw new NotImplementedException(); public int Count get throw new NotImplementedException(); public bool IsReadOnly get throw new NotImplementedException(); public bool Remove(T item) throw new NotImplementedException(); public System.Collections.Generic.IEnumerator GetEnumerator() throw new NotImplementedException(); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() throw new NotImplementedException(); Ajouter un article à un ArrayList est où la différence entre le tableau et la liste liée montre vraiment. Il y a deux raisons à cela. Le premier est qu'un ArrayList prend en charge l’insertion de valeurs au milieu de la collection, tandis qu’une liste liée prend en charge l’ajout d’éléments au début ou à la fin de la liste. La seconde est que l’ajout d’un élément à une liste liée est toujours une opération O (1), mais l’ajout d’éléments à un ArrayList est une opération O (1) ou O (n).
Lorsque des éléments sont ajoutés à la collection, le tableau interne peut éventuellement devenir complet. Lorsque cela se produit, vous devez effectuer les tâches suivantes:
La seule question à laquelle nous devons répondre à ce stade est la taille de la nouvelle matrice. La réponse à cette question est définie par le ArrayList politique de croissance.
Nous examinerons deux stratégies de croissance et pour chacune d’elles, nous examinerons la rapidité avec laquelle la baie se développe et son impact sur les performances..
Il y a deux implémentations de la ArrayList classe, nous pouvons regarder en ligne: Mono et Rotor. Les deux utilisent un algorithme simple qui double la taille du tableau chaque fois qu'une allocation est nécessaire. Si la taille du tableau est zéro, la capacité par défaut est 16. L'algorithme est le suivant:
taille = taille == 0? 1: taille * 2;
Cet algorithme a moins d'allocations et de copies de tableaux, mais gaspille plus d'espace en moyenne que l'approche Java. En d'autres termes, il est biaisé en faveur d'un plus grand nombre d'insertions O (1), ce qui devrait réduire le nombre de fois où la collecte effectue l'opération fastidieuse d'allocation-copie. Cela se traduit par un encombrement mémoire moyen plus important et, en moyenne, par un nombre accru de logements de tableaux vides..
Java utilise une approche similaire mais agrandit le tableau un peu plus lentement. L'algorithme utilisé pour agrandir le tableau est le suivant:
taille = (taille * 3) / 2 + 1;
Cet algorithme a une courbe de croissance plus lente, ce qui signifie qu'il est orienté vers moins de surcharge de mémoire au détriment d'allocations supplémentaires. Regardons la courbe de croissance de ces deux algorithmes pour un ArrayList avec plus de 200 000 articles ajoutés.
La courbe de croissance de Mono / Rotor par rapport à Java pour plus de 200 000 articles Vous pouvez voir sur ce graphique qu'il a fallu 19 allocations pour que l'algorithme de doublage franchisse la limite des 200 000, alors qu'il a fallu 30 allocations pour l'algorithme plus lent (Java) pour atteindre le même point.
Alors, lequel est correct? Il n'y a pas de réponse juste ou fausse. Le doublage effectue moins d'opérations O (n), mais a en moyenne plus de mémoire en surcharge. L'algorithme de croissance plus lente effectue plus d'opérations O (n) mais génère moins de surcharge de mémoire. Pour une collection à usage général, l'une ou l'autre approche est acceptable. Votre domaine de problèmes peut avoir des exigences spécifiques qui rendent l’un plus attrayant, ou vous obliger à créer une autre approche. Quelle que soit l'approche choisie, les comportements fondamentaux de la collection resteront inchangés..
Notre ArrayList la classe utilisera l'approche du doublage (mono / rotor).
void privé GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Comportement | Ajoute la valeur fournie à l'index spécifié dans la collection. Si l'index spécifié est égal ou supérieur à Compter, une exception est levée |
| Performance | Sur) |
L'insertion à un index spécifique nécessite de décaler d'un unité tous les éléments après le point d'insertion. Si la matrice de support est pleine, il faudra la faire pousser avant de pouvoir effectuer le transfert..
Dans l'exemple suivant, il y a un tableau d'une capacité de cinq éléments, dont quatre sont utilisés. La valeur trois sera insérée comme troisième élément du tableau (index deux).
Le tableau avant l'insertion (un slot ouvert à la fin) 
Le tableau après avoir décalé à droite 
Le tableau avec le nouvel élément ajouté à l'emplacement ouvert public void Insert (index int, élément T) if (index> = Count) jette new IndexOutOfRangeException (); if (_items.Length == this.Count) this.GrowArray (); // Décalez tous les éléments suivants à la suite de l'index d'un emplacement. Array.Copy (_items, index, _items, index + 1, Count - index); _items [index] = item; Comptez ++;
| Comportement | Ajoute la valeur fournie à la fin de la collection. |
| Performance | O (1) lorsque la capacité de la matrice est supérieure à Count; O (n) quand la croissance est nécessaire. |
public void Ajouter (élément T) if (_items.Length == Count) GrowArray (); _items [Count ++] = item;
| Comportement | Supprime la valeur à l'index spécifié. |
| Performance | Sur) |
La suppression à un index est essentiellement l'inverse de l'opération d'insertion. L'élément est supprimé du tableau et le tableau est décalé vers la gauche.
Le tableau avant la valeur 3 est supprimé 
Le tableau avec la valeur 3 enlevé 
Le tableau s'est déplacé vers la gauche, libérant le dernier emplacement public void RemoveAt (int index) if (index> = Count) jette new IndexOutOfRangeException (); int shiftStart = index + 1; si (shiftStart < Count) // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart); Count--;
| Comportement | Supprime le premier élément de la collection dont la valeur correspond à la valeur fournie. Résultats vrai si une valeur a été supprimée. Sinon il retourne faux. |
| Performance | Sur) |
public bool Supprimer (élément T) pour (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Comportement | Retourne le premier index de la collection dont la valeur est égale à la valeur fournie. Renvoie -1 si aucune valeur correspondante n'est trouvée.. |
| Performance | Sur) |
public int IndexOf (élément T) pour (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Comportement | Obtient ou définit la valeur à l'index spécifié. |
| Performance | O (1) |
public T this [int index] get if (index < Count) return _items[index]; throw new IndexOutOfRangeException(); set if (index < Count) _items[index] = value; else throw new IndexOutOfRangeException();
| Comportement | Renvoie true si la valeur fournie existe dans la collection. Sinon, il retourne faux. |
| Performance | Sur) |
public bool Contient (élément T) return IndexOf (élément)! = -1;
| Comportement | Retourne un IEnumerator instance qui permet d'énumérer les valeurs de liste de tableau dans l'ordre du premier au dernier. |
| Performance | Le renvoi de l'instance de l'énumérateur est une opération O (1). L'énumération de chaque élément est une opération O (n). |
Notez que nous ne pouvons pas simplement renvoyer à la _articles le tableau GetEnumerator car cela renverrait également les éléments qui ne sont pas actuellement remplis de données.
public System.Collections.Generic.IEnumerator GetEnumerator () pour (int i = 0; i < Count; i++) yield return _items[i]; System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() return GetEnumerator();
| Comportement | Supprime tous les éléments de la liste de tableaux. |
| Performance | O (1) |
Il y a deux options lors de la mise en œuvre Clair. Le tableau peut être laissé seul ou il peut être réaffecté en tant que tableau de longueur 0. Cette implémentation réalloue un nouveau tableau avec une longueur de zéro. Un tableau plus grand sera alloué lorsqu'un élément est ajouté au tableau à l'aide de la touche Ajouter ou Insérer les méthodes.
Public void Clear () _items = new T [0]; Compter = 0;
| Comportement | Copie le contenu du tableau interne du début à la fin dans le tableau fourni à partir de l'index de tableau spécifié. |
| Performance | Sur) |
Notez que la méthode ne se limite pas simplement à la _articles le tableau Copier méthode. En effet, nous voulons seulement copier la plage de l'index 0 à Compter, pas toute la capacité du tableau. En utilisant Tableau.Copie nous permet de spécifier le nombre d'éléments à copier.
public void CopyTo (T [] tableau, int tableauIndex) Array.Copy (_items, 0, tableau, arrayIndex, Count);
| Comportement | Retourne un entier qui indique le nombre d'éléments actuellement dans la collection. Lorsque la liste est vide, la valeur est 0. |
| Performance | O (1) |
Compter est simplement une propriété implémentée automatiquement avec un getter public et un setter privé. Le comportement réel se produit dans les fonctions qui manipulent le contenu de la collection.
public int Count get; ensemble privé;
| Comportement | Renvoie false car la collection n'est pas en lecture seule.. |
| Performance | O (1) |
public bool IsReadOnly get return false;
