Collection de sets C #?

488

Est-ce que quelqu'un sait s'il existe un bon équivalent à la Setcollection Java en C #? Je sais que vous pouvez imiter un ensemble en utilisant a Dictionaryou a HashTableen remplissant mais en ignorant les valeurs, mais ce n'est pas une manière très élégante.

c# .net collections set Omar Kooheji
la source

Réponses:

142

Essayez HashSet :

La classe HashSet (Of T) fournit des opérations d'ensemble hautes performances. Un ensemble est une collection qui ne contient aucun élément en double et dont les éléments ne sont pas dans un ordre particulier ...

La capacité d'un objet HashSet (Of T) est le nombre d'éléments que l'objet peut contenir. La capacité d'un objet HashSet (Of T) augmente automatiquement à mesure que des éléments sont ajoutés à l'objet.

La classe HashSet (Of T) est basée sur le modèle d'ensembles mathématiques et fournit des opérations d'ensembles hautes performances similaires à l'accès aux clés des collections Dictionary (Of TKey, TValue) ou Hashtable . En termes simples, la classe HashSet (Of T) peut être considérée comme une collection Dictionary (Of TKey, TValue) sans valeurs.

Une collection HashSet (Of T) n'est pas triée et ne peut pas contenir d'éléments en double ...

Leahn Novash
la source
8
Malheureusement, les HashSets n'ont été ajoutés que récemment. Si vous travaillez dans une version plus ancienne du framework, vous devrez vous en tenir à votre dictionnaire Munged <> ou Hashtable.
Greg D
413

Si vous utilisez .NET 3.5, vous pouvez utiliser HashSet<T>. Il est vrai que .NET ne prend pas en charge les ensembles aussi bien que Java.

Les PowerCollections de Wintellect peuvent également vous aider.

Jon Skeet
la source
16
Je soupçonne que Set est un mot-clé dans certaines langues, ce qui pourrait provoquer des problèmes.
Jon Skeet
3
@Manish: Non, ce n'est pas le cas. Voir la section 2.4.3 de la spécification C # 3. Il n'a qu'une signification particulière pour les propriétés.
Jon Skeet
28
La raison de l'appeler HashSet, au lieu de simplement Set, est la même qu'en Java - "Set" décrit une interface, tandis que "HashSet" décrit une implémentation - spécifiquement, il s'agit d'un Set soutenu par une Hash Map. De cette façon, nous savons (ou devrions fortement nous attendre) que l'insertion et l'accès doivent prendre le temps d'accès O (1), par rapport à un "LinkedListSet" qui nous amènerait à attendre que l'insertion et l'accès prennent le temps O (n).
David Souther
5
que voulez-vous dire par ".NET ne prend pas en charge les ensembles aussi bien que Java." Cet ensemble est-il en quelque sorte imparfait par rapport à Java?
Louis Rhys
34
@Louis: De quel ensemble parlez-vous? Java a de nombreuses implémentations différentes de Set pour diverses situations. .NET en avait un dans .NET 3.5 (HashSet) et deux dans .NET 4 (HashSet et SortedSet). Le fait que nous ayons dû attendre .NET 3.5 pour commencer est assez surprenant.
Jon Skeet
26

Si vous utilisez .NET 4.0 ou version ultérieure:

Dans le cas où vous avez besoin de trier, utilisez SortedSet<T>. Sinon, si vous ne le faites pas, utilisez-le HashSet<T>car c'est O(1)pour rechercher et manipuler des opérations. Alors SortedSet<T>est O(log n)pour la recherche et de manipuler les opérations.

Derek W
la source
13

J'utilise un wrapper autour d'un Dictionary<T, object>, stockant des valeurs nulles dans les valeurs. Cela donne O (1) ajouter, rechercher et supprimer sur les clés, et à toutes fins utiles agit comme un ensemble.

thecoop
la source
2
Vous devez dire que c'est à peu près équivalent à std :: unordered_set. std :: set est ordonné. Par exemple, vous pouvez trouver rapidement le point de départ et le point final d'une plage et parcourir du début à la fin, en visitant les éléments dans l'ordre des clés. SortedDictionary est à peu près équivalent à std :: set.
doug65536
11

Jetez un œil à PowerCollections sur CodePlex. Outre Set et OrderedSet, il a quelques autres types de collections utiles tels que Deque, MultiDictionary, Bag, OrderedBag, OrderedDictionary et OrderedMultiDictionary.

Pour plus de collections, il y a aussi la bibliothèque de collections génériques C5 .

dpan
la source
-5

Je sais que c'est un vieux thread, mais je rencontrais le même problème et j'ai trouvé que HashSet n'était pas très fiable car, étant donné la même graine, GetHashCode () a renvoyé des codes différents. Alors, j'ai pensé, pourquoi ne pas simplement utiliser une liste et masquer la méthode d'ajout comme celle-ci

public class UniqueList<T> : List<T>
{
    public new void Add(T obj)
    {
        if(!Contains(obj))
        {
            base.Add(obj);
        }
    }
}

Étant donné que List utilise la méthode Equals uniquement pour déterminer l'égalité, vous pouvez définir la méthode Equals sur votre type T pour vous assurer d'obtenir les résultats souhaités.

Bob Heck
la source
13
La raison pour laquelle vous ne voudriez pas utiliser ceci est à cause List.Containsde la O(n)complexité, ce qui signifie que votre Addméthode devient désormais également de la O(n)complexité. En supposant que la collection interne n'a pas besoin d'être redimensionnée, Addpour les deux, Listet HashMapdevrait être O(1)complexe. TLDR: Cela fonctionnera, mais c'est hacky et moins efficace.
Richard Marskell - Drackir
6
Bien sûr, si vos objets ne renvoient pas une valeur appropriée pour GetHashCode, vous ne devez pas les placer dans un conteneur basé sur le hachage. Il serait préférable de corriger GetHashCode que d'utiliser un conteneur moins efficace.
bmm6o