SortedSet Enumeration not working as expected

Question

Lets say ClassA is a random class and I am creating SortedSet of ClassA. I am storing the enumeration in dictionary but whenever I try to access then it always gives null;

var set = new SortedSet<ClassA>();
set.Add(new ClassA());
var map = new Dictionary<int, SortedSet<ClassA>.Enumerator>();
map[1] = set.GetEnumerator();
map[1].MoveNext();
var val = map[1].Current;
//Why val is null ???

Saving an enumerator to a collection like that is generally a bad idea. Is there a reason you want to do that? — juharr, Apr 02 '20 at 02:38
@juharr: I would say it's uncommon, but it does come up. For example, code that wants to enumerator through multiple data sets in parallel, may store the enumerators in some collection type. Obviously, for that kind of scenario, an array is a better choice than a dictionary, because of exactly this issue. But it's a genuine application for which a collection of enumerators is a reasonable, even preferable, solution. — Peter Duniho, Apr 02 '20 at 02:42

Peter Duniho · Answer 1 · 2020-04-02T02:49:57.607

This happens because SortedSet<T>.Enumerator is a struct. Each time you use the dictionary's indexer to retrieve the enumerator, you get a new copy of it. So even though you call MoveNext() on that copy, the next time you get a copy of the enumerator, it does not have any value for Current.

Interestingly, because of a quirk in the exact implementation of that struct, each copy of the enumerator gets the same reference-type object to track the state of the enumeration (a stack), and so the MoveNext() method seems to work (i.e. it returns true the first time you call it, but false any subsequent time).

There are at least four options for handling this correctly…

Retrieve the copy into a variable, and use the variable instead of the dictionary:

var set = new SortedSet<ClassA>();
set.Add(new ClassA());
var map = new Dictionary<int, SortedSet<ClassA>.Enumerator>();
map[1] = set.GetEnumerator();
var e = map[1];
e.MoveNext();
val = e.Current;

Note that in this example, the dictionary's copy of the enumerator still will not have the Current value you want. You would have to set the dictionary's copy back again after calling MoveNext() to preserve that: map[1] = e;

Use an array instead of a dictionary:

var set = new SortedSet<ClassA>();
set.Add(new ClassA());
var map = new SortedSet<ClassA>.Enumerator[2];
map[1] = set.GetEnumerator();
map[1].MoveNext();
var val = map[1].Current;

Other than the difference in the declaration and initialization of map, this works exactly as you have the code now. This is because indexed elements of an array are variables, rather than going through an indexer as the indexing syntax would with any other collection. So you are operating directly on the copy of the enumerator stored in the array, rather than a fresh copy returned by an indexer.

Of course, this would only work if the key values were constrained enough to make it feasible to allocate an array large enough to hold all possibilities for the key.

Declare a reference-type wrapper to contain the value-type enumerator:

class E<T>
{
    public SortedSet<T>.Enumerator Enumerator;

    public E(SortedSet<T>.Enumerator enumerator)
    {
        Enumerator = enumerator;
    }
}

then…

var set = new SortedSet<ClassA>();
set.Add(new ClassA());
var map = new Dictionary<int, E<ClassA>>();
map[1] = new E<ClassA>(set.GetEnumerator());
map[1].Enumerator.MoveNext();
val = map[1].Enumerator.Current;

In this example, the dictionary is just returning the reference to the wrapper object, ensuring just a single copy of the enumerator (which is stored in that wrapper object rather than the dictionary). Thus every time you access the object through the dictionary, you get the same copy.

Of course, you wind up having to go through the Enumerator field of the wrapper. It's a bit clumsy. But it would work.

Store the enumerators in an array, but index through a dictionary:

var set = new SortedSet<ClassA>();
set.Add(new ClassA());
var map = new Dictionary<int, int>();
var a = new SortedSet<ClassA>.Enumerator[1];
map[1] = 0;
a[map[1]] = set.GetEnumerator();
a[map[1]].MoveNext();
val = a[map[1]].Current;

This blends the two previous options. The array is used to store the actual enumerators, so that you can address them as variables, but the dictionary is used as a level of indirection to the array, so that you can refer to the enumerators via whatever keys you like.

Obviously, in a real application you would initialize the array by enumerating the original collections, storing their enumerators in the array and mapping the original key to the array index in the dictionary as you go.

The extra indirection is a little clumsy, as in the wrapper option, but not quite as bad as that, and solves the array-size concern of the array-based option.

Arguably, your question is a duplicate of this question: List.All(e => e.MoveNext()) doesn't move my enumerators on

It is definitely closely related to that one, as well as this one: Details on what happens when a struct implements an interface

SortedSet Enumeration not working as expected

1 Answers1