A data structure in .NET that stores items as sorted and unique and requested by range (and not sorted)

Question

A script is a timeline of events, and I want to be able to query all the elements in a specific date range.

I am looking for a data structure in .NET (prior to version 4.0) that stores elements as sorted and unique (for example, using a comparator or a unique key). It should support adding / removing of no more logarithmic complexity and performing binary search with such complexity.

System.Collections.Generic.SortedSet looked the way I wanted, but its GetViewBetween() method returns a list containing the list, like a SortedSet.

I miss two things:

• Calling ToList() or listing a SortedSet is too expensive because the list is long. I need a return a List<T> method, not a SortedSet<T> .
• A call with an included / exclusive date range, of my choice, is impossible, and I need it too.

If you know a good library that contains such a data structure that is verified and familiar, I would really like to try it.

Thanks.

Answer 1

After a bit of reading, it looks like a SortedList or SortedDictionary is what you need. SortedList seems to use less memory and is technically a binary tree, where SortedDictionary is faster with unsorted data. In addition, they are very close relatives.

Here's a good question / answer for the differences: SortedList vs. SortedDictionary vs. Sort ()

Answer 2

The problem is that you want the data structure to be organized along two axes - your unique key and time. If you can exchange space for time, I would suggest different data structures (wrapped in your own class to ensure consistency) for each. You can use SortedList to track your keyword-targeted data. I believe this is based on the Red-Black Tree and should have the characteristics you want for keyword searches. Alternatively, if you do not need them ordered by key, you can use a simple dictionary.

To support date searching, you can have a B-tree (one implementation, note I have not tested: http://blog.daisley-harrison.com/blog/post/NET-Generic-BTree-Library-and-Source -Code.aspx ) by date. However, make sure it supports duplicate keys, as they may not be unique. It can contain either a copy of the data, or just a key associated with this timestamp.

All of these structures have log (n) or, better, search complexity. Enumerating items between two dates should be pretty efficient, with better performance coming with the B-Tree / Dictionary combination.