Collection triable C # qui permet la duplication des clés

95

J'écris un programme pour définir une séquence dans laquelle divers objets apparaîtront dans le rapport. La séquence est la position Y (cellule) sur la feuille de calcul Excel.

Une partie démo du code est ci-dessous. Ce que je veux accomplir est d'avoir une collection, ce qui me permettra d'ajouter plusieurs objets et je pourrai obtenir une collection triée en fonction de la séquence

SortedList list = new SortedList();

Header h = new Header();
h.XPos = 1;
h.name = "Header_1";
list.Add(h.XPos, h);

h = new Header();
h.XPos = 1;
h.name = "Header_2";
list.Add(h.XPos, h);

Je sais que le SortedListne permettra pas cela et j'ai cherché une alternative. Je ne veux pas éliminer les doublons et déjà essayé List<KeyValuePair<int, object>>.

Merci.

Mayur Kotlikar
la source
1
La collection doit-elle prendre en charge les insertions / suppressions après avoir reçu la liste initiale des membres?
Ani
2
Qu'est-ce qui n'a pas fonctionné lorsque vous avez essayé List?
diceguyd30
Je ne veux pas simplement trier et récupérer l'objet. Mais je veux plutôt obtenir la liste triée entière. Ainsi, dans l'exemple ci-dessous, les deux objets Header doivent exister et dans l'ordre l'un sous l'autre. Si j'ajoute un autre objet Header avec XPos = 2, je devrais alors avoir 3 objets dans la liste, 2 objets avec XPos = 1 et le troisième comme XPos = 2
Mayur Kotlikar
Juste une note: lorsque je rencontre ce type de situation, je trouve que la liste générique en combinaison avec le comportement peu connu de BinarySearch pour les éléments non trouvés fonctionne à merveille.
J Trana

Réponses:

76

Utilisez votre propre IComparer!

Comme déjà indiqué dans d'autres réponses, vous devez utiliser votre propre classe de comparaison. Pour cela, j'utilise une classe IComparer générique, qui fonctionne avec tout ce qui implémente IComparable:

/// <summary>
/// Comparer for comparing two keys, handling equality as beeing greater
/// Use this Comparer e.g. with SortedLists or SortedDictionaries, that don't allow duplicate keys
/// </summary>
/// <typeparam name="TKey"></typeparam>
public class DuplicateKeyComparer<TKey>
                :
             IComparer<TKey> where TKey : IComparable
{
    #region IComparer<TKey> Members

    public int Compare(TKey x, TKey y)
    {
        int result = x.CompareTo(y);

        if (result == 0)
            return 1;   // Handle equality as beeing greater
        else
            return result;
    }

    #endregion
}

Vous l'utiliserez lors de l'instanciation d'une nouvelle SortedList, SortedDictionary etc:

SortedList<int, MyValueClass> slist = new SortedList<int, MyValueClass>(new DuplicateKeyComparer<int>());

Ici, int est la clé qui peut être dupliquée.

Knasterbax
la source
40
Mais vous ne pourrez en retirer aucune clé.
Shashwat
11
Oui c'est vrai, Shachwat! Vous ne pouvez pas utiliser Remove (key) ou IndexOfKey (key), car le comparateur ne renvoie jamais 0 pour signaler l'égalité de clé. Mais vous pouvez RemoveAt (index) pour supprimer des éléments si vous avez leur index.
Knasterbax
1
J'ai également rencontré le même problème, que j'ai utilisé SortedDictionary. Il permet également le retrait.
Shashwat
10
Notez que vous rompez la réflexivité de votre comparateur de cette façon. Cela peut (et va) casser des choses dans BCL.
ghord
1
cela devrait en fait retourner -1 pour maintenir l'ordre
M.kazem Akhgary
16

Vous pouvez utiliser List <> en toute sécurité. La liste a une méthode Sort, dont une surcharge accepte IComparer. Vous pouvez créer votre propre classe de tri au format. Voici un exemple:

