Как отсортировать список с дубликатами ключей?

Question

У меня есть набор элементов / ключей, которые я читаю из двух разных конфигурационных файлов. Таким образом, ключи могут быть одинаковыми, но с разными значениями, связанными с каждым из них.

Я хочу перечислить их в отсортированном порядке. Что я могу сделать ? Я пробовал с SortedList классом, но он не позволяет дублировать ключи.

Как я могу это сделать?

например, скажем, у меня есть 3 элемента с ключами 1,2,3. Затем я получаю еще один элемент, имеющий ключ 2 (но другое значение). Затем я хочу, чтобы новый ключ вставлялся после существующего ключа 2, но до 3. Если я хочу найти элемент с ключом 2, то он должен идти после последнего добавленного ключа 2.

Обратите внимание, чем я пользуюсь .NET 2.0

Answer 1

Я предпочитаю использовать LINQ для такого типа вещей:

using System.Linq;

...

var mySortedList = myList.Orderby(l => l.Key)
                         .ThenBy(l => l.Value);

foreach (var sortedItem in mySortedList) {
    //You'd see each item in the order you specified in the loop here.
}

Примечание: вы должны использовать .NET 3.5 или более позднюю версию для этого.

Answer 2

Вам нужна функция сортировки с пользовательским IComparer . Теперь у вас есть icomparer по умолчанию, когда вы используете sort. это проверит значение поля.

Когда вы создаете пользовательский IComparer (вы делаете это в своем классе, реализуя интерфейс Icomparable ). что он делает: ваш объект проверяет себя на любой другой объект в списке, который вы сортируете.

