C # Sortierbare Sammlung, die doppelte Schlüssel ermöglicht

94

Ich schreibe ein Programm, um eine Reihenfolge festzulegen, in der verschiedene Objekte im Bericht erscheinen. Die Sequenz ist die Y-Position (Zelle) in der Excel-Tabelle.

Ein Demo-Teil des Codes ist unten. Was ich erreichen möchte, ist eine Sammlung, mit der ich mehrere Objekte hinzufügen und eine sortierte Sammlung basierend auf der Reihenfolge erhalten kann

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

Ich weiß, dass die SortedList dies nicht zulässt, und habe nach einer Alternative gesucht. Ich will nicht zu beseitigen , die Duplikate und bereits versucht List<KeyValuePair<int, object>>.

Vielen Dank.

Mayur Kotlikar
quelle
1
Muss die Sammlung Einfügungen / Entfernungen unterstützen, nachdem sie die erste Mitgliederliste erhalten hat?
Ani
2
Was hat nicht funktioniert, als du es versucht hast List?
diceguyd30
Ich möchte nicht nur sortieren und das Objekt bekommen. Sondern ich möchte die gesamte sortierte Liste erhalten. Im folgenden Beispiel sollten also beide Header-Objekte vorhanden sein und nacheinander untereinander. Wenn ich ein weiteres Header-Objekt mit XPos = 2 hinzufüge, sollte ich 3 Objekte in der Liste haben, 2 Objekte mit XPos = 1 und das dritte als XPos = 2
Mayur Kotlikar
Nur eine Anmerkung: Wenn ich auf diese Art von Situation stoße, stelle ich fest, dass die generische Liste in Kombination mit dem wenig bekannten BinarySearch-Verhalten für nicht gefundene Elemente Wunder wirkt.
J Trana

Antworten:

76

Verwenden Sie Ihren eigenen IComparer!

Wie bereits in einigen anderen Antworten angegeben, sollten Sie Ihre eigene Vergleichsklasse verwenden. Aus diesem Grund verwende ich eine generische IComparer-Klasse, die mit allem funktioniert, was IComparable implementiert:

/// <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
}

Sie werden es verwenden, wenn Sie eine neue SortedList, SortedDictionary usw.:

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

Hier ist int der Schlüssel, der dupliziert werden kann.

Knasterbax
quelle
40
Sie können jedoch keinen Schlüssel daraus entfernen.
Shashwat
11
Ja das ist richtig, Shachwat! Sie können Remove (Schlüssel) oder IndexOfKey (Schlüssel) nicht verwenden, da der Vergleicher niemals 0 zurückgibt, um die Schlüsselgleichheit zu signalisieren. Sie können jedoch RemoveAt (Index) entfernen, um Elemente zu löschen, wenn Sie deren Index haben.
Knasterbax
1
Ich bin auch auf das gleiche Problem gestoßen, das ich verwendet habe SortedDictionary. Es ermöglicht auch das Entfernen.
Shashwat
10
Beachten Sie, dass Sie auf diese Weise die Reflexivität Ihres Komparators unterbrechen. Es kann (und wird) Dinge in BCL brechen.
Ghord
1
Dies sollte tatsächlich -1 zurückgeben, um die Ordnung
aufrechtzuerhalten
16

Sie können List <> sicher verwenden. Die Liste verfügt über eine Sortiermethode, deren Überladung IComparer akzeptiert. Sie können Ihre eigene Sortierklasse als erstellen. Hier ist ein Beispiel:

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
quelle
1
Ich möchte nicht nur sortieren und das Objekt bekommen. Sondern ich möchte die gesamte sortierte Liste erhalten. Im folgenden Beispiel sollten also beide Header-Objekte vorhanden sein und nacheinander untereinander. Wenn ich ein weiteres Header-Objekt mit XPos = 2 hinzufüge, sollte ich 3 Objekte in der Liste haben, 2 Objekte mit XPos = 1 und das dritte als XPos = 2
Mayur Kotlikar
1
In Ordnung, Sie wollen damit sagen, dass ein Element, sobald es in die Liste eingefügt wird, an der richtigen Position gemäß der Sortierung eingefügt werden sollte. Bitte korrigieren Sie mich, wenn Sie falsch liegen. Lassen Sie mich einen Blick darauf werfen, wir kommen gleich wieder
Dipti Mehta
Beachten Sie, dass List <T> .Sort abhängig von der Sammlungsgröße mehrere Sortieralgorithmen verwendet und nicht alle stabile Sortierungen sind. Daher werden der Sammlung hinzugefügte Objekte, die mit dem Äquivalent verglichen werden, möglicherweise nicht in der Reihenfolge angezeigt, in der sie hinzugefügt wurden.
stiller Ton
Ich entschied
mich für
10

Ich benutze folgendes:

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

}

Mein Testfall:

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

Die Ausgabe:

1:cab
1:coconut
1:car
1:cat
2:door
2:dog
3:elephant
user450
quelle
Tuple ist nicht in allen Versionen von .NET verfügbar, kann jedoch durch KeyValuePair <K, V>
Reuben
6

