LG

Outils pour utilisateurs

Outils du site

Piste : • list
lang:csharp:list

Table des matières

Extension des IEnumerable

De base, un IEnumerable ne peut être utilisé que pour une seule chose, le foreach.

Il est cependant possible de pouvoir le doter des mêmes capacités qu'une liste via LINQ, simplement en ajoutant l'import using System.Linq;.

Il est alors possible de compter le nombre d'éléments .Count(), d'accéder à un élément de la liste .ElementAt(int), etc…

Pour savoir si c'est vide : !enumerable.Any() signifie isEmpty().

Différents types

Généric

Type Unique Ajouter Vérifier Consulter Taille Supprimer Trié Lecture seule Implémentation
List<T> Non $O(1)$ : Add (à la fin),
$O(n)$ : Insert (à la position X) 		$O(n)$ : Contains et *IndexOf $O(1)$ : [i]

$O(n)$ : Find* 		$O(1)$ : Count $O(n)$ : Remove* Non $O(1)$ : AsReadOnly() (l'objet encapsule la liste)

readonlycollection.cs, Archive le 27/04/2020 		Tableau (Array) de capacité 0 au début. A la première insertion, la capacité passe à 4 puis double à chaque fois que nécessaire avec un minimum à la nouvelle taille demandée pour InsertRange. La taille maximale est 0X7FEFFFFF (Array.MaxArrayLength). Insert et Remove appellent Array.Copy. Remove et Clear ne déduisent pas l'occupation mémoire.
list.cs, Archive le 27/04/2020
SortedList<T,U> Oui, Add génère ArgumentException $O(n)$ (insertion) + $O(log(n))$ (position) : Add $O(log(n))$ : ContainsKey et IndexOfKey

$O(n)$ : ContainsValue et IndexOfValue 		$O(log(n))$ : [Key] et TryGetValue $O(1)$ : Count $O(n)$ (suppression) + $O(log(n))$ (position) : Remove

$O(n)$ : RemoveAt 		Oui $O(1)$ : Keys et Values (l'objet encapsule la liste)
Stockage en mémoire identique à List.
Source, Archive le 27/04/2020
Queue<T> Non $O(1)$ : Enqueue $O(n)$ : Contains $O(1)$ : Peek $O(1)$ : Count $O(1)$ : Dequeue Non $O(n)$ : ToArray (pas un lien mais une copie) Buffer tournant de type FIFO.
Accès uniquement à la première valeur ajoutée (Peek : sans enlever ou Dequeue en enlevant).
Stockage en mémoire identique à List.
Source, Archive le 27/04/2020
Stack<T> Non $O(1)$ : Push $O(n)$ : Contains $O(1)$ : Peek $O(1)$ : Count $O(1)$ : Pop Non $O(n)$ : ToArray (pas un lien mais une copie) Accès uniquement à la dernière valeur ajoutée (Peek : sans enlever ou Pop en enlevant).
Stockage en mémoire identique à List.
Source, Archive le 27/04/2020
LinkedList<T> Non $O(1)$ : Add* $O(n)$ : Contains $O(n)$ : Find* $O(1)$ : Count $O(1)$ : Remove* Non $O(n)$ : CopyTo (pas un lien mais une copie) Liste doublement chaînée.
Les éléments sont stockées de façon discontinue en mémoire.
Source, Archive le 27/04/2020
HashSet<T>
* Les $O(1)$ sont
théoriques si
la liste chainée
est de longueur 1. 		Oui, Add renvoie false $O(1)$* : Add
$O(n)$ : UnionWith (boucle sur Add) 		$O(1)$* : Contains - $O(1)$ : Count $O(1)$* : Remove Non $O(n)$ : CopyTo (pas un lien mais une copie) Un HashSet possède :
* le nombre d'éléments,
* le nombre maxi d'éléments (au début 0 puis 3, 7, 11, … (Source, Archive le 27/04/2020), jusqu'à 7199369 automatiquement, au delà, calcul manuel et chute de la performance),
* un tableau de taille “Nombre d'éléments maxi” dont chaque élément pointe vers un début d'une liste chaînée. Chaque élément est stocké dans la liste à l'indice HashCode % TailleMaxiTableau,
* un tableau de taille “Nombre d'éléments maxi” qui stocke chaque élément unitaire d'une liste chaînée où next pointe vers l'indice dans le tableau (-1 pour fin de la liste).
Si on modifie la taille maxi du tableau (un resize est forcé si le nombre de collisions de HashCode % TailleMaxiTableau est supérieur à 100), on passe au nombre premier suivant dans la liste, on modifie la taille des deux tableaux et on recalcule dans quelle liste chaînée doit être stockée chaque élément en fonction du nouveau HashCode % TailleMaxiTableau. Source, Archive le 27/04/2020
Dictionary<T,U> Oui, Add génère ArgumentException $O(1)$* : Add $O(1)$* : ContainsKey
$O(n)$ : ContainsValue 		$O(1)$* : [Key] et TryGetValue $O(1)$ : Count $O(1)$* : Remove Non $O(1)$ : Keys et Values (l'objet encapsule la liste) Stockage en mémoire identique à HashSet sur la clé. Source, Archive le 27/04/2020
SortedSet<T> Oui, Add renvoie false $O(log(n))$ : Add,
$O(n \cdot log(n))$ : UnionWith (boucle sur Add) 		$O(log(n))$ : Contains - $O(1)$ : Count $O(log(n))$ : Remove Oui $O(n)$ : CopyTo (pas un lien mais une copie) C'est un arbre Red-Black.
Les éléments sont stockées de façon discontinue en mémoire.
Source, Archive le 27/04/2020
SortedDictionary<T,U> Oui, Add génère ArgumentException $O(log(n))$ : Add $O(log(n))$ : ContainsKey
$O(n)$ : ContainsValue 		$O(log(n))$ : [Key] et TryGetValue $O(1)$ : Count $O(log(n))$ : Remove Oui $O(1)$ : Keys et Values (l'objet encapsule la liste) Utilise en interne SortedSet.
Source, Archive le 27/04/2020

Thread-safe

Note : $O(n)$ peut signifier deux choses : soit qu'il faut lire / écrire entre 1 et toutes les valeurs, soit qu'il faut obligatoirement lire toutes les valeurs. $O(log(n))$ correspond par exemple à une recherche dichotomique.

Convertir une liste en un string avec un délimiteur

string.Join(", ", new List<int> { 1, 2, 3, 4 });

Déplacer une ligne dans une liste

Pas de méthode miracle :

Pour List 

T item = liste[oldIndex];
liste.RemoveAt(oldIndex);
liste.Insert(oldIndex - 1, item);

Implémenter une classe supportant foreach

Soit une structure qui possède une List privée.

Il suffit d'avoir la propriété GetEnumerator qui renvoie vers celle de List.

lang/csharp/list.txt · Dernière modification : 2020/04/27 19:53 de root