How to sort the list with duplicate keys?

Question

I have a set of elements/keys which I'm reading from two different config files. So the keys may be same but with different values associated with each of them.

I want to list them in the sorted order. What can I do ? I tried with SortedList class but it does not allow duplicate keys.

How can I do it?

e.g Lets say I have 3 elements with keys 1,2,3. Then i get one more element having key 2 (but different value). Then I want the new key to get inserted after existing key 2 but before 3. If I againg find an element with key 2, then it should go after most recently added key 2.

Please note than I'm using .NET 2.0

Fairleigh

Do you really care whether the elements with equal keys go before or after the existing elements? – Shir

Yes. I want to maintain the order as mentioned in my question – Fairleigh

Answer 1

I prefer to use LINQ for this type of thing:

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

Note: you must be using .NET 3.5 or later to accomplish this.

Prickly

Thank you but I'm using .NET 2.0 – Fairleigh

Yuck. This alone is reason enough to upgrade. – Prickly

this is not possible when using .net 2.0 so not an answer to his question – Attached

@nealv: you might want to take a look at the edit history of the question. You might notice that this information was not originally in the question text. – Prickly

I agree, but since his question changed this answer is no longer a relevant one, (no offence at all) – Attached

@Dave : You are right. I did not think of LINQ and so did not mention .NET framework version in my original question. But your answer is really helpful for me going forward. Thank you. – Fairleigh

I thought you wanted the newly added keys with equal values to go after the keys already in the list. This won't do that. This will sort items with equal key values based on value. – Shir

True enough, but how would you know that the items were different if they had the same key and value? ;-) I suppose if you had a InsertedTime member you could do something like .ThenByDescending(l => l.InsertedTime); – Prickly

Answer 2

what you need is a Sort function with a custom IComparer. What you have now is the default icomparer when you use sort. this will check on a field value.

When you create a custom IComparer (you do this in you class by implementing the Icomparable interface). what it does is: your object checks itself to every other object in the list you sort.

this is done by a function. (don't worry VS will implementd it when refering your interface

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

read on the links above for better information.

I know I had some troubles understanding this myself in the beginning, so for any extra help add a comment and I will elaborate

Attached

Answer 3

I did it by creating a SortedList<int, List<string>>. Whenever I find the duplicate key, I simply insert the value in the existing list associated with the key already present in the SortedList object. This way, I can have list of values for a particular key.

Fairleigh

@BlueRaja-DannyPflughoeft: There is a SortedList, but it does not allow duplicate keys. And note that my questions was specific to .NET 2.0. Anyway, from .NET 3.5 onward, the same problem can be solved using the the Lookup in Linq. See this link - msdn.microsoft.com/en-us/library/bb460184.aspx . – Fairleigh

I am aware of SortedList and Lookup. But these are both maps, not lists. There is no actual sorted list in C#. There is List.Sort(), but then inserting-then-sorting the list is an O(n log n) operation, whereas it should be simply O(log n) or O(n) in the worst case. – Clayborne

Answer 4

Use your own comparer class! If your keys in the sorted list are integers, you may use for example this comparer:

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
}

To instanciate a new SortedList with int keys and string values use:

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

Helbonnah

Answer 5

If you don't really care about the sequence of the elements with equal keys, add everything to a list and then sort it by key:

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

If you really want the items inserted later to be after those inserted earlier, sort them as they are inserted:

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
}

Or you could have a sorted list of lists:

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

I'm not sure if you can use List initializers in .NET 2.0 like I did in the first example above, but I'm sure you know how to populate a list with data.

Shir

Answer 6

.NET doesn't have huge support for stable sorts (meaning that equivalent elements maintain their relative order when sorted). However, you can write your own stable-sorted-insert using List.BinarySearch and a custom IComparer<T> (that returns -1 if the key is less than or equal to the target, and +1 if greater).

Note that List.Sort is not a stable sort, so you'd either have to write your own stable quicksort routine or just use insertion sort to initially populate the collection.

Mass

Answer 7

did you contemplate the NameValueCollection class as it allows you to store multiple values per key? you could for example have the following:

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

and then to retrieve the values you could have:

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

    }

which give the output:

'1' = 'one'

'1' = 'one bis'

'2' = 'two'

'2' = 'another value for two'

'3' = 'three'

Marciamarciano

Answer 8

In .NET 2.0 you can write :

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

Output :

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

Bolger

Answer 9

How about this

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

Acerb

Thanks for looking at the question. But SortedList is of no use. As mentioned in the question itself, I will have duplicate keys due to some reason and SortedList does not allow duplicate keys. – Fairleigh

@CSharpLearner, this answer doesn't use duplicate keys. Items with duplicate keys get added to a list, so if you iterate through the keys you get a list of unique keys. For any key you might have 1 or more values because each value is a list by itself. Meaning it's a SortedList of List for values. – Transcaucasia

Answer 10

I had a similar issue where I was designing a game similar to the concept of a Chess game where you have the computer make a move. I needed to have the possibility of multiple pieces being able to make a move and thus I needed to have multiple Board-States. Each BoardState needed to be ranked based on the position of the pieces. For argument sake and simplicity, say my game was Noughts and Crosses and I was Noughts and the Computer was Crosses. If the board-state was showing 3 in a row of Noughts then this is the best state for me, if it shows 3 in a row of Crosses then this is the worst state for me and best for the computer. There are other states during the game that are more favourible to one or the other and furthermore there are muliplte states that result in a Draw, so how do I go about ranking it when there are equal rank scores. This is what I came up with (apologise in advance if you are not a VB programmer).

My comparer class:

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

My declarations:

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

My Board-State implementation:

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

As you can see RankScores are maintained in descending order and any 2 states having the same rank-score the later state goes to the bottom as it will always have a greater assigned Index and thus this allows duplicates. I can also safely call boardStates.Remove(myCurrentBoardState) which also uses the comparer and the comparer must return a 0 value in order to locate the objected to be deleted.

Pitiable