Das Problem ist, dass das Datenstrukturdesign nicht den Anforderungen entspricht: Es müssen mehrere Header für dasselbe XPos gespeichert werden. Daher SortedList<XPos, value>sollte nicht ein Wert von Header, sondern ein Wert von haben List<Header>. Es ist eine einfache und kleine Änderung, die jedoch alle Probleme löst und verhindert, dass neue Probleme wie bei anderen Lösungsvorschlägen entstehen (siehe Erklärung unten):

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

Bitte beachten Sie, dass das Hinzufügen eines "lustigen" Schlüssels, wie das Hinzufügen einer Zufallszahl oder das Vorgeben, dass 2 XPos mit demselben Wert unterschiedlich sind, zu vielen anderen Problemen führt. Zum Beispiel wird es schwierig oder sogar unmöglich, einen bestimmten Header zu entfernen.

Beachten Sie auch, dass die Sortierleistung viel besser ist, wenn nur wenige List<Header>als alle sortiert werden müssen Header. Beispiel: Wenn es 100 XPos gibt und jeder 100 Header hat, müssen 10000 Headerim Gegensatz zu 100 sortiert werden List<Header>.

Natürlich hat auch diese Lösung einen Nachteil: Wenn es viele XPos mit nur 1 Header gibt, müssen so viele Listen erstellt werden, was einen gewissen Aufwand bedeutet.

Peter Huber
quelle
Dies ist die einfachste Lösung. Überprüfen Sie auch SortedDictionary, es ist ähnlich, in einigen Fällen schneller.
Hogan
Dies ist eine wirklich gute Lösung. Man könnte diese Funktionalität ganz einfach in ein benutzerdefiniertes Sammlungsobjekt einbinden, und es wäre sehr nützlich. Guter Gedanke, danke, dass du Peter geteilt hast!
Adam P
5

Einfachste Lösung (im Vergleich zu allen oben genannten): Verwenden SortedSet<T>Sie diese Option, um eine IComparer<SortableKey>Klasse zu akzeptieren , und implementieren Sie dann die Compare-Methode auf folgende Weise:

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
quelle
4
Ich habe SortedSet <T> verwendet und T hatte eine eigene inkrementierende int-ID, die bei jeder Instanziierung inkrementiert wurde, um sicherzustellen, dass jedes T eindeutig ist, auch wenn die anderen Felder gleich sind.
Skychan
3
GetHashCode zum Vergleich ist gefährlich. Kann zu unerwarteten falschen Duplikaten führen. Es könnte die meiste Zeit funktionieren, aber ich würde es nie für etwas Ernstes verwenden.
Hogan
4

Vielen dank für Deine Hilfe. Bei der Suche nach mehr habe ich diese Lösung gefunden. (Verfügbar in Stackoverflow.com in anderer Frage)

Zuerst habe ich eine Klasse erstellt, die meine Objekte für Klassen (Kopf- und Fußzeilen usw.) kapselt.

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

Diese Klasse soll also die Objekte halten, und PosX jedes Objekts wird als int-Position angegeben

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

Was ich schließlich bekomme, ist die sortierte "Sequenz" -Liste.

Mayur Kotlikar
quelle
2

Haben Sie versucht Lookup<TKey, TElement>, dass doppelte Schlüssel http://msdn.microsoft.com/en-us/library/bb460184.aspx möglich sind?

Nasmi Sabeer
quelle
Vielen Dank. Mein Problem ist, dass die Objekte nicht nur von einem Typ sind (nur nicht von Header), diese können variieren (sagen wir Fußzeile, Seitenleiste usw.), sondern jedes hat XPos
Mayur Kotlikar
LookupIch glaube , es gibt auch keinen öffentlichen Konstrukteur . Irgendein guter Weg, um das zu umgehen?
Jeff B
1
@ JeffBridgman Sie müssen sich auf Linq verlassen. Sie können ToLookupauf jedem tun IEnumerable<T>.
Nawfal
7
Ja, es erlaubt doppelte Schlüssel, aber es wird nichts sortiert!
Roman Starkov
2

Sie können die SortedList verwenden, Ihren Wert für den TKey und int (count) für den TValue verwenden.

Hier ein Beispiel: Eine Funktion, die die Buchstaben eines Wortes sortiert.

    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é
quelle
2

Diese Auflistungsklasse verwaltet Duplikate und fügt die Sortierreihenfolge für das Duplikat ein. Der Trick besteht darin, die Elemente beim Einfügen mit einem eindeutigen Wert zu versehen, um eine stabile Sortierreihenfolge aufrechtzuerhalten. Dann packen wir alles in eine ICollection-Oberfläche.

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

eine Testklasse

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

}

Die Tagging-Struktur

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

Der Lambda-Vergleichshelfer

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);
    }
}
Bradgonesurfing
quelle
1

Das Problem ist, dass Sie etwas als Schlüssel verwenden, das kein Schlüssel ist (weil es mehrmals vorkommt).

Wenn Sie also echte Koordinaten haben, sollten Sie diese möglicherweise Pointals Schlüssel für Ihre SortedList verwenden.