private List<Curve> Curves;
this.Curves.Sort(new CurveSorter());

public class CurveSorter : IComparer<Curve>
{
    public int Compare(Curve c1, Curve c2)
    {
        return c2.CreationTime.CompareTo(c1.CreationTime);
    }
}
Dipti Mehta
la source
1
Je ne veux pas simplement trier et récupérer l'objet. Mais je veux plutôt obtenir la liste triée entière. Ainsi, dans l'exemple ci-dessous, les deux objets Header doivent exister et dans l'ordre l'un sous l'autre. Si j'ajoute un autre objet Header avec XPos = 2, je devrais alors avoir 3 objets dans la liste, 2 objets avec XPos = 1 et le troisième comme XPos = 2
Mayur Kotlikar
1
d'accord, vous voulez dire que le moment même où un élément est inséré dans la liste, il doit être inséré dans la bonne position selon le tri. Veuillez me corriger si vous avez tort. Laissez-moi jeter un oeil, je reviendrai dans un court instant
Dipti Mehta
Notez que List <T> .Sort utilise plusieurs algorithmes de tri en fonction de la taille de la collection et tous ne sont pas des tris stables. Ainsi, les objets ajoutés à la collection qui se comparent à l'équivalent peuvent ne pas apparaître dans l'ordre dans lequel ils ont été ajoutés.
ton silencieux
J'ai choisi cette option pour pouvoir arrêter de créer des quantités excessives de KeyValuePairs en appliquant des fonctions de réduction à un dictionnaire
Chris Marisic
10

J'utilise ce qui suit:

public class TupleList<T1, T2> : List<Tuple<T1, T2>> where T1 : IComparable
{
    public void Add(T1 item, T2 item2)
    {
        Add(new Tuple<T1, T2>(item, item2));
    }

    public new void Sort()
    {
        Comparison<Tuple<T1, T2>> c = (a, b) => a.Item1.CompareTo(b.Item1);
        base.Sort(c);
    }

}

Mon cas de test:

[TestMethod()]
    public void SortTest()
    {
        TupleList<int, string> list = new TupleList<int, string>();
        list.Add(1, "cat");
        list.Add(1, "car");
        list.Add(2, "dog");
        list.Add(2, "door");
        list.Add(3, "elephant");
        list.Add(1, "coconut");
        list.Add(1, "cab");
        list.Sort();
        foreach(Tuple<int, string> tuple in list)
        {
            Console.WriteLine(string.Format("{0}:{1}", tuple.Item1,tuple.Item2));
        }
        int expected_first = 1;
        int expected_last = 3;
        int first = list.First().Item1;  //requires using System.Linq
        int last = list.Last().Item1;    //requires using System.Linq
        Assert.AreEqual(expected_first, first);
        Assert.AreEqual(expected_last, last);
    }

Le résultat:

1:cab
1:coconut
1:car
1:cat
2:door
2:dog
3:elephant
utilisateur450
la source
Tuple n'est pas disponible dans toutes les versions de .NET, mais peut être remplacé par KeyValuePair <K, V>
Reuben
6

