[2.0] Allow duplicate keys in a SortedList

[wey97]

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?

[jmcilhinney]

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

[wey97]

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:

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

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

[jmcilhinney]

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:

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.

[wey97]

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:

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.

[jmcilhinney]

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

[wey97]

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.

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