Is there an IDictionary implementation that keeps the keys in the order they were added ? (NOT sorted order)

Question

I guess everything is in the title...

I know that Dictionary<TKey,TValue> does keep the keys in addition order, but only as long as you don't remove any, and anyway this behavior is not documented and can't be relied upon (see this question for details).

Basically, what collection should I use if I want an ordered collection of key/value pairs, while keeping an O(1) access time? (List<KeyValuePair<K,V>> isn't a good option since it would have O(n) access time). I don't think there is anything like that in the BCL, but I just want to be sure before I roll my own...

Just to make it clear to everyone: I don't want the keys to be sorted, I just want them to remain in addition order. So SortedList/SortedDictionary are not what I'm looking for...

score 2 · Answer 1 · answered Nov 07 '11 at 21:55

2

If you can accept non-generic, then System.Collections.Specialized.OrderedDictionary may do what you need. Otherwise, I would be tempted to write a wrapper that combines a list and dictionary, using the list for GetEnumerator and the dictionary for the indexer.

answered Nov 07 '11 at 21:55

Marc Gravell

1,026,079
266
2,566
2,900

Thanks, it seems to be what I'm looking for... too bad it's not generic :(. – Thomas Levesque Nov 07 '11 at 21:58
I guess I could write a generic wrapper, but I would lose performance for value types because of boxing, so I guess I will eventually implement my own... – Thomas Levesque Nov 07 '11 at 22:02
@ThomasLevesque - Generic collections usually don't require boxing. – H H Nov 07 '11 at 22:07
@Henk `OrderedDictionary` is non-generic. It depends on what the values are of course; it it maps a string to a class: no boxing. – Marc Gravell Nov 07 '11 at 22:08
Right, I kind of missed it was about the 1st option. – H H Nov 07 '11 at 22:10

score 2 · Accepted Answer · answered Nov 07 '11 at 21:57

2

Could you perhaps just keep a List and a Dictionary that allows you to lookup where keys are in the list? That would allow you to get the key/value pairs in order of addition but still maintain O(1) lookup.

answered Nov 07 '11 at 21:57

Stuart Golodetz

20,238
4
51
80

Eventually I used a `LinkedList` rather than a simple `List`, but the idea is the same... – Thomas Levesque Nov 07 '11 at 23:09

score 1 · Answer 3 · answered Nov 07 '11 at 21:56

1

So, you don't want an associative container and the order is completely based on insertion order... why don't you simply use a basic array?

answered Nov 07 '11 at 21:56

Brandon Moretz

7,512
3
33
43

2

I'm assuming the lookup may also be by the key, which is not necessarily the same as the int-index. – Marc Gravell Nov 07 '11 at 21:58
As Marc says, I want to lookup items by key; and I don't know beforehand how many items there will be, so an array is not a practical option. – Thomas Levesque Nov 07 '11 at 21:59

score 1 · Answer 4 · answered Nov 07 '11 at 21:56

1

"Addition order" is not normally an issue for a Dictionary, so don't expect one int a std library.

It is of course possible but will always come at the cost of performance. If you find O(1) lookup important I would suggest a wrapper containing a Dictionary<K,V> and an coupled List<K>. Add and Remove will become slower.

answered Nov 07 '11 at 21:56

H H

263,252
30
330
514

Thanks, that's probably what I'll do – Thomas Levesque Nov 07 '11 at 22:03
Actually, Add and Remove don't have to be slower: I used a `LinkedList>` and a `Dictionary>>`, so all operations are O(1), unless I'm missing something... (except access by index if it was needed, but it's not) – Thomas Levesque Nov 07 '11 at 23:11
O(1), yes. But with different constants. – H H Nov 07 '11 at 23:13

score 0 · Answer 5 · answered Nov 07 '11 at 21:53

0

You could use a SortedDictionary with a custom IComparer that maintains the insertion order. Whether you want to wrap this in your own more convenient interface is up to you, of course.

answered Nov 07 '11 at 21:53

Domenic

110,262
41
219
271

Thanks, but I don't see how the IComparer would know about the insertion order... Did you have an implementation in mind? – Thomas Levesque Nov 07 '11 at 21:55
Since you implement the `IComparer` yourself, and you know the insertion order, you certainly could make one that knows the insertion order. Again, might need some wrapping to be user-friendly. – Domenic Nov 07 '11 at 22:03

Is there an IDictionary implementation that keeps the keys in the order they were added ? (NOT sorted order)

5 Answers5