Le problème est que la conception de la structure de données ne correspond pas aux exigences: il est nécessaire de stocker plusieurs en-têtes pour le même XPos. Par conséquent, SortedList<XPos, value>ne doit pas avoir une valeur de Header, mais une valeur de List<Header>. C'est un changement simple et léger, mais il résout tous les problèmes et évite de créer de nouveaux problèmes comme d'autres solutions suggérées (voir l'explication ci-dessous):

using System;
using System.Collections.Generic;

namespace TrySortedList {
  class Program {

    class Header {
      public int XPos;
      public string Name;
    }

    static void Main(string[] args) {
      SortedList<int, List<Header>> sortedHeaders = new SortedList<int,List<Header>>();
      add(sortedHeaders, 1, "Header_1");
      add(sortedHeaders, 1, "Header_2");
      add(sortedHeaders, 2, "Header_3");
      foreach (var headersKvp in sortedHeaders) {
        foreach (Header header in headersKvp.Value) {
          Console.WriteLine(header.XPos + ": " + header.Name);
        }
      }
    }

    private static void add(SortedList<int, List<Header>> sortedHeaders, int xPos, string name) {
      List<Header> headers;
      if (!sortedHeaders.TryGetValue(xPos, out headers)){
        headers = new List<Header>();
        sortedHeaders[xPos] = headers;
      }
      headers.Add(new Header { XPos = xPos, Name = name });
    }
  }
}

Output:
1: Header_1
1: Header_2
2: Header_3

Veuillez noter que l'ajout d'une touche "drôle", comme ajouter un nombre aléatoire ou prétendre que 2 XPos avec la même valeur sont différents, conduit à de nombreux autres problèmes. Par exemple, il devient difficile voire impossible de supprimer un en-tête particulier.

Notez également que les performances de tri sont bien meilleures si seulement quelques List<Header>- uns doivent être triés que tous Header. Exemple: s'il y a 100 XPos et que chacun a 100 en-têtes, 10000 Headerdoivent être triés au lieu de 100 List<Header>.

Bien sûr, cette solution a également un inconvénient: s'il y a beaucoup de XPos avec seulement 1 en-tête, autant de listes doivent être créées, ce qui est une surcharge.

Peter Huber
la source
C'est la solution la plus simple. Vérifiez également SortedDictionary, c'est similaire, plus rapide dans certains cas.
Hogan
C'est une très bonne solution. On pourrait assez facilement intégrer cette fonctionnalité dans un objet de collection personnalisé et ce serait très utile. Bonne réflexion, merci d'avoir partagé Peter!
Adam P
5

Solution la plus simple (par rapport à tout ce qui précède): utilisez SortedSet<T>, il accepte une IComparer<SortableKey>classe, puis implémentez la méthode Compare de cette façon:

public int Compare(SomeClass x, SomeClass y)
{
    var compared = x.SomeSortableKeyTypeField.CompareTo(y.SomeSortableKeyTypeField);
    if (compared != 0)
        return compared;

    // to allow duplicates
    var hashCodeCompare = x.GetHashCode().CompareTo(y.GetHashCode());
    if (hashCodeCompare != 0)
        return hashCodeCompare;

    if (Object.ReferenceEquals(x, y))
        return 0;

    // for weird duplicate hashcode cases, throw as below or implement your last chance comparer
    throw new ComparisonFailureException();

}
knocte
la source
4
J'ai utilisé SortedSet <T> et T avait son propre ID int incrémenté qui s'incrémentait à chaque instanciation pour s'assurer que chaque T est unique même si les autres champs sont identiques.
Skychan
3
GetHashCode pour la comparaison est dangereux. Peut conduire à de faux doublons inattendus. Cela peut fonctionner la plupart du temps, mais je ne l'utiliserais jamais pour quelque chose de sérieux.
Hogan
4

Merci beaucoup pour votre aide. En cherchant plus, j'ai trouvé cette solution. (Disponible sur Stackoverflow.com dans une autre question)

Tout d'abord, j'ai créé une classe qui encapsulerait mes objets pour les classes (en-têtes, pied de page, etc.)

public class MyPosition
{
    public int Position { get; set; }
    public object MyObjects{ get; set; }
}

Donc, cette classe est censée tenir sur les objets, et PosX de chaque objet va comme int Position

List<MyPosition> Sequence= new List<MyPosition>();
Sequence.Add(new MyPosition() { Position = 1, Headerobject });
Sequence.Add(new MyPosition() { Position = 2, Headerobject1 });
Sequence.Add(new MyPosition() { Position = 1, Footer });

League.Sort((PosA, PosB) => PosA.Position.CompareTo(PosB.Position));

Ce que j'obtiens finalement, c'est la liste triée "Séquence".

Mayur Kotlikar
la source
2

Avez-vous essayé Lookup<TKey, TElement>qui autorisera les clés en double http://msdn.microsoft.com/en-us/library/bb460184.aspx

Nasmi Sabeer
la source
Merci. Mon problème est que les objets ne seront pas seulement d'un type (mais pas en-tête), ils peuvent varier (disons pied de page, barre latérale, etc.) mais chacun aura XPos
Mayur Kotlikar
De plus, Lookupje crois qu'il n'y a pas de constructeur public . Un bon moyen de contourner cela?
Jeff B
1
@JeffBridgman vous devrez vous fier à Linq. Vous pouvez faire ToLookupsur n'importe quel IEnumerable<T>.
nawfal
8
Oui, cela permet la duplication des clés, mais il ne garde rien de trié!
Roman Starkov
2

Vous pouvez utiliser la SortedList, utiliser votre valeur pour la TKey et int (count) pour la TValue.

Voici un exemple: une fonction qui trie les lettres d'un mot.

    private string sortLetters(string word)
    {
        var input = new System.Collections.Generic.SortedList<char, int>();

        foreach (var c in word.ToCharArray())
        {
            if (input.ContainsKey(c))
                input[c]++;
            else
                input.Add(c, 1);
        }

        var output = new StringBuilder();

        foreach (var kvp in input)
        {
            output.Append(kvp.Key, kvp.Value);
        }

        string s;

        return output.ToString();

    }
Patrice Calvé
la source
2

Cette classe de collection conservera les doublons et insérera un ordre de tri pour le duplicata. L'astuce consiste à étiqueter les éléments avec une valeur unique lorsqu'ils sont insérés pour maintenir un ordre de tri stable. Ensuite, nous enveloppons le tout dans une interface ICollection.

public class SuperSortedSet<TValue> : ICollection<TValue>
{
    private readonly SortedSet<Indexed<TValue>> _Container;
    private int _Index = 0;
    private IComparer<TValue> _Comparer;

    public SuperSortedSet(IComparer<TValue> comparer)
    {
        _Comparer = comparer;
        var c2 = new System.Linq.Comparer<Indexed<TValue>>((p0, p1) =>
        {
            var r = _Comparer.Compare(p0.Value, p1.Value);
            if (r == 0)
            {
                if (p0.Index == -1
                    || p1.Index == -1)
                    return 0;

                return p0.Index.CompareTo(p1.Index);

            }
            else return r;
        });
        _Container = new SortedSet<Indexed<TValue>>(c2);
    } 

    public IEnumerator<TValue> GetEnumerator() { return _Container.Select(p => p.Value).GetEnumerator(); }

    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

    public void Add(TValue item) { _Container.Add(Indexed.Create(_Index++, item)); }

    public void Clear() { _Container.Clear();}

    public bool Contains(TValue item) { return _Container.Contains(Indexed.Create(-1,item)); }

    public void CopyTo(TValue[] array, int arrayIndex)
    {
        foreach (var value in this)
        {
            if (arrayIndex >= array.Length)
            {
                throw new ArgumentException("Not enough space in array");
            }
            array[arrayIndex] = value;
            arrayIndex++;
        }
    }

    public bool Remove(TValue item) { return _Container.Remove(Indexed.Create(-1, item)); }

    public int Count {
        get { return _Container.Count; }
    }
    public bool IsReadOnly {
        get { return false; }
    }
}

une classe de test

[Fact]
public void ShouldWorkWithSuperSortedSet()
{
    // Sort points according to X
    var set = new SuperSortedSet<Point2D>
        (new System.Linq.Comparer<Point2D>((p0, p1) => p0.X.CompareTo(p1.X)));

    set.Add(new Point2D(9,10));
    set.Add(new Point2D(1,25));
    set.Add(new Point2D(11,-10));
    set.Add(new Point2D(2,99));
    set.Add(new Point2D(5,55));
    set.Add(new Point2D(5,23));
    set.Add(new Point2D(11,11));
    set.Add(new Point2D(21,12));
    set.Add(new Point2D(-1,76));
    set.Add(new Point2D(16,21));

    var xs = set.Select(p=>p.X).ToList();
    xs.Should().BeInAscendingOrder();
    xs.Count.Should()
       .Be(10);
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,5,9,11,11,16,21});

    set.Remove(new Point2D(5,55));
    xs = set.Select(p=>p.X).ToList();
    xs.Count.Should()
       .Be(9);
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,9,11,11,16,21});

    set.Remove(new Point2D(5,23));
    xs = set.Select(p=>p.X).ToList();
    xs.Count.Should()
       .Be(8);
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,9,11,11,16,21});

    set.Contains(new Point2D(11, 11))
       .Should()
       .BeTrue();

    set.Contains(new Point2D(-1, 76))
        .Should().BeTrue();

    // Note that the custom compartor function ignores the Y value
    set.Contains(new Point2D(-1, 66))
        .Should().BeTrue();

    set.Contains(new Point2D(27, 66))
        .Should().BeFalse();

}

