Différences

Ci-dessous, les différences entre deux révisions de la page.

--- lang:csharp:list [2017/07/16 14:47] – Modification de Dictionary root
+++ lang:csharp:list [2020/04/27 19:53] (Version actuelle) – mhtml -> html root
@@ Ligne 8: / Ligne 8: @@
 Pour savoir si c'est vide : ''!enumerable.Any()'' signifie ''isEmpty()''.
 =====Différents types=====
+====Généric====
 <sortable 3phase>
 ^  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) \\ \\ [[https://referencesource.microsoft.com/#mscorlib/system/collections/objectmodel/readonlycollection.cs|Source]], {{ :lang:csharp:list:readonlycollection_cs.maff |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. \\ [[https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs|Source]], {{ :lang:csharp:list:list_cs.maff |Archive}} |
+| ''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) \\ \\ [[https://referencesource.microsoft.com/#mscorlib/system/collections/objectmodel/readonlycollection.cs|readonlycollection.cs]], {{ :lang:csharp:list:readonlycollection.cs_2020-04-27_7_34_43_pm_.html |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. \\ [[https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs|list.cs]], {{ :lang:csharp:list:list.cs_2020-04-27_7_34_47_pm_.html |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedlist.cs|Source]], {{ :lang:csharp:list:sortedlist_cs.maff |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedlist.cs|Source]], {{ :lang:csharp:list:sortedlist.cs_2020-04-27_7_34_46_pm_.html |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/queue.cs|Source]], {{ :lang:csharp:list:queue.cs.htm.maff |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/queue.cs|Source]], {{ :lang:csharp:list:queue.cs_2020-04-27_7_34_43_pm_.html |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/queue.cs|Source]], {{ :lang:csharp:list:queue.cs.htm.maff |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/queue.cs|Source]], {{ :lang:csharp:list:queue.cs_2020-04-27_7_34_43_pm_.html |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. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs|Source]], {{ :lang:csharp:list:linkedlist_cs.maff |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. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/linkedlist.cs|Source]], {{ :lang:csharp:list:linkedlist.cs_2020-04-27_7_34_44_pm_.html |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, ... ([[https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs|Source]], {{ :lang:csharp:list:hashtable_cs.maff |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''. [[https://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs|Source]], {{ :lang:csharp:list:hashset_cs.maff |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, ... ([[https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs|Source]], {{ :lang:csharp:list:hashtable.cs_2020-04-27_7_34_51_pm_.html |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''. [[https://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs|Source]], {{ :lang:csharp:list:hashset.cs_2020-04-27_7_34_51_pm_.html |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é. [[https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs|Source]], {{ :lang:csharp:list:dictionary_cs.maff |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é. [[https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs|Source]], {{ :lang:csharp:list:dictionary.cs_2020-04-27_7_34_47_pm_.html |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. \\ [[http://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedset.cs|Source]], {{ :lang:csharp:list:sortedset.cs_2020-04-27_7_34_51_pm_.html |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''. \\ [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sorteddictionary.cs|Source]], {{ :lang:csharp:list:sorteddictionary.cs_2020-04-27_7_34_45_pm_.html |Archive le 27/04/2020}} |
 </sortable>
-| ''SortedSet<T>'' | Oui, ''Add'' renvoie ''false'' | ''Add'' | ''UnionWith'' |  -  |  Oui  | C'est un arbre Red-Black. [[http://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedset.cs|Source]], {{ :lang:csharp:list:sortedset_cs.maff |Archive}} |
+====Thread-safe====
-| ''SortedDictionary<T,U>'' | Oui, ''Add'' génère ''ArgumentException'' | ''Add'' |  Non  |  -  |  Oui  | Utilise en interne ''SortedSet''. [[https://referencesource.microsoft.com/#System/compmod/system/collections/generic/sorteddictionary.cs|Source]], {{ :lang:csharp:list:sorteddictionary_cs.maff |Archive}} |
+  * ''ConcurrentBag<T>'' : utilise une liste chainée en interne. [[https://referencesource.microsoft.com/#System/sys/system/collections/concurrent/ConcurrentBag.cs|Source]], {{ :lang:csharp:list:concurrentbag.cs_2020-04-27_7_34_47_pm_.html |Archive le 27/04/2020}}
+  * ''ConcurrentDictionary<T,U>'' : utilise un fonctionnement proche de HashSet. [[https://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs|Source]], {{ :lang:csharp:list:concurrentdictionary.cs_2020-04-27_7_34_52_pm_.html |Archive le 27/04/2020}}
+  * ''ConcurrentQueue<T>'' : utilise une liste chainée en interne dont chaque nœud contient de 32 éléments. [[https://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentQueue.cs|Source]], {{ :lang:csharp:list:concurrentqueue.cs_2020-04-27_7_34_46_pm_.html |Archive le 27/04/2020}}
+  * ''ConcurrentStack<T>'' : utilise une liste chainée en interne. [[https://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentStack.cs|Source]], {{ :lang:csharp:concurrentstack.cs_2020-04-27_7_34_44_pm_.html |Archive le 27/04/2020}}
 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.
@@ Ligne 39: / Ligne 45: @@
 liste.Insert(oldIndex - 1, item);
 </code>
+=====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''.