Oder Sie erstellen einen List<List<Header>>Index , in dem Ihr erster Listenindex die x-Position und der innere Listenindex die y-Position definiert (oder umgekehrt, wenn Sie möchten).

Oliver
quelle
Ein Schlüssel kann mehrere Instanzen haben, solange er kein Primärschlüssel ist. Zumindest haben sie mir das in der Datenbankklasse gesagt, die ich besucht habe.
Amalgamate
1
Diese Antwort ist etwas kurz, erklärt aber das Problem richtig und bietet die richtige Lösung, dh die Verwendung von SortedList <int, List <Header>>. Dadurch bleibt der Header sortiert und es können viele Header auf demselben xPos gespeichert werden. Für ein Codebeispiel suchen Sie nach meiner Antwort. Ich habe eine dieser Antworten formuliert, da sie in die richtige Richtung weist. Bitte plus 1 meine Antwort auch, wenn Sie es für hilfreich halten.
Peter Huber
1

Der Schlüssel (Wortspiel beabsichtigt) besteht darin, eine IComparableKlasse auf Basis zu erstellen , die Gleichheit und Hashing beibehält, aber niemals mit 0 verglichen wird, wenn sie nicht gleich ist. Dies kann durchgeführt werden und kann mit ein paar Boni erstellt werden - stabile Sortierung (dh Werte, die zuerst zur sortierten Liste hinzugefügt werden, behalten ihre Position bei) undToString() können einfach den tatsächlichen Wert der Schlüsselzeichenfolge zurückgeben.

Hier ist ein Strukturschlüssel, der den Trick machen sollte:

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
quelle
Das ist eine schöne Idee. Ich habe das Konzept in eine benutzerdefinierte ICollection verpackt. Siehe stackoverflow.com/a/21625939/158285
Bradgonesurfing
0

Linq.Lookup ist cool und alles, aber wenn Ihr Ziel darin besteht, einfach die "Schlüssel" zu durchlaufen , während sie dupliziert werden können, können Sie diese Struktur verwenden:

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"),
};

Dann können Sie schreiben:

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

HTH

Michael Bahig
quelle
0

Der Trick besteht darin, Ihr Objekt mit einem eindeutigen Schlüssel zu erweitern. Siehe den folgenden Test, der bestanden wird. Ich möchte meine Punkte nach ihrem X-Wert sortieren. Wenn Sie in meiner Vergleichsfunktion nur einen nackten Point2D verwenden, werden Punkte mit demselben X-Wert entfernt. Also verpacke ich den Point2D in eine Tagging-Klasse namens 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});

}

Dienstprogramme, um diese Arbeit zu machen, sind

Ein Vergleicher, der ein Lambda nimmt

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

Eine Tagging-Struktur

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);
    }
}
Bradgonesurfing
quelle
Siehe meine andere Antwort für eine vollständige Zusammenfassung der oben genannten Konzepte in eine benutzerdefinierte ICollection-Klasse
Bradgonesurfing
0

So habe ich das Problem gelöst. Es soll threadsicher sein, obwohl Sie das locks einfach entfernen können, wenn Sie das nicht brauchen. Beachten Sie auch, dass ein beliebiger InsertIndex nicht unterstützt wird, da dies die Sortierbedingung verletzen könnte.

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
quelle
-1

Erstellen Sie eine Klasse und fragen Sie die Liste ab:

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
quelle
-1

Hier ist meine Meinung dazu. Seien Sie sich bewusst, hier könnten Drachen sein, C # ist für mich noch ziemlich neu.

  • Doppelte Schlüssel sind zulässig, Werte werden in einer Liste gespeichert
  • Ich habe es als sortierte Warteschlange verwendet, daher die Namen und Methoden

Verwendung:

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
quelle
QueueIn BCL gibt es bereits eine Klasse , die eine First-In- und First-Out-Sammlung von Elementen darstellt. Die Semantik Ihrer Klasse ist unterschiedlich. Ihre Klasse hat einen Anfang (wo Elemente aus der Warteschlange entfernt werden), aber kein Ende (ein Element kann überall eingefügt werden). Die EnqueueMethode in Ihrer Klasse ist also meiner Meinung nach bedeutungslos.
Theodor Zoulias
@TheodorZoulias Ja, das Benennen ist hier ein bisschen scheiße, aber ich denke kaum, dass es eine Abwertung verdient, es hat das, was OP braucht und es geht nur darum, die Eingabe- / Ausgabemethoden umzubenennen und neu zu implementieren. Warum heißt es so? Ich brauchte eine Struktur, die ich von Anfang an in einer while-Schleife leeren und neue Elemente basierend auf dem Prioritätswert hinzufügen kann. Also PriorityQueuewäre passender Name.
Solo
Das OP möchte eine sortierbare Sammlung, die doppelte Schlüssel zulässt. Ihre Klasse ist keine Sammlung , da sie nicht aufgezählt werden kann. Ich mag auch die Nutzung öffentlicher Felder nicht. Nehmen Sie die Abstimmungen nicht persönlich. Sie können den Reputationsschaden von 5 Downvotes mit einem einzigen Upvote ( -2 * 5 == +10) reparieren , es ist also keine große Sache. :-)
Theodor Zoulias