La structure de balisage

public struct Indexed<T>
{
    public int Index { get; private set; }
    public T Value { get; private set; }
    public Indexed(int index, T value) : this()
    {
        Index = index;
        Value = value;
    }

    public override string ToString()
    {
        return "(Indexed: " + Index + ", " + Value.ToString () + " )";
    }
}

public class Indexed
{
    public static Indexed<T> Create<T>(int indexed, T value)
    {
        return new Indexed<T>(indexed, value);
    }
}

L'assistant de comparaison lambda

public class Comparer<T> : IComparer<T>
{
    private readonly Func<T, T, int> _comparer;

    public Comparer(Func<T, T, int> comparer)
    {
        if (comparer == null)
            throw new ArgumentNullException("comparer");
        _comparer = comparer;
    }

    public int Compare(T x, T y)
    {
        return _comparer(x, y);
    }
}
bradgonesurf
la source
1

Le problème est que vous utilisez quelque chose comme clé qui n'est pas une clé (car cela se produit plusieurs fois).

Donc, si vous avez de vraies coordonnées, vous devriez peut-être prendre le Pointcomme clé de votre SortedList.

Ou vous créez un List<List<Header>>où votre premier index de liste définit la position x et l'index de liste interne la position y (ou vice versa si vous le souhaitez).

