Helge Jensen wrote:[color=blue]
>
>
> Paul Delhanty wrote:
>[color=green]
>> 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.[/color]
>
>
> 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.
>[/color]
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 
