Thomas T. Veldhouse <ve*****@yahoo.comwrote:
Bruce Wood <br*******@canada.comwrote:
>>
Then use System.Collections.SortedList. SortedList is just a Hashtable
that also maintains the entries sorted by key value. You can do all of
the hashing you used to do, plus index into the i-th entry in order by
key, which is what you want to do.
I do believe you lose the constant lookup times of a hashtable when using a
sorted list; if that is important to you.
It appears that I was incorrect.
"The SortedList generic class is a binary search tree with O(log n) retrieval,
where n is the number of elements in the dictionary. In this, it is similar to
the SortedDictionary generic class. The two classes have similar object
models, and both have O(log n) retrieval. Where the two classes differ is in
memory use and speed of insertion and removal:
SortedList uses less memory than SortedDictionary.
SortedDictionary has faster insertion and removal operations for unsorted
data, O(log n) as opposed to O(n) for SortedList.
If the list is populated all at once from sorted data, SortedList is faster
than SortedDictionary."
However, I am correct in indicating that simply using a Dictionary (or
Hashtable) will be much faster than using a SortedList.
"The Dictionary generic class provides a mapping from a set of keys to a set
of values. Each addition to the dictionary consists of a value and its
associated key. Retrieving a value by using its key is very fast, close to
O(1), because the Dictionary class is implemented as a hash table."
O(1) is much faster than O(log n) or O(n). Lookup time is constant in all
cases, but with the SortedLists it is based upon the size of the list.
--
Thomas T. Veldhouse
Key Fingerprint: 2DB9 813F F510 82C2 E1AE 34D0 D69D 1EDC D5EC AED1