Oliver
la source
Une clé peut avoir plusieurs instances tant qu'il ne s'agit pas d'une clé primaire. Au moins c'est ce qu'ils m'ont dit dans le cours de bases de données que j'ai suivi.
fusionner le
1
Cette réponse est un peu courte, mais elle explique correctement le problème et fournit la bonne solution, c'est-à-dire en utilisant SortedList <int, List <Header>>. Cela maintient l'en-tête trié et peut stocker plusieurs en-têtes dans le même xPos. Pour un exemple de code, recherchez ma réponse. J'ai ajouté une de cette réponse, car elle pointe dans la bonne direction. S'il vous plaît plus 1 ma réponse aussi si vous pensez que c'est utile.
Peter Huber
1

La clé (jeu de mots) pour cela est de créer une IComparableclasse basée sur l'égalité et le hachage, mais qui ne se compare jamais à 0 si elle n'est pas égale. Cela peut être fait et peut être créé avec quelques bonus - un tri stable (c'est-à-dire que les valeurs ajoutées en premier à la liste triée conserveront leur position), et ToString()peut simplement renvoyer la valeur réelle de la chaîne de clé.

Voici une clé struct qui devrait faire l'affaire:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace System
{
    /// <summary>
    /// Defined in Totlsoft.Util.
    /// A key that will always be unique but compares
    /// primarily on the Key property, which is not required
    /// to be unique.
    /// </summary>
    public struct StableKey : IComparable<StableKey>, IComparable
    {
        private static long s_Next;
        private long m_Sequence;
        private IComparable m_Key;

        /// <summary>
        /// Defined in Totlsoft.Util.
        /// Constructs a StableKey with the given IComparable key.
        /// </summary>
        /// <param name="key"></param>
        public StableKey( IComparable key )
        {
            if( null == key )
                throw new ArgumentNullException( "key" );

            m_Sequence = Interlocked.Increment( ref s_Next );
            m_Key = key;
        }

        /// <summary>
        /// Overridden. True only if internal sequence and the
        /// Key are equal.
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override bool Equals( object obj )
        {
            if( !( obj is StableKey ) )
                return false;

            var dk = (StableKey)obj;

            return m_Sequence.Equals( dk.m_Sequence ) &&
                Key.Equals( dk.Key );
        }

        /// <summary>
        /// Overridden. Gets the hash code of the internal
        /// sequence and the Key.
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            return m_Sequence.GetHashCode() ^ Key.GetHashCode();
        }

        /// <summary>
        /// Overridden. Returns Key.ToString().
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            return Key.ToString();
        }

        /// <summary>
        /// The key that will be compared on.
        /// </summary>
        public IComparable Key
        {
            get
            {
                if( null == m_Key )
                    return 0;

                return m_Key;
            }
        }

        #region IComparable<StableKey> Members

        /// <summary>
        /// Compares this Key property to another. If they
        /// are the same, compares the incremented value.
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public int CompareTo( StableKey other )
        {
            var cmp = Key.CompareTo( other.Key );
            if( cmp == 0 )
                cmp = m_Sequence.CompareTo( other.m_Sequence );

            return cmp;
        }

        #endregion

        #region IComparable Members

        int IComparable.CompareTo( object obj )
        {
            return CompareTo( (StableKey)obj );
        }

        #endregion
    }
}
Bruce Pierson
la source
C'est une bonne idée. J'ai enveloppé le concept dans une ICollection personnalisée. Voir stackoverflow.com/a/21625939/158285
bradgonesurfing
0

