[2.0] Allow duplicate keys in a SortedList

I realize the purpose of a <key, value> SortedList is to make retrieval of a key/value pair quick and that's the purpose of using unique keys.

Is there a different generic class for this I'm overlooking or will I have to write my own?

If you could have duplicate keys then how would you retrieve a value corresponding to a key?

If you want more than one value for each key then make the TValue argument a type that can store more than one value. For instance, if you want string keys and int values then declare a SortedList<string, List<int>>.

Quote:

---

Originally Posted by jmcilhinney

If you could have duplicate keys then how would you retrieve a value corresponding to a key?

---

I see what you mean. I wasn't really concerned about retrieval, just the speed of inserting items then sorting - or inserting in order.

And correct me if I'm wrong but doesn't an ordered list use a binary tree for fast retrieval? Which is the reason you'd never be able to have duplicate keys.

Here's what I finally did:

Code:

---


struct Pair
{
        int size;
        string str;
};

List<Pair> listPair = new List<Pair>();


public class PairComparer : IComparer<Pair>
{
        // sorts in descending order
        public int Compare(Pair p1, Pair p2)
        {

                if (p1.size > p2.size)
                        return -1;

                if (p1.size < p2.size)
                        return 1;

                // equal
                return 0;
        }
}

listPair.Add(...)
listPair.Add(...)
listPair.Add(...)

listPair.Sort(new PairComparer());

---

What I'm concerned about is what algorithm Sort() actually uses to sort the List because I think it uses Bubble Sort :sick:

How can I implement a faster sorting algorithm with a generic List<Pair> ?

You should read the MSDN documentation for the SortedList and SortedDictionary classes for some details of how they're implemented and what the implications are.

It's ALWAYS a good idea to read the documentation first, before making any assumptions and before asking any questions. This is from the MSDN help topic for the List<T>.Sort method:

Quote:

---

This method uses System.Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

---

The Array.Sort method is used because a List maintains an internal array to contain its items.

Quote:

---

Originally Posted by jmcilhinney

The Array.Sort method is used because a List maintains an internal array to contain its items.

---

Interesting. I would have thought the underlying structure would be a linked list. I guess since linked lists and nodes were used so much by my C++ instructors to implement "Lists".

Also found this interesting:

Quote:

---

A SortedList is a hybrid between a Hashtable and an Array. When an element is accessed by its key using the Item indexer property, it behaves like a Hashtable. When an element is accessed by its index using GetByIndex or SetByIndex, it behaves like an Array.

---

That sounds like the standard SortedList. The Generic SortedList doesn't have those methods.

Quote:

---

Originally Posted by jmcilhinney

That sounds like the standard SortedList. The Generic SortedList doesn't have those methods.

---

I stand corrected.

I was on the old documentation describing the Systems.Collections.SortedList not System.Collections.Generic.SortedList<Tkey, Tvalue>

I was right about the Generic SortedList being a binary tree.

Quote:

---

The SortedList generic class is a binary search tree with O(log n) retrieval...

---