Helge Jensen wrote:
Paul Delhanty wrote:
I can't seem to find IndexOfKey on SortedDictionary. I can see
IndexOfKey on SortedList, but that is an array based implementation
rather than a red-black tree as per SortedDictionary, so I might
expect something like IndexOfKey.
Ups, sorry. I obviously mixed up those 2 when reading -- haven't looked
at .NET2 too much yet, so I mistakenly read it as SortedList.
Here are a few ideas for what you could do, although I must admit i
don't really like them as good as just being able to obtain some kind of
iterator at lookup-point from data-structures that have ordering ;)
- If the data is first built and then repeatedly looked up, you can
build the data in a SortedDictionary and when built, copy it to an array
which you can then index using the BinarySearch-functions
- Implement IDictionary<T> by extending SortedDictionary. Use a
seperate hash-table to track previous/next relations.
- Use introspection to get at the implementation of SortedDictionary
and hack up a class that will return a useable iterator. I don't think
the .NET runtime checks privacy, only the C# compiler -- don't quote me
on that though!
- Reimplement SortedDictionary yourself, (you know red/black trees are
just such fun ;) and let it exhibit the methods you need.
- Implement IDictionary<T> using std::map from C++ through the managed
extensions for C++, and expose enough methods to make it work.
Thanks once again for your reply.
I have reordered things so the data is first built and then repeatedly
queried, so I will do as you suggest with copying into an array and
using BinarySearch. That should be pretty efficient - like using a
sorted vector in STL.
As for the other suggestions, I don't really want to get into the
business of building and maintaining my own collections if I can help
it. If I had not been able to use the batch build first and then query
approach, I would probably have had to do one of the other things you
suggested though. Implementing using hash-tables to track previous-next
would probably have been fairly solid, even if less efficient than just
a straight red-black tree. Using introspection was not something that
occurred to me - I guess it would give the same o(log(n)) performance
for inserts etc, though I'm not sure about the constant term. As for
reimplementing, SortedDictionary, I have just reconstructed and built
the source code using Lutz Roeder's Reflector (
http://www.aisto.com/roeder/dotnet/ ), but there is quite a lot and I am
glad that I won't have to maintain it now. Using C++, would work
though, I want to compile everything as safe, so as to be able to run in
a partial trust environment, so it would have had to have been the new
managed STL. I read somewhere recently, (I can't remember where), that
managed STL might not ship with Visual C++ 2005.
Anyway, once again, thanks for your help.
Paul Delhanty
Cadcambridge Limited
http://www.cadcambridge.net 
