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

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

hi,

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'

Answer 6

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.

Answer 7

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]