CODEWITHSUNDEEP
.netcollectionsdictionary
Thomas Levesque
Thomas Levesque

Reputation: 292425

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

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...

Upvotes: 3

Views: 169

Answers (5)

Stuart Golodetz
Stuart Golodetz

Reputation: 20616

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.

Upvotes: 2

Henk Holterman
Henk Holterman

Reputation: 273244

"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.

Upvotes: 1

Brandon Moretz
Brandon Moretz

Reputation: 7621

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?

Upvotes: 1

Marc Gravell
Marc Gravell

Reputation: 1062780

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.

Upvotes: 2

Domenic
Domenic

Reputation: 112827

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.

Upvotes: 0

Related Questions