I'm using SortedDictionary<Key, Value> to store a sorted list of Keys, but don't care to store the Values. The Key has one set of criteria for uniqueness and another for sorting (i.e., the properties that GetHashValue() and Equals(Object obj) use are different than the ones used by CompareTo(Key key)).
I know that it is only storing a reference to the Value, so the memory usage is small. In my use case, I'll never need to access the Value part of the KeyValuePair<Key, Value> stored in the dictionary.
Is there some convention specifying what kind of object to use for Value in these cases? I'm currently using the same object for both Key and Value, that is, the type is Dictionary<Key, Key> and the I'm using .Add(key, key) to add objects.
The same question applies to SortedList<Key, Value>, but I need the insertion performance of SortedDictionary<Key, Value> in this case.
If Value is a reference type, storing it would waste from 4 to 8 bytes, depending on whether the process is 32-bit or 64-bit. If Value is a value type, it may waste even more.
If you don't need it, you can set Value to Byte. You can't go lower than 1 byte even with an empty struct. You can set to any value, probably 0 is a good choice.
Ideally, if all you need is a set, you should use a set.
There's a SortedSet<T> in .NET 4.0+ which uses a tree internally. In fact, SortedDictionary<TKey, TValue> uses SortedSet<KeyValuePair<TKey, TValue>> internally.
The set counterpart of SortedList<TKey, TValue> is a List<T>, I guess. You'll just need to use binary search and insert values into sorted positions. Implementing ISet<T> should be simple.