C# Dictionary add entry with wrong order

Question

I add a new item into the RoutingList but after the first delete the order is wrong.

public Dictionary<int, Route> RoutingList = new Dictionary<int, Route>();

For example:

1,route
2,route
3,route
4,route
5,route

Now I delete the first one.

2,route
3,route
4,route
5,route

By adding the next item I get this list:

6,route
2,route
3,route
4,route
5,route

And after this the first one (6) will deleted. But this is wrong. I want to delete the No. 2.

Why?

int key = RoutingList.LastOrDefault().Key;
RoutingList.Add(key + 1, tmpRoute);

if (RoutingList.Count == 5)
{
    RoutingList.Remove(RoutingList.First().Key);
}

yes, by the key with this line :RoutingList.Remove(RoutingList.First().Key); — 6EQUJ5HD209458b, Jun 14 '14 at 19:14

score 4 · Accepted Answer · answered Jun 14 '14 at 19:14

4

The order of a standard dictionary is not to keep the items in order by default. If you want to retain the order and keep the fast lookup you need to use an OrderedDictionary.

Alternatively if you don't need quick lookups, or your key is always your index (it looks like it might be) simply look at using a list, which will be ordered:

List<Route> routes;
Route route = routes[key];

answered Jun 14 '14 at 19:14

Ian

33,605
26
118
198

Sorry. Can't use OrderedDictionary cause it's not available in Windows Phone 8 Framework. But, I think thats a good idea without the Dictionary-Key. I did't need the key. – 6EQUJ5HD209458b Jun 14 '14 at 19:19
@6EQUJ5HD209458b: Glad it's helpful - I'm not fully aware of the W8 phone framework - is there an MSDN site of namespaces/classes you use? The usual .NET Framework one doesn't seem to have a phone filter. – Ian Jun 14 '14 at 19:22

score 1 · Answer 2 · answered Jun 14 '14 at 19:18

You can't rely on the order of items in a dictionary. If you need to delete an entry with the lowest id an alternative to an OrderedDictionary would be to change change your query (I am not 100% sure this will compile as I don't have VS available right now, but you get the idea):

if (RoutingList.Count == 5)
{
    RoutingList.Remove(RoutingList.Keys.Min());
}

score 1 · Answer 3 · answered Jun 14 '14 at 19:18

Per the MSDN:

The capacity of a Dictionary is the number of elements the Dictionary can hold. As elements are added to a Dictionary, the capacity is automatically increased as required by reallocating the internal array.

This then sounds like the behavior of an ArrayList, where the order is not maintained. When you remove an item from the dictionary, the size of the internal array is not reduced. Therefore, the index remains open at the item that you removed until the next item gets added which goes into that empty index.

C# Dictionary add entry with wrong order

3 Answers3

Linked