Linq.Lookup est cool et tout, mais si votre cible est simplement de boucler sur les "clés" tout en leur permettant d'être dupliquées, vous pouvez utiliser cette structure:

List<KeyValuePair<String, String>> FieldPatterns = new List<KeyValuePair<string, string>>() {
   new KeyValuePair<String,String>("Address","CommonString"),
   new KeyValuePair<String,String>("Username","UsernamePattern"),
   new KeyValuePair<String,String>("Username","CommonString"),
};

Ensuite, vous pouvez écrire:

foreach (KeyValuePair<String,String> item in FieldPatterns)
{
   //use item.Key and item.Value
}

HTH

Michael Bahig
la source
0

L'astuce consiste à augmenter votre objet avec une clé unique. Voir le test suivant qui réussit. Je souhaite que mes points soient triés en fonction de leur valeur X. Le simple fait d'utiliser un Point2D nu dans ma fonction de comparaison entraînera l'élimination des points avec la même valeur X. J'emballe donc le Point2D dans une classe de marquage appelée Indexed.

[Fact]
public void ShouldBeAbleToUseCustomComparatorWithSortedSet()
{
    // Create comparer that compares on X value but when X
    // X values are uses the index
    var comparer = new 
        System.Linq.Comparer<Indexed<Point2D>>(( p0, p1 ) =>
        {
            var r = p0.Value.X.CompareTo(p1.Value.X);
            return r == 0 ? p0.Index.CompareTo(p1.Index) : r;
        });

    // Sort points according to X
    var set = new SortedSet<Indexed<Point2D>>(comparer);

    int i=0;

    // Create a helper function to wrap each point in a unique index
    Action<Point2D> index = p =>
    {
        var ip = Indexed.Create(i++, p);
        set.Add(ip);
    };

    index(new Point2D(9,10));
    index(new Point2D(1,25));
    index(new Point2D(11,-10));
    index(new Point2D(2,99));
    index(new Point2D(5,55));
    index(new Point2D(5,23));
    index(new Point2D(11,11));
    index(new Point2D(21,12));
    index(new Point2D(-1,76));
    index(new Point2D(16,21));
    set.Count.Should()
       .Be(10);
    var xs = set.Select(p=>p.Value.X).ToList();
    xs.Should()
      .BeInAscendingOrder();
    xs.ShouldBeEquivalentTo(new[]{-1,1,2,5,5,9,11,11,16,21});

}

