16

Suppose I have a given collection. Without ever changing the collection in any way, I loop through its contents twice with a foreach. Barring cosmic rays and what not, is it absolutely guaranteed that the order will be consistent in both loops?

Alternatively, given a HashSet<string> with a number of elements, what can cause the output from the the commented lines in the following to be unequal:

{
    var mySet = new HashSet<string>();
    // Some code which populates the HashSet<string>

    // Output1
    printContents(mySet);

    // Output2
    printContents(mySet);
}

public void printContents(HashSet<string> set) {
    foreach(var element in set) {
         Console.WriteLine(element);
    }
}

It would be helpful if I could get a general answer explaining what causes an implementation to not meet the criteria described above. Specifically, though, I am interested in Dictionary, List and arrays.

Superbest
  • 25,318
  • 14
  • 62
  • 134
  • 1
    What kind of collection? – Kevin DiTraglia Jul 27 '12 at 01:38
  • 1
    I am most interested in Dictionary, but it would be nice to have an overview of all of them. – Superbest Jul 27 '12 at 01:42
  • 1
    Given that there's only so many implementations of .NET, I think you might have better luck just looking at their source codes/decompilations. It's not like C++ where there's a gazillion implementations and the wrong assumptions give you undefined behavior... – user541686 Jul 27 '12 at 01:50
  • Dictionary for sure you can't assume with enumerate in the same order. That's what a Sorted Dictionary is for. – scottheckel Jul 27 '12 at 01:54
  • 2
    Good question. Now please excuse me while I create a class called `RandomList` where the enumerator randomly iterates the elements. Mwuhaha! – Nick Babcock Jul 27 '12 at 01:54
  • @scottheckel but it is reasonable to expect that enumeration will be stable until the dictionary is modified. This makes a lot of things easier to do when consuming the collections as read-only without requiring the (likely inconsequential) overhead that a sorted dictionary has. – binki Oct 10 '17 at 14:25

4 Answers4

15

Array enumeration guarantees order.

List and List<T> are expected to provide stable order (since they are expected to implement sequentially-indexed elements).

Dictionary, HashSet are explicitly do not guarantee order. Its is very unlikely that 2 calls to iterate items one after each other will return items in different order, but there is no guarantees or expectations. One should not expect any particular order.

Sorted versions of Dictionary/HashSet return items in sort order.

Other IEnumerable objects are free to do whatever they want. Normally one implements iterators in such a way that it matches user's expectations. I.e. enumeration of something that have implicit order should be stable, if explicit order provided - expected to be stable. Query to database that does not specify order should be expected to return items in semi-random order.

Check this question for links: Does the foreach loop in C# guarantee an order of evaluation?

Community
  • 1
  • 1
Alexei Levenkov
  • 98,904
  • 14
  • 127
  • 179
5

Everything that implements IEnumerable<T> does so in its own way. There is no general guarantee that any given collection must ensure stability.

If you are referring specifically to Collection<T> (http://msdn.microsoft.com/en-us/library/ms132397.aspx) I don't see any specific guarantee in its MSDN reference that ordering is consistent.

Will it probably be consistent? Yes. Is there a written guarantee? Not that I can find.

Eric J.
  • 147,927
  • 63
  • 340
  • 553
  • Excellent! Not to mention that the order of a set doesn't matter, so a HashSet would by definition still be correct in not always returning things in the same order. A SortedSet would though for sure. – scottheckel Jul 27 '12 at 01:52
  • @Hexxagonal: A HashSet would be correct in not *guaranteeing* a stable order of iteration. As a practical matter you probably will get the same order if you iterate the same HashSet twice without changing it's internal state between iterations. It's unlikely that the first iteration will do anything to change internal state. Then again, it might. Thus no *guarantee* :-) – Eric J. Jul 27 '12 at 05:43
  • How **wouldn’t** `Collection.GetEnumerator()` return things in a stable order? It defines [`Collection.Item(int)`](https://msdn.microsoft.com/en-us/library/ms132434.aspx) which means that you can do `for (var i = 0; i < collection.Count; i++) { var x = collection[i]; }` and be guaranteed to see all elements. That can’t happen without also resulting in a stable enumeration order, can it? Or, at the very least, you could write your own enumerator that uses `Item(int)` since that *has* to be stable to be usable. – binki Oct 10 '17 at 14:29
  • @binki: As a matter of actual implementation, you're right. There's no guarantee that `Collection` in fact works that way, but current implementations (and probably future implementations) do. – Eric J. Oct 27 '17 at 19:09
3

For many of the C# collections there are sorted versions of the collection. For instance, a HashSet is to a SortedSet as a Dictionary is to a SortedDictionary. If you're working with something where the order isn't important like the Dictionary then you can't assume the loop order will behave the same way every time.

scottheckel
  • 9,106
  • 1
  • 35
  • 47
0

As per your example with HashSet<T>, we now have source code to check: HashSet:Enumerator

As it is, the Slot[] set.m_slots array is iterated. The array object is only changed in the methods TrimExcess, Initialize (both of which are only called in the constructor), OnDeserialization, and SetCapacity (only called by AddIfNotPresent and AddOrGetLocation).

The values of m_slots are only changed in methods that change elements of the HashSet(Clear, Remove, AddIfNotPresent, IntersectWith, SymmetricExceptWith).

So yes, if nothing touches the set, it enumerates in the same order.

Dictionary:Enumerator works in quite the same way, iterating an Entry[] entries that only changes when such non-readonly methods are called.

Wolfzoon
  • 418
  • 4
  • 10