C # Сортируемая коллекция, позволяющая дублировать ключи

Я пишу программу, чтобы установить последовательность, в которой различные объекты будут появляться в отчете. Последовательность - это позиция (ячейка) Y в электронной таблице Excel.

Демо-часть кода ниже. Я хочу создать коллекцию, которая позволит мне добавлять несколько объектов, и я могу получить отсортированную коллекцию на основе последовательности

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

Я знаю, что этого SortedListне допустят, и искал альтернативу. Не хочу удалять дубликаты и уже пробовал List<KeyValuePair<int, object>>.

Спасибо.

Используйте свой собственный IComparer!

Как уже было сказано в некоторых других ответах, вы должны использовать свой собственный класс сравнения. Для этого я использую общий класс IComparer, который работает со всем, что реализует 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
}

Вы будете использовать его при создании экземпляра нового SortedList, SortedDictionary и т. Д .:

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

Здесь int - это ключ, который можно дублировать.

Вы можете смело использовать List <>. Список имеет метод Sort, перегрузка которого принимает IComparer. Вы можете создать свой собственный класс сортировщика как. Вот пример:

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

Я использую следующее:

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

}

Мой тестовый пример:

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

Выход:

1:cab
1:coconut
1:car
1:cat
2:door
2:dog
3:elephant

Проблема в том, что конструкция структуры данных не соответствует требованиям: необходимо хранить несколько заголовков для одного и того же XPos. Следовательно, SortedList<XPos, value>не должно быть значения Header, а должно быть значение List<Header>. Это простое и небольшое изменение, но оно решает все проблемы и позволяет избежать создания новых проблем, подобных другим предлагаемым решениям (см. Объяснение ниже):

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

Обратите внимание, что добавление «забавного» ключа, например добавление случайного числа или вид, что два XPos с одинаковым значением разные, приводит ко многим другим проблемам. Например, становится трудно или даже невозможно удалить определенный заголовок.

Также обратите внимание, что производительность сортировки намного лучше, если List<Header>нужно отсортировать только несколько , чем каждый Header. Пример: если имеется 100 XPos и ​​у каждого по 100 заголовков, Headerнеобходимо отсортировать 10000, а не 100 List<Header>.

Конечно, у этого решения есть и недостаток: если есть много XPos только с 1 заголовком, необходимо создать столько списков, что является накладными расходами.

Самое простое решение (по сравнению со всем вышеперечисленным): используйте SortedSet<T>, он принимает IComparer<SortableKey>класс, а затем реализуйте метод Compare следующим образом:

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

}

Спасибо большое за вашу помощь. Пытаясь найти больше, я нашел это решение. (Доступно на Stackoverflow.com в другом вопросе)

Сначала я создал класс, который инкапсулирует мои объекты для классов (заголовки, нижний колонтитул и т. Д.).

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

Итак, этот класс должен удерживать объекты, а PosX каждого объекта идет как 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));

В конце концов я получаю отсортированный список «Последовательностей».

Вы пробовали, Lookup<TKey, TElement>что позволит дублировать ключи http://msdn.microsoft.com/en-us/library/bb460184.aspx

Вы можете использовать SortedList, использовать свое значение для TKey и int (count) для TValue.

Вот пример: функция, сортирующая буквы слова.

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

    }

Этот класс коллекции будет поддерживать дубликаты и вставлять порядок сортировки для дубликата. Хитрость заключается в том, чтобы пометить элементы уникальным значением по мере их вставки, чтобы поддерживать стабильный порядок сортировки. Затем мы оборачиваем все это в интерфейс 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; }
    }
}

тестовый класс

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

}

Структура тегов

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

Помощник лямбда-компаратора

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

Проблема в том, что вы используете в качестве ключа что-то, что не является ключом (потому что это происходит несколько раз).

Поэтому, если у вас есть настоящие координаты, вам, возможно, следует взять Pointключ в качестве ключа для вашего SortedList.

Или вы создаете, List<List<Header>>где ваш первый индекс списка определяет x-позицию, а внутренний список индексирует y-позицию (или наоборот, если хотите).

Ключ (предназначенный каламбур) к этому состоит в том, чтобы создать IComparableкласс, основанный на равенстве и хешировании, но никогда не сравнивающий с 0, если не равен. Это можно сделать и создать с помощью пары бонусов - стабильной сортировки (то есть значения, добавленные в отсортированный список первыми, сохранят свою позицию) и ToString()могут просто вернуть фактическое значение ключевой строки.

Вот ключ структуры, который должен помочь:

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

Linq.Lookup - это круто, но если ваша цель - просто перебирать «ключи», позволяя их дублировать, вы можете использовать эту структуру:

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

Тогда вы можете написать:

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

HTH

Хитрость заключается в том, чтобы дополнить ваш объект уникальным ключом. См. Следующий тест, который прошел успешно. Я хочу, чтобы мои баллы отсортировывались по их значению X. Простое использование «голого» Point2D в моей функции сравнения приведет к удалению точек с одинаковым значением X. Поэтому я оборачиваю Point2D в класс тегов под названием 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});

}

Утилиты для этой работы есть

Компаратор, который принимает лямбду

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

Структура тегов

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

Вот как я решил проблему. Он предназначен для обеспечения потоковой безопасности, хотя вы можете просто удалить locks, если вам это не нужно. Также обратите внимание, что произвольный Insertпо индексу не поддерживается, потому что это может нарушить условие сортировки.

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

Создайте класс и запросите список:

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

Вот мой взгляд на это. Имейте в виду, здесь могут быть драконы, C # все еще для меня в новинку.

• Допускаются повторяющиеся ключи, значения хранятся в списке
• Я использовал его как сортированную очередь, отсюда и названия и методы

Применение:

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