3

didn't find an answer to this.

I like KeyedCollection, because it keeps the insertion order and has ~O(1) key lookup times.

Now I am looking for a similar type that will sort on the key instead of the insertion order.

SortedDictionary does exactly that, however the implementation is exactly the opposite of what I want. Inserts are O(1), lookups O(log n). However, I would like lookups ~O(1) (e.g. hash table) and the inserts can be O(log n) (binary tree?).

Does this exist? Shouldn't be hard implementation wise...

Thanks

Cookie
  • 12,004
  • 13
  • 54
  • 83
  • As to third parties, C5 Generic Collection Library has a hashed linked list, which comes close, except that I would have to re-implement inserts to maintain order. And tbh, a hashed tree would be better. Will continue looking, but this is a bit frustrating. – Cookie Apr 11 '11 at 08:13

2 Answers2

5

There is no data structure in the .NET BCL that provides what you're looking for. Maybe there are 3rd party solutions out there.

In most cases, O(log n) will be sufficient. You might be micro-optimizing if you try to implement your own data structure.

However, the quickest way to do so might be by simply declaring a new class that has both a Dictionary and a SortedDictionary as private members. For all read methods, you'd choose the more efficient dictionary to return a value. For all write methods, you would handle both inner dictionaries and be careful that they'd stay in sync. This might be not the most memory efficient approach though. But if you like to optimize here, you'd have to re-implement most functionality of a hashtable.

herzmeister
  • 11,101
  • 2
  • 41
  • 51
  • If it were not implemented, and I wouldn't want to do it from scratch, the last approach seems like a good performance improvement. However, deletes would still be log(n). Ideally you want the Dictionary to point to tree member of the SortedDictionary for fast deletes as well. That would, however, come at the expense of longer lookups as you have to follow two references. As to whether this is micro-optimizing, surely this depends on the problem at hand? I think a lot of people wouldn't consider picking appropriate datastructures for a problem micro-optimizing anyway. – Cookie Apr 11 '11 at 07:27
1

I think OrderedBag might be what you want:

Frequent inserts into sorted collection

Community
  • 1
  • 1
sehe
  • 374,641
  • 47
  • 450
  • 633
  • OrderedBag actually has similar to worse performance and overhead as it can contain multiple keys of the same value. From the same thread though, OrderedSet seems to be the answer. From what I can tell so far. Thanks! – Cookie Apr 11 '11 at 07:23
  • Edit - OrderedSet doesn't have key lookup, so doesn't work unfortunately. – Cookie Apr 11 '11 at 07:37
  • SortedList? I have't further looked into this, but since you apparently have read the rest... :) – sehe Apr 11 '11 at 07:40