Les utilitaires pour faire ce travail sont

Un comparateur qui prend un lambda

public class Comparer<T> : IComparer<T>
{
    private readonly Func<T, T, int> _comparer;

    public Comparer(Func<T, T, int> comparer)
    {
        if (comparer == null)
            throw new ArgumentNullException("comparer");
        _comparer = comparer;
    }

    public int Compare(T x, T y)
    {
        return _comparer(x, y);
    }
}

Une structure de balisage

public struct Indexed<T>
{
    public int Index { get; private set; }
    public T Value { get; private set; }
    public Indexed(int index, T value) : this()
    {
        Index = index;
        Value = value;
    }

    public override string ToString()
    {
        return "(Indexed: " + Index + ", " + Value.ToString () + " )";
    }
}

public class Indexed
{
    public static Indexed<T> Create<T>(int indexed, T value)
    {
        return new Indexed<T>(indexed, value);
    }
}
bradgonesurf
la source
Voir mon autre réponse pour un
aperçu
0

C'est ainsi que j'ai résolu le problème. Il est censé être thread-safe, bien que vous puissiez simplement supprimer les locks si vous n'en avez pas besoin. Notez également que l'arbitraire Insertà un index n'est pas pris en charge car cela pourrait violer la condition de tri.

public class ConcurrentOrderedList<Titem, Tsort> : ICollection<Titem>
{
    private object _lock = new object();
    private SortedDictionary<Tsort, List<Titem>> _internalLists;
    Func<Titem, Tsort> _getSortValue;
    
    public ConcurrentOrderedList(Func<Titem,Tsort> getSortValue)
    {
        _getSortValue = getSortValue;
        _internalLists = new SortedDictionary<Tsort, List<Titem>>();            
    }

    public int Count { get; private set; }

    public bool IsReadOnly => false;

    public void Add(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
            {
                values = new List<Titem>();
                _internalLists.Add(sortVal, values);
            }
            values.Add(item);
            Count++;
        }            
    }

    public bool Remove(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
                return false;

            var removed = values.Remove(item);
            if (removed)
                Count--;
            return removed;
        }
    }

    public void Clear()
    {
        lock (_lock)
        {
            _internalLists.Clear();
        }
    }

    public bool Contains(Titem item)
    {
        lock (_lock)
        {
            List<Titem> values;
            Tsort sortVal = _getSortValue(item);
            if (!_internalLists.TryGetValue(sortVal, out values))
                return false;
            return values.Contains(item);
        }
    }

    public void CopyTo(Titem[] array, int arrayIndex)
    {
        int i = arrayIndex;
        lock (_lock)
        {
            foreach (var list in _internalLists.Values)
            {
                list.CopyTo(array, i);
                i += list.Count;
            }
        }
    }

    public IEnumerator<Titem> GetEnumerator()
    {
        foreach (var list in _internalLists.Values)
        {
            foreach (var item in list)
                yield return item;
        }
    }

    public int IndexOf(Titem item)
    {
        int i = 0;
        var sortVal = _getSortValue(item);
        lock (_lock)
        {               
            foreach (var list in _internalLists)
            {
                if (object.Equals(list.Key, sortVal))
                {
                    int intIndex = list.Value.IndexOf(item);
                    if (intIndex == -1)
                        return -1;
                    return i + intIndex;
                }
                i += list.Value.Count;
            }
            return -1;
        }           
    }

    public void Insert(int index, Titem item)
    {
        throw new NotSupportedException();
    }

    // Note this method is indeterminate if there are multiple
    // items in the same sort position!
    public void RemoveAt(int index)
    {
        int i = 0;
        lock (_lock)
        {
            foreach (var list in _internalLists.Values)
            {
                if (i + list.Count < index)
                {
                    i += list.Count;
                    continue;
                }
                else
                {
                    list.RemoveAt(index - i);
                    return;
                }
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}
Peter Moore
la source
-1

Créez une classe et interrogez la liste:

Public Class SortingAlgorithm
{
    public int ID {get; set;}
    public string name {get; set;}
    public string address1 {get; set;}
    public string city {get; set;}
    public string state {get; set;}
    public int age {get; set;}
}

//declare a sorting algorithm list
List<SortingAlgorithm> sortAlg = new List<SortingAlgorithm>();

//Add multiple values to the list
sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age});
sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age});
sortAlg.Add( new SortingAlgorithm() {ID = ID, name = name, address1 = address1, city = city, state = state, age = age});

