CODEWITHSUNDEEP
.netdata-structuresdictionary
tpower
tpower

Reputation: 56876

When I iterate through a Dictionary (.NET generic data structure) will it be in the same order that I added them?

I have a dictionary that I normally access with a key, so I need fast random access reads. However for one function I need to process every item in the dictionary where the order is important. It seems to be working OK in tests. Is it OK to depend on the order of items in a dictionary?

Upvotes: 9

Views: 3517

Answers (5)

Josh Mouch
Josh Mouch

Reputation: 3558

You definitely can't rely on Dictionary<> returning results in the order you added them - just as the documentation states.

In testing, Dictionary<> seems to always enumerate KeyValuePairs<> in the same order they were added. However, the Mono implementation of Dictionary<> does not. Mono follows the documentation when implementing behavior, and I assume they saw that part of the documentation and then implemented in some way that didn't maintain order.

Another option is to use OrderedDictionary, which will maintain order.

Upvotes: 4

Eoin Campbell
Eoin Campbell

Reputation: 44268

tpower, Dictionary and SortedDictionary are very similar in that they both hold a collection of objects, accessible by a key. Where they differ is in the way they are internally built.

Dictionary is faster for insertion as far as I know, whereas SortedDictionary is built on top of a binary tree search algorithm and is faster for reading back.

In both situations though, the internal order is maintained by the key order. There is nothing to guarantee that the order you iterate through the entire collection will be the same as you inserted your items.

In this case, you may need to store both a list and a dictionary for your different requirements.

Upvotes: 0

bruno conde
bruno conde

Reputation: 48265

The documentation clearly states that "For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<(Of <(TKey, TValue>)>) structure representing a value and its key. The order in which the items are returned is undefined." but I'm not convinced.

In all the tests I performed, the items are always ordered by insertion.

I found this strange because I also tested HashMap and LinkedHashMap (in Java) and the order in the HashMap is not correct as expected but, like Jon Skeet said, the order in LinkedHashMap is.

Can anyone point a fail test with Dictionary?

Here is the code I use to test:

        IDictionary<string, int> dic = new Dictionary<string, int>(10);

        Console.WriteLine("Adding ...");
        for (int i = 0; i < 1000000; i++)
        {
            Guid guid = Guid.NewGuid();
            dic.Add(guid.ToString(), i);
        }
        Console.WriteLine("Testing ...");

        bool first = true;
        int lastItem = 0;
        foreach (var item in dic.Values)
        {
            if (first)
            {
                first = false;
            }
            else
            {
                if (lastItem != item - 1)
                {
                    Console.WriteLine("Test Failed !");
                    break;
                }

            }
            lastItem = item;
        }
        Console.WriteLine("Done.");

Upvotes: -2

Jon Skeet
Jon Skeet

Reputation: 1500385

No. If you need to keep an order, you should have a list of items as well. You could encapsulate all the operations you need in your own collection class, which would update both the dictionary and the list at the same time.

It's unfortunate that .NET doesn't have a dictionary which supports this itself - it's a reasonably common request - Java does, as LinkedHashMap.

Upvotes: 10

OJ.
OJ.

Reputation: 29401

No. You're better off using a SortedDictionary if you want to keep your keys in an order.

Edit: Either that, or add your keys to a linked list if you want to keep track of the order you added the items.

Upvotes: -1

Related Questions