foreach Dictionary<>.Values or foreach Dictionary<>

Question

I want to know the details of this two styles of iterating Dictionary collections in C#:

Dictionary<X, Y> xydic = new Dictionary<X, Y>();

Style one:

foreach (Y y in xydic.Values) { use y }

Style two:

foreach (var it in xydic) { Y y = it.Value; use y... }

I've been C++ developer for years (now I'm working in a C# project) and I don't know the details of how the Dictionary collection works, the memory layout or how the elements are iterated so I'm wondering:

xydic.Values creates a temporary List<Y>? I don't see in the documentation any information about the creation of a temporary list.

If a temporary list is created wouldn't this mean that the collection is iterated twice: first to create the List<Y> and second to iterate the list itself?

If the the answer to question above is yes, the second style should be more efficient making the first style almost useless so I think that I should be wrong in some way.

I have the feeling that this question should be answered somewhere but I'm unable to locate an answer.

Answer 1

Retrieving the .Values property of a Dictionary<,> is an O(1) operation (documented). The nested type Dictionary<,>.ValueCollection is a simple wrapper around the dictionary, so there is no iterating in creating it.

On calling GetEnumerator(), you get an instance of the nested, nested Dictionary<,>.ValueCollection.Enumerator struct. It acccesses the entries directly through the private array entries of the Dictionary<,>.

You can see the source code.

So your "Style one" above is a good and clear way of doing things, with no performance overhead.

Note that the order in which you get the values, is arbitrary. You do not know how the underlying array entries is organized, once the Dictionary<,> has had many insertions and removals before you start foreaching it.

However, the order you get with "Style one" and "Style two" is the same; both access the private entries array of the Dictionary<,> in the same way.

Answer 2

Values is not creating a List<T>, no. It's not even pulling the entire set of values into a separate data structure. All it's doing is creating an enumerator that can iterate over the values. It's doing exactly the same thing that happens when you iterate the dictionary directly; the difference is that instead of constructing a KeyValuePair object for each pair of objects, its only giving you one half of the pair. Other than that, the iteration process is the same.