System.Collections.Generic.SortedDictionary - lookup and then iterateto next/previous in o(log(n)) t

[Paul Delhanty]

Hi,

I am converting an existing native C++ program making heavy use of STL
to C#2.0 with STL usage replaced by the new generic collections. The
conversion has gone well to the point where I am replacing an STL map
instance by a System.Collections.Generic.SortedDictionary instance. In
need the collection to be ordered, and to have o(log(n)) look up - that
is fine so far SortedDictionary.TryGetValue does the job. I also need
the ability after a lookup to iterate to the next and previous values in
o(log(n)) time or better. In STL this is easy because map::find returns
an iterator. However, I can't see how to perform the equivalent
operation for a SortedDictionary in o(log(n)) time. (Enumerating the
whole SortedDictionary is o(n) for both average and worst case.)

Have I missed anything obvious? SortedDictionary seems to be based on a
red-black tree - System.Collections.Generic.TreeSet - so the
data-structure appears to be rich enough, but the public methods of
SortedDictionary do not appear to allow access to the functionality I need.

Thanks in advance for any replies.

Paul Delhanty
Cadcambridge Limited
http://www.cadcambridge.net

 

[Helge Jensen]

Have I missed anything obvious? SortedDictionary seems to be based on a
red-black tree - System.Collections.Generic.TreeSet - so the
data-structure appears to be rich enough, but the public methods of
SortedDictionary do not appear to allow access to the functionality I need.

SortedDictionary can use the natural numbers as an iterator.

You can use IndexOfKey to obtain the index of your item. Then you can
add/subtract from that index and pass it to GetKey and GetByIndex to get
the Key/Value next to the original key.

Note, that you may need to "lock ( dict.SyncRoot )", during these
operations, and that you won't get an exception if the data-structure
changes while you are holding an index, unlike most other iterators in .NET.

 

[Paul Delhanty]

SortedDictionary can use the natural numbers as an iterator.

You can use IndexOfKey to obtain the index of your item. Then you can
add/subtract from that index and pass it to GetKey and GetByIndex to get
the Key/Value next to the original key.

Note, that you may need to "lock ( dict.SyncRoot )", during these
operations, and that you won't get an exception if the data-structure
changes while you are holding an index, unlike most other iterators in
.NET.

Thanks very much for your reply.

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.

Thanks for the lock ( dict.SyncRoot ) tip.

Paul Delhanty
Cadcambridge Limited
http://www.cadcambridge.net

 

[Helge Jensen]

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.

 

[Paul Delhanty]

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

 

[Helge Jensen]

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

That was a nice and sneaky approach... perhaps you should read the EULA,
just to make sure you're not on shaky ground

 

[Paul Delhanty]

That was a nice and sneaky approach... perhaps you should read the EULA,
just to make sure you're not on shaky ground

Luckily your first suggestion about building the data first and then
querying first worked better anyway, so I was able to throw the
reflector generated code away (I didn't want to maintain it anyway,
as it had a lot of legacy pre-generics stuff in there.)


Paul