Is the order of objects returned by FOREACH stable?

Question

Is it safe to assume that two itterations over the same collection will return the objects in the same order? Obviously, it is assumed that the collection has not otherwise been changed.

Answer 1

Short answer - yes.

Obviously, though, the order of the items in the collection may not be exactly as they were inserted, depending on the type of collection (a dictionary, for example).

But you will get the same results each time you iterate over a single, unmodified collection using a foreach loop.

Answer 2

It depends on the collection type. For most collections, the answer is "Yes".

However, this is not guaranteed. The docs of a collection type should specify whether or not it does, but as most do, that detail is generally over looked. However, if it is not stable, it would be a tremendous oversight if the docs didn't mention that.

Answer 3

You can't guarantee this unless you know the concrete implementation of the class you're iterating over.

Collections that have a defined element order (e.g. List<T>) will enumerate in a stable order.

For collections where the state of the object doesn't change it's highly likely that elements will come back in the same order, e.g. Dictionary<K,V>, although this not guaranteed by the specification.

As an example of where this would not be the case, you could imagine a hashtable based dictionary implementation that compacts or resizes the table asynchronously. Such an implementation would not guarantee a stable iteration order.

Answer 4

While the answer is “yes” for all builtin collections and probably any sane collection class out there, the documentation doesn't have any constraints formulated for IEnumerable. Therefore, nothing tells us that every iteration must be stable.

I could imagine the following use case:

foreach (int i in new Shuffler(1, 2, 3, 4, 5, 6, 7, 8, 9))
    Console.WriteLine(i);

This might well be implemented as a class that yields a different ordering for each iteration.

So – if you also want to consider strange borderline cases, the answer should be “no”.

Answer 5

While typically, the elements will be returned in the same order, there's absolutely no guarantee. It's entirely dependant on the internal implementation of the collection class.

I can see a case for a collection class that's specifically designed to return elements in a random order, for example.

In short, unless you know the internal implementation of the collection class, don't assume anything about the order.

Answer 6

Linq defines the IOrderedEnumerable interface for this purpose.

Answer 7

Re "unmodified" (NM's reply) - note that many complex containers like Dictionary do not guarantee to preserve order. Sometimes adding an item will make it appear last (giving the impression that order is preserved), and sometimes it will cause the internal buckets to re-organise, giving a completely different order.

Things like SortedList<,> etc obviously have their own rules.

Answer 8

I would say that for most collection it is safe to assume this. It's not beyond the realms of possibility that a certain collection could have the enumerator implemented in a non-deterministic way, but that's probably not going to happen...