LG

Ceci est une ancienne révision du document !

Table des matières

Extension des IEnumerable
Différents types
Convertir une liste en un string avec un délimiteur
Déplacer une ligne dans une liste

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

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) Source, Archive	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. Source, Archive
`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
`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
`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
`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
`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), 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, 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
`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
`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

SortedDictionary<T,U> Oui, Add génère ArgumentException Add Non - Oui Utilise en interne SortedSet. Source, Archive

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