это делается функцией. (не волнуйтесь, VS выполнит это при обновлении вашего интерфейса

public class  ThisObjectCLass : IComparable{

    public int CompareTo(object obj) {
            ThisObjectCLass something = obj as ThisObjectCLass ;
            if (something!= null) 
                if(this.key.CompareTo(object.key) == 0){
                //then:
                   if .....
                }
                else if(this.value "is more important then(use some logic here)" something.value){
                 return 1
                }
                else return -1
            else
               throw new ArgumentException("I am a dumb little rabid, trying to compare different base classes");
        }
}

читайте по ссылкам выше для лучшей информации.

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

Answer 3

Я сделал это, создав SortedList<int, List<string>>.Всякий раз, когда я нахожу дублирующий ключ, я просто вставляю значение в существующий список, связанный с ключом, уже присутствующим в объекте SortedList.Таким образом, у меня может быть список значений для определенного ключа.

Answer 4

Используйте свой собственный класс компаратора! Если ваши ключи в отсортированном списке целые, вы можете использовать, например, этот компаратор:

public class DegreeComparer : IComparer<int>
{
    #region IComparer<int> Members

    public int Compare(int x, int y)
    {
        if (x < y)
            return -1;
        else
            return 1;
    }

    #endregion
}

Для создания нового SortedList с помощью ключей intи строковые значения используют:

var mySortedList = new SortedList<int, string>(new DegreeComparer());

Answer 5

Если вас не интересует последовательность элементов с одинаковыми ключами, добавьте все в список и затем отсортируйте его по ключу:

static void Main(string[] args)
{
   List<KeyValuePair<int, MyClass>> sortedList = 
      new List<KeyValuePair<int, MyClass>>() {
         new KeyValuePair<int, MyClass>(4, new MyClass("four")), 
         new KeyValuePair<int, MyClass>(7, new MyClass("seven")),
         new KeyValuePair<int, MyClass>(5, new MyClass("five")),
         new KeyValuePair<int, MyClass>(4, new MyClass("four-b")),
         new KeyValuePair<int, MyClass>(7, new MyClass("seven-b"))
      };
   sortedList.Sort(Compare);
}
static int Compare(KeyValuePair<int, MyClass> a, KeyValuePair<int, MyClass> b)
{
   return a.Key.CompareTo(b.Key);
}

Если вы действительно хотите, чтобы элементы, вставленные позже, были после элементов, вставленных ранее, сортируйте их по мере вставки:

class Sorter : IComparer<KeyValuePair<int, MyClass>>
{

static void Main(string[] args)
{
   List<KeyValuePair<int, MyClass>> sortedList = new List<KeyValuePair<int, MyClass>>();
   Sorter sorter = new Sorter();
   foreach (KeyValuePair<int, MyClass> kv in new KeyValuePair<int, MyClass>[] {
      new KeyValuePair<int, MyClass>(4, new MyClass("four")), 
      new KeyValuePair<int, MyClass>(7, new MyClass("seven")),
      new KeyValuePair<int, MyClass>(5, new MyClass("five")),
      new KeyValuePair<int, MyClass>(4, new MyClass("four-b")),
      new KeyValuePair<int, MyClass>(4, new MyClass("four-c")),
      new KeyValuePair<int, MyClass>(7, new MyClass("seven-b")) })
   {
      sorter.Insert(sortedList, kv);
   }
   for (int i = 0; i < sortedList.Count; i++)
   {
      Console.WriteLine(sortedList[i].ToString());
   }
}
void Insert(List<KeyValuePair<int, MyClass>> sortedList, KeyValuePair<int, MyClass> newItem)
{
   int newIndex = sortedList.BinarySearch(newItem, this);
   if (newIndex < 0)
      sortedList.Insert(~newIndex, newItem);
   else
   {
      while (newIndex < sortedList.Count && (sortedList[newIndex].Key == newItem.Key))
         newIndex++;
      sortedList.Insert(newIndex, newItem);
   }
}
#region IComparer<KeyValuePair<int,MyClass>> Members

public int Compare(KeyValuePair<int, MyClass> x, KeyValuePair<int, MyClass> y)
{
   return x.Key.CompareTo(y.Key);
}

#endregion
}

Или вы можете иметь отсортированный список списков:

static void Main(string[] args)
{
   SortedDictionary<int, List<MyClass>> sortedList = new SortedDictionary<int,List<MyClass>>();
   foreach (KeyValuePair<int, MyClass> kv in new KeyValuePair<int, MyClass>[] {
      new KeyValuePair<int, MyClass>(4, new MyClass("four")), 
      new KeyValuePair<int, MyClass>(7, new MyClass("seven")),
      new KeyValuePair<int, MyClass>(5, new MyClass("five")),
      new KeyValuePair<int, MyClass>(4, new MyClass("four-b")),
      new KeyValuePair<int, MyClass>(4, new MyClass("four-c")),
      new KeyValuePair<int, MyClass>(7, new MyClass("seven-b")) })
   {
      List<MyClass> bucket;
      if (!sortedList.TryGetValue(kv.Key, out bucket))
         sortedList[kv.Key] = bucket = new List<MyClass>();
      bucket.Add(kv.Value);
   }
   foreach(KeyValuePair<int, List<MyClass>> kv in sortedList)
   {
      for (int i = 0; i < kv.Value.Count; i++ )
         Console.WriteLine(kv.Value[i].ToString());
   }
}

Я не уверен, что вы можете использовать инициализаторы списка в .NET 2.0, как я это делал в первом примере выше, но я уверен, что вы знаете, как заполнить список данными.

Answer 6

Как насчет этого

        SortedList<string, List<string>> sl = new SortedList<string, List<string>>();

        List<string> x = new List<string>();

        x.Add("5");
        x.Add("1");
        x.Add("5");
        // use this to load  
        foreach (string z in x)
        {
            if (!sl.TryGetValue(z, out x))
            {
                sl.Add(z, new List<string>());
            }

            sl[z].Add("F"+z);
        }
        // use this to print 
        foreach (string key in sl.Keys)
        {
            Console.Write("key=" + key + Environment.NewLine);

            foreach (string item in sl[key])
            {
                Console.WriteLine(item);
            }
        }

Answer 7

.NET не имеет огромной поддержки стабильных сортировок (это означает, что эквивалентные элементы сохраняют свой относительный порядок при сортировке). Однако вы можете написать свою собственную стабильную сортировку-вставку, используя List.BinarySearch и пользовательский IComparer<T> (который возвращает -1, если ключ меньше или равен цели, и +1, если больше ).

Обратите внимание, что List.Sort не является стабильной сортировкой, поэтому вам придется либо написать собственную процедуру стабильной быстрой сортировки, либо просто использовать сортировку вставкой для первоначального заполнения коллекции.

Answer 8

У меня была похожая проблема, когда я проектировал игру, похожую на концепцию игры в шахматы, в которой ваш компьютер делает ход.Мне нужно было иметь возможность сделать несколько фигур, чтобы сделать ход, и поэтому мне нужно было иметь несколько государств-членов.Каждое BoardState нужно было ранжировать в зависимости от положения фигур.Ради аргументации и простоты, скажем, моя игра была Noughts and Crosses, а я был Noughts, а компьютер - Crosses.Если состояние платы показывало 3 в ряду Noughts, то это лучшее состояние для меня, если оно показывает 3 в ряду крестов, то это худшее состояние для меня и лучшее для компьютера.Есть другие состояния во время игры, которые являются более благоприятными для одного или другого, и, кроме того, есть многократные состояния, которые приводят к ничьей, так как я могу оценивать это, когда есть равные оценки ранга.Вот что я придумал (заранее извиняюсь, если вы не программист на VB).

Мой класс для сравнения:

Class ByRankScoreComparer
    Implements IComparer(Of BoardState)

    Public Function Compare(ByVal bs1 As BoardState, ByVal bs2 As BoardState) As Integer Implements IComparer(Of BoardState).Compare
        Dim result As Integer = bs2.RankScore.CompareTo(bs1.RankScore) 'DESCENDING order
        If result = 0 Then
            result = bs1.Index.CompareTo(bs2.Index)
        End If
        Return result
    End Function
End Class

Мои объявления:

Dim boardStates As SortedSet(Of BoardState)(New ByRankScoreComparer)

Моя реализация State-State:

Class BoardState
    Private Shared BoardStateIndex As Integer = 0
    Public ReadOnly Index As Integer
    ...
    Public Sub New ()
        BoardStateIndex += 1
        Index = BoardStateIndex
    End Sub
    ...
End Class

Как вы можете видеть, RankScores поддерживаются в порядке убывания, и любые 2 состояния, имеющие одинаковый рейтинг, более позднее состояние переходит на дно, поскольку оно всегда будет иметь большийназначенный индекс и, таким образом, это позволяет дубликаты.Я также могу безопасно вызывать boardStates.Remove (myCurrentBoardState), который также использует компаратор, и компаратор должен возвращать значение 0, чтобы найти объект, подлежащий удалению.

Answer 9

В .NET 2.0 вы можете написать:

List<KeyValuePair<string, string>> keyValueList = new List<KeyValuePair<string, string>>();

// Simulate your list of key/value pair which key could be duplicate
keyValueList.Add(new KeyValuePair<string,string>("1","One"));
keyValueList.Add(new KeyValuePair<string,string>("2","Two"));
keyValueList.Add(new KeyValuePair<string,string>("3","Three"));

// Here an entry with duplicate key and new value
keyValueList.Add(new KeyValuePair<string, string>("2", "NEW TWO")); 

// Your final sorted list with one unique key
SortedList<string, string> sortedList = new SortedList<string, string>();

foreach (KeyValuePair<string, string> s in keyValueList)
{
    // Use the Indexer instead of Add method
    sortedList[s.Key] = s.Value;
}

Вывод:

[1, One]
[2, NEW TWO]
[3, Three]

Answer 10

Вы рассматривали класс NameValueCollection , поскольку он позволяет хранить несколько значений для каждого ключа? Вы можете, например, иметь следующее:

    NameValueCollection nvc = new NameValueCollection();
    nvc.Add("1", "one");
    nvc.Add("2", "two");
    nvc.Add("3", "three");

    nvc.Add("2", "another value for two");
    nvc.Add("1", "one bis");

и затем получить значения, которые вы могли бы иметь:

    for (int i = 0; i < nvc.Count; i++)
    {
        if (nvc.GetValues(i).Length > 1)
        {
            for (int x = 0; x < nvc.GetValues(i).Length; x++)
            {
                Console.WriteLine("'{0}' = '{1}'", nvc.GetKey(i), nvc.GetValues(i).GetValue(x));
            }
        }
        else
        {
            Console.WriteLine("'{0}' = '{1}'", nvc.GetKey(i), nvc.GetValues(i)[0]);
        }

    }

, которые дают вывод:

'1' = 'one'

'1' = 'один бис'

'2' = 'two'

'2' = 'другое значение для двоих'

'3' = 'три'