CODEWITHSUNDEEP
c#dictionary
Oleg Vazhnev
Oleg Vazhnev

Reputation: 24067

is it guaranteed that Dictionary.Values returns elements in the order they were added?

During review of code of one application i've found that it assumes that order of Dictionary.Values is the same as elements were added to collection.

I've wrote application to test if this true:

using System;
using System.Collections.Generic;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<string, int> values = new Dictionary<string, int>();

            values.Add("apple2", 2);
            values.Add("apple3", 3);
            values.Add("apple4", 4);
            values.Add("apple5", 5);
            values.Add("apple6", 6);
            values.Add("apple1", 1);

            var list = new List<int>(values.Values);

            for (int i = 0; i < list.Count; i++)
            {
                Console.WriteLine(list[i]);
            }

        }
    }
}

And output is:

2
3
4
5
6
1

First of all I wonder how is that possible. Isn't Dictionary supposed to use unordered Tree or something like that?

Moreover MSDN states that:

The order of the values in the Dictionary<TKey, TValue>.ValueCollection is unspecified, but it is the same order as the associated keys in the Dictionary<TKey, TValue>.KeyCollection returned by the Keys property.

So why MSDN tells that "order is unspecified" but implementation happens to keep order? Am I correct that I'm better not to rely on that fact?

Upvotes: 3

Views: 258

Answers (3)

bradgonesurfing
bradgonesurfing

Reputation: 32162

If you want that behaviour then you should use an explicit ordered dictionary.

http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx

Upvotes: 0

Adil
Adil

Reputation: 148110

You are getting the values in order by chance could be due to your data that appears to be in order. Change the elements for mixed order and add remove the element the its order would be changed. You can not rely on the order.

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1500385

Am I correct that I'm better not to rely on that fact?

Absolutely. Just because sometimes it keeps the order doesn't mean that either it will in future implementations, or indeed that it will do in all cases right now.

When the internal data structure is resized or if items are deleted, the order can change.

For example, if you add this code before you construct the list:

values.Remove("apple4");
values.Add("jon", 10);

on my box, I see the value 10 come where 4 was before... even though it was added after the entries for 5, 6 and 1.

You should definitely, definitely not rely on the ordering.

Upvotes: 5

Related Questions