//query and order by the list
  var sortedlist = (from s in sortAlg
                    select new { s.ID, s.name, s.address1, s.city, s.state, s.age })
                                                     .OrderBy(r => r.ID)
                                                     .ThenBy(r=> r.name)
                                                     .ThenBy(r=> r.city)
                                                     .ThenBy(r=>r.state)
                                                     .ThenBy(r=>r.age);
Satty FL
la source
-1

Voici mon point de vue à ce sujet. Attention, voici peut-être des dragons, C # encore assez nouveau pour moi.

  • Les clés en double sont autorisées, les valeurs sont stockées dans une liste
  • Je l'ai utilisé comme file d'attente triée, d'où les noms et les méthodes

Usage:

SortedQueue<MyClass> queue = new SortedQueue<MyClass>();
// new list on key "0" is created and item added
queue.Enqueue(0, first);
// new list on key "1" is created and item added
queue.Enqueue(1, second);
// items is added into list on key "0"
queue.Enqueue(0, third);
// takes the first item from list with smallest key
MyClass myClass = queue.Dequeue();
class SortedQueue<T> {
  public int Count;
  public SortedList<int, List<T>> Queue;

  public SortedQueue() {
    Count = 0;
    Queue = new SortedList<int, List<T>>();
  }

  public void Enqueue(int key, T value) {
    List<T> values;
    if (!Queue.TryGetValue(key, out values)){
      values = new List<T>();
      Queue.Add(key, values);
      Count += 1;
    }
    values.Add(value);
  }

  public T Dequeue() {
    if (Queue.Count > 0) {
      List<T> smallest = Queue.Values[0];
      if (smallest.Count > 0) {
        T item = smallest[0];
        smallest.Remove(item);
        return item;
      } else {
        Queue.RemoveAt(0);
        Count -= 1;
        return Dequeue();
      }
    }
    return default(T);
  }
}
Solo
la source
Il existe déjà une classe Queuedans BCL, qui représente une collection d'éléments premier entré, premier sorti. La sémantique de votre classe est différente. Votre classe a un début (où les éléments sont retirés de la file d'attente) mais pas de fin (un élément peut être inséré n'importe où). Donc, la Enqueueméthode dans votre classe n'a aucun sens à mon humble avis.
Theodor Zoulias le
@TheodorZoulias Oui, le nommage est un peu merdique ici mais je ne pense pas que cela mérite un vote défavorable, il a ce dont OP a besoin et il ne s'agit que de renommer et de réimplémenter les méthodes d'entrée / sortie. Pourquoi ça s'appelle comme ça? J'avais besoin d'une structure que je puisse vider dès le début dans une boucle while et ajouter de nouveaux éléments en fonction de la valeur de priorité. Ce PriorityQueueserait donc un nom plus approprié.
Solo le
L'OP veut une collection triable qui autorise la duplication des clés. Votre classe n'est pas une collection , car elle ne peut pas être énumérée. Je n'aime pas non plus l'utilisation des champs publics. Ne prenez pas personnellement les votes négatifs. Vous pouvez réparer les dommages à la réputation de 5 votes négatifs avec un seul vote positif ( -2 * 5 == +10), donc ce n'est pas un gros problème. :-)
